Jak prawidłowo zbudować RSA ?

Odpowiedz Nowy wątek
2011-08-01 00:57
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 ?

polecam http://www.woodmann.com/collaborative/tools/index.php/RSA-Tool_2 do zabawy z RSA, szybko zweryfikujesz swoje wyniki - Bartosz Wójcik 2011-08-01 01:47
ewidentne przekroczenie zakresu typu. Stawiam na to, że stosujesz typ prosty int (1 błąd bo do RSA należy stosować dużo większe liczby). 2 twój błąd to to, że na pewno stosujesz naiwną postać algorytmu i prawdopodobnie wykonujesz potęgowanie. Przy obliczaniach trzeba skorzystać z właściwości operacji modulo w ten sposób obliczne wartości pośrednie nigdy nie przekroczą n. - MarekR22 2011-08-01 09:21

Pozostało 580 znaków

2011-08-01 01:14
signed
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.

Pozostało 580 znaków

2011-08-01 09:45
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

edytowany 1x, ostatnio: masterO, 2011-08-01 09:57

Pozostało 580 znaków

2011-08-01 10:00
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.


Not Found
The requested URL /wypasiona_sygnaturka.txt was not found in this brain.
-----
Human/1.0.00 (Earth) Server at Poland Port 65535

Pozostało 580 znaków

2011-08-01 11:51
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)

edytowany 1x, ostatnio: mwili, 2011-08-01 11:52

Pozostało 580 znaków

2011-08-01 12:07
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;
}
edytowany 2x, ostatnio: masterO, 2011-08-01 12:08

Pozostało 580 znaków

2011-08-01 12:30
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!!

edytowany 6x, ostatnio: mwili, 2011-08-01 13:20

Pozostało 580 znaków

2011-08-01 13:24
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

Pozostało 580 znaków

2011-08-01 13:51
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

edytowany 2x, ostatnio: mwili, 2011-08-01 14:05

Pozostało 580 znaków

2011-08-01 13:58
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ą).

Not Found
The requested URL /wypasiona_sygnaturka.txt was not found in this brain.
-----
Human/1.0.00 (Earth) Server at Poland Port 65535

Pozostało 580 znaków

2011-08-01 14:03
0

do punktu 3)
e=1 nie moze byc, bo wtedy d = 1
e=f(n) tez NIE moze byc, bo NWD(e, f(n))=f(n)

No niby podałem zakres otwarty, ale dla spokoju niech będzie <2, f(n)-1> :D - mnbvcX 2011-08-01 14:11

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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