algoritmo criptatura rsa

[bigboss1984]

ciao a tutti,
nn so se sia il posto giusto dove chiederlo, ma guardando le varie parti del forum mi sermbra la piu appropriata. nn riesco a capire un esempio delle dispense di un proff. sulla crittografia mediante chiave pubblica rsa.

qui c'è l'esempio della generazione delle chiavi:

Generate a public/private key pair:
1 Generate p = 47, q = 71
2 Compute n = pq = 3337 and  f= (p − 1)(q − 1) = 46 * 70 = 3320
3 Choose e = 79 (randomly in the interval [1..3320])
4 Compute d = 79^(−1) mod 3320 = 1019
5 Public key (e, n) = (79, 3337), private key (d, n) = (1019, 3337)

ci sto dietro da tutto il giorno e nn riesco a capire come possa venire 1019 nel punto 4, ho fatto un sacco di prove ma nn capisco....mi suggerite qualcosa?
grazie

[Ikon O'Cluster]

Hai ragione è il solito esempio. Anche sui miei appunti di sicurezza. Non spiega come si determini. Allora, proviamo ad arrivarci in due.

In pratica si ha che:

e*d = 1 (mod f)

Questo significa che:

(e*d) mod f = 1

Ovvero e*d - 1 deve essere multiplo di f:

e*d - 1 = k*f

Con k intero positivo arbitrario.

Quindi cosa sai: sai che 'e' e 'd' devono essere tali da soddisfare questa regola. Tuttavia tu determini 'e' in maniera del tutto autonoma salvo soddisfare la relazione:

MCD(e, f) = 1

Cioè e < n ed e <> 1 che non ha fattori in comune con f (in pratica 'e' deve essere relativamente primo rispetto a f).

Cosa ne deriva: che tu prendi una coppia di numeri a caso <e, d> e verifichi se (e*d - 1) è multiplo di f se non lo è prendi un'altra coppia. Come costruire la coppia non lo so. Si potrà fare in maniera più o meno efficiente ma a Rivest, Shamir ed Adleman non interessava più di tanto. Loro hanno detto se tu prendi una coppia così allora la tua chiave è questa qui. Poi la coppia la devi prendere tu, sono problemi tuoi... un classico dei matematici :)

[Ikon O'Cluster]

Aggiungo che di fatto non è detto che per ogni scelta di p e q esista una coppia valida di 'e' e d!!! Però non saprei dimostrarlo, ma a occhio penso sia molto probabile...

[franksisca]

credo che questo esempio renda più chiara la risoluzione (anche se mi sembra strano che non lo abbiate visto)
http://it.wikipedia.org/wiki/RSA

[Ikon O'Cluster]

Uhm... ma il problema di chi aperto il topic è sicuramente lo stesso che ho avuto io quando ho studiato quella roba. In pratica ci domandiamo non "cosa succede qua? non c'ho capito una ceppa!" ma piuttosto "come cavolo li trovo in 30 secondi i valori di 'e' e di 'd' se f è un numero enorme?". Penso che l'esempio da te proposto con f=21 sia alquanto immediato :) prova con f nell'ordine delle migliaia!!!!!

[franksisca]

Uhm... ma il problema di chi aperto il topic è sicuramente lo stesso che ho avuto io quando ho studiato quella roba. In pratica ci domandiamo non "cosa succede qua? non c'ho capito una ceppa!" ma piuttosto "come cavolo li trovo in 30 secondi i valori di 'e' e di 'd' se f è un numero enorme?". Penso che l'esempio da te proposto con f=21 sia alquanto immediato :) prova con f nell'ordine delle migliaia!!!!!

ma infatti all'esame (quando l'ho fatto io) il prof consigliava di usare numeri piccoli per non perderci ore X_X

[Ikon O'Cluster]

Se il prof. non lo consiglia però, si potrebbe pensare che c'è un metodo di calcolo semplice che non hai capito. Il tuo prof cmq non era molto "saggio" il mio consigliava numeri primi di 100/200 cifre per stare più sicuri!!! ;)

[franksisca]

Se il prof. non lo consiglia però, si potrebbe pensare che c'è un metodo di calcolo semplice che non hai capito. Il tuo prof cmq non era molto "saggio" il mio consigliava numeri primi di 100/200 cifre per stare più sicuri!!! ;)

ti assicuro che il mio prof è molto saggio....certo in un esame di 1 ora non può pretendere che tu cerchi un numero primo di 2-300 cifre -.-

tanto poi all'orale ti chiedeva la teoria dietro RSA...quindi il problema non si poneva :D

[Ikon O'Cluster]

No ma avevo capito cosa intendevi, era solo una battuta ironica che avevo utilizzato per dire che è comodo prendere numeri piccoli, ma che ovviamente è tutto a discapito della sicurezza della cifratura/decifratura... infatti per sottolineare che era una battuta alla fine della frase avevo messo uno smile: ;)

[franksisca]

No ma avevo capito cosa intendevi, era solo una battuta ironica che avevo utilizzato per dire che è comodo prendere numeri piccoli, ma che ovviamente è tutto a discapito della sicurezza della cifratura/decifratura... infatti per sottolineare che era una battuta alla fine della frase avevo messo uno smile: ;)

si tranquillo la mia era un puntualizzazione non volta al flame, scusami se ho lasciato trasparire questo ;)

:D

[Ikon O'Cluster]

No avevo inteso che non te la sei presa, però rileggendo avevo notato che non si capivae ho precisato...

[wingman87]

Penso vi possa tornare utile questa pagina che ho trovato googlando: http://www.dm.unito.it/~cerruti/cp0/primi0.html