MB104 řešené příklady (RSA) Jaro 2020
Jak postupovat v příkladu s RSA?
Pan A posílá zprávu panu B, aby to ovšem mohl udělat, musel pan B něco udělat předem.
1. Pan B si vzal dvě prvočísla p, q a vynásobil je, n = pq.
2. Pan B dále spočítal ϕ(n) a to snadno, protoze zná prvočíselný rozklad čísla n, takže
ϕ(n) = (p − 1)(q − 1).
3. Pan B si dále zvolí nějaké číslo e menší než ϕ(n), které je s ním nesoudělné, (e, ϕ(n)) = 1.
4. Pan B si ještě dopočítá hodnotu d, což je inverze k e modulo ϕ(n), tedy e · d ≡ 1 (mod ϕ(n)).
5. Poslední krok je, že předá veřejnosti (a tedy i panu A) veřejný klíč, což je dvojice n, e (e se nazývá
šifrovací exponent).
Nyní tedy opravdu pan A posílá zprávu panu B, přečte si, že B zveřejnil n, e. Chce poslat zprávu M,
tak ji zašifruje jako C, přičemž platí C ≡ Me
(mod n). Toto C pošle panu B.
Pan B se již připravil na dešifrování, když si spočítal číslo d, dešifrovací exponent. Dostal zašifrovanou
zprávu ve formě čísla C. Spočítá Cd
≡ M (mod n).
Nyní tedy nějaké skutečné („minipísemkové“) zadání.
Příklad 1. Šifrou RSA s veřejným klíčem n = 95, e = 55 bylo posláno číslo C = 42. Šifru prolomte a
určete zaslanou zprávu M ∈ {1, . . . , 95}.
Řešení. Abychom prolomili šifru, potřebujeme se seznámit s prvočísly p, q. V tomto případě snadno spočítáme,
že
n = 95 = 5 · 19 = p · q.
Díky tomu dopočítáme i hodnotu Eulerovy funkce pro n, tedy
ϕ(n) = (5 − 1)(19 − 1) = 4 · 18 = 72.
Podíváme se, že e = 55, takže počítáme 55d ≡ 1 (mod ). Zde pozor na ten modul, který je ϕ(n) a nikoliv
n, v tom se často dělá chyba.
Inverzi spočítáme například takto: 72d ≡ 0 (mod )
55d ≡ 1 (mod )
17d ≡ −1 (mod )
4d ≡ 4 (mod )
d ≡ −17 (mod )
0d ≡ 4 + 4 · 17 ≡ 72 ≡ 0 (mod ) Takže d ≡ −17 ≡ 55 (mod ). Nyní dešifrujeme: M ≡ Cd
≡
4255
(mod ). Zde je vhodné (opět díky znalosti prvočíselného rozkladu) řešit umocnění modulo 5 a pak
modulo 19.
4255
≡? (mod )
255
≡ (24
)13
· 23
≡ 113
· 8 ≡ 3 (mod )
M ≡ 3 (mod ) Nyní modulo 19. 4255
≡? (mod )
455
≡ 2110
≡ (218
)6
· 22
≡ 1 · 4 ≡ 4 (mod )
M ≡ 4 (mod )
(Použili jsme Malou Fermatovu větu.) Z toho plyne, že M = 3 + 5t pro nějaké celé číslo t. Takže
dosadíme do druhé kongruence
3 + 5t ≡ 4 (mod )
5t ≡ 1 (mod )
MB104 řešené příklady (RSA) Jaro 2020
t ≡ 4 (mod )
Dopočítáme M = 3+5(4+19k), kde k ∈ Z, tedy M = 3+20+95k = 23+95k. Protože jsme chtěli dostat
číslo v intervalu [1, 95], tak jsme hotovi, řešením je
M = 23.
Vyřešme ještě jeden příklad, stručněji.
Příklad 2. Šifrou RSA s veřejným klíčem n = 115, e = 15 bylo posláno číslo C = 47. Šifru prolomte a
určete zaslanou zprávu M ∈ {1, . . . , 115}.
Řešení. n = 115 = 5 · 23, ϕ(n) = 4 · 22 = 88
15d ≡ 1 (mod )
15d ≡ 1 + 2 · 88 ≡ 177 (mod )
15d ≡ 177 ≡ 3 · 59 (mod )
5d ≡ 59 (mod )
5d ≡ 59 + 2 · 88 ≡ 235 ≡ 5 · 47 (mod )
d ≡ 47 (mod )
M ≡ 4747
(mod )
M ≡ 4747
(mod )
M ≡ 247
(mod )
M ≡ (24
)11
· 23
≡ 8 ≡ 3 (mod )
M ≡ 3 (mod )
M ≡ 4747
(mod )
M ≡ 147
≡ 1 (mod )
3 + 5t ≡ 1 (mod )
5t ≡ 1 + 23 − 3 ≡ 21 (mod )
5t ≡ 21 − 46 ≡ −25 (mod )
t ≡ −5 (mod )
M = 3 + 5(−5 + 23k) = 3 − 25 + 115k = −22 + 115k = (115 − 22) + 115k = 93
M = 93.
Pro kontrolu si lze ještě spočítat, že 9315
≡ 47 (mod ).