[es] - Teorijske osnove RSA algoritma

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8704
212.200.65.*

+2801 Profil

^{22.03.2010. u 00:17 - pre 184 meseci}

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

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

broj

deljiv sa

. Stoga brojevi

daju isti ostatak pri delenju sa

.

U našem slučaju će biti

proizvod različitih prostih brojeva

, odakle će biti

. Ukoliko su

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

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

, š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]}

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8704
89.216.32.*

+2801 Profil

Re: Teorijske osnove RSA algoritma

^{11.04.2011. u 13:56 - pre 171 meseci}

Postoje još neke važne stvari vezane za RSA. Naime, u našoj simbolici je

proizvod različitih velikih prostih brojeva

. Obzirom da su oni neparni, brojevi

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

veliki prosti brojevi za koje želimo da generišemo prost broj

takav da