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ą).
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)

0

Przecież liczby 1 i f(n) nie należą do (1;f(n)).

0

no nie naleza jesli te nawiasy oznaczaja zakres otwarty, ktory w przypadku liczb calkowitych nie wiem po co sie stosuje. Sam tez uzylelm tych nawiasow, majac na mysli oczywiscie zamkniety przedzial ;)

0

widze ze autor bazowal na tym artykule: RSA - szyfrowanie asymetryczne
Jak widac na przykladzie doboru klucza publicznego ten artykol zawiera bledy. Warto dodac ze powinno sie miec TYLKO jedna pare kluczow dla jednego modulo N, w przeciwnym razie istnieje algorytm, dzieki ktoremu mozna uzyskac ekwiwalentna postac klucza prywatnego,
tzn w postaci d mod phi(n) = d' mod phi(n)

0

A jak pozniej zakodowac jakies zdanie ?
np napisze: "Ala ma KOTA albo dwa"
i jak to zdanie pozniej zakodowac ?

0

do zakodowania potrzebujesz na pewno liczby M < N (gdzie N jest modulo). Zeby przedstawic tekst jako liczba jest pare sposobow. Mozesz przedstawic poszczegolne litery jako znaki ASCII w systemie dziesietnym minus 32 pierwszych znakow, ktorych nie bedziesz w tekscie uzywal. Znak tylda (~) ma numer 129-32 = 97. Teraz w zaleznosci jaki modulo uzywasz, mozesz sobie pogrupowac litery w paczki, zeby je razem zaszyfrowac. Jesli na przyklad masz modulo 3.885.444 to mozesz zgropowac tylko 3 znaki ~ : 979797, bo juz 4 przekrocza modulo: 97.979.797 .

Przyklad:
Dla ulatwienia zaszyfruje tekst: BACA uzywajac alfabetu ABC
A - 65-32 = 33
B - 66-32 = 34
C- 67-32 = 35

RSA:
Klucz publiczny:e = 1721,N = 263713
Klucz prywatny:d =1373, N = 263713

Tekst bedzie grupowany po 2 znaki:

BA(3433) CA(3533) = M1M2

szyfrowanie:
C1 = M1e mod N = 34331721 mod 263713 = 131184
C2 = M2e mod N = 35331721 mod 263713 = 176675

C1:C2

odszyfrowanie:
M1 = C1d mod N = 1311841373 mod 263713 = 3433
M2 = C2d mod N = 1766751373 mod 263713 = 3533

34333533=BACA

0

Czyli znaki o kodzie ascii co
Maja powyzej 100 odejmuje 32 czyli znaczy wszystkie znaki zmniejszam o 32 ale jak ktos wstawi znak wiekszy niz99 nawet po odjeciu 32 to juz nie moze byc uzyty no bylby blad w odkodowaniu tekstu dobrze mysle?

0

w tym przykladzie nie moze byc uzyty. Jako Alfabet wybralem znaki ascci od spacji do znaku tyldy 129-32=97. I kazdy znak pakuje jako liczbe dwucyfrowa. Jesli uzywaz inny alfabet, to musisz odbowiednio zmienic sposob kodowania, idea zostanie ta sama.
Mozesz tez brac jak leci ciagi np po 100 bajtow ( przy odpowiednim duzym N) i kodowac nie tylko znaki ascii ale tez utf i binarne dane.

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