Jak prawidłowo zbudować RSA ?

0

Mam przykład kodu dla algorytmu RSA
Jednak nie działa on na wszystkich liczbach pierwszych.
Czy to znaczy, że algorytm jest zły czy że powinny być jakieś dodatkowe warunki
tych liczb pierwszych. Dla przykładu dałem (p,q) 7213, 7219
oraz liczbe e = 7211
I przy obliczaniu klucza pokazuje się liczba -8837548 Jak to w ogole mozliwe ?

0
masterO napisał(a)

I przy obliczaniu klucza pokazuje się liczba -8837548 Jak to w ogole mozliwe ?

Jest możliwe, jeżeli mówisz o liczbie d, operując na liczbach ze znakiem łapiesz gdzieś integer overflow przy jej przeliczaniu. W każdym razie algorytm przeliczający d musi mieć jakieś błędy lub wady.

0

A te liczby 1 prime: C8A81678A224ADE8D68BA85E8BE6F69B
to co to a format HEX ? bo ja chyba robilem ta metoda potegowania i strasznie dlugo
sie to generuje

0

Do potęgowania modulo używa się małej modyfikacji algorytmu szybkiego potęgowania - nietrudno ją znaleźć, a zwłaszcza na stronach poświęconych RSA.

0

ze klucz wychodzi -8837548 to nie znaczy jeszcze ze jest przekroczenie zakresu, zle potegowanie itp. Autor nie pokazal sposobu jaki uzywa do obliczania klucza. Jakiego potegowania sie uzywa z reszta to obliczenia klucza d? Klucz to jest odwrotny element do e, czyli taki ze d*e mod Phi(n) = 1.
d = d + Phi(n) => -8837548 mod Phi(n) = (-8837548 + Phi(n)) mod Phi(n)

0
 #include<stdio.h>

int phi,M,n,e,d,C,FLAG;

int check() {
    int i;
    for(i=3; e%i==0 && phi%i==0; i+2) {
        FLAG = 1;
        return;
    }
    FLAG = 0;
}

void encrypt() {
    int i;
    C = 1;
    for(i=0; i< e; i++) C = C * M % n;
    C = C % n;
    printf("\n\tZakodowany tekst : %d",C);
}

void decrypt() {
    int i;
    M = 1;
    for(i=0;i< d;i++) M=M*C%n;
    M = M%n;
    printf("\n\tOdkodowany tekst : %d\n",M);
}

int main() {
    int p,q,s;

    printf("Wprowadz dwie liczby pierwsze\t: ");
    scanf("%d%d",&p,&q);
    n = p*q;
    phi=(p-1)*(q-1);
    printf("\n\tF(n)\t= %d",phi);
    do {
        printf("\n\nWprowadz e\t: ");
        scanf("%d",&e);
        check();
    } while(FLAG==1);
    d = 1;

    do {
        s = (d*e)%phi;
        d++;
    } while(s!=1);
    d = d-1;

    printf("\n\tKlucz publiczny\t: {%d,%d}",e,n);
    printf("\n\tKlucz prywatny\t: {%d,%d}",d,n);
    printf("\n\nWprowadz liczbe do zaszyfrowania\t: ");
    scanf("%d",&M);
    encrypt();
    printf("\n\nWprowadz zaszyfrowana liczbe\t: ");
    scanf("%d",&C);
    decrypt();

    return 0;
}
0
do {
                s = (d*e)%phi;
                d++;
        } while(s!=1);
        d = d-1;

wez napisz jakis ludzki algorytm do obliczania liczby odwrotnej i do sprawdzania czy wprowadzona prawidlowa liczbe e (tu wystarczy po prostu największy wspólny dzielnik). Nie uzywasz odpowiedniej liczby e to nie mozesz obliczyc tez d.
tego to w ogole nie rozumiem:
for(i=3; e%i==0 && phi%i==0; i+2) {
FLAG = 1;
return;
}

Troche bedzie trwalo obliczenie d, jak bedziesz mial baardzo duze liczby pierwsze. no i te d inkrementujesz okazuje ze wyniki jest rowny 1 i potem musisz d zdekrementowac, zeby sie zgadzalo. No i tu bardzo szybko o przekroczenie zakresu!!

0

No to żeby zrobić to porządnie to zacznę od początku.
Mniej więcej ma to wyglądać tak:

  1. Wybieramy dwie duże liczby pierwsze p i q - np. o długości 1024 bitów
    Do tego zadania należy użyć jakiegoś sprawdzonego sposobu generatora liczb pierwszych.
    To czego najlepiej użyć ?

  2. Obliczana jest liczba n będąca iloczynem p i q. n=p*q
    A jeśli liczby są większe niż int ? to jak to użyć ?

  3. klucz publiczny e wybieramy ze zbioru [max(p,q)+1, n-1] będący względnie pierwszą liczbą z funkcją Eulera dla n => f(n)=(p-1)(q-1)
    f(n)=(p-1)
    (q-1)= liczba
    e = liczba pierwsza z maksymalnego zbioru (liczba) ? dobrze myśle ?

  4. klucz prywatny d obliczamy z równania d=inv(e,f(n)), czyli jako odwrotność e modulo f(n), tj. (ed) mod (p-1)(q-1)=1

  5. Szyfrowanie: C=M^e mod n

  6. Deszyfrowanie M=C^d mod n

0

1) nie znam generatora liczb pierwszych, ale sa metody ktore pozwalaja sprawdzic czy dana liczba jest liczba pierwsza (test Millera-Rabina albo Pocklingtona)
2) niech ktos sie wypowie kto programuje w c, co tu najlepiej uzyc
3) tu sie w ogole nie zgodze. Skad masz takie informacje? e wybera sie ze zbioru (2, phi(n)-1), takie ze NWD(e,phi(n)) = 1. W praktyce stosuje sie e = 3 albo e = 65537 (czwarta liczba fermata, chodzi o to ze szybko mozna wykonac potegowanie. 65537 to w systemie binarnym 10000000000000001)
4) tak
5) tak
6) tak

0
  1. http://en.wikipedia.org/wiki/Generating_primes#Large_primes
  2. Dowolne biblioteki do obsługi dużych liczb, np. GMP (mogą być problemy z instalacją pod Windows), TTMath, NTL itd.
  3. Może być dowolną liczbą z zakresu ( 1, f(n) ), która jest względnie pierwsza z f(n) - czyli na przykład dowolna liczba pierwsza z tego wzoru.
  4. Tak, patrz na rozszerzony algorytm Euklidesa.
    5,6. Tak. W tym celu korzysta się z szybkich algorytmów potęgowania modulo (w większości bibliotek dużych liczb takie funkcje istnieją).

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0