Sagemath

Sagemath
Γενικά
Ημερ. Δημιουργίας	2005
Είδος	σύστημα υπολογιστικής άλγεβρας, ελεύθερο και ανοιχτού κώδικα λογισμικό
Διανομή
Έκδοση	10.3 (20 Μάρτιος 2024);
Λειτουργικά	Linux, Microsoft Windows, macOS
Ανάπτυξη
Γραμμένο σε	Python, Cython, C, C++, Fortran
Κατάσταση	Ενεργή
Άδεια χρήσης	GPLv2
Σύνδεσμοι
Επίσημος ιστότοπος
	https://www.sagemath.org/
Αποθετήριο κώδικα
	https://github.com/sagemath/sage

Το αλγεβρικό υπολογιστικό σύστημα Sagemath είναι ανοιχτού κώδικα με Γενική Άδεια Δημόσιας Χρήσης GNU. Χρησιμοποιεί πολλά πακέτα ανοιχτού κώδικα όπως: NumPy, SciPy, matplotlib, Sympy, Maxima, GAP, FLINT, R και αρκετά ακόμη που έχουν γραφεί από την αρχή. Βασίζεται στην γλώσσα προγραμματισμού Python.

To σύστημα Sage μπορεί να εγκατασταθεί σε Linux, Mac καθώς και σε MS windows.

Τα βασικά[Επεξεργασία | επεξεργασία κώδικα]

Μπορείτε αμέσως να αρχίσετε να χρησιμοποιείτε το sage cell (δεν χρειάζεται λογαριασμός). Αν θέλετε να ξεκινήσετε να δουλεύετε τα δικα σας project με το Sage, θα χρειαστείται έναν λογαριασμό στο cloud sage. Κάποιος με γνώση python θα βρει το Sage πολύ εύκολο, αφού στην ουσία το Sage μας δίνει ένα python shell. Πολλά παραδειγματα μπορείτε να βρείτε στο βιβλίο Sage for Undergraduates^[2]. Επίσης μπορείτε να συμβουλευτείτε το επίσημο tutorial^[3].

Μπορείτε να χρησιμοποιείτε το Sagemath σαν απλή αριθμομηχανή, π.χ.

sage: 1+1 # για να το εκτελέσετε στο sage cell, δεν χρειάζεται να γράψετε ''sage:1+1'', αλλά μόνο το ''1+1''
2
sage: 0.291*80
23.2800000000000
sage: 2^3
8
sage: 1/2*(1/3-1)^2
2/9
sage:pi.n()
3.14159265358979
sage:numerical_approx(pi,200) #200 ψηφία του αριθμού π
3.1415926535897932384626433832795028841971693993751058209749
sage:numerical_approx(exp(1),digits=3) # τρία ψηφία του αριθμού e
2.72
sage:sin(pi/3)
1/2*sqrt(3)

Μπορούμε να ορίσουμε δύο σύνολα και να βρούμε την ένωση (& τομή) τους

sage:L=set([1,8,2]);M=set([8,5,0]);
sage:print(L.union(M),L,M) #τυπώνει την ένωση των L,M καθώς και τα σύνολα L,M
set([0, 1, 2, 5, 8]) set([8, 1, 2]) set([8, 0, 5])
sage:print(L.intersection(M))
set([8])

Επίσης ο μέγιστος κοινός διαιρετής δύο ακεραίων

sage: gcd(327,757) #gcd=greatest common divisor
1

Ενώ το ελάχιστο κοινό πολλαπλάσιο

sage: lcm(327,757) #lcm=least common multiple
247539

Για την παραγοντοποίηση ενός ακέραιου

sage:factor(2^67+2^32+1) # εξαιρετικά γρήγορη συνάρτηση
5^2 * 7 * 2508083 * 336224809589

Για πολλαπλασιασμό πολυώνυμων

sage:f=x^2;g=x^3+1;(f*g).expand();
x^5 + x^2

ή για παραγοντοποίηση

sage:factor(x^5+x^2);
(x^2 - x + 1)*(x + 1)*x^2

