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 fatemi sapere.
--
Posted from 
twingo.tiscalinet.it
 [195.130.224.85] 
via Mailgate.ORG Server - 
http://www.Mailgate.ORG

 in mente un modo per evitare l' overflow? se si fatemi sapere.
  Tutto qui? Non potevi chiederlo subito? ;)
  I compilatori GNU supportano ormai da svariate versioni il tipo /long
long/ a sessantaquattro bit. Ti basta una chiave cosi` lunga?
	Alla prossima,
		Marco

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


  Tutto qui? Non potevi chiederlo subito? ;)
  I compilatori GNU supportano ormai da svariate versioni il tipo /long
long/ a sessantaquattro bit. Ti basta una chiave cosi` lunga?
Io ho installato la RED HAT 6.1 (la penultima della RED HAT) e il tipo long
long a 64 bit non e' supportato.....
--
Posted from 
laguna.tiscalinet.it
 [195.130.224.86] 


Sedgewich ???
Prima o poi mi decidero' anche io a scrivere la criptoapi RSA.
Non ti conviene sperare di eseguire mai quell' elevamento
a potenza, neanche usando la libreria la libreria GPL per
calcoli in arbitraria precisione. Te lo immagini PGP che
usa chiavi anche maggiori di 1024 bits eseguire quel calcolo?
L' unica soluzione e' nell' aritmetica modulare:
Prima ti devi sviluppare una mini libreria per calcoli in 
arbitraria precisione che agisca su operandi di tipo stringa
(char *) e quindi dovrai fare come a sQuola :) , mettere in
colonna e gestire i riporti. Ti basta una funzione che
moltiplica due stringhe di bits e una che ne calcola il resto.
Poi e' da comprendere che problema ti sei posto: se la base
e' un numero da 1000 bits e l' esponente pure, non e' che devo
eseguire qualche miliardo di moltiplicazioni, infatti per avere
numeri di unita' di miliardi bastano 32 bits, ma qui' hai 1024
bits di esponente. Non puoi farlo se non sfruttando altre proprieta'
dell' operazione resto.
considera solo numeri interi per cio' che segue:
x / y = q  /* x didiso y uguale quoziente intero */
x % y = r  /* x modulo y uguale resto */
una proprieta' facilmente intuibile e' che un numero divisibile
senza resto per un altro, moltiplicato per QUALSIASI NUMERO INTERO
dara' sempre un numero divisibile senza resto per il medesimo
numero.
se immagini x uguale a y*q + r il primo termine, moltiplicando
x per z e' uguale a (y*q)*z + r*z. il primo termine e' senz' altro
divisibile per x senza resto, quindi sapere il resto dix*z % y
equivale a calcolare r*z % y  se r e' stato precedentemente
calcolato.
quindi calcoli x % y = r
con r*x % y rxquadro
con rxquadro*rxquadro % y = rxquarta
....
per un esponente di 1024 bits potresti calcolare per ogni bit
a 1 dell' esponente il resto con 1024 passi. poi, siccome
l' esponente e' scomponibile come numero binario in somme di
potenze di due e delle somme all' esponente sono convertibili cosi'
X^(A + B) e' uguale a (X^A)+(X^B), puoi moltiplicare i resti
"parziali" cosi' ottenuti e AD OGNI MOLTIPLICAZIONE NE CALCOLI
ANCORA IL RESTO	, solo in corrispondenza di ogni bit a 1
(hai quindi bisogno di un array di puntatori a char lungo
quanto i bits della chiave)
Quindi i numeri interi saranno stringhe del C da manipolare con
le due funzioni descritte.
Altra classe di problemi e' avere un buon generatore di numeri
casuali, un buon verificatore di numeri primi (probabilistico,
qualcuno ha postato il nome di un metodo che non ricordo)
e inoltre la chave p e s devono essere in quella relazione che
hai trovato sul Sedgewich e quindi devi anche implementare
l' algoritmo di Euclide per grandi numeri rappresentati con
stringhe.
Io farei cosi' (e lo faro' prima o poi)
Buon lavoro.
Roberto Cappellini.

 "parziali" cosi' ottenuti e AD OGNI MOLTIPLICAZIONE NE CALCOLI
Roberto Cappellini.

 supportata per gli int e' a 32 bit...
kronos:~$ gcc --version
egcs-2.91.66
questa supporta il tipo long long
ciao
Kronos
-- 
Home: 
http://kronoz.tsx.org
"I've seen things you people wouldn't believe...
 Attack Ships on fire off the shores of Orion.
 I've watched C-beams glitter in the dark off of Tanhauser Gate.
 All those moments will be lost in time...like tears, in rain.
 Time to die." -- Roy Batty (played by Rutger Hauer)

 tipo long long a 64 bit non e' supportato.....
  Su cosa basi un'affermazione cosi` perentoria?
	Alla prossima,
		Marco