Lineární modely MB141, 3. část
David Krum
3.4.2024
□ ť5P
Připomenutí počítání ve zbytkových třídách, kongruence
Píšeme
3 = b   (mod n).
pokud a, b dávají stejný zbytek po dělení n, rozdíl a — b je dělitelný n, atd.
S kongruencemi pracujeme podobně jako s rovnicemi.
Násobení číslem soudělným s modulem není ekvivalentní operace (ztrácíme část informace).
Pro aplikace (šifrování) je velmi důležité naučit se efektivně umocňovat ve zbytkových třídách.
Přirozené číslo p nazýváme prvočíslem, pokud je různé od 1 a jeho jedinými děliteli jsou lap.
Malá Fermatova věta
Nechť p je prvočíslo a a celé číslo, které není dělitelné p (p { a). Pak platí:
ap_1 = 1   (mod p).
(Důkaz se vede matematickou indukcí vzhledem k a a využívá binomickou větu aplikovanou na (a + l)p.)
Příklad: Určete zbytek po dělení čísla 32024 číslem 17.
Řešení: Protože 17 { 3, podle malé Fermatovy věty platí 316 = 1 (mod 17).
Potřebujeme tedy zjistit, čemu je kongruentní exponent 2024 v modulu 16: Nejbližším menším násobkem šesnácti je číslo 2016 tj. 2024 = 8 (mod 16).
Celkem dostáváme 32024 = 316/c+8 = (S16)^ • 38 = 1 • 38 = (32)4 94 = (-8)4 = 642 = 132 = (-4)2 = 16 (mod 17).
Odpověď: Zbytek je 16.
Eulerova funkce
Eulerova funkce vyjadřuje počet celých čísel v množině {1, 2,..., n — 1} nesoudělných s n.
Značíme (f)(n).
Nepraktický vzorec:
kde pi, p2,..., p/c jsou všechna prvočísla dělící n. Praktický algoritmus:
► Pro prvočíslo p a přirozené k platí (f)(pk) = (p — l)p
► Pro nesoudělná m. n platí (f)(mn) = 0(m)0(r?).
Příklad na Eulerovu funkci
Spočtěte 0(240)
Řešení: 0(240) = 0(24 • 3 • 5) = 0(24)0(3)0(5) = (2 - 1) • 23 • (3 - 1) • (5 - 1) = 8 • 2 • 4 = 64.
Řešení nepraktickým vzorcem: 2,3,5  240, tj.
«240) = 240.(l-|).(l-|)-(l-|
~ „   1    2    4 r
= 240 ------= 64.
2   3 5
ulerova věta
Pro nesoudělná a, n platí:
a^n) = 1   (mod n).
Eulerova věta zobecňuje malou Fermatovu větu, protože 0(p) = p — 1 pro prvočíselné p.
Příklad: Spočtěte zbytek po dělení čísla 2ZUZ číslem 15.
■v
Řešení: 2 a 15 jsou nesoudělná, můžeme tedy využít Eulerovu větu 0(15) = 0(3)0(5) = (3 - 1) • (5 - 1) = 8, 28 = 1 (mod 15).
Protože 8 | 2024, dostáváme 22024 = (28)fc = 1 (mod 15), tj. hledaný zbytek je 1.
Co když jsou a, n soudělná?
Je-li základ soudělný s modulem, obvykle dojde při umocňování k určité „degeneraci".
Můžeme si pomoci rozkladem modulu na složku nesoudělnou s a a složku tvořenou prvočísly společnými s a.
Na první složku použijeme Eulerovu větu (nebo malou Fermatovu), ve druhé složce můžeme očekávat „rychlý konec" — nulový zbytek (násobek modulu) se objeví už na menší mocnině.
Příklad: Určete poslední číslici čísla 22024.
Řešení: Základ 2 a modul 10 jsou soudělné, nemůžeme tedy využít Eulerovu větu přímo. Nicméně zjistíme zbytek po dělení 5: malá Fermatova věta říká 24 = 1 (mod 5), tedy i 22024 = (24)k = 1 (mod 5). Poslední číslicí tak může být 1 nebo 6.
Protože 22024 je zřejmě sudé, poslední číslicí musí být 6.
Duševní příprava na rád čísla
Příklad: Najděte nějaké číslo       1 a exponent k, pro něž xk = 1 (mod 36) a nějaké číslo x, pro nějž žádný takový exponent k neexistuje.
Řešení: Zkusme třeba x = 2. Číslo xk je vždy sudé, stejně jako modul 36, kongruence tedy platit nemůže. Našli jsme odpověď na druhou otázku. Podobně bychom zjistili, že ani x = 3 kongruenci nevyhoví kvůli soudělnosti s modulem, a stejně tak x = 4.
Pro x = 5 máme (v modulu 36):
52 = 25,
53 = 5 • 25 = 125 = 3 • 36 + 17 = 17,
54 = (52)2 = 252 = (-11)2 = 1212 = 13,
55 = 54 • 5 = 13 • 5 = 65 = -7,
56 = 55 • 5 = -7 • 5 = -35 = 1,
h 11rá I
Řád čísla
Úloha „pro dané x najít k, aby xk = 1 (mod n)il je řešitelná právě tehdy, když x, n jsou nesoudělná.
Existenci takového k zaručuje Eulerova věta, ale často se zadaří najít k menší než (f)(n).
Nejmenší k splňující xk = 1 (mod n) nazýváme řád čísla x v modulu n.
Mocniny x se v modulu n chovají poměrně chaoticky, proto je zjistovani radu tezke.
Platí ovšem důležitá věta: Řád dělí (j){n).
Vysvětlení: Jestliže xk = 1, pak i xkl = {xk)1 = 1. Obráceně, pokud xk = l,x/ = 1, pak i xnsd^'^ = 1. Proto řád musí dělit jakékoli k řešící kongruenci, tedy i (f)(n).
Příklad na řád
Určete řád čísla 7 v modulu 18.
Řešení: Čísla 7, 18 jsou nesoudělná, zadání tedy má smysl. Podle předchozího poznatku má cenu zkoušet pouze exponenty dělící 0(18) = (2 - 1) • (3 - 1) • 3 = 6, tj. k = 2,3,6:
72 = 49 = 13 = -5,
73 = 72 • 7 = -5 • 7 = -35 = 1.
Odpověď: Řád čísla 7 modulo 18 je 3.
Poznámka: Množina dělitelů (f)(n) (kandidátů na řád) je docela důkladně provázána relací dělitelnosti. To se nám hodí, protože můžeme při výpočtu zužitkovat dílčí výsledky pro předchozí (menší) kandidáty.
Při zkoušení kandidátů postupujeme samozřejmě od menších exponentů k větším, protože je to jednodušší a nechceme řád „propást".
Primitivní kořen
Číslo se nazývá primitivní kořen modulo n, pokud (je nesoudělné sna) jeho řád je roven (f)(n). (Tzn. řád primitivního kořene je „nejzazší možný".)
Mocniny x,x2,... , x^n) primitivního kořene x se neopakují, jinak by některé menší musely být 1 a x by nebyl primitivní. V důsledku toho mocniny „navštíví" všechny nesoudělné prvky s n.
Pohyb mocnin po Zn je „neuspořádaný", proto je velmi těžké řešit obrácené úlohy, tzn. pro r?,y nesoudělná počítat
► odmocninu: pro dané k a najít x,
► diskrétní logaritmus: pro dané x a najít k,
aby platilo
xk = y   (mod n).
Tohoto faktu využívají některé šifrovací metody, jak si brzy ukážeme.
Příkad na primitivní kořeny
Najděte všechny primitivní kořeny modulo 14.
Řešení: Bavíme se jen o prvcích v Z14 nesoudělných se 14, tj. 1,3,5,9,11,13.
Jedničku ihned vyřadíme, protože ji řeší exponent k = 1. Podobně vyřadíme 13, protože 13 = — 1 a (—l)2 = 1.
Ostatní prvky zkusíme umocnit na 2 a 3, což jsou dělitelé 0(14) = 6. Předtím si ještě všimněme, že jsou v Z14 rozmístěny „středově symetricky", čehož využijeme přepisem 11 = —3,9 = —5
1
1
Rád čísel 9 a 11 je jen 3, nejde tedy o primitivní kořeny Odpověď: Primitivní kořeny modulo 14 jsou 3c?>5<ť
Komentáře k mocninám ve zbytkových třídách
► Při „ručním" výpočtu mocnin využíváme přednostně umocňování na druhou než prosté opakované násobení, např. 36 = (32)2-32.
► Víc než kdekoli jinde se vyplácí přepis „horní poloviny" zbytk do záporných reprezentantů.
► V mocninách vyšších než 0(r?) se výsledky zacyklí.
► To se děje i u prvků nesoudělných s n, které nejsou primitivními kořeny, ale cyklus je kratší.
► Prvky nesoudělné s r? jsou invertibilní. Inverzí primitivního kořene je primitivní kořen.
► Požadavky: Znát malou Fermatovu větu, Eulerovu větu, pojmy řád čísla, primitivní kořen, vědět, že řád dělí (f)(n). Umět počítat (/)(n), poradit si s jakoukoli vysokou mocninou v Zn, určit řád čísla, prověřit primitivnost kořene.
Lineární kongruence
Z dřívějšího umíme řešit (jednodušší) kongruence tvaru
ax = b   (mod n).
tj. určit x pro daná r?, a, b.
Obvykle si pomáháme vhodným násobením.
Systematický přístup: najdeme inverzi a-1 k a a spočítáme x = a_1b.
Příklad: Řešte kongruenci 5x = 3 (mod 7).
Řešení: 1) Řešení x = 2 uhodneme, nebot 5 • 2 = 10 = 3 (mod 7)
2) Koeficienty 5, 3 nahradíme podle kongruenci 5 = —2, 3 = —4. Odtud —2x = —4, a tedy x = 2. (Poslední krok využívá faktu, že 2,7 jsou nesoudělná, a tedy —2 má inverzi.)
3) 5 • 3 = 15 = 1, tj. 5"1 = 3, proto x = 5"1 • 3 = 3 • 3 = 9 = 2.
Rozklad modulu
Inverze ne vždy existuje (a, n soudělná) a výpočet může být komplikovaný.
Někdy pomáhá rozbití složeného modulu na menší činitele, což vede na řešení soustavy kongruencí:
Dílčí kongruence můžeme samostatně řešit a dosadit do následující (obdoba řešení soustav lineárních rovnic). Např. řešení 1. kongruence x = c (mod r?i) dosadíme do 2. kongruence jako x = dni + c, spočítáme d, vyjádříme x v modulu r?ir?2 atd.
ax
ax
ax
(mod rik)
Příklad na složený modul I
■v
Reste kongruenci
21x = 18   (mod 60).
Řešení: 60 = 2 • 3 • 5, kongruenci tedy rozložíme na soustavu
21x = 18 (mod 4) 21x = 18 (mod 3) 21x = 18   (mod 5)
Po úpravě v dílčích modulech dostáváme:
x = 2   (mod 4) Ox = 0   (mod 3) x = -2   (mod 5)
Druhá kongruence platí vždy, nic se z ní nedozvíme.
Příklad na složený modul II
V soustavě
x = 2   (mod 4) x = -2   (mod 5)
můžeme první kongruenci přepsat také jako x odtud bychom měli hned x = —2 (mod 20).
Tvařme se, že nás to nenapadlo. Vyjádříme x do x = — 2 (mod 5):
2 + 4a = -2   (mod 5) 4a = -4
-2 (mod 4), a 2 + 4a a dosadíme
Příklad na složený modul III
Celkem tedy x = 2 - 4 = -2 (mod 20) (či x V modulu 60 máme 3 řešení:
xi = 18   (mod 60), x2 = 38, x3 = 58.
Příklad na soustavu kongruencí I
Reste soustavu kongruencí
3x = 4 (mod 7) 5x = 2 (mod 8) 4x = 6   (mod 9)
Řešení: První kongruencí vynásobíme 5: 15x = 20, x = —1 (mod 7), tj. x = 7 a — 1.
Dosazení do druhé kongruence:
5 • (7a - 1) = -3 • (-a - 1) = 3a + 3 = 2,3a = -1 (mod 8). Vynásobíme 3: 9a = —3, a = —3 = 5 (mod 8). Odtud x = 7 • 5 - 1 = 34 (mod 56).
Příklad na soustavu kongruencí II
Víme x = 56b + 34. Dosadíme do třetí kongruence:
4 • (566 + 34) = 4 • (2b - 2) = 8b - 8 = -fa + 1 = 6, f> = -5
(mod 9).
Dostáváme x = 56 • 4 + 34 = 258 (mod 504). Zkouška:
258 =-1   (mod 7),      3 • (-1) =-3 = 4   (mod 7), 258 = 2   (mod 8), 5 • 2 = 10 = 2   (mod 8),
258 = -3   (mod 9),      4 • (-3) = -12 = 6   (mod 9).
Čínská zbytková věta
Zaručuje existenci řešení soustavy kongruencí (již upravených se separovaným x).
Jsou-li r?i, r?2, • • • nk po dvou nesoudělné moduly, pak má soustava kongruencí
x
x
bi
(mod r?i) (mod r?2)
x
bk
(mod rik)
jediné řešení v modulu r?ir?2 • • • nk-
Příklad na složenou mocninu
Určete zbytek po dělení čísla 121212 číslem 25.
Řešení: 0(25) = (5 — 1) • 5 = 20. Z Eulerovy věty víme, že 12^(25) = i (mod 25), potřebuj eme tedy zjistit zbytek po dělení 1212 dvaceti.
Čísla 12, 20 jsou soudělná, budeme tedy samostatně řešit zbytek pro moduly 4 a 5. Zřejmě 1212 = 0 (mod 4), v druhém případě využijeme malou Fermatovu větu: 124 = 1 (mod 5), proto i 1212 = 1 (mod 5). Tedy 1212 = 4a a 4a = 1 (mod 5). Odtud a = 4 (mod 5) a 1212 = 16 (mod 20).
Můžeme se vrátit na začátek a dopočítat zbytek pro 1212l2\ 121212 = 1216 = (122)8 = 1448 = (-6)8 = (62)4 = 364 = ll4 = = (ll2)2 = 1212 = (-4)2 = 16   (mod 25).
Odpověď: Hledaný zbytek je 16.
Komentáře k soustavám kongruencí
► Inverzní prvky můžeme i pro složený modul počítat z Bezoutovy rovnosti (a mnohdy je to rychlejší).
► Pro dosazování výsledků dílčích kongruencí nepotřebujeme mít kongruence „učesané" jako v čínské zbytkové větě. Úpravy provedeme až po dosazení— analogie s řešením soustav lineárních rovnic a zpětným dosazováním.
► Požadavky: Umět počítat soustavy lineárních kongruencí. Využívat tuto schopnost při rozkladu složeného modulu a při výpočtu složených mocnin.
► Doporučení: zopakovat si druhé mocniny čísel do 20 a třetí mocniny do 10.
Historie kryptografie
Využití: diplomacie, vojenství, bankovnictví, přístupová práva, elektronický podpis, atd.
Základní způsoby šifrování:
► transpoziční— písmena jsou prohozena (skytala, mřížka),
► steganografie — zpráva je skryta balastní informací (šifra ve Švejkovi, tj. výběr písmen z knihy),
► substituční— písmena/shluky písmen jsou nahrazovány jinými (Caesar, Vigeněr, Enigma),
► kombinace — DES, AES, speciální čipy.
Většina „tradičních" systémů je symetrická: šifrovania dešifrování jsou stejně náročné a vzájemně inverzní procesy.
Vigeněrova šifra — šifrování
A = l, B = 2, C = 3,
Zpráva: TOTOJEVELMITAJNAZPRAVA Klíč: PRŮDUCH
Šifrování— rozkopírujeme klíč podle délky zprávy: PRUDUCHPRUDUCHPRUDUCHP a sčítáme se zprávou modulo 26:
T+P =	20 + 16	= 36 =	10	= J
0 + R =	15 + 18	= 33 =	7 =	= G
T+U =	20 + 21	= 41 =	15	= 0
Zašifrovaná zpráva: JGO.
□ rS1
=        1    -O q,o
Vigeněrova šifra — dešifrování
J - P = 10 - 16 = -6 = 20 = T   (mod 26) G - R = 7 - 18 = -11 = 15 = O O - U = 15 - 21 = -6 = 20 = T
nebo si nejdřív připravíme dešifrovací klíč
26 - P = 26 - 16 = 10 = J 26 - R = 26 - 18 = 8 = H 26 - U = 26 - 21 = 5 = E
a ten přičítáme k zašifrované zprávě:
J +J = 10 + 10 = 20= T   (mod 26) G + H = 7 + 8 = 15=0 0 + E = 15+ 5 = 20= T
□ r5P
Obecný princip šifrování
Alice Bob
□ S
Zranitelnost šifry
Tři informační kanály:
► dohoda o metodě (nebo předání šifrovacího stroje, atp.),
► předání šifrovacího/dešifrovacího klíče,
► předání zašifrované zprávy.
Mnohé stasí šifrovací způsoby podceňují možnosti útoku na první dva kanály.
Samotný přenos zašifrované zprávy pokládáme za bezpečný (věříme šifře), v zásadě je tedy veřejný.
Ovšem i zpráva může být podrobena zejména frekvenční analýze. Východiskem může být dostatečně rozsáhlý klíč, ale pak se opět dostáváme k problémům s přenosem klíče.
Optimální situace: přenos informací všemi třemi kanály bude veřejný, přesto se útočník ke zprávě nedostane.
Tzv. asymetrické šifrování: využívá se „mezer v matematice" — jedním směrem to jde snadno, obráceně velmi ztuha. < 1, < 1, t
RSA (Rivest, Shamir, Adleman 1977, Cocks 1973)
n ... dostatečně velké číslo takové, ze n — pq, p, q prvočísla, rozklad n je soukromý,
(f)(n) . .. kvůli velikosti n a neznámému rozkladu n — pq není možné efektivně spočítat,
e ... verejný klíč (šifrovací), nesoudělný s (f)(n),
d ... soukromý klíč (dešifrovací), splňuje de = 1 (mod 0(r?)),
M ... zpráva,
C ... zašifrovaná zpráva.
Šifrování: C = Me (mod n).
Dešifrování: M = Cd, protože {Me)d = Med = Mk^+1 = M (mod n).
rnutí RSA
r?, e ... veřejné,
p, q, d ... soukromé.
Důkaz korektnosti dešifrovaní provádíme pomocí čínské zbytkové věty pro moduly p a q. (Pokud by M byla soudělná s p nebo q, je v tomoto modulu kongruentní s 0, a tedy i její mocniny. Tj. malá Fermatova věta ve formě ap = a (mod p) platí i bez předpokladu nesoudělnosti.)
Faktory p — 1, q — 1 čísla 0(r?) by měly být „málo soudělné", jinak hrozí snazší prolomení.
Využití pro digitální podpis: majiteli soukromého klíče d pošleme zprávu M, on nám vrátí Md. Pomocí veřejného klíče e zkontrolujeme, že (Md)e = M.
Příklad na RSA I
a) Zašifrujte zprávu M = 123 užitím veřejného klíče n = 209, e = 7.
b) Šifru prolomte a dešifrujte zprávu.
Řešení: a) C = Me = 1237 (mod n) se nám počítat nechce bez znalosti rozkladu n. Začněme tedy částečným prolomením 209 = 11 • 19, spočítáme C pro faktory 11 a 19 a výsledky poskládáme přes čínskou zbytkovou větu:
1237 = 27 = (23)2 • 2 = (-3)2 ■ 2 = -2 • 2 = -4 (mod 11) 1237 = 97 = (92)3 - 9 = 53- 9 = 11- 9 = 4   (mod 19)
Tedy 1237 = 11/c - 4 a llk - 4 = 4 (mod 19). Po úpravě -8k = 8, tj. k = -l (mod 19). Celkem C = 1237 = -15 = 194 (mod 209).
Příklad na RSA II
b) 0(209) = (11 - 1) • (19 - 1) = 180.
Prolomení dešifrovacího klíče: inverzi d k e = 7 najdeme např. pomocí Eukleidova algoritmu pro hledání koeficientů do Bezoutovy rovnosti
180a+ 76 = 1.
z	a	b
180	1	0
7	0	1
5	1	-25
2	-1	26
1	3	-77
Tj. d = -77 = 103 (mod 180).
Příklad na RSA III
Dešifrování: M = Cd = 194103 = (-15)103 (mod 209). Obdobně jako u šifrování počítáme M odděleně přes faktory 11 a 19:
(-15)103 = -410 10+3 = -43 = -64 = 2   (mod 11) (-15)103 = 45 18+13 = (43)4 • 4 = 74 • 4 = 492 • 4 =    (mod 19) = (-8)2 -4 = 7-4 = 9
Tedy (-15)103 = 11 k + 2,11 k + 2 = 9,11 k = 7 (mod 19).
Odtud -8/c = 12,2k = 3 = 22, k = 11.
Celkem M = 194103 = 11 • 11 + 2 = 123 (mod 209).
Vyšlo.
Výměna klíčů (Diffie, Hellman 1976, Williamson 1974)
p ... prvočíslo (modul),
g .. . primitivní kořen v modulu p. (Tzn. nejmenší n splňující gn = 1 (mod n) je n = p — 1.)
a . .. Alicin soukromý klíč (libovolný),
b ... Bobův soukromý klíč (libovolný),
Alice pošle veřejně Bobovi ga, podobně Bob pošle Alici gb.
Přidáním svého klíče do mocniny si obě strany umí spočítat g což bude jejich společný klíč.
P, g, ga, gb jsou tedy veřejné, Alice navíc vidí a,gab a Bob navíc vidí b,gab.
frovánř na základě Diffie-Hellman, šifra EIGamal
Po výpočtu společného soukromého klíče e = gab mohou své soukromé klíče a, b obě strany zapomenout.
Dešifrovacím klíčem je inverze d k e (v modulu p), kterou si obě strany umí spočítat.
Alice zašifruje zprávu C = Me.
Bob dešifruje zprávu M = Cd.
Pro jednostranně posílanou zprávu stačí provést tyto kroky:
► Kdokoli zveřejní p,g,
► Bob zveřejní gb,
► Alice si spočítá e = gab a zveřejní gaC = Me,
► Bob spočítá d = e-1 a M = Cc/.
K prolomení šifry by bylo třeba z p^g^g3 umět určit a, o čemž jsme si říkali, že je obtížné (diskrétní logaritmus).
Příklad na šifru EIGamal
Nechť p = 13, g" = 7 a Alice má veřejný klíč ga = 6.
a) Ověřte, že g je primitivní kořen v modulu p.
b) Prolomte šifru nalezením Alicina soukromého klíče a.
Řešení: a) Musí platit g12 = 1 (mod 13), ale my potřebujeme ověřit, že neplatí podobná kongruence pro menší exponent. Stačí ověřit gA ^ 1, g"6 ^ 1:
74 = (72)2 = (-3)2 = -4   (mod 13), 76 = (72)3 = (-3)3 = -4 • (-3) = -1.
b) V a) jsme si rozumnou úvahou o kandidátních mocninách ušetřili práci, ale teď ty ostatní stejně musíme „otrocky" vyzkoušet
72 = -3, 73 = 72 • 7 = -3 • 7 = 5,
75 = 72 • 73 = -3 • 5 = -2,    77 = 72 • 75 = -3 • (-2) = 6.
Odpověď: a = 7. n =
Komentáře k šifrování
► I protokol Diffie-Hellman / EIGamal lze využít k digitálnímu podpisu: ověřovatel vytvoří zprávu m a Alici (majitelce klíče a) pošle gm. Ona odpoví (gm)a = gam. Ověřovatel si výsledek zkontroluje jako (ga)m.
► Moderní šifrovací protokoly neutajují metodu. I bezpečná výměna klíčů může probíhat veřejně.
► U digitálního podpisu se nadělá spousta řečí kolem hashování zprávy, což jsme pro jednoduchost ignorovali. Zpráva by měla podepisovaného dostatečně prověřit a současně nevystavit nebezpečí prolomení soukromého klíče.
► Požadavky: Porozumět základní podstatě šifrování, dešifrování, digitálního podpisu. Znát princip protokolů RSA a Diffie-Hellman / EIGamal. Umět v nich šifrovat, dešifrovat a prolomit šifru pro malý modul.