Diffie–Hellman: avalikult kokku lepitud saladus

Alice saadab gᵃ mod p, Bob saadab gᵇ mod p ning mõlemad jõuavad väärtuseni gᵃᵇ mod p, ilma et kumbki seda välja saadaks. Eve näeb igat liinil liikunud arvu. Tee vahetus ja sellele järgnev rünne sammhaaval läbi ning muuda arve p ja g, et näha, mis teeb tema töö ootamatult lihtsaks.

Näidisarvutus — Diffie–Hellman: avalikult kokku lepitud saladus

Alice'i avalik arv	8
Bobi avalik arv	19
Ühissaladus	2
Ühissaladuse võimalikud väärtused	22 22-st
Toorjõukatsed selle A korral	7 (halvimal juhul 22)
Pohlig–Hellmani katsed selle A korral	8 (halvimal juhul 13)
Eve'i arvutatud saladus leitud x põhjal	2

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

Õppetund

Teooria — Diffie–Hellman: avalikult kokku lepitud saladus

Diffie–Hellmani võtmevahetuses lepivad kaks osapoolt salajases arvus kokku kõigile loetavas kanalis. Avalikult lepitakse kokku algarv p ja alus g. Kumbki valib salajase astendaja, avaldab arvu g selles astmes mod p ning astendab teise avaldatud arvu oma salajase astendajaga: (gᵇ)ᵃ = (gᵃ)ᵇ = gᵃᵇ mod p. Selle lahtimurdmine nõuab diskreetse logaritmi leidmist: kui on antud A = gᵃ mod p, tuleb leida selline x, et gˣ ≡ A (mod p). Diffie ja Hellman märkisid 1976. aastal, et nemad ei näe võimalust tuletada ühissaladust avalikest arvudest ilma logaritmita, ent neil puudus ka tõestus, et seda teha ei saa. Elemendi g järk on vähim selline n ≥ 1, mille korral gⁿ ≡ 1 (mod p); g on generaator, kui tema järk on p − 1.

Mida iga sümbol tähendab

p: avalik algarvuline moodul
g: avalik alus
a, b: Alice'i ja Bobi salajased astendajad
A, B: nende avalikud arvud gᵃ mod p ja gᵇ mod p
x: Eve'i leitud astendaja; sobib iga x, mille korral gˣ ≡ A, seega saab ta teada väärtuse a modulo elemendi g järk
ord(g): elemendi g järk: mitu eri väärtust saab ühissaladus võtta

Eeldab: p on algarv vahemikus 5 kuni 1999, g on mis tahes alus vahemikus 2 kuni p − 2 ning a ja b jäävad vahemikku 1 kuni p − 2. Üks katse tähendab arvutatud astme ühtainsat võrdlust sihtväärtusega; mõlemad loendurid võtavad arvesse ka õnnestunud katse. Iga Pohlig–Hellmani number leitakse kandidaate järjest läbi proovides, täpselt nii, nagu autorid seda väikese teguri puhul kirjeldasid; suure teguri jaoks pakuvad nad ka mälu ja aega tasakaalustavat otsingut, mida siinsel lehel ei kasutata. Diffie ja Hellmani algne näide kasutas umbes 200-bitist algarvu, mille puhul hindasid nad logaritmi leidmise keerukuseks ligikaudu 2¹⁰⁰ tehet.

Arvu 257 korral jätab alus 2 alles vaid kuusteist võimalikku saladust 🖖

Vajuta nuppu 16 elemendiga tsükkel. Kuna 257 on algarv, näivad arvud A ja B esmapilgul võivat olla mis tahes 256 jäägi seast. Ent 2⁸ = 256 ≡ −1 mod 257, millest 2¹⁶ = 1; seega tiirlevad arvu 2 astmed 16 väärtusega ringis: 1, 2, 4, 8, 16, 32, 64, 128, 256, 255, 253, 249, 241, 225, 193 ja 129. Need ongi esile tõstetud ruudud. Olgu a ja b millised tahes, kuulub gᵃᵇ alati sellesse tsüklisse ning siin on see 129. Eve'i toorjõurünne lõpeb 14 katse järel ega nõuaks kunagi üle 16; tema leitud x = 13 ei lange küll kokku Alice'i arvuga 77, kuid sobib sama hästi: 77 = 4 × 16 + 13, ja enamat kui jääki modulo 16 astendaja edasi ei kannagi. Algarvuline moodul selle eest ei kaitse. Vahemiku 2 kuni 255 kokku 254 alusest tervelt 126 ei ole generaatorid ning neist kahel, 16 ja 241, jääb alles kõigest neli võimalikku saladust. Algarvu 263 puhul, kus p − 1 = 2 × 131, on iga aluse järk vahemikus 2 kuni 261 kas 131 või 262.

