Newsgroup: it.comp.sicurezza.pgp
Titolo: RSA & overflow

Su un inserto informatico del Sole24Ore di tempo fa il prof. L. Felician
dell'universita' di Trento (se non sbaglio), illustrava l'algoritmo RSA per
cifrare un documento di testo.
Utilizzando la sua spiegazione ho provato, dopo aver calcolato i valori
delle chiavi, a cifrare un carattere usando la calcolatrice. Naturalmente
funziona, ma se i valori sono appena un po' grandi la calcolatrice va in
overflow!
Per risolvere la cosa (non spiegata dal prof.) ho notato che si giunge al
risultato scomponendo nei calcoli il valore
della parte esponenziale e applicando per ogni calcolo il Mod.
Es. :
C = 67 alla 9ª (Mod 13)
9 = 2 + 3 + 4
C = ((67^2ª(Mod13)) * (67^3ª(Mod13)) * (67^4ª(Mod13)) (Mod 13)
Questo empiricamente, ma sapreste dirmi per favore l'esatta regola
matematica per la scomposizione dell'esponente?
o se si puo' fare in altro modo.
Regards,
 Mattex
--------------------------------
Inviato via 
http://usenet.libero.it

o se si puo' fare in altro modo.
Sì, questa regola vale.
Ovvero
  a^b mod n = (a^c mod n)^d mod n
per ogni
  b = c + d
Ci sono però metodi più rapidi che non moltiplicare il numero b volte
per sé stesso: se usi la scomposizione binaria di b puoi usare
sfruttare molto shift e somme per risparmiare molti calcoli.
ad esempio:
  b = 77 (non ci sono motivi per cui l'esponente non sia un numero
grande)
  b2 = 1001101
  b = 2^7 + 2^5 + 2^4 + 2^0
quindi
  c = a ^ b = a^2^0 * a^2^4 * a^2^5 * a^2^7
come lista di operazioni:
  t = a // ora vale a^2^0
  c = t
  t = t * t // ora vale a^2^1
  t = t * t // ora vale a^2^2
  t = t * t // ora vale a^2^3
  t = t * t // ora vale a^2^4
  c = c * t
  t = t * t // ora vale a^2^5
  c = c * t
  t = t * t // ora vale a^2^6
  t = t * t // ora vale a^2^7
  c = c * t
Quindi ho eseguito 10 moltipliazioni (a modulo) invece di 77.
Per numeri maggiori ovviamente il guadagno è ancora maggiore, dato che
va con logaritmo in base due del numero.
--
L a p o   L u c h i n i
l a p o @ l a p o . i t
w w w . l a p o . i t /

sfruttare molto shift e somme per risparmiare molti calcoli.
Nota: ovviamente č un lapsus.. qua non si convertono le
moltiplicazioni in shift ma le potenze in moltiplicazioni..
rileggere la frase come:
"sfruttare molto moltiplicazioni e somme in modo intelligente per
risparmiare molti calcoli"


 va con logaritmo in base due del numero.
...i logaritmi li sto studio quest'anno a scuola! :)
magari se ci studio su un po' su riesco a capirci qualcosa di cio' che hai
scritto! Grazie!
Volevo chiederti: cio' che hai proposto che limiti ha su un PC 32 bit?
Voglio dire che in partenza, si possono avere valori grandi al massimo la
grandezza di un double. In pratica a parte esprimerlo in bit,
quante cifre per ogni valore della chiave pubblica l'utente puo' in teoria
digitare per cifrare un messaggio
utilizzando l'algoritmo da te espresso? (scrivendo in numeri interi)
Io utilizzando quello prima proposto non andavo oltre le 8 :-(
tipo : C = a ^ 12345678 Mod 12345678


tipo : C = a ^ 12345678 Mod 12345678
Se usi una librria per numeri interi grandi non hai limiti di
dimensione, solo di velocità.
Per ora non ti consiglio di avventurarti nello scrivere da solo una
libreria per numero interi grandi perché ti servirebbe quantomeno la
conoscenza delle trasformate di Fourier per fare una moltiplicaizione
veloce ^_^
(e con la scusa di sconsigliartelo ti ho detto un'altra parola che può
servirti se vuoi approfondire l'argomento =P)


 b = 2^7 + 2^5 + 2^4 + 2^0
com'e' che gia' qui a me viene:
b = 2^7 + 2^5 + 2^4 + 2^0 == 177 ??
2)
 Visto che a casa uso ancora un Celeron 366 Mhz:
con l'aumentare del numero di cifre la velocita' di esecuzione
si abbassa in modo esponenziale?
Perdero' un sacco di tempo?


Perdero' un sacco di tempo?
Non č comunque esponenziale, anche col "metodo non ottimizzato" per
elevare alla n devi 'solo' fare n moltiplicazioni modulari.. il metodo
che ti ho proposto ti permette di farne (asintotticamente) solo
logaritmo di n circa.
Lapo