Για να λύσω (συμβολικά) εξισώσεις πρέπει να δηλώσω πρώτα τις μεταβλητές και κατόπιν να ορίσω ως προς ποια μεταβλητη θα λύθεί η εξισωση. Η μεταβλητή x είναι η μόνη μεταβλητή που δεν χρειάζεται να οριστεί.

sage:var('a,b,c');solve(a*x^2+b*x+c==0,x)
[x == -1/2*(b + sqrt(b^2 - 4*a*c))/a, x == -1/2*(b - sqrt(b^2 - 4*a*c))/a]

sage:solve(x^3+b*x+c==0,x) # θα μας δώσει τον τύπο του Cardano
[x == 1/6*b*(-I*sqrt(3) + 1)/(-1/2*c + 1/6*sqrt(4/3*b^3 + 9*c^2))^(1/3) 
- 1/2*(-1/2*c + 1/6*sqrt(4/3*b^3 + 9*c^2))^(1/3)*(I*sqrt(3) + 1),
 x == 1/6*b*(I*sqrt(3) + 1)/(-1/2*c + 1/6*sqrt(4/3*b^3 + 9*c^2))^(1/3) 
- 1/2*(-1/2*c + 1/6*sqrt(4/3*b^3 + 9*c^2))^(1/3)*(-I*sqrt(3) + 1), 
x == -1/3*b/(-1/2*c + 1/6*sqrt(4/3*b^3 + 9*c^2))^(1/3) +
 (-1/2*c + 1/6*sqrt(4/3*b^3 + 9*c^2))^(1/3)]

Για πιο όμορφη εκτύπωση μπορείτε να δώσετε

sage:show(solve(a*x^2+b*x+c==0,x))

Για να λύσω ένα γραμμικό σύστημα

sage:var('y');solve([x+y==1,x-y==2],[x,y])
[[x == (3/2), y == (-1/2)]]

Αν θέλουμε να βρούμε προσεγγιστικές λύσεις εξισώσεων σ' ένα συγκεκριμένο διάστημα

sage:f=x^3+7*x-1;find_root(f,-2,2)
0.14244425060384266

Συναρτήσεις[Επεξεργασία | επεξεργασία κώδικα]

Για να ορίσω μια συνάρτηση απλά δίνω

sage:f=x^3+x*exp(x)

Για να υπολογίσω την τιμή της σ΄ ένα σήμειο

sage:f(1)
e+1

sage:f(1).n()
3.71828182845905

Για δύο μεταβλητές

sage:var('y');g=x^2+y

και

sage:g(1,1)
2

Ενώ

sage:diff(f,x) # η παράγωγος
3*x^2 + x*e^x + e^x

Για τις δύο μετάβλητές

sage:diff(g,x) # η μερική παράγωγος ως προς x
2*x

Η σειρά Taylor

sage:exp(x).taylor(x,0,3) # τρεις όροι της e^x με κέντρο το 0
1/6*x^3 + 1/2*x^2 + x + 1

Μπορώ να σχεδιάζω το γράφημα μιας συνάρτησης, π.χ. της παραβολής

sage:plot(x^2,x)

Επίσης για 3d γραφήματα, πρέπει να ορίσουμε την μεταβλητή y αλλά όχι την x (είναι by default ορισμένη στο Sagemath)

sage:var('y');plot3d(x^2+y^2,[-2,2],[-2,2]);

Γραμμική Άλγεβρα[Επεξεργασία | επεξεργασία κώδικα]

sage:A=matrix([[1,2],[-3,-2]]); # γράφουμε μέσα στις αγκύλες τις γραμμές του πίνακα
sage:A^2; # υψώνουμε στο τετράγωνο τον πίνακα Α, δηλαδή εκτελούμε την πράξη Α*Α
[-5 -2]
[ 3 -2]

sage:B=matrix([[3,4],[-3,-2]]); # ορίζω ένα νέο πίνακα 2Χ2
sage:A*B; #πολλαπλασιαζω τους πίνακες Α,Β
[-3  0]
[-3 -8]

sage:B*A  #$πολλαπλασιαζω τους πίνακες Β,Α
[-9 -2]
[ 3 -2]

sage:A=matrix(4,2,[[1,1],[1,-2],[1,2],[1,3]]);A; #ορίζουμε έναν νέο πίνακα Α διαστάσεων 4Χ2
[ 1  1]
[ 1 -2]
[ 1  2]
[ 1  3]

