Sagemath

Το αλγεβρικό υπολογιστικό σύστημα 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. Επίσης μπορείτε να συμβουλευτείτε το επίσημο tutorial.

Μπορείτε να χρησιμοποιείτε το 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 στο πεδίο της κρυπτογραφίας γίνεται για εκπαιδευτικούς σκοπούς ώστε να γίνονται κατανοητοί οι αλγόριθμοι κρυπτογράφησης, για ερευνητικές δοκιμές των κρυπτό-συστημάτων σε διάφορες επιθέσεις και για προσομείωση της λειτουργίας του κρυπτό-συστήματος πριν την χρήση του.

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

Αρχικά εισάγουμε την βιβλιοθήκη 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 
Για ένα κρυπτοσύστημα δημόσιου κλειδιού χρειαζόμαστε τρεις αλγορίθμους.

: Ένας πιθανοτικός που παράγει δύο κλειδιά.

: Ένας ντετερμινιστικός αλγόριθμος που ορίζει μια συνάρτηση 

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

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

Η συνάρτηση  ενώ η αντίστροφη είναι . Μπορούμε κάνοντας χρήση του θεωρήματος τoυ Euler
να αποδείξουμε ότι 

Η ασφάλεια του 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.

.

Αρχικά σε ένα φύλλο εργασίας του 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))

Αναφορές

Εξωτερικοί σύνδεσμοι 

 Επίσημη ιστοσελίδα
 wiki
 Tutorial για κρυπτογραφία

GNU