Newsgroup: it.comp.lang.c++
Titolo: RSA e overflow

Sto implementando l' algoritmo RSA (quello implementato da PGP), segue una
breve spiegazione dell' algoritmo :
Il sistema di cifratura a
chiavi pubbliche RSA, e' basato sull'applicazione di algoritmi aritmetici a
grandi valori interi. La chiave P e' in realta' una coppia di interi (N, p),
mentre la chiave S e' una coppia di interi (N, s) con s segreto.
Questi numeri devono essere estremamente grandi (tipicamente, N potrebbe
essere di 200 cifre, p ed s di 100). I metodi utilizzati per cifrare e
decifrare sono semplici: innanzitutto si scompone il messaggio in numeri
minori di N (ad esempio, considerando Log(N) bit alla volta della stringa
binaria corrispondente alla rappresentazione per caratteri del messaggio).
Questi numeri sono indipendentemente elevati ad una potenza modulo N: per
cifrare il messaggio M (in realta' una sua parte), si calcola:
C = P(M) = M^p mod N
per decifrare un testo cifrato C si calcola:
M = S(C) = C^s mod N.
Occupiamoci adesso di scegliere le crittovariabili N, p ed s in modo tale da
soddisfare la prima e la terza condizione. E' necessario, introdurre alcuni
concetti di teoria dei numeri che vanno ben oltre le mie conoscenze, ma e'
possibile accennare alle idee di base. Per prima cosa, e' ncessario generare
tre grandi numeri primi (approssimativamente di 200 cifre) "casuali": il
maggiore verra' preso come s, mentre gli altri due verranno chiamati x ed y.
A questo punto, si pone N uguale al prodotto di x ed y e si sceglie p in
modo
che soddisfi la relazione:
ps mod (x-1)(y-1)=1
E' possibile dimostrare che, scegliendo N, p ed s in questo modo, risulti:
M^ps mod N = M
per tutti i messaggi M.
Ad esempio, sfruttando una codifica binaria del tipo:
----------------------------------------------------------------------------
-
A |B |C |D |E |F |G |H |I |J |K |L |M |N |O |P |Q |R |S |T |U |V |W |X |Y |Z
----------------------------------------------------------------------------
-
01|02|03|04|05|06|07|08|09|10|11|12|13|14|15|16|17|18|19|20|21|22|23|24|25|2
6
----------------------------------------------------------------------------
-
il messaggio "FUCK THE NSA" potrebbe corrispondere al seguente numero:
062103110020080500141901
A questo punto, per non rendere l'esempio troppo complicato, si parte con
dei
numeri primi di 2 cifre (invece delle almeno 100 richieste): si ponga:
x = 47
y = 79
s = 97.
Questi valori definiscono N = 3713 (il prodotto di x ed y) e p = 37
(l'unico intero che da' resto 1 se moltiplicato per 97 e diviso per 3588).
A questo punto, per codificare il messaggio, lo si scompone in blocchi di 4
cifre e li si eleva alla p-esima potenza (modulo N). Queste operazioni
portano
ad una codifica del tipo:
0621^37 (mod N) = 3286
0311^37 (mod N) = 3536
0020^37 (mod N) = 3413
.
.
.
1901^37 (mod N) = 335
Il processo di decodifica e' lo stesso, ma si utilizza s al posto di p;
cosi'
si riottiene lo stesso messaggio di partenza poiche' 3286^97 (mod
3713)=0621,
etc.
La parte piu' importante del calcolo richiesto e' la codifica del messaggio.
Pur richiedendo sofisticati concetti di teoria dei numeri e programmi
piuttosto elaborati per la gestione di numeri di notevole lunghezza, il
tempo
richiesto per il calcolo delle chiavi tende ad essere inferiore al quadrato
della loro lunghezza.
Il programma in pratica l' ho finito.
Il problema e' che il compilatore g++ supporta i long sino a 32 bit e questo
non consente di usare chiavi di cifre elevate anche perche' poi va svolta l'
operazione di elevamento a potenza:
C = P(M) = M^p mod N ,nell' esempio 0621^37 (mod N) = 3286, benche il
risultato finale non produca overflow, questo avviene perche' l' operazione
di elevamento viene svolta prima...
Domanda: vi viene in mente un modo per evitare l' overflow?
se si fammi sapere.
Ciao Gianni
--
Posted from 
twingo.tiscalinet.it
 [195.130.224.85] 