#υπολογίζουμε τον ανάστροφο του πίνακα A και το αποτέλεσμα το πολλαπλασιάζουμε με τον Α
sage:C=(A.transpose()*A);C 
[ 4  4]
[ 4 18]

sage: A=matrix([[1,1,-2,3],[-3,1,1,3],[2,-1,-1,-4],[1,2,3,-2]]);det(A); #υπολογίζουμε την ορίζουσα του πίνακα Α
49

#Μπορούμε να υπολογίσουμε την ισοδύναμη τριγωνική άνω μορφή ενός πίνακα
sage:A=matrix([[13,12,2],[12,13,-2],[2,-2,8]]);A.echelon_form()
[  1  24 -46]
[  0  25 -50]
[  0   0   0]

sage:b=matrix(2,1,[1,-2]);
sage:from numpy import linalg # καλούμε την linalg από την βιβλιοθήκη numpy της python
sage:linalg.solve(A,b) #λύνουμε το σύστημα AX=b
array([[-0.13636364],
       [-0.27272727]])

Διαγωνοποίηση[Επεξεργασία | επεξεργασία κώδικα]

sage:A = matrix(QQ, [[1,2,0],[1,0,-1],[0,1,1]]);A
[ 1  2  0]
[ 1  0 -1]
[ 0  1  1]

sage:f=A.charpoly();factor(f);
(x - 1) * (x^2 - x - 1)
sage:A.eigenvalues()   # οι ιδιοτιμές του πίνακα Α
[1, -0.618033988749895?, 1.618033988749895?]
# Άρα ο πίνακας διαγωνοποιείται αφού έχει απλές ιδιοτιμές
sage: A.eigenvectors_right() # τα ιδιοδιανύσματα 
[(1, [(1, 0, 1)], 1), 
(-0.618033988749895?, [(1, -0.8090169943749474?, 1/2)], 1), (1.618033988749895?, 
[(1, 0.3090169943749474?, 1/2)], 1)]

Κρυπτογραφία[Επεξεργασία | επεξεργασία κώδικα]

Το SAGE έχει υλοποιημένους μερικούς κλασικούς αλγορίθμους κρυπτογράφησης όπως και κάποιους προχωρημένους αλγορίθμους που έχουν σχέση με τα S-boxes και τα Lattices. Όποιος θέλει μπορεί να τους βρει εδώ.

Επίσης μπορεί να ενσωματώσει την βιβλιοθήκη pycrypto η οποία περιέχει τους περισσότερους αλγόριθμους κρυπτογράφησης αλλά και ασφαλείς συναρτήσεις κατακερματισμού.

Η χρήση του SAGE στο πεδίο της κρυπτογραφίας γίνεται για εκπαιδευτικούς σκοπούς ώστε να γίνονται κατανοητοί οι αλγόριθμοι κρυπτογράφησης, για ερευνητικές δοκιμές των κρυπτό-συστημάτων σε διάφορες επιθέσεις και για προσομείωση της λειτουργίας του κρυπτό-συστήματος πριν την χρήση του.

Η αναλυτική λειτουργία των αλγορίθμων που θα δοθούν ως παραδείγματα υπάρχει στο σχετικό βιβλίο^[4].

Αρχικά εισάγουμε την βιβλιοθήκη pycrypto και με την εντολή help μπορούμε να βλέπουμε την δομή της και αναλυτικές διευκρινήσεις για κάθε συνάρτηση.

import Crypto
help (Crypto)

Συμμετρική κρυπτογράφηση[Επεξεργασία | επεξεργασία κώδικα]

Κρυπτό-συστήματα ροής[Επεξεργασία | επεξεργασία κώδικα]

One Time Pad[Επεξεργασία | επεξεργασία κώδικα]

Χρειαζόμαστε ένα κλειδί ίδιου μήκους με το μήνυμα που θέλουμε να κρυπτογραφήσουμε, για να γίνει η πράξη XOR bit με bit.

Η αναβάθμιση που προσφέρει ένα κρυπτό-σύστημα ροής (stream cipher) είναι ότι δεν έχουμε την ανάγκη να θυμόμαστε το κλειδί του OTP αλλά χρησιμοποιούμε ένα πολύ μικρότερο μέσα σε μια ψευδό τυχαία γεννήτρια αριθμών (PRG).

