[ Nedeljko @ 22.03.2010. 00:17 ] @
Da priložim i ja nešto

RSA - kriptografija javnim ključem

Neka je skup prirodnih brojeva i skup prirodnih brojeva sa nulom. Za par prirodnih brojeva se kaže da su uzajamno prosti ako ne postoji prirodan broj veći od 1 koji deli svaki od njih. Ojlerova funkcija je funkcija koja svakom prirodnom broju pridružuje broj prirodnih brojeva ne većih od njega, a koji su uzajamno prosti sa njim. Primera radi, od brojeva 1,...,9, sa 9 su uzajamno prosti 1,2,4,5,7 i 8. Dakle, ima ih 6, pa je . Za ovu funkciju dokayuje se da za ma koje uzajamno proste brojeve i važi (ova osobina se zove multiplikativnost), kao i da je za ma koji prost broj i prirodan broj , odakle je u opštem slučaju

,

pri čemu se proizvod izmima po svim prostim deliteljima broja uzimajući svaki prost delitelj po jedanput.

RSA algoritam je zasnovan na Ojlerovoj teoremi, koja kaže da je za ma koje uzajamno proste prirodne brojeve i broj deljiv sa . Stoga brojevi daju isti ostatak pri delenju sa .

U našem slučaju će biti proizvod različitih prostih brojeva i , odakle će biti . Ukoliko su i prirodni brojevi za koje je deljivo sa , onda će za ma koji prirodan broj manji od i uzajamno prost sa njim ostatak pri delenju broja sa biti jednak .

Par je jedan deo ključa, koji zovemo tajnim, a par je drugi deo kluča, koji zovemo javnim. Poruka je bilo koji prirodan broj . Svaki niz bitova možemo shvatiti kao prirodan broj čiji je to binarni zapis. Ako ima 2049 bitova, i veći je od , onda poruci maksimalne dužine 2048 bita shvaćenoj kao prirodan broj, možemo dodati 2 i dobiti broj za šifriranje. Duža poruka se u tom slučaju može podeliti na blokove od po 2048 bita, nakon čega se šifrira svaki blok ponaosob.

Broj šifriramo tako što izračunavamo ostatak od pri delenju sa . Rezultat dešifrujemo tako što izračunamo ostatak pri delenju po modulu . Ukoliko je broj uzajamno prost sa , rezultat će biti , pa umanjivanjem za 2 dobijamo originalnu poruku. To smo i očekivali, jer kada se šifrovana poruka dešifruje, treba da se dobije originalna poruka. To će se svakako desiti ako je bilo uzajamno prosto sa . Ojlerova funkcija nam kaže da među mogućih poruka problem može nastati sa njih , odnosno da je verovatnoća za to oko za velike proste brojeve i , što je rizik koji se može zanemariti.

Sada prelazimo na detaljnije objašnjenje svih koraka. Da bi implementacija bila brza, treba koristiti algoritam množenja zasnovan na brzoj Furijeovoj transformaciji (FFT) i ovde neće biti izložen, jer je tekst i bez toga preopterećen matematikom.


1. Stepenovanje

Stepenovanje realizovano po definiciji, uzastopnim množenjem, je neprihvatljivo sporo. Stoga se za izračunavanje po zadatom modulu može realizovati sledećom rekurentnom funkcijom:

Code:
int power(int a, int b, int n) {
    if (b == 0)
        return 1;
    
    int ret = pow(a, b >> 1, n);
    
    if (b & 1)
        ret *= a;
    
    return ret % n;
}


2. Generisanje prostih brojeva

Da bismo dobili ključeve širine 4096 bita, trebaju nam dva prosta broja sa po 1024 binarne cifre. Oni se tipično generišu tako što se generišu nasumični brojevi željene širine, a potom testira da li su prosti. Nažalost, vrlo je teško utvrditi da je neki broj sigurno prost, pa se koriste razni testovi pseudoprimalnosti, među koje spada Miler-Rabinov test. Ako neki broj prođe taj test, on je najverovatnije prost (jako je mala verovatnoća da je složen), a ako ga ne prođe, sigurno je složen. Algoritam sledi.

