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:

1. 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).
2. NastÄ?pnie obliczamy (poniewa?? wybrali??my wzglÄ?dnie pierwsze e, ma ono odwrotno??Ä? i obliczyÄ? jÄ? mo??emy szybko rozszerzonym algorytmem Euklidesa)
3. W kolejnym kroku obliczamy n kt??ra jest iloczynem p i q
4. Klucz publiczny to para (e,n), klucz prywatny za?? to para (d,n). Liczby p i q nale??y zniszczyÄ?.
5. Szyfrujemy wiadomo??Ä? M za pomocÄ?: c=m^e mod n (c- kryptogram, wiadomo??Ä? zaszyfrowana = wiadomo??Ä? m do potÄ?gi e modulo n)
6. ??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) )