import Crypto.Random._UserFriendlyRNG
import Crypto.Cipher.XOR

st = "It is a sunny day" #Το μήνυμα για κρυπτογράφηση

#Δημιουργούμε μια ψευδό τυχαία ακολουθία από bytes 
#μήκους len(st) που είναι το κλειδί, με χρήση μιας PRG

key = Crypto.Random._UserFriendlyRNG.get_random_bytes(len(st))
#Το len(st) είναι το μήκος του μηνύματος

#Δημιουργούμε ένα αντικείμενο που κάνει 
#κρυπτογράφηση-αποκρυπτογράφηση με την πράξη XOR και το κλειδί
e = Crypto.Cipher.XOR.new(str(key))

c = e.encrypt(st) #Το κρυπτογραφημένο μήνυμα
print(c)

print(e.decrypt(c)) #Η αποκρυπτογράφηση είναι σωστή

RC4[Επεξεργασία | επεξεργασία κώδικα]

Ο RC4 είναι ένα πολύ γνωστό κρυπτό-σύστημα ροής που χρησιμοποιήθηκε τα προηγούμενα χρόνια αλλά πλέον δεν πρέπει να χρησιμοποιείται, όπως και όλες οι παραλλαγές του. Ο RC4 παίρνει ένα κλειδί και το μεταλλάζει σε ένα μεγαλύτερο. Το μεγαλύτερο πλέον κλειδί το χρησιμοποιεί ως μια PRG γεννήτρια ψευδό τυχαίων αριθμών όπου για κάθε byte του μηνύματος προς κρυπτογράφηση διαλέγει ένα byte από την PRG και εκτελεί την πράξη XOR μεταξύ τους.

from Crypto.Cipher import ARC4

key = "Secret" #Το κλειδί που θα μεταλλάξει

msg = "Attack at dawn" #Το μήνυμα για κρυπτογράφηση

#Δημιουργούμε ένα αντικείμενο που κάνει κρυπτογράφηση-αποκρυπτογράφηση 
#με τον αλγόριθμο ARC4 και το κλειδί
erc = ARC4.new(key)

cipher = erc.encrypt(msg) #Το κρυπτογραφημένο μήνυμα
print(cipher)

Κρυπτό-συστήματα τμήματος[Επεξεργασία | επεξεργασία κώδικα]

DES[Επεξεργασία | επεξεργασία κώδικα]

Ο DES είναι ένα πολύ γνωστό κρυπτό-σύστημα τμήματος που χρησιμοποιήθηκε τα προηγούμενα χρόνια αλλά πλέον δεν πρέπει να χρησιμοποιείται, όπως και όλες οι παραλλαγές του. Το τμήμα του μηνύματος που εισέρχεται στον DES για κρυπτογράφηση δέχεται πρώτα μια μετάθεση των bits του και το αποτέλεσμα χωρίζεται σε δύο τμήματα. Στα δύο τμήματα εφαρμόζεται ένα σχήμα Feistel με 16 κύκλους. Το αποτέλεσμα που θα προκύψει ανακατεύεται με την αντίστροφη μετάθεση που έγινε στην αρχή και αυτό είναι η έξοδος του αλγορίθμου.

from Crypto.Cipher import DES
from Crypto import Random

key = "8byteKey" #Το κλειδί

plaintext = "not trusted line" #Το μήνυμα για κρυπτογράφηση

iv = Random.new().read(DES.block_size) #Απαραίτητη αρχικοποίηση

#Δημιουργούμε ένα αντικείμενο που κάνει κρυπτογράφηση-αποκρυπτογράφηση 
#με τον αλγόριθμο DES, το κλειδί και συγκεκριμένη μέθοδο
edes = DES.new(key, DES.MODE_CBC, iv)

cip = edes.encrypt(plaintext) #Το κρυπτογραφημένο μήνυμα
print(cip)

AES[Επεξεργασία | επεξεργασία κώδικα]

