[RISOLTO] esercizio di crittografia RSA

[Crow]

ciao a tutti sto impazzendo in questi giorni tra teoria dei numeri teorema esteso di euclide ecce in pratica devo fare questo esercizio:
ho la chiave pubblica di alice (e=11,n=49) e devo trovare la chiave calcolare la chiave privata di alice (d,n) il teorema esteso di euclide mi sta facendo impazzire esattamente questo non riesco a risolvere d-->congruenza-->e^-1(modf(n))
spero che qualcuno mi possa dare una mano grazie.

[pulmro]

Prima di tutto f(n) = f(7^2) = (7-1)*7 = 42.

Poi Euclide per ottenere l'uguaglianza di Bezout: e*d + k*f(n)=1.

42 = 3*11 + 9
11 = 1*9 + 2
9 = 4*2 + 1
e rileggendole al contrario:
1 = 9 - 4*2 = 9 - 4*(11 - 9) =
= 5*9 - 4*11 = 5*(42 - 3*11) - 4*11=
= -19*11 + 5*42

Quindi d=-19 che è congruo a 23 modulo f(n).

happy RSA!

[Crow]

ciao pulmro grazie mille della risposta sei stato super gentilissimo, comunque volevo delle informazioni se puoi te ne sarei molto grato in pratica io devo fare un esame di informatica, crittografia e sicurezza su reti, sfortunatamente proprio la lezione su RSA me la persi per cui adesso sono un pò in panne con questi esercizi, in pratica io sul libro ho letto che f(n)=(p-1)x(p-1)

infatti sul libro ci sta un esempio eccolo:
p=17, q=11
calcolo n=pq = 17x11=186
calcolo f(n)=(p-1)(q-1)= 16x10=160
selezionare e tale che sia primo relativo di f(n)=160 e minore di f(n) per cui scelgo e=7
e alla fine determinare d tale che de-->congruenza-->1 (mod 160)

e alla fine dice che d=23 perchè 23x7=161 = 10x16+1
per cui 23x7-->congruenza -->1(mod 160)

volevo delle spiegazioni in merito su tutto quello che ci sta da dire partendo da p e q.

se possibile te ne sarei molto ma molto grato, grazie ancora.

[pulmro]

Allora, prima cosa: la formula per f(n)=(p-1)*(q-1) la puoi usare solo se p, q sono diversi, altrimenti se n=p^2 devi usare la formula f(n)=(p-1)*p. (ricorri alla mitica wikipedia phi di eulero se vuoi i dettagli : )

fino alla scelta di e fila tutto liscio. Il motivo per cui si tira fuori euclide per risolvere la congruenza per d è che
de-->congruenza-->1 (mod 160)

equivale a dire: d*e = 1 + 160*k per un certo k, ovvero: d*e +160*k = 1.
Si dimostra che quando due numeri sono coprimi ( 160 ed e lo sono) esistono unici d,k per cui vale l'identità magica della riga sopra.
Visto che 160 ed e sono coprimi l'algoritmo di euclide deve terminare con l'ultimo resto non nullo uguale a 1 (è il mcd). Sono le tre divisioni che ho fatto nel primo esercizio.
Per ottenere l'identità magica devi rileggere al contrario le divisioni fatte, sostituendo via via il quoziente di quella precedente e raccogliendo e facendo i conti (è più facile vederlo che raccontarlo)
Alla fine ottieni l'dentità che volevi e da lì prendi d!
spero di non aver esagerato nei dettagli e di esserti stato d'aiuto

[Crow]

grazie mille del chiarimento + che esaustivo veramente grazie, mi sono fatto un lettura della teoria dei numeri per la funzione toziente di eulero.
e adesso tocca a euclide hihihihihihihiihhi.

comunque alla fine ci sta un punto che non mi è chiaro :
allora
sto cercando di capire quale sia la ralazione che intercorre(se c'è) tra x e y cioè 42 = 3*11 + 9 in questo caso 3 e 9 e poi quell'11 sappresenta e oppure è naturalmente correlato con x e y.
semplificando: 3 e 9 li scelgo per una qualche proprietà del teorema di euclide o sono numeri scelti secondo unaltro modo.
scusami se ti prendo tempo ma sto impazzendo per questo esame comunque grazie ancora.

[pulmro]

è che scritta così si vede male, ma 42=3*11 + 9 significa semplicemente fai la divisione di 42 per 11: l'11 ci sta 3 volte e avrai resto 9. In genere si scrive a = b*q + r per indicare la divisione euclidea. (In pratica r = a%b del linguaggio C)
Al passo successivo fai la divisione di b per r. (nell'esempio dividi 11 per 9) e così via finchè hai resto 1.

Questo funziona perchè ogni volta MCD(a,b) = MCD(b,r).

[Crow]

ciao pulmro grazie mille sei stato gentilissimo ad offrirmi il tuo aiuto che mi è stato di grandissimo aiuto, grazie ancora