Kaksikalgarvud: 811 katset 21 vastu 🖖

Vajuta nuppu p − 1 väikeste osadena. 1621 on algarv ja 1620 = 2² · 3⁴ · 5, mistõttu ei pea Pohlig–Hellman iial läbi vaatama arvu g kõiki 1620 astet. Algoritm leiab a mod 4 kahe kandidaadi kaupa, a mod 81 kolme kaupa ning a mod 5 viie seast, sidudes tulemused seejärel Hiina jäägiteoreemiga: halvimal juhul 2·2 + 4·3 + 5 = 21 katset ja siin kõigest 15, samal ajal kui toorjõud vajab 1235. Nüüd vali naaberalgarvude tabelist 1619. See on kahe võrra väiksem ja 1618 = 2 × 809: üksainus 809 kandidaadiga osa, halvimal juhul 811 katset ning sama a korral 427. Eve'i töömahu määrab arvu p − 1 suurim algtegur, mitte p ise. Selle lehe 301 toetatud algarvu seas ei ületa Pohlig–Hellmani halvim juhtum seda tegurit kunagi rohkem kui 25 võrra, 172 algarvu puhul jääb see alla kümnendiku toorjõu omast ning 146 sammul 300-st järgmisele algarvule liikudes katselimiit koguni kahaneb. Pohlig ja Hellman sõnastasid selle 1978. aastal tabavalt: kui arvu p − 1 algtegurid on vaid väikesed, siis astendamine mod p „ei ole hea ühesuunaline funktsioon”.

Turvalisem alus ei ole generaator 🖖

Vajuta nuppu Algarvuline järk. Algarvu 263 puhul ei ole alus 2 generaator: selle astmed korduvad 131 järel, seega on võimalikke saladusi vaid 131. Kirjuta lahtrisse g = 5, mis on generaator, ja võimalusi saab kohe kaks korda rohkem. Vaata nüüd selle Pohlig–Hellmani halvimat juhtu: 133 katset, millest 2 kulub arvu a viimasele kahendkohale, sest paarisarvulise a korral on A¹³¹ võrdne 1-ga ning paaritu a korral 262-ga (ehk −1). Generaator annab selle biti iga paaritu algarvu korral tasuta ära, sest p − 1 on alati paarisarv. Vali uuesti g = 2. Selle järk 131 on algarv, mistõttu pole Pohlig–Hellmanil midagi teguriteks lahutada ning tema halvim juht on täpselt sama mis toorjõul: 131 katset. Generaator küll kahekordistas võimalike saladuste arvu, ent kinkis Eve'ile ühe biti ilma vaevata: ainuüksi arvudest A ja B saab ta teada, kas tegemist on ruutjäägiga mod 263. Arvu 2 iga aste on aga nagunii ruut, nii et aluse g = 2 puhul ei reeda avalikud arvud midagi.

Ülesanne täielikult lahendatud

Alice'i saladuse leidmine, kui p = 101 5 sammu
Alice ja Bob kasutavad arve p = 101 ja g = 2. Eve näeb arve A = 12 ja B = 53. Leia Pohlig–Hellmani algoritmiga selline x, et 2ˣ ≡ 12 (mod 101), loenda katsed ja leia leitud x abil ühissaladus. Seejärel hinda sama ründe maksumust algarvu p = 65 537 korral.

Ava see ülesanne tööriistas
1. 100 = 2² · 5², seega määravad arvu x jäägid x mod 4 ja x mod 25. Arvu 2 järk jagab arvu 100 ning kuna 2⁵⁰ = 100 ja 2²⁰ = 95 erinevad mõlemad arvust 1, on järk 100 ise: 2 on generaator.
  
  $100 = 2^{2} \cdot 5^{2}, 2^{50} \equiv 100, 2^{20} \equiv 95 (both \neq = 1) \Rightarrow ord (2) = 100$