Ο AES είναι ένας συμμετρικός αλγόριθμος τμήματος, χρησιμοποιεί κλειδιά μήκους 128, 192 και 256 bits. Δέχεται τμήμα μηνύματος 128 bits, αντί για το σχήμα Feistel που χρησιμοποιούσε ο DES χρησιμοποιεί SPN.

reset()
from Crypto.Cipher import AES
import os

key = b'Sixteen byte key'
iv = os.urandom(AES.block_size)
ciphobj = AES.new(key, AES.MODE_CFB, iv)
msg = b'Attack at dawn'
cipher = iv + ciphobj.encrypt(msg)
print(cipher)

print(ciphobj.decrypt(cipher)[AES.block_size:])

Ασύμμετρη κρυπτογράφηση - Κρυπτογράφηση Δημόσιου Κλειδιού[Επεξεργασία | επεξεργασία κώδικα]

Trapdoor Function - RSA[Επεξεργασία | επεξεργασία κώδικα]

Για ένα κρυπτοσύστημα δημόσιου κλειδιού χρειαζόμαστε τρεις αλγορίθμους.

$G$ : Ένας πιθανοτικός που παράγει δύο κλειδιά $(public\;key,secret\;key)$ .

$F(pk,*)$ : Ένας ντετερμινιστικός αλγόριθμος που ορίζει μια συνάρτηση $X\rightarrow Y$

$F^{-1}(sk,*)$ : Ένας ντετερμινιστικός αλγόριθμος που ορίζει μια συνάρτηση $Y\rightarrow X$ αντίστροφη της $F(pk,*)$ .

Στην περίπτωση του RSA παράγουμε δύο μεγάλους πρώτους αριθμούς p,q (τουλάχιστον 1024 bits). Θέτουμε Ν=pq. Επίσης διαλέγουμε έναν ακέραιο αριθμό 0<e<Ν και $d$ τέτοιo ώστε $ed\equiv 1(mod\ \phi (N)).$

Η συνάρτηση $y=F(e,x)=x^{e}(mod\ N)$ ενώ η αντίστροφη είναι $F^{-1}(d,y)=y^{d}(mod\ N)$ . Μπορούμε κάνοντας χρήση του θεωρήματος τoυ Euler να αποδείξουμε ότι $y^{d}\equiv x(mod\ N).$

Η ασφάλεια του RSA βασίζεται στην δυσκολία εύρεσης e-οστών ριζών mod N όταν δεν γνωρίζουμε την παραγοντοποίηση του Ν. Το πρόβλημα αυτό δεν έχει αποδειχτεί ότι είναι ισοδύναμο με το πρόβλημα της παραγοντοποίησης (RSA problem).

reset()
from Crypto.PublicKey import RSA

rsaobj = RSA.generate(2048)
msg = b'Attack at dawn'
cipher = rsaobj.encrypt(msg,5)
print(cipher)
print("------------------")
message = rsaobj.decrypt(cipher)
print(message)

Επίθεση Wiener στον RSA-textbook[Επεξεργασία | επεξεργασία κώδικα]

Η επίθεση του Wiener βασίζεται στα συνεχή κλάσματα και στο θεώρημα του Legendre, μπορεί να υλοποιηθεί σε χρόνο O(lne lnN) όταν το μυστικό κλειδί d είναι μικρότερο από ένα συγκεκριμένο αριθμό bit που σχετίζονται από το N.

$d<{\frac {1}{3}}N^{\frac {1}{4}}$ .^[5]

Αρχικά σε ένα φύλλο εργασίας του Sagemath ορίζουμε τις συναρτήσεις.

reset()
#####
# N : factorization of p and q
# e : encryption key
#####
def wiener_attack(N, e):
    nd = convergents(e/N)
    nd.pop(0)
    ##
    fi = [((e*c.denominator())-1)/c.numerator() for c in nd]
    ##
    for i in range(0,len(fi)):
        ##
        if fi[i].is_integer():
            f = x**2 - x*(N-fi[i]+1) + N
            #type(f)
            rizes = solve (f,x)
            ##
            if rizes[0].rhs().is_integer() and rizes[1].rhs().is_integer():
                d = nd[i].denominator()
                print("d is: ", d)
                break
    ##            
    return d
    
