Kompilator gcc, kompilacja: make w katalogu build uruchamianie programu jak w podanych niżej zadaniach (pomoc - podana też na końcu tego pliku: ./main --help) ######## Zadanie 1 Klucz publiczny: (N=31313 e=4913) 1. Utworzenie pliku z liczbami pierwszymi do maksymalnej wartości równej co najmniej N/2. Poniższa komenda tworzy plik 'primes_2_15700.txt' w aktualnym katalogu roboczym $ ./main --gen_primes 2 15700 2. Kryptoanaliza, na wejście podawany jest: $ ./main --rsa_crypto --primes primes_2_15700.txt --cipher cipher_zad1.txt --result result.txt --n 31313 --e 4913 Opis argumentów: --primes primes_2_15700.txt Plik z liczbami pierwszymi utworzonymi w 1 kroku --cipher cipher_zad1.txt Plik z liczbami wiadomości zaszyfrowanej --result result.txt Plik docelowy rezultatów --n 31313 --e 4913 Parametry klucza publicznego Dany klucz publiczny: (N=31313 e=4913) Otrzymane wartości p, q, fi(n), d: * (p,q)=(173,181), * fi(n) = (p-1)*(q-1) = 30960 * d = e^(-1) mod fi(n) = 6497 Do deszyfrowania został użyty wzór m = c^d (mod N) gdzie c jest liczbą zaszyfrowaną, m jest liczbą odszyfrowaną, następnie m zostały zamienione na liczbę o podstawie 26 i stąd na fragment tekstu jawnego Wiadomość odszyfrowana (spacje dodane ręcznie, |A| - litera A dodana ręcznie) Tekst zawiera błędy LAKEWOBEGON IS MOSTLY POORS |A|ND Y SOIL AND EVERY SPRING THE EARTH HEAVES UP A NEW CROP OF ROCKS PILES OF ROCKS TEN FEET HIGH IN THE CORNERS OF FIELDS PICKED BY GENERATIONS OF US MONUMENTS TO OUR INDUSTRY OUR |A|NCESTORS CHOSE THE PLACE TIRED FROM THEIR LONG JOURNEYS D FOR H|A|VING LEFT THE MOTHER LAND BEHIND AND THIS PLACE REMINDED THEM OF THERE SO THEY SETTLED HERE FORGETTING THAT THEY HAD LEFT THERE BECAUSE THE L|A|ND BSKYNT SO GOOD SO THE NEW LIFE TURNED OUT TO BE LOT LIKE THE OLD EXCEPT THE WINTERS |A|RE WORSE SEZ ######## Zadanie 2 a) Łatwo można sprawdzić wszystkie możliwe kombinacje: for (i = 0 ; i < cipher.length; i++) { if (cipher[i] == 0) puts('A'); else { for (m = 0; m < 26; m++) { if (modular_pow(m, e, N) == cipher[i]) { puts('A' + m); break; } } } } $ ./main --singleblock --cipher cipher_zad2.txt --result result_zad2.txt --n 18721 --e 25 Opis argumentów: --cipher cipher_zad2.txt Plik z liczbami wiadomości zaszyfrowanej, alfabetem i liczbą bloków (szczegóły ./main --help) --result result_zad2.txt Plik docelowy rezultatów --n 18721 --e 25 Parametry klucza publicznego ### Zadanie 3 Dowód w pliku Zadanie3a.pdf b) Obliczenie wartości x dla N = 18721, e1 = 43, e2 = 7717, y1 = 12677, y2 = 14702 $ ./main --rsa_crypto2 --n 18721 --e 43 7717 --y 12677 14702 x = 15001 ######## Zadanie 4 $ ./main --jacobi --a 610 --b 987 Jacobi(a=610, b=987) returned value: -1 $ ./main --jacobi --a 20964 --b 1987 Jacobi(a=20964, b=1987) returned value: 1 $ ./main --jacobi --a 1234567 --b 11111111 Jacobi(a=1234567, b=11111111) returned value: -1 ######## $ ./main --help Użycie: [1] ./main --gen_primes [min_number] max_number [2] ./main --rsa_crypto --primes pfile --cipher cfile --result rfile --n N --e E [3] ./main --singleblock --cipher cfile --result rfile --n N --e E [4] ./main --rsa_crypto2 --n N --e e1 e2 --y y1 y2 [5] ./main --jacobi --a a --b b [1] Generowanie liczb pierwszych (do pliku primes_{min_number}_{max_number}.txt) min_number Minimalna liczba pierwsza zapisywana do pliku (domyślnie 2) max_number Maksymalna liczba pierwsza zapisywana do pliku [2] Kryptoanaliza RSA pfile Plik z liczbami pierwszymi (jedna na linie, linia komentarza od '#') cfile Plik z liczbami wiadomości zaszyfrowanej (pierwsza linia liczba liczb, kolejne - liczby) rfile Plik z rezultatami - tworzony przez program N Parametr N z klucza publicznego E Parametr E z klucza publicznego [3] Kryptoanaliza RSA (jeden znak szyfrowany w jednym bloku) cfile Plik z liczbami wiadomości zaszyfrowanej: # 1. Alfabet ( oraz ALPHA= - wymagane) ALPHA="ABCDEFGHIJKLMNOPQRSTUVWXYZ" # 2. Długość tekstu zaszyfrowanego (BLOCKS= - wymagane) BLOCKS=3 # Bloki (jeden w linii) 3499 123 9 rfile Plik z rezultatami - tworzony przez program N Parametr N z klucza publicznego E Parametr E z klucza publicznego [4] Kryptoanaliza RSA - szyfrowanie jednego znaku (x) dwoma kluczami y1 = x^e1 (mod N) ; y2 = x^e2 (mod N) ; gcd(e1, e2) = 1 Znajduje wartość jawną x na podstawie dwóch wartości zaszyfrowanych odpowiadających x i dwóm kluczom publicznym: (N, e1), (N, e2), gdzie e1 i e2 są względnie pierwsze [5] Obliczanie symbolu Jacobiego ( a nad n ) a licznik b mianownik