Witam,
Dzisiaj chcia??bym przedstawiÄ? wam implementacje algorytmu RSA( Ronald Rivest, Adi Shamir, Leonard Adleman). WykorzystujÄ?c potÄ???nÄ? bibliotekÄ? LiDIA (strona domowa biblioteki: http://www.cdc.informatik.tu-darmstadt.de/TI/LiDIA/)
Najpierw przedstawie algorytm:
- Losujemy dwie du??e(ok 1024 bity tj. Liczba sk??adajÄ?ca siÄ? z 300 cyfr) liczby pierwsze p i q, oraz liczbÄ? e = (p â?? 1)(q â?? 1).
- NastÄ?pnie obliczamy
(poniewa?? wybrali??my wzglÄ?dnie pierwsze e, ma ono odwrotno??Ä? i obliczyÄ? jÄ? mo??emy szybko rozszerzonym algorytmem Euklidesa)
- W kolejnym kroku obliczamy n kt??ra jest iloczynem p i q
- Klucz publiczny to para (e,n), klucz prywatny za?? to para (d,n). Liczby p i q nale??y zniszczyÄ?.
- Szyfrujemy wiadomo??Ä? M za pomocÄ?: c=m^e mod n (c- kryptogram, wiadomo??Ä? zaszyfrowana = wiadomo??Ä? m do potÄ?gi e modulo n)
- ??eby M zdeszyfrowaÄ? podnosimy zaszyfrowanÄ? wiadomo??Ä? do potÄ?gi d. Zgodnie z twierdzeniem Eulera dostaniemy oryginalnÄ? wiadomo??Ä? (o ile m nie jest wielokrotno??ciÄ? p lub q): c^d = m^(ed) = m mod n
Implementacja:
#include <LiDIA/bigint.h> #include <iostream>using namespace std; using namespace LiDIA; bigint get_liczba() { bigint rand_liczba; bigint max = 1; shift_left(max, max, 1024); // powiÄ?kszamy liczbÄ? do 1024 bajt??w wielko??ci do { rand_liczba.randomize(max); }while(!is_prime(rand_liczba)); return rand_liczba; } int main(){ bigint p, q; // losowanie p i q do{ p = get_liczba(); q = get_liczba(); } while(p==q); //licznie n bigint n; n = p * q; bigint fi; fi = (p-1)*(q-1); bigint u,v,e; do { e.randomize(fi); e++; }while(xgcd(u,v,e,fi)!=1); bigint m,c,de; m=50000; // nasza wiadomo??Ä? cout<<"message: "<<m<<endl; if (u<0){ u=u%fi; } power_mod(c,m,e,n); cout<<"zaszyfrowane = "<<c<<endl<<endl; power_mod(de,c,u,n); cout<<"odszyfrowane = "<<de<<endl<<endl; }
Kompilacja:
g++ -O test.cc -I/usr/local/include -L/usr/local/lib -o test -lLiDIA -lgmp -lm
Opis Funkcji:
- bigint xgcd(bigint & u, bigint & v, const bigint & a, const bigint & b) – funkcja oblicza (a, b) = au + vb)
- void power_mod (bigint & res, const bigint & a, const bigint & n, const bigint m, int err = 0) – funkcja oblicza res = a^n (mod m)
- void div_rem (bigint & q, bigint & r, const bigint & a, const bigint & b) – funkcja oblicza: q i r takie, ??e a = qb + r
- bool is_prime (const bigint & a, int n = 10) – funkcja zwraca warto??Ä? true je??li a jest liczbÄ? pierwszÄ?(Prawdopodobie??stwo tego, ??e a jest liczbÄ? pierwszÄ? jest nie mniejsze ni?? 1 – 1/(4^n) )
LiczbÄ? e obliczamy, a nie losujemy,(ale wiadomo, o co chodzi). Nie uda??o mi siÄ? biblioteki Lidia wsadziÄ? do Borland C Buildera:(
A szkoda, bo potrzebna mi by??a obs??uga du??ych int??w. W??a??nie do RSA i ElGamala. W ko??cu przesiad??em siÄ? na javÄ?. Ale gdyby??, kolego, wiedzia?? jak ruszyÄ? LidiÄ? (?!) pod BC B to pewnie wr??cÄ? do c . Ale, jak tu czytam, Ty g????wnie piszesz na potrzeby Internetu, wiÄ?c pewnie nie wiesz…
P.S. Fajny kod. Czysty i kr??tki i elegancki.
no to by??o gcc pisane na uczelnianym serwerze gdzie poradzili sobie z instalacja Lidii, podobno nie jest to proste.