Matematyka dyskretna 2/Ćwiczenia 7: Zastosowanie teorii liczb w kryptografii

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Zastosowania teorii liczb w kryptografii

Ćwiczenie 1

Przechwyciłeś zakodowaną wiadomość i pragniesz poznać jej treść. Oto kod wiadomości:


24,28,17,39,14,42,24,18,10,40,38,15,10,26,27,42,40,18,10,46,17,20,
14,26,18,10,45,28,17,15,14,46,12,14,26,37,18,10,14,28,14,43,23,45,
17,36,42,31,40,6,18,15,10,26,14,12,24,28,17,14,6,10,14,46,6,10,14,
46,6,18,10,14,31,6,12,29,10,29,14,13,45,12,37,18,14,45,42,45,17,27,
45,12,28,34,38,24,28,14,29,38,40,38,20,0,39,38,4,14,46,28,18,6,37,
17,14,46,12,14,28,18,10,26,18,14,26,37,18,10,14,34,45,28,17,13,18,15,0.


Wiadomo, że użyto kryptosystemu afinicznego o następujących parametrach:

  • symbole alfabetu, tak jak i numeracja jest taka sama jak w tabeli z przykładu rozważanego podczas wykładu,
  • jednostka wiadomości składa się z jednego symbolu; zbiór jednostek wiadomości to , (w porównaniu z wykładem dodana została jedna wartość - - oznaczająca "," (przecinek) także po to aby moc zbioru jednostek wiadomości była liczbą pierwszą),
  • funkcja kodująca jest postaci


{ mod}


gdzie są nieznanymi Ci kluczami.

Złam te klucze i poznaj treść wiadomości!

Wskazówka
Rozwiązanie

Ćwiczenie 2

Otrzymałeś wiadomość w kryptosystemie RSA następującej postaci:



Wiadomość jest zakodowana przy nastepujących założeniach:

  • symbole alfabetu, tak jak i numeracja jest taka sama jak w tabeli z przykładu omawianego podczas wykładu,
  • jednostka wiadomości składa się z dwu symboli, odpowiedniość między jednostkami wiadomości, a kolejnymi liczbami jest taka sama jak we wspomnianym przykładzie, zbiór jednostek wiadomości to ( jest iloczynem dwu liczb pierwszych), przy czym wartości większe od nie są wykorzystywane,
  • klucz kodujący to .

Odczytaj otrzymaną wiadomość.

Wskazówka
Rozwiązanie

Ćwiczenie 3

Pokaż, że dla liczby pierwszej oraz , liczba jest pseudopierwsza przy podstawie wtedy i tylko wtedy, gdy .

Wskazówka
Rozwiązanie

Ćwiczenie 4

Pokaż, że dla dowolnej ustalonej liczby pierwszej jest skończenie wiele liczb Carmichaela postaci , gdzie są liczbami pierwszymi. Przy pomocy wypracowanej metody:

  • wypisz wszystkie liczby Carmichaela postaci i ,
  • udowodnij, że jest najmniejszą liczbą Carmichaela.
Wskazówka
Rozwiązanie

Ćwiczenie 5

Pokaż, że jeśli jest silnie pseudopierwsza przy podstawie , to jest też silnie pseudopierwsza przy podstawie dla dowolnego .

Wskazówka
Rozwiązanie

Ćwiczenie 6

Rozłóż na czynniki pierwsze liczbę:

251959084756578934940271832400483985714292821262040320277771
378360436620207075955562640185258807844069182906412495150821
892985591491761845028084891200728449926873928072877767359714
183472702618963750149718246911650776133798590957000973304597
488084284017974291006424586918171951187461215151726546322822
168699875491824224336372590851418654620435767984233871847744
479207399342365848238242811981638150106748104516603773060562
016196762561338441436038339044149526344321901146575444541784
240209246165157233507787077498171257724679629263863563732899
121548314381678998850404453640235273819513786365643912120103
97122822120720357

Wskazówka