2. Modulo 4 on γ = 2⁵⁰ = 100 ≡ −1. Esimene kahendnumber: 12⁵⁰ = 100, seega d = 1 teisel katsel. Eemaldame selle: 12 · 2⁻¹ = 12 · 51 = 612 ≡ 6 ning 6²⁵ = 100, mistõttu ka järgmine number on 1, taas teisel katsel. Saame x ≡ 1 + 1 · 2 = 3 (mod 4).
  
  $1 2^{50} \equiv 100 \Rightarrow d_{0} = 1; 12 \cdot 2^{- 1} = 12 \cdot 51 \equiv 6, 6^{25} \equiv 100 \Rightarrow d_{1} = 1; x \equiv 3 (mod 4)$
3. Modulo 25 on γ = 2²⁰ = 95, mille astmed on 1, 95, 36, 87, 84. Esimene 5-süsteemi number: 12²⁰ = 95, seega d = 1 teisel katsel. Eemaldame selle: 6⁴ = 1296 ≡ 84, seega järgmine number on 4, mis leitakse viiendal katsel. Saame x ≡ 1 + 4 · 5 = 21 (mod 25).
  
  $9 5^{0..4} = 1, 95, 36, 87, 84; 1 2^{20} \equiv 95 \Rightarrow d_{0} = 1; 6^{4} = 1296 \equiv 84 \Rightarrow d_{1} = 4; x \equiv 21 (mod 25)$
4. Arvudest alla 100 annavad 21 mod 25 väärtused 21, 46, 71 ja 96, millest vaid 71 on 3 mod 4. Seega x = 71 pärast 2 + 2 + 2 + 5 = 11 katset, kusjuures halvim juht oleks 2·2 + 2·5 = 14. Toorjõud oleks proovinud väärtusi 0 kuni 71 ehk teinud 72 katset. Ühissaladuseks on 53⁷¹ mod 101 = 35.
  
  $x \in {21, 46, 71, 96}, x \equiv 3 (mod 4) \Rightarrow x = 71; 2 + 2 + 2 + 5 = 11 tries, at worst 2 \cdot 2 + 2 \cdot 5 = 14$
5. 65 537 = 2¹⁶ + 1 on algarv ning p − 1 = 2¹⁶. Pohlig–Hellman võtab selle kuusteist kahendkohta ette ükshaaval, kummaski kaks kandidaati: halvimal juhul 32 katset, samas kui toorjõud võiks vajada 65 536 katset. Pohlig ja Hellman analüüsisid just seda juhtu, p = 2ⁿ + 1, enne üldise lahenduseni jõudmist.
  
  $s = B^{x} = 5 3^{71} mod 101 = 35; 65537 = 2^{16} + 1 : at worst 16 \cdot 2 = 32 tries$
Vastus

x = 71 pärast 11 katset (halvimal juhul 14) ning ühissaladus on 35. Mooduli p = 65 537 korral vajab rünnak kõige rohkem 32 katset. Siinne tööriist toetab arve kuni 1999, mistõttu on see tulemus puhtalt arvutuslik, mitte läbi mängitud simulatsioon.

$x = 71, 11 tries, s = 35$

Õpitee

Kuidas koode murtakse

Allikad (2)

The exchange itself, the definition's sentence that its authors could see no way round a logarithm and had no proof, and the 200-bit example in `assumes`: Whitfield Diffie and Martin E. Hellman, "New Directions in Cryptography," IEEE Transactions on Information Theory 22(6), 644–654, November 1976. §III, p. 649.
The second insight's quotation, the digit-by-digit search the page runs, and the worked problem's p = 2ⁿ + 1: Stephen C. Pohlig and Martin E. Hellman, "An Improved Algorithm for Computing Logarithms over GF(p) and Its Cryptographic Significance," IEEE Transactions on Information Theory 24(1), 106–110, January 1978. §III–IV, pp. 107–110.

42Mathi meeskond · Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud.