Domanda Generazione chiavi RSA

[narakuyama]

Sto studiando l'algoritmo per la generazione delle chiavi RSA che viene fatta attraverso l'utilizzo dell'algoritmo di EE (Euclide Esteso ) .
Ho difficoltà nel trovare la chiave privata .

L'esempio che sto guardando è cosi :

i due numeri primi sono : 5 e 11
il loro prodotto è 55
il prodotto dei suddetti numeri diminuiti di uno è 40
(qui e dove iniziano i problemi)
il numero coprimo con 40 è 3
3^(-1)mod40= 27 ????? (Non riesco a capire il perchè )

Grazie in anticipo per le vostre risposte
Thx Nara.

 

[St3ve]

Non ho capito qual'è la tua domanda. Hai fatto questo:

• scegli due numeri primi: 5 e 11;
• calcoli n = 5*11 = 55;
• calcoli phi(n) = 4*10 = 40;
• scegli un esponente che sia coprimo con phi(n): 3;
• calcoli l'inversa moltiplicativa dell'esponente modulo phi(n), quindi cerchi una d tale che d*3 = 1 mod 40; questo valore è 27, perché 27*3 = 1 mod 40.

Adesso la tua chiave pubblica è formata dalla coppia (55, 3) e la tua chiave privata dalla tripla (5, 11, 27).

Supponiamo che il tuo messaggio sia rappresentato dal numero 32, per criptarlo fai 32^3 = 43 mod 55. Quindi 43 è l'encryption di 32 usando la tua chiave pubblica. Supponiamo che vuoi decriptare 43, fai 43^27 = 32 mod 55, ecco che hai ritrovato il 32.

 

[_ _]

Se d=gcd(a,b) allora l'Identità di Bézout assicura l'esistenza di x e y tali che ax+by=d, in particolare se i due numeri sono coprimi (come nel caso dell'RSA) allora è possibile trovare x e y tali che ax+by=1.

Questi due valori x e y sono ottenibili mediante l'algoritmo di Euclide esteso, la prima parte del quale è semplicemente il calcolo del gcd mediante una serie di divisioni con resto, mentre la seconda si tratta di risalire le divisioni fatte al contrario in modo da esprimere il gcd come combinazione lineare dei due numeri di partenza.

Nel caso specifico con 40 e 3, commentando qualche passaggio:
40=13*3+1 divido con resto 40 per 3
3=3*1+0 divido con resto 3 per 1, essendo il resto 0 so che il gcd è il resto ottenuto al passaggio precedente, ovvero 1.

Adesso risalgo queste operazioni e scrivo, portando isolando l'1, il gcd come combinazione lineare di 40 e 3:
1=40*1+(-13)*3

Ma visto che sto lavorando in Z/40Z la prima parte è nulla e mi resta 1=(-13)*3 ma -13=27 mod 40 quindi l'inverso moltiplicativo di 3 che stavo cercando è 27 (tecnicamente puoi anche tenere -13 come chiave, ma ti complichi la vita più avanti quando devi calcolare le potenze quindi ti conviene prenderla positiva)