Sagemath

Tα βασικά

Mπορείτε αμέσως να αρχίσετε να χρησιμοποιήσετε το sage cell (δεν χρειάζεται λογαριασμός).
Αν θέλετε να ξεκινήσετε να δουλεύετε τα δικα σας project με το Sage, θα χρειαστείται έναν λογαριασμό στο cloud sage.
Κάποιος με γνώση python θα βρει το Sage πολύ εύκολο, αφού στην ουσία το Sage μας δίνει ένα python shell.
Πολλά παραδειγματα μπορείτε να βρείτε στο βιβλίο Sage for Undergraduates. Επίσης μπορείτε να συμβουλευτείτε το επίσημο tutorial.
Μπορείτε να χρησιμοποιείτε το Sagemath σαν απλή αριθμομηχανή, π.χ.
sage: 1+1 # για να το εκτελέσετε στο sage cell, δεν χρειάζεται να γράψετε ''sage:1+1'', αλλά μόνο το ''1+1''2sage: 0.291*8023.2800000000000sage: 2^38sage: 1/2*(1/3-1)^22/9sage:pi.n()3.14159265358979sage:numerical_approx(pi,200) #200 ψηφία του αριθμού π3.1415926535897932384626433832795028841971693993751058209749sage:numerical_approx(exp(1),digits=3) # τρία ψηφία του αριθμού e2.72sage: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,Mset([0, 1, 2, 5, 8]) set([8, 1, 2]) set([8, 0, 5])sage:print(L.intersection(M))set([8])
Eπίσης ο μέγιστος κοινός διαιρετής δύο ακεραίων
sage: gcd(327,757) #gcd=greatest common divisor1
Ενώ το ελάχιστο κοινό πολλαπλάσιο
sage: lcm(327,757) #lcm=least common multiple247539
Για την παραγοντοποίηση ενός ακέραιου
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)]]
Aν θέλουμε να βρούμε προσεγγιστικές λύσεις εξισώσεων σ' ένα συγκεκριμένο διάστημα
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+1sage: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) # η μερική παράγωγος ως προς x2*x
H σειρά Taylor
sage:exp(x).taylor(x,0,3) # τρεις όροι της e^x με κέντρο το 01/6*x^3 + 1/2*x^2 + x + 1

Μπορώ να σχεδιάζω το γράφημα μιας συνάρτησης, π.χ. της παραβολής
sage:plot(x^2,x)
Eπίσης για 3d γραφήματα, πρέπει να ορίσουμε την μεταβλητή y αλλά όχι την x (είναι by default ορισμένη στο Sage)
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Χ2sage: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 της pythonsage:linalg.solve(A,b) #λύνουμε το σύστημα AX=barray([[-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 στο πεδίο της κρυπτογραφίας γίνεται για εκπαιδευτικούς σκοπούς ώστε να γίνονται κατανοητοί οι αλγόριθμοι κρυπτογράφησης, για ερευνητικές δοκιμές των κρυπτό-συστημάτων σε διάφορες επιθέσεις και για προσομείωση της λειτουργίας του κρυπτό-συστήματος πριν την χρήση του.
Η αναλυτική λειτουργία των αλγορίθμων που θα δοθούν ως παραδείγματα υπάρχει στο σχετικό βιβλίο.
Αρχικά εισάγουμε την βιβλιοθήκη pycrypto και με την εντολή help μπορούμε να βλέπουμε την δομή της και αναλυτικές διευκρινήσεις για κάθε συνάρτηση.
import Cryptohelp (Crypto)

One Time Pad

Χρειαζόμαστε ένα κλειδί ίδιου μήκους με το μήνυμα που θέλουμε να κρυπτογραφήσουμε, για να γίνει η πράξη XOR bit με bit.
Η αναβάθμιση που προσφέρει ένα κρυπτό-σύστημα ροής (stream cipher) είναι ότι δεν έχουμε την ανάγκη να θυμόμαστε το κλειδί του OTP αλλά χρησιμοποιούμε ένα πολύ μικρότερο μέσα σε μια ψευδό τυχαία γεννήτρια αριθμών (PRG).
import Crypto.Random._UserFriendlyRNGimport Crypto.Cipher.XORst = "It is a sunny day" #Το μήνυμα για κρυπτογράφηση#Δημιουργούμε μια ψευδό τυχαία ακολουθία από bytes #μήκους len(st) που είναι το κλειδί, με χρήση μιας PRGkey = Crypto.Random._UserFriendlyRNG.get_random_bytes(len(st))#Το len(st) είναι το μήκος του μηνύματος#Δημιουργούμε ένα αντικείμενο που κάνει #κρυπτογράφηση-αποκρυπτογράφηση με την πράξη XOR και το κλειδίe = Crypto.Cipher.XOR.new(str(key)) 