#####
# a : the message
# gtemp : exponent
# N : factorization of p and q
#####
def rsa_tdf(a, gtemp, N):
    gtemp = bin(gtemp)[2:]
    g = map(int,str(gtemp))
    ##
    listlen = len(g)
    ##
    d = 1
    x = a
    for i in range(0,listlen):
        ##
        if (g[listlen-i-1]==1):
            d = (d * x) % N
        ##    
        x = x * x % N
    ##
    return d

Ψηφιακές υπογραφές[Επεξεργασία | επεξεργασία κώδικα]

DSA[Επεξεργασία | επεξεργασία κώδικα]

Ο αλγόριθμος DSA χρησιμοποιείται μόνο για ψηφιακή υπογραφή, η ασφάλεια του βασίζεται στον διακριτό λογάριθμο modp.

Ένα σημαντικό σημείο ασφάλειας στην υλοποίηση του αλγορίθμου είναι ότι το εφήμερο κλειδί πρέπει να είναι διαφορετικό για κάθε υπογραφή.

from Crypto.PublicKey import DSA
from Crypto.Hash import SHA
import os

#Το μήνυμα.
message = "Hello"
# Το αντικείμενο με τα κλειδιά.
dsaobj=DSA.generate(int(1024))
# το p είναι 1024 bits
p=dsaobj.p
# δημόσιο κλειδί 1024 bits  
pk=dsaobj.y
# ιδιωτικο κλειδί 160 bits
a=dsaobj.x 
# ο γεννήτορας του πεπερασμένου σώματος g είναι 1024 bits
g=dsaobj.g  
# ο πρωτος q είναι 160 bits 
q=dsaobj.q  
# Το hash του μηνύματος.
h = SHA.new(message).digest()
# Εφήμερο κλειδί.
k = os.urandom((20))
# Το hash του μηνύματος υπογεγραμμένο.
sig = dsaobj.sign(h,k)
# Επιβεβαίωση τις υπογραφής.
print(dsaobj.verify(h,sig))

Αναφορές[Επεξεργασία | επεξεργασία κώδικα]

↑ «Release 10.3». 20 Μάρτιος 2024. Ανακτήθηκε στις 25 Μάρτιος 2024.
↑ G.Bard (2014). Sage for Undergraduates. AMS. Αρχειοθετήθηκε από το πρωτότυπο στις 2015-04-09. https://web.archive.org/web/20150409230709/http://www.gregorybard.com/SAGE.html. Ανακτήθηκε στις 2015-04-25.
↑ «official tutorial» (PDF). Αρχειοθετήθηκε από το πρωτότυπο (PDF) στις 17 Μαρτίου 2015. Ανακτήθηκε στις 25 Απριλίου 2015.
↑ D.R.Kohel. Cryptography. http://www.sagemath.org/files/kohel-book-2008.pdf.
↑ Boneh, Dan (1999). Twenty Years of attacks on the RSA Cryptosystem. Notices of the American Mathematical Society (AMS) 46 (2).

Εξωτερικοί σύνδεσμοι[Επεξεργασία | επεξεργασία κώδικα]

Commons logo

Τα Wikimedia Commons έχουν πολυμέσα σχετικά με το θέμα
Sagemath

[wikidata-17f7e2f7c7d7f7fca5e7c53d94f147a51f30e8a1-v5-1] «Release 10.3». 20 Μάρτιος 2024. Ανακτήθηκε στις 25 Μάρτιος 2024.

[2] G.Bard (2014). Sage for Undergraduates. AMS. Αρχειοθετήθηκε από το πρωτότυπο στις 2015-04-09. https://web.archive.org/web/20150409230709/http://www.gregorybard.com/SAGE.html. Ανακτήθηκε στις 2015-04-25.

[3] «official tutorial» (PDF). Αρχειοθετήθηκε από το πρωτότυπο (PDF) στις 17 Μαρτίου 2015. Ανακτήθηκε στις 25 Απριλίου 2015.

[4] D.R.Kohel. Cryptography. http://www.sagemath.org/files/kohel-book-2008.pdf.

[5] Boneh, Dan (1999). Twenty Years of attacks on the RSA Cryptosystem. Notices of the American Mathematical Society (AMS) 46 (2).

[1]

[2]

[3]

[4]

[5]