Andmeturbe 2. KT (0)

Ül1.1
Arvuta (võimalikult lihtsalt) 7^162 mod 205
205=5*41
Phi(205)=4*40=160 // Euler
7^162=7*(5*41+2)=7*(5*41)7^2=7^2=49 // Fermat
Ül1.2
Arvuta (võimalikult lihtsalt) 7^398 mod 451.
451=11*41
Phi(451)=10*40=400 //Euler
7^(400­2)=7^(­2)=49^­1 mod 451 //Fermat
49
451
a
b
49
10
a
b­9a
9
10
37 a­4 b
b­9a
9
1
37 a­4 b
5 b­46 a
// Eukleides  // d =1/49 mod 451= 451­46 mod 451 = 405 mod 451
Ül2.1
RSA krüptosüsteemis kasutatakse algarvudena p = 101 ja q = 37.
Avalik  astendaja  e = 17. Leia salajane astendaja d.
Kas  samade  algarvude korral oleks e = 5 sobilik avalik astendaja? Põhjenda!
Phi(101 * 37) =  3600  = n
17
3600
a
b
17
13
a
b­211a
4
13
212a­b
b­211a
4
1
212a­b
4 b­847 a
d =1/17 mod 3600 = 3600­847 mod 3600 = 2753  mod 3600 .
gcd(5,3600) = 5 != 1 ja seega 5 ei ole pööratav mooduli phi(n) järgi
Ül2.2
RSA krüptosüsteemis kasutatakse algarvudena p = 113 ja q = 47.
Avalik astendaja e = 19. Leia salajane astendaja d.
Kas samade algarvude korral oleks e = 23 sobilik avalik astendaja? Põhjenda!
Phi(113 * 47) = 5152 = n
19
5152
a
b
19
3
a
b­271a
1
3
1627 a­6 b
b­271a
d =1/19 mod 5152 = 1627 mod 5152 .
gcd(23,5152) = 23 != 1 ja seega 23 ei ole pööratav mooduli phi(n) järgi
Ül3.1
Süsteemis on kolm kasutajat: A, B ja C.
Kõigil neil on RSA salajased võtmed,  kusjuures  vastavad avalikud võtmed (st moodulid) on
nA = 451, nB = 391 ja nC = 145. Avalik astendaja on kõigil ühine: e = 3.
Ründajale on teada, et kõigile kolmele kasutajale  saadetakse  üks ja sama salasõnum x ∈ {0, . .
.144}, kusjuures vastavad krüptogrammidon:
yA = x^3 mod 451 = 133
yB = x^3 mod 391 = 213
yC = x^3 mod 145 = 80
Kuidas saab ründaja leida sõnumi x? Leia x ja põhjenda vastust!
x^3 ≡ 80 (mod 145) järeldub:
x^3 mod 5 = 0
x^3 mod 29 = 22
3
28
a
b
3
1
a
b­9a
1/3 mod 28=­9 mod 28 = 19 mod 28
x ≡ 22^19 (mod 28)
22^19 ≡ 22^(2^4) * 22^(2^1) * 22^(2^0)
Mod[22^2^{0, 1, 2, 3, 4}, 29] = {22,20,23,7,20}
22^19 ≡20 *20 * 22 mod 29 = 13
Süsteem
x mod 5 = 0
x mod 29 = 13
//Hi na jäägiteoreem
6 * 5 ­ 1 * 29 = 1
x = 6*5*13 +(­1)*29*0 mod (29*5)= 390 mod 145=100 mod 145
Lahendid  on 100+145v, kus v on Z arv.
Vahemikus [0...144] on 1 sel ine arv, see on 100.
Ül3.2
Süsteemis on kolm kasutajat: A, B ja C.
Kõigil neil on RSA salajased võtmed, kusjuures vastavad avalikud võtmed (st moodulid) on
nA = 205, nB = 391 ja nC = 319. Avalik astendaja on kõigil ühine: e = 19.
Ründajale on teada, et kõigile kolmele kasutajale saadetakse üks ja sama salasõnum x ∈ {0, . .
.204}, kusjuures vastavad krüptogrammidon:
yA = x^3 mod 205 = 10
yB = x^3 mod 391 = 213
yC =x^3 mod 319 = 254
Kuidas saab ründaja leida sõnumi x? Leia x ja põhjenda vastust!
x^3 ≡ 10 (mod 205) järeldub:
x^3 mod 5 = 0
x^3 mod 41 = 10
3
40
a
b
3
1
a
b­13a
1/3 mod 40 = ­13 mod 40 = 27.
10^27 ≡ 10^2^4+ 10^2^3+ 10^2^1+ 10^2^0
Mod[10^2^{0, 1, 2, 3, 4}, 
Süsteem
x mod 5 = 0
x mod 41 = 18
//Hi na jäägiteoreem
­8 * 5 + 1 * 41 = 1
x = ­8 * 5 * 18 + 1 * 41 * 0 mod 41 * 5 = ­720 mod 205 = 100 mod 205
Lahendid on 100+205v, kus v on Z arv.
Vahemikus [0...205] on 1 sel ine arv, see on 100.