c = e.encrypt(st) #Το κρυπτογραφημένο μήνυμαprint cprint e.decrypt(c) #Η αποκρυπτογράφηση είναι σωστή

RC4

Ο RC4 είναι ένα πολύ γνωστό κρυπτό-σύστημα ροής που χρησιμοποιήθηκε τα προηγούμενα χρόνια αλλά πλέον δεν πρέπει να χρησιμοποιείται, όπως και όλες οι παραλλαγές του. Ο RC4 παίρνει ένα κλειδί και το μεταλλάζει σε ένα μεγαλύτερο. Το μεγαλύτερο πλέον κλειδί το χρησιμοποιεί ως μια PRG γεννήτρια ψευδό τυχαίων αριθμών όπου για κάθε byte του μηνύματος προς κρυπτογράφηση διαλέγει ένα byte από την PRG και εκτελεί την πράξη XOR μεταξύ τους.
from Crypto.Cipher import ARC4key = "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 DESfrom Crypto import Randomkey = "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 AESimport oskey = 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 cipherprint ciphobj.decrypt(cipher)[AES.block_size:]

Trapdoor Function - RSA

Για ένα κρυπτοσύστημα δημόσιου κλειδιού χρειαζόμαστε τρεις αλγορίθμους.
: Ένας πιθανοτικός που παράγει δύο κλειδιά.
: Ένας ντετερμινιστικός αλγόριθμος που ορίζει μια συνάρτηση 
: Ένας ντετερμινιστικός αλγόριθμος που ορίζει μια συνάρτηση  αντίστροφη της .
Στην περίπτωση του RSA παράγουμε δύο μεγάλους πρώτους αριθμούς p,q (τουλάχιστον 1024 bits). Θέτουμε Ν=pq.
Επίσης διαλέγουμε έναν ακέραιο αριθμό 0<e<Ν 
και  τέτοιo ώστε 
Η συνάρτηση  ενώ η αντίστροφη είναι . Mπορούμε κάνοντας χρήση του θεωρήματος τoυ Euler
να αποδείξουμε ότι 
Η ασφάλεια του RSA βασίζεται στην δυσκολία εύρεσης e-οστών ριζών mod N όταν δεν γνωρίζουμε την παραγοντοποίηση του Ν. Το πρόβλημα αυτό δεν έχει αποδειχτεί ότι 
είναι ισοδύναμο με το πρόβλημα της παραγοντοποίησης (RSA problem).
reset()from Crypto.PublicKey import RSArsaobj = RSA.generate(2048)msg = b'Attack at dawn'cipher = rsaobj.encrypt(msg,5)print cipherprint "------------------"message = rsaobj.decrypt(cipher)print message

Επίθεση Wiener στον RSA-textbook

Η επίθεση του Wiener βασίζεται στα συνεχή κλάσματα και στο θεώρημα του Legendre, μπορεί να υλοποιηθεί σε χρόνο O(lne lnN) όταν το μυστικό κλειδί d είναι μικρότερο από ένα συγκεκριμένο αριθμό bit που σχετίζονται από το N.
.
Αρχικά σε ένα φύλλο εργασίας του 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 DSAfrom Crypto.Hash import SHAimport os#Το μήνυμα.message = "Hello"# Το αντικείμενο με τα κλειδιά.dsaobj=DSA.generate(int(1024))# το p είναι 1024 bitsp=dsaobj.p# δημόσιο κλειδί 1024 bits  pk=dsaobj.y# ιδιωτικο κλειδί 160 bitsa=dsaobj.x 
# ο γεννήτορας του πεπερασμένου σώματος g είναι 1024 bitsg=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)