Implementacja algorytmu RSA w C++

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 d = e^{-1} \mod (p-1)(q-1) (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) )

2 myśli nt. „Implementacja algorytmu RSA w C++

  1. Halfdan

    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.

  2. mmx3 Autor wpisu

    no to by??o gcc pisane na uczelnianym serwerze gdzie poradzili sobie z instalacja Lidii, podobno nie jest to proste.

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *

Możesz użyć następujących tagów oraz atrybutów HTML-a: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>