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 σαν απλή αριθμομηχανή, π.χ.


```python
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)
```

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

```python
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])
```

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

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

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

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

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

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

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

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

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

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

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

```python
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)]
```

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

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

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

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

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

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


## Συναρτήσεις
Για να ορίσω μια συνάρτηση απλά δίνω

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

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

```python
sage:f(1)
e+1

sage:f(1).n()
3.71828182845905
```


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

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

και

```python
sage:g(1,1)
2
```

Ενώ

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

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

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


thumb|190px
Η σειρά Taylor

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


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

```python
sage:plot(x^2,x)
```


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

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


## Γραμμική Άλγεβρα

```python
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]])
```

### Διαγωνοποίηση

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


```python
import Crypto
help (Crypto)
```


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

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


```python
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 μεταξύ τους.

```python
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 κύκλους. Το αποτέλεσμα που θα προκύψει ανακατεύεται με την αντίστροφη μετάθεση που έγινε στην αρχή και αυτό είναι η έξοδος του αλγορίθμου.

```python
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.


```python
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.
Επίσης διαλέγουμε έναν ακέραιο αριθμό 0d τέτοι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).


```python
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.

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


```python
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.

Ένα σημαντικό σημείο ασφάλειας στην υλοποίηση του αλγορίθμου είναι ότι το εφήμερο κλειδί πρέπει να είναι διαφορετικό για κάθε υπογραφή.
```python
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