via Mailgate.ORG Server - 
http://www.Mailgate.ORG

Mi scuso per avervi fatto subire il pappone sull' RSA.
Il problema e' tutto qua' :
#include <math.h>
void main(void)
{
unsigned long x;
int y=122,z=9999,k=9999999;
x=pow(y,x)%k;
printf("%d\n",x);
}
come fare per avere x corretto?
ho installata la RED HAT 6.1 e sia per il gcc che per il g++ la max versione
supportata per gli int e' a 32 bit...
grazie Gianni


 se si fammi sapere.
Innanzitutto potresti usare il tipo long long
(ora presente anche in ANSI/ISO C).
Su di un PC long long č di 64 bit.
Comunque mi sembra ci siano metodi per calcolare
 M^p mod N
senza dover calcolare M^p (che produce l'overflow).
Se non ricordo male c'č un cenno nel libro
"Algoritmi in C++" di Sedgewich.
Manlio Perillo

supportata per gli int e' a 32 bit...
ci sono i long long a 64 bit ( ma non so se ti risolve del tutto il problema
o sposta solo un po' piu' in la' il limite )

 supportata per gli int e' a 32 bit...
se scrivi y=n*k+m (ovvero (y mod k)=m), y^z vale m^z piu' termini che
moltiplicano una potenza intera di k.
quindi (y^z mod k) e' uguale a (m^z mod k); o sbaglio qualcosa?
in questo modo dovresti evitare l'overflow.  ammesso che z sia intero...
-- 
Maurizio Loreti                         
http://www.pd.infn.it/~loreti/mlo.html
Univ. of Padova, Dept. of Physics - Padova, Italy            
lor...@pd.infn.it

 Si se definisco m=(y mod k) e' cosi', ma quando elevo per z, l' overflow
occorre....forse non ho capito bene cosa intendevi dire...se e' cosi'
spiegami please.
Ciao Gianni.



Ciao,
 aggiungo qualche delucidazione e considerazione:
Maurizio, giustamente, ha suggerito questa semplificazione
x=pow(y,z)%k
equivale a
x=pow(y%k,z)%k
se k fosse piccolo si ridurrebbe notevolmente il primo argomento;
consideranto i valori indicativi del tuo esempio (y=122,k=9999999)
questo accorgimento non è sufficiente infatti, nella peggiore delle
ipotesi avresti:
pow(9999998,z) che va in o.f. con z=2
Credo che non ti resti altra soluzione che utilizzare qualche
libreria sui numeri arbitrariamente lunghi.
Davide
PS it.scienza.matematica sarebbe stato più appropriato.

 supportata per gli int e' a 32 bit...
Probabilmente c'e una svista: se volevi scrivere
    x=pow(y,z)%k;
puoi usare questa semplice routine:
ULONG ME(const ULONG a,const UI64 k,const ULONG n)
{
 if(k==0) return 1;
 char buf[65];
 _ui64toa(k,buf,2); UI64 b=1,A=a; if(k&1) b=a;
 const int t=strlen(buf)-2;
 for(int i=t;i>=0;i--) {
  A=(A*A)%n; if(buf[i]=='1') b=(A*b)%n;
 }
 return b;
}
ULONG č unsigned long, UI64 č unsigned a 64 bits,
_ui64toa(k,buf,2) memorizza in buf la rappresentazione binaria di k.
Quindi per x=pow(y,z)%k scriverai  x=ME(y,z,k) da cui x=6672806.
Ma mi sorge un dubbio: se hai il problema dell'elevamento a potenza devo
presumere che non disponi di una libreria per numeri interi di lunghezza
indefinita. In questo caso come fai ad effettuare tutti gli altri calcoli
(numeri primi, lcm, gcd inverso del modulo, ecc)?
Cristiano