Code:
bool is_pseudoprime(int p, int b) {
    int d = p - 1;
    int s = 0;
    
    while (d & 1 == 0) {
        d >>= 1;
        s = s + 1;
    }
    
    int a = power(b, d, p - 1);
    
    if (a == 1 || a == -1)
        return true;
    
    for (int i = 1; i < s; i = i + 1) {
        a = a * a % (p - 1);
        
        if (a == -1)
            return true;
    }
    
    return false;
}

int pseudoprime(int max) {
    int p;
    
    while (true) {
        p = rand() % max;
        
        if (p < 2)
            continue;

        if (is_pseudoprime(p, 2) == false)
            continue;
        
        if (is_pseudoprime(p, 3) == false)
            continue;
        
        if (is_pseudoprime(p, 5) == false)
            continue;
        
        if (is_pseudoprime(p, 7) == false)
            continue;
        
        if (is_pseudoprime(p, 11) == false)
            continue;
        
        break;
    }
    
    return p;
}


Funkcija za testiranje pseudoprimalnosti zahteva osnovu kao argument. Ovde je primalnost testirana za pet prostih osnova. Funkcija za generisanje pseudoprostog broja generiše broj u opsegu .

3. Generisanje brojeva e i d

Jedan od ovih brojeva se moze izabrati nasumicno, na primer e, a drugi generisati sledecim algoritmom:

Code:
bool extednded_euclid(int m, int n, int &u, int &v) {
    if (m < 0 || n < 0) {
        if (extended_euclid(abs(m), abs(n), u, v) == false)
            return false;
        
        if (m < 0)
            u = -u;
        
        if (n < 0)
            v = -v;
        
        return true;
    }
    
    if (m < n)
        return extednded_euclid(n, m, v, u);
    
    if (n == 0)
        return false;
    
    int q = m / n;
    int r = m - q * n;
    int t;
    
    if (extednded_euclid(n, r, t, u) == false)
        return false;
    
    v = t - q * u;
    
    return true;
}

void generate_keys(int max, int &n, int &e, int &d) {
    while (true) {
        int p = pseudoprime(max);
        int q = pseudoprime(max);
        
        if (p == q)
            continue;
        
        n = p * q;
        
        int fi_n = (p-1)*(q-1);
        
        while(true) {
            int e = rand() % fi_n;
            int d, t;
            
            if (extednded_euclid(fi_n, e, t, d) == false)
                continue;
            
            d = d % fi_n;
            
            if (d < 0)
                d += fi_n;
            
            break;
        }
        
        break;
    }
}


4. Funkcije za enkripciju i dekripciju

Code:

int encrypt(int message, int n, int e) {
    return power(message + 2, e, n);
}

int decrypt(int message, int n, int d) {
    return power(message, d, n) - 2;
}


Zasad toliko.

[Ovu poruku je menjao Mihajlo Cvetanović dana 16.03.2011. u 16:26 GMT+1]
[ Nedeljko @ 24.03.2010. 12:39 ] @
U funkciji extended_euclid se potkrala greška. Umesto

Code:

    if (n == 0) 
        return false;


treba

Code:

    if (n == 0) {
        if (m > 1)
            return false;

        u = 1;
        v = 0;

        return true;
    }


Takođe, ostao sam dužan funkciju za delenje sa ostatkom. Ona se najefikasnije realizuje na sledeći način: Najpre realizovati realno delenje. To se ostvaruje množenjem brojioca recipročnom vrednošću imenioca, koja se izračunava Njutnovim metodom tangente

za . Recimo, ako je za neki ceo broj i , onda je dovoljno uzeti .

