gap> 2 * 2
> ;
4
gap> 6753178538435821435 * 124964129649421614;
843905078422785554085457306733496090
gap> Read("RSA.gap");


findPQ(SIZE) restituisce una lista [p, q]
dove p e q sono primi, e p * q è circa SIZE

tenToB (n, B) gives B-ary digits

 
findR([p, q]) calcola un intero r coprimo con Phi(n),
(ove n = p * q)
che si possa dunque usare come esponente per cifrare nell'RSA
 
 
findS(r, [p, q]), ove n = p * q, e r è coprimo con Phi(n),
calcola un intero s tale che r * s = 1 (mod Phi(n)),
dunque s si usa come esponente per decifrare nell'RSA.
 
 
RSAencode(TESTO, r, n), ove r è coprimo con Phi(n),
cifra il TESTO (solo lettere maiuscole non accentate)
usando RSA in una successione di numeri compresi fra 0 e n
 
 
RSAdecode(SUC_NUM, s, n), ove s è coprimo con Phi(n),
decifra la successione di  numeri compresi fra 0 e n SUC_NUM
(ottenuta mediante RSA, usando r e n)
ricavando il testo originale. Qui s è tale che
r * s = 1 (mod Phi(n))
 
# findPQ := function (SIZE)
# findR := function([p,q])
# findS := function(r,[p,q])
# RSAencode := function (stringa, r, n)
# RSAdecode := function(successione_di_numeri, s, n)
gap> findPQ(1000);
[ 29, 37 ]
gap> p := 29; q := 37;
29
37
gap> 2 = 3;
false
gap> n := p * q;
1073
gap>  r := findR([p, q]);
425
gap> Phi(n);
1008
gap> (p-1) * (q-1);
1008
gap> Gcd(r, Phi(n));
1
gap> Read("MCD.gap");

# Qui vediamo tre versioni dell'algoritmo di Euclide
#   per il calcolo del massimo comun divisore di due numeri

# La prima *MCDlento* fa solo il MCD,
#   ma racconta ogni divisione che sta facendo
# La seconda *MCD* è meno verbosa,
#   ma calcola anche i coefficienti della combinazione lineare

# La terza *MCDcompleto*,
#   fa proprio tutto, vedere per credere

gap> MCDcompleto(r, Phi(n));
Combinazione #-1: 425 * 1 + 1008 * 0 = 425
Combinazione #0: 425 * 0 + 1008 * 1 = 1008
Divisione #1: 425 = 1008 * 0 + 425
Combinazione #1: 425 * (1) + 1008 * (0) = 425
Divisione #2: 1008 = 425 * 2 + 158
Combinazione #2: 425 * (-2) + 1008 * (1) = 158
Divisione #3: 425 = 158 * 2 + 109
Combinazione #3: 425 * (5) + 1008 * (-2) = 109
Divisione #4: 158 = 109 * 1 + 49
Combinazione #4: 425 * (-7) + 1008 * (3) = 49
Divisione #5: 109 = 49 * 2 + 11
Combinazione #5: 425 * (19) + 1008 * (-8) = 11
Divisione #6: 49 = 11 * 4 + 5
Combinazione #6: 425 * (-83) + 1008 * (35) = 5
Divisione #7: 11 = 5 * 2 + 1
Combinazione #7: 425 * (185) + 1008 * (-78) = 1
Divisione #8: 5 = 1 * 5 + 0
Il massimo comun divisore è 1,
 ci sono volute 8 divisioni,
 e la combinazione lineare è:
