Materiały dydaktyczne – Wybrane zagadnienia Matematyki Dyskretnej (Zestaw 6) Wybrane zagadnienia Matematyki Dyskretnej
Zestaw 6
1. W poniższej tablicy zaszyfrowany jest tekst za pomocą systemu RSA z kluczem publicznym (N, e) = (31313, 4913). Kodowanie tekstu do postaci liczbowej jest standardowe (litery alfabetu angielskiego są odpowiednikami cyfr przy podstawie 26).
6340
8309
14010
8936
27358
25023
16481
25809
23614
7135
24996
30590
27570
26486
30388
9395
27584
14999
4517
12146
29421
26439
1606
17881
25774
7647
23901
7372
25774
18436
12056
13547
7908
8635
2149
1908
22076
7372
8686
1304
4082
11803
5314
107
7359
22470
7372
22827
15698
30317
4685
14696
30388
8671
29956
15705
1417
26905
25809
28347
26277
7897
20240
21519
12437
1108
27106
18743
24144
10685
25234
30155
23005
8267
9917
7994
9694
2149
10042
27705
15930
29748
8635
23645
11738
24591
20240
27212
27486
9741
2149
29329
2149
5501
14015
30155
18154
22319
27705
20321
23254
13624
3249
5443
2149
16975
16087
14600
27705
19386
7325
26277
19554
23614
5553
4734
8091
23973
14015
107
3183
17347
25234
4595
21498
6360
19837
8463
6000
31280
29413
2066
369
23204
8425
7792
25973
4477
30989
2.
Przypuśćmy, że Bolek ma system kryptograficzny RSA z dużym modułem N , którego faktoryzacji nie można przeprowadzić w rozsądnym czasie. Załóżmy ponadto, że Alicja, wysyłając do Bolka komunikat, reprezentuje każdy znak alfabetu za pomocą liczby całkowitej od 0 do 25, po czym każdą resztę modulo 26 szyfruje jako odrębny znak tekstu jawnego.
(a) Opisz w jaki sposób Oskar, po przechwyceniu szyfrogramu, może łatwo odczytać tak zaszyfrowany komunikat.
(b) Zilustruj ten rodzaj ataku, deszyfrując następujący tekst zaszyfrowany (za pomocą systemu RSA z kluczem (N, e) = (18721, 25)) bez rozkładania modułu N na czynniki: 365, 0, 4845, 14930, 2608, 2608, 0.
3. Załóżmy, że Bolek dysponuje systemem kryptograficznym RSA z modułem N i wykładnikiem szyfrowania e1, natomiast Cezary używa tego samego systemu z wykładnikiem szyfrowania e2.
Załóżmy dodatkowo, że N W D(e1, e2) = 1. Rozpatrzmy sytuację, gdy Alicja przekazała szyfrem ten sam tekst jawny x do Bolka i Cezarego. Obliczyła y1 = xe1 (mod N ) oraz y2 = xe2 (mod N ), po czym wysyła y1 do Bolka oraz y2 do Cezarego. Oskar przejmuje oba teksty y1 i y2 i wykonuje obliczenia:
Dane wejściowe: N , e1, e2, y1, y2
(1) oblicz c1 = e−1 (mod e
1
2)
1
Materiały dydaktyczne – Wybrane zagadnienia Matematyki Dyskretnej (Zestaw 6) (2) oblicz c2 = (c1e1 − 1)/e2
(3) oblicz x1 = yc1 (yc2)−1 (mod N )
1
2
(a) Wykaż, że wartość x1 obliczona w trzecim kroku tego algorytmu jest w istocie tekstem jawnym Alicji, czyli x
(b) Zilustruj tak przeprowadzony atak, obliczając tą metodą x, gdy N = 18721, e1 = 43, e2 = 7717, y1 = 12677, y2 = 14702.
4. Napisz program do obliczania symbolu Jakobiego. Przetestuj na przykładach:
610 20964 1234567
,
,
.
987
1987
11111111
2