Kada izračunamo realan količnik brojeva i , onda možemo izračunati ostatak po formuli . E, sad, prilikom računanja realnog količnika javlja se greška koja se ispoljava u ostatku. Nakon izračunavanja ostatka po navedenoj formuli se lako koriguju količnik i ostatak.
[ Nedeljko @ 30.05.2010. 23:57 ] @
E, da, i u funkciji za stepenovanje se potkrala greška. Treba da glasi ovako

Code:
int power(int a, int b, int n) {
    if (b == 0)
        return 1;
    
    int ret = pow(a, b >> 1, n);

    ret *= ret;    

    if (b & 1)
        ret *= a;
    
    return ret % n;
}


Naravno, sve algoritme treba realizovati sa bigint tipom umesto sa int.
[ Nedeljko @ 16.03.2011. 13:09 ] @
Evo poboljšanja funkcije is_pseudoprime():

Code:
bool is_pseudoprime(int p, int b) {
    int d = p - 1;
    int s = 0;
    
    while (d & 1 == 0) {
        d >>= 1;
        s = s + 1;
    }
    
    int a = power(b, d, p - 1);
    
    if (a == 1 || a == -1)
        return true;
    
    for (int i = 1; i < s; i = i + 1) {
        a = a * a % (p - 1);
        
        if (a == -1)
            return true;
        else if (a == 1)
            return false;
    }
    
    return false;
}


Osim toga, prosti brojevi i treba da budu izabrani tako da odnos broja njihovih cifara (ne računajući vodeće nule) bude između 0,35 i 0,45, jer ako su približni, postoji poznat napad faktorizacijom metodom pretraživanja u okolini broja .
[ Nedeljko @ 16.03.2011. 13:17 ] @
Što se brojeva i tiče, javni deo se može izabrati na standardan način kao neki mali prost broj (recimo 3 ili 65537) radi efikasnosti stepenovanja u jednom smeru, a drugi se onda određuje opisanim proširenim euklidovim algoritmom.
[ Mihajlo Cvetanović @ 16.03.2011. 15:19 ] @
Na Nedeljkov zahtev premeštene poruke u novu temu.
[ Nedeljko @ 11.04.2011. 13:56 ] @
Postoje još neke važne stvari vezane za RSA. Naime, u našoj simbolici je proizvod različitih velikih prostih brojeva i . Obzirom da su oni neparni, brojevi i su složeni kao parni. Ako neki od njih ima samo male proste faktore, onda se faktorizacija broja može efikasno obaviti Polardovim algoritmom. Stoga je potrebno prilikom generisanja prostih brojeva obezbediti da njima susedni parni brojevi imaju po bar jedan veliki prost faktor.

Recimo da su i veliki prosti brojevi za koje želimo da generišemo prost broj takav da i . Ako želimo da ima bitova, onda biramo i tako da imaju ne više od bitova.

Obzirom da su brojevi parni, važi i , pa postoje prirodni brojevi i takvi da je i . Oduzimanjem ovih jednačina zaključujemo da je , odnosno . Dakle, za ma koji ceo broj broj ispunjava uslove i , pa ako je još prost i ima željeni broj bitova, rešili smo problem.

Postupak bi išao na sledeći način:

1. Generisati nasumične proste brojeve i sa manje od bitova.
2. Proširenim Euklidsovim algoritmom izračunati i takve da je .
3. Izabrati nasumično prirodan broj takav da broj ima bitova.
4. Ispitati da li je broj prost. Ako jeste, onda je kraj, a u suprotnom se vrati na korak 3, a u slučaju većeg broja neuspeha na korak 1.
[ Nedeljko @ 01.06.2011. 08:49 ] @
Sve ovo možete da zaboravite jer je počela proizvodnja komercijalnih kvantnih računara. RSA i svi ostali kriptografski algoritmi zasnovani na težini faktorizacije celih brojeva i računanju diskretnog logaritma su ranjivi pred kvantnim računarima. Nadalje će morati da se koriste algoritmi post kvantne kriptografije.