425 * (185) + 1008 * (-78) = 1
gap> s := findS(r, [p,q]);
185
gap> GcdRepresentation(r,Phi(n));
[ 185, -78 ]
gap> 
gap> 
gap> 
gap> r;
425
gap> n;
1073
gap> chiaro := "PROVA";
"PROVA"
gap> 26 < n;
true
gap> 26^2 < n;
true
gap> 26^3 < n;
false
gap> 26^4 < n;
false
gap> ic('A');
0
gap> ic('P');
15
gap> ic('R');
17
gap> 15 + 17 * 26;
457
gap> 457^r;
2913298798203090158419197806056137368520609043657640938313442449445533477896\
6754597255265763715076185312355096660060196588935929024889049142791606562516\
1097507731472631326894243335063932742691702084870504451648581860906342351027\
0572555458183488031106215060629422185668691920472466900415154128121739114240\
4898766352542903378334735367973644107624985355301569100764371824967845316695\
7469493121319777377538956603153397768833279870179576060320054972079032504498\
6669613195590786567488697214519999653453102965333547033494619873737153116196\
1632591684555089987966159185559328827132262744228129708641344957706037755763\
2583615147446491393722175249113260418065312223867779670688977349725782632824\
3142593110709599821301170466367505764477547598579040397430333725560328519268\
3080083204466631472000747656821931365444424506752893938335142850817507686587\
2742696289038592707627319279412062812587486276266054650375987048438117026767\
3155912148594663368226460071087347032232850384268153093149623899096833228087\
2010984863029742025309020726002293617785201925759469711797911035324310315470\
8852340992623407822238256312647913915448531269407997447487667522057
gap> 457^r mod n;
651
gap> PowerMod(457, r, n);
651
gap>  tenToB(r,2);
[ 1, 0, 0, 1, 0, 1, 0, 1, 1 ]
gap>  tenToB(457,26);
[ 15, 17 ]
gap> PowerMod(457, r, n);
651
gap> RSAencode(chiaro, r, n);
[ 651, 701, 450 ]
gap> chiaro;
"PROVAX"
gap> PowerMod(651, s, n);
457
gap> tenToB(last, 26);
[ 15, 17 ]
gap> RSAencode(chiaro, r, n);
[ 651, 701, 450 ]
gap> RSAdecode(last, s, n);
Blocklength is 2
"PROVAX"
gap> findPQ(1000000);
[ 47, 21277 ]
gap> findPQ(1000000);
[ 887, 1129 ]
gap> p := 887; q := 1129;
887
1129
gap> n := p * q;
1001423
gap>  r := findR([p, q]);
339211
gap> s := findS(r, [p,q]);
834019
gap> GcdRepresentation(r, Phi(n));
[ -165389, 56135 ]
gap> MCDcompleto(r, Phi(n));
Combinazione #-1: 339211 * 1 + 999408 * 0 = 339211
Combinazione #0: 339211 * 0 + 999408 * 1 = 999408
Divisione #1: 339211 = 999408 * 0 + 339211
Combinazione #1: 339211 * (1) + 999408 * (0) = 339211
Divisione #2: 999408 = 339211 * 2 + 320986
Combinazione #2: 339211 * (-2) + 999408 * (1) = 320986
Divisione #3: 339211 = 320986 * 1 + 18225
Combinazione #3: 339211 * (3) + 999408 * (-1) = 18225
Divisione #4: 320986 = 18225 * 17 + 11161
Combinazione #4: 339211 * (-53) + 999408 * (18) = 11161
Divisione #5: 18225 = 11161 * 1 + 7064
Combinazione #5: 339211 * (56) + 999408 * (-19) = 7064
Divisione #6: 11161 = 7064 * 1 + 4097
Combinazione #6: 339211 * (-109) + 999408 * (37) = 4097
Divisione #7: 7064 = 4097 * 1 + 2967
Combinazione #7: 339211 * (165) + 999408 * (-56) = 2967
Divisione #8: 4097 = 2967 * 1 + 1130
Combinazione #8: 339211 * (-274) + 999408 * (93) = 1130
Divisione #9: 2967 = 1130 * 2 + 707
Combinazione #9: 339211 * (713) + 999408 * (-242) = 707
Divisione #10: 1130 = 707 * 1 + 423
Combinazione #10: 339211 * (-987) + 999408 * (335) = 423
Divisione #11: 707 = 423 * 1 + 284
Combinazione #11: 339211 * (1700) + 999408 * (-577) = 284
Divisione #12: 423 = 284 * 1 + 139
Combinazione #12: 339211 * (-2687) + 999408 * (912) = 139
Divisione #13: 284 = 139 * 2 + 6
Combinazione #13: 339211 * (7074) + 999408 * (-2401) = 6
Divisione #14: 139 = 6 * 23 + 1
Combinazione #14: 339211 * (-165389) + 999408 * (56135) = 1
Divisione #15: 6 = 1 * 6 + 0
Il massimo comun divisore è 1,
 ci sono volute 15 divisioni,
 e la combinazione lineare è:
339211 * (-165389) + 999408 * (56135) = 1
gap> -165389 + Phi(n);
834019
gap> s;
834019
gap> s := findS(r, [p,q]);
834019
gap> 26^4 < n;
true
gap> 26^5 < n;
false
gap> chiaro := "PROVADITRASMISSIONECONRSA";
"PROVADITRASMISSIONECONRSA"
gap> scuro := RSAencode(chiaro, r, n);
[ 262363, 648563, 326014, 630623, 288285, 765897, 93893 ]
gap> ic('P');
15
gap> ic('R');
17
gap> ic('O');
14
gap> ic('V');
21
gap> 15 + 26* 17 + 14 * 26^2 + 21 * 26^3;
379017
gap> tenToB(last,26);
[ 15, 17, 14, 21 ]
gap> last2 mod 26;
15
gap> PowerMod(last3,r,n);
262363
gap> 379017^r;
<<an integer too large to be printed>>
gap> tenToB(r,2);
[ 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1 ]
gap> RSAdecode(scuro, s, n);
Blocklength is 4
"PROVADITRASMISSIONECONRSAXXX"