Polig-Hellman-algoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 23. huhtikuuta 2020 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Polyg-Hellman-algoritmi (kutsutaan myös Silver-Polig-Hellman-algoritmiksi ) on deterministinen diskreetti logaritmi -algoritmi jäännösrenkaassa , joka on modulo a alkuluku . Eräs algoritmin ominaisuuksista on, että erikoismuotoisille alkuluvuille löytyy diskreetti logaritmi polynomiajassa . [yksi]

Historia

Tämän algoritmin keksi amerikkalainen matemaatikko Roland Silver , mutta sen julkaisivat ensimmäisen kerran kaksi muuta amerikkalaista matemaatikkoa Stephen Pohlig ja Martin Hellman vuonna 1978 artikkelissa " Parannettu algoritmi logaritmien laskemiseen GF(p):n yli ja sen kryptografinen merkitys" [2] , joka kehitti tämän algoritmin Roland Silveristä riippumatta. [3]

Alkutiedot

Esitetään vertailu

$a^{x}\equiv b{\pmod {p)),$

(yksi)

ja luvun hajoaminen alkutekijöiksi tunnetaan: $p-1$

p-1=\prod\limits_{i=1}^{k}q_i^{\alpha_i}.

(2)

On tarpeen löytää luku , joka tyydyttää vertailun (1). [neljä] $x,\;0\leq x < p-1$

Algoritmin idea

Algoritmin ydin on, että riittää, että kaikille löydetään moduulit ja sitten ratkaisu alkuperäiseen vertailuun löytyy kiinalaisen jäännöslauseen avulla . Löytääksesi kunkin näistä moduuleista sinun on ratkaistava vertailu: $x$ $q_i^{\alpha_i}$ $i$
$x$

(a^x)^{(p-1)/{q_i^{\alpha_i}}} \equiv b^{(p-1)/{q_i^{\alpha_i}}} \pmod{p}

. [5]

Algoritmin kuvaus

Yksinkertaistettu versio

Paras tapa käsitellä tätä algoritmia on ottaa huomioon erikoistapaus, jossa . $p = 2^n + 1$

Meille annetaan , ja vaikka on olemassa primitiivinen elementti, ja meidän on löydettävä sellainen , joka tyydyttää . $a$ $s$ $b$ $a$ $GF(p)$ $x$ $a^x\equiv b\pmod{p}$

Oletetaan, että koska sitä ei voi erottaa , koska meidän tapauksessamme primitiivielementillä on määritelmän mukaan aste , siksi: $0\leq x \leq p-2$ $x = p-1$ $x=0$ $a$ $p-1$

a^{p-1}\equiv 1\equiv a^{0}\pmod{p}

Milloin , on helppo määrittää binäärilaajennuksella kertoimilla , esimerkiksi: $p = 2^n + 1$ $x$ $\{q_0, q_1,\pisteet, q_{n-1}\}$

x = \sum\limits_{i = 0}^{n-1}q_i2^i=q_{0} + q_{1}2^1 + \cdots + q_{n-1}2^{n-1}

Vähiten merkitsevä bitti määritetään nostamalla potenssiin ja soveltamalla sääntöä $q_{0}$ $b$ $(p-1)/2 = 2^{n-1}$

b^{(p-1)/2}\pmod{p}\equiv \begin{cases}+1, & q_0 = 0\\ -1, & q_0 = 1. \end{cases}

Ylemmän säännön johtaminen

Harkitse aiemmin saatua vertailua :

a^{p-1}\equiv 1\pmod{p}\Rightarrow a^{(p-1)/2}\equiv\pm 1\pmod{p}

mutta määritelmän mukaan saa muun arvon kuin , joten vertailua on jäljellä vain yksi : $a$ $(p-1)/2 < p - 1$ $yksi$

a^{(p-1)/2}\equiv -1\pmod{p}

Nosta vertailu (1) potenssiin ja korvaa yllä saatu vertailu: $(p-1)/2$

b^{(p-1)/2}\equiv (a^x)^{(p-1)/2}\equiv(a^{(p-1)/2})^x\equiv(-1 )^x\pmod{p}

Tasa-arvo on totta, jos se on parillinen, eli polynomin muodossa olevassa laajennuksessa vapaa termi on yhtä suuri kuin , joten on totta, kun . $(-1)^x=1$ $x$ $q_{0}$ $0$ $(-1)^x = -1$ $q_0 = 1$

Nyt muunnetaan tunnettu hajoaminen ja otetaan käyttöön uusi muuttuja : $z_{1}$

b\equiv a^x\equiv a^{x_1 + q_0}\pmod{p}\Rightarrow z_1\equiv ba^{-q_0}\equiv a^{x_1}\pmod{p}

missä

x_1 = \sum\limits_{i = 1}^{n-1}q_i2^i=q_{1}2^1 + q_{2}2^2 + \cdots + q_{n-1}2^{n -yksi}

On selvää, että on jaollinen milloin , ja milloin on jaollinen , mutta ei enää. $x_{1}$ $neljä$ $q_1=0$ $q_1=1$ $2$ $neljä$

Väittelemällä kuten ennenkin, saamme vertailun :

z_1^{(p-1)/4}\pmod{p}\equiv \begin{cases}+1, & q_1 = 0\\ -1, & q_1 = 1, \end{cases}

josta löydämme . $q_{1}$

Loput bitit saadaan samalla tavalla. Kirjoitetaan etsinnän yleinen ratkaisu uudella merkinnällä: $q_{i}$

m_i=(p-1)/2^{i+1}

z_i\equiv b\cdot a^{-q_0 - q_{1}2^1 - \dots - q_{i-1}2^{i-1}}\equiv a^{x_i}\pmod{p}

missä

x_i = \sum\limits_{k = i}^{n-1}q_k2^k

Joten tehoon nostaminen antaa: $z_{i}$ $mi$

z_i^{m_i} \equiv a^{(x_{i}\cdot m_i)}\equiv\left(a^{(p-1)/2}\oikea)^{(x_i/2^i)}\ equiv (-1)^{x_i/2^i}\equiv(-1)^{q_i}\pmod{p}

Näin ollen:

z_i^{m_i}\pmod{p}\equiv \begin{cases}+1, & q_i = 0\\ -1, & q_i = 1, \end{cases}

josta löydämme . $q_{i}$

Kun kaikki bitit on löydetty, saamme tarvittavan ratkaisun . [6] $x$

Esimerkki

Annettu:

a = 3,\;b = 11,\;p = 17 = 2^4 + 1

Löytö:

x

Ratkaisu:
Saamme . Siksi se näyttää tältä: $p-1 = 2^4$ $x$

x = q_0 + q_{1}2^1 + q_{2}2^2 + q_{3}2^3

Löydämme : $q_{0}$

b^{(p-1)/2} \equiv 11 ^ {(17 - 1)/2} \equiv 11 ^ {8} \equiv (-6) ^ 8 \equiv (36) ^ 4 \equiv 2 ^ 4 \equiv 16 \equiv -1 \pmod{17} \Rightarrow q_0 = 1

Laskemme myös : $z_{1}$ $m_1$

z_1 \equiv b\cdot a^{-q_0} \equiv 11\cdot 3 ^{-1} \equiv 11 \cdot 6 \equiv 66 \equiv -2 \pmod{17}

m_1 = (p-1)/2^{1+1}= (17-1)/2^2 = 4

Löydämme : $q_{1}$

z_1^{m_1} \equiv (-2)^4 \equiv 16 \equiv -1 \pmod{17} \Oikea nuoli q_1 = 1

Laskemme myös : $z_{2}$ $m_2$

z_2 \equiv z_1 \cdot a^{-q_{1}2^1} \equiv (-2) \cdot 3^{-2} \equiv (-2) \cdot 6^2 \equiv (-2) \ cdot 36 \equiv (-2) \cdot 2 \equiv -4 \equiv 13 \pmod{17}

m_2 = (p-1)/2^{2+1}= (17-1)/2^3 = 2

Löydämme : $q_{2}$

z_2^{m_2} \equiv 13 ^2 \equiv (-4) ^2 \equiv 16 \equiv -1 \pmod{17} \Rightarrow q_2 = 1

Laskemme myös : $z_{3}$ $m_3$

z_3 \equiv z_2 \cdot a^{-q_{2}\cdot2^2} \equiv 13 \cdot 3^{-4} \equiv 13 \cdot 9^{-2} \equiv 13 \cdot 2^2 \ equiv (-4) \cdot 4 \equiv -16 \equiv 1 \pmod{17}

m_3 = (p-1)/2^{3+1}= (17-1)/2^4 = 1

Löydämme : $q_{3}$

z_3^{m_3} \equiv 1 ^ 1 \equiv 1 \pmod{17} \Rightarrow q_3 = 0

Löydä etsimäsi : $x$

x = 1 + 1\cdot 2^1 + 1 \cdot 2^2 + 0 \cdot 2^3 \equiv 7

Vastaus: $x=7$

Peruskuvaus

Vaihe 1 (taulukon kokoaminen). Tee arvotaulukko , missä

\{r_{i,j}\}

r_{i,j}=a^{j\cdot\frac{p-1}{q_i}}, i\in\{1,\dots,k\}, j\in\{0,\dots,q_i -yksi\}.

Vaihe 2 (laskenta ).

\log_a{b}\;\bmod{q_i^{\alpha_i}}

I : lle 1 - k : Päästää

x\equiv\log_a{b}\equiv x_0+x_1q_i+...+x_{\alpha_{i}-1}q_i^{\alpha_{i}-1}\pmod{q_i^{\alpha_i)),

missä

0\leq x_i\leq q_i-1

. Sitten vertailu on oikea:

a^{x_0\cdot\frac{p-1}{q_i}} \equiv b^{\frac{p-1}{q_i}} \pmod{p}

Ylin vertailutulos

Nostetaan vertailun (1) vasen ja oikea osa potenssiin : $(p-1)/q_i$

a^{x\cdot \frac{p-1}{q_i}} \equiv b ^ {\frac{p-1}{q_i}} \pmod{p}

Korvaa ja muunna vertailu: $x$

a^{x_0 \cdot \frac{p-1}{q_i} + x_1\cdot(p-1) + x_2\cdot q_i \cdot(p-1) + \dots + x_{\alpha_i - 1} \cdot q_i^{\alpha_i - 2} \cdot (p-1)} \equiv b ^ {\frac{p-1}{q_i)) \pmod{p}

a^{x_0 \cdot \frac{p-1}{q_i}}\cdot a^{x_1\cdot(p-1)} \cdot a^{x_2\cdot q_i \cdot(p-1)} \cdot \dots \cdot a^{x_{\alpha_i - 1} \cdot q_i^{\alpha_i - 2} \cdot (p-1)} \equiv b ^ {\frac{p-1}{q_i)) \pmod {p}

Koska on primitiivinen elementti, joten muodon vertailut: $a$

a^{m \cdot (p-1)} \equiv 1 \pmod{p},\;\forall m \in \{0,1, \dots, p-1\}

Saamme

a^{x_0 \cdot \frac{p-1}{q_i}}\cdot 1 \cdot 1 \cdot \dots \cdot 1 \equiv b ^ {\frac{p-1}{q_i}} \pmod{p }

a^{x_0\cdot\frac{p-1}{q_i}} \equiv b^{\frac{p-1}{q_i}} \pmod{p}

[neljä] Vaiheessa 1 laaditun taulukon avulla löydämme For j :n välillä 0 -

x_{0}.

\alpha_{i}-1

Vertailua harkiten

a^{x_{j}\cdot\frac{p-1}{q_i}} \equiv (ba^{-x_0-x_1q_i...-x_{j-1}q_i^{j-1}})^ {\frac{p-1}{q_i^{j+1}}} \pmod{p}

Ratkaisu löytyy jälleen taulukosta Silmukan loppu j :ssä Silmukan loppu kohdassa i Vaihe 3 (vastauksen löytäminen). Kaikille i : lle etsiminen löydämme kiinalaisen jäännöslauseen avulla . [7]

\log_a{b}\;\bmod{q_i^{\alpha_i}}

\log_a{b}\;\bmod\;(p-1)

Esimerkki

On tarpeen löytää diskreetti logaritmi kantaan kohdasta , toisin sanoen löytää : $28$ $2$ $GF(37)$ $x$

2^x \equiv 28 \pmod{37}

Löydämme hajoamisen . $\varphi(37) = 37 - 1 = 36 = 2^{2}\cdot3^{2}$

Me saamme . $q_{1} = 2, \alpha_{1} = 2, q_{2} = 3, \alpha_{2} = 2$

Teemme pöydän : $r_{{ij}}$

r_{20}\equiv 2^{0\cdot {\frac {37-1}{2}}}\equiv 1{\pmod {37}}

r_{21}\equiv 2^{1\cdot {\frac {37-1}{2}}}\equiv 2^{18}\equiv -1{\pmod {37}}

r_{30}\equiv 2^{0\cdot {\frac {37-1}{3}}}\equiv 1{\pmod {37}}

r_{31}\equiv 2^{1\cdot {\frac {37-1}{3))}\equiv 2^{12}\equiv 26{\pmod {37))

r_{32}\equiv 2^{2\cdot {\frac {37-1}{3))}\equiv 2^{24}\equiv 10{\pmod {37))

Me harkitsemme . Totta : $q_{1} = 2$ $x$

x\equiv x_{0} + x_{1}q_{1} \pmod{q_{1}^{\alpha_i}} \equiv x_{0} + x_{1}\cdot 2 \pmod{2^2}

Vertailusta löydämme : $x_{{0}}$

a^{x_{0}\cdot\frac{p-1}{q_{1}}} \equiv b^{\frac{p-1}{q_{1}}} \pmod{p}\Rightarrow 2 ^{x_{0}\cdot\frac{37 - 1}{2}} \equiv 28^{\frac{37-1}{2}} \equiv 28^{18} \equiv 1 \pmod{37}

Taulukosta huomaamme, että yllä oleva vertailu pitää paikkansa. $x_{0}=0$

Vertailusta löydämme : $x_{1}$

a^{x_{1}\cdot\frac{p-1}{q_{i))} \equiv (b\cdot a^{-x_{0)))^{\frac{p-1}{q_ {i}^{2}}} \Rightarrow 2^{x_{1}\cdot\frac{37 - 1}{2}} \equiv (28 \cdot 2 ^ {-0}) ^ {\frac{37 -1}{4}} \equiv 28 ^{9} \equiv -1 \pmod{37}

Taulukosta saamme, että yllä oleva vertailu pitää paikkansa. Löydämme : $x_{1} = 1$ $x$

x \equiv 0 + 1 \cdot 2 \equiv 2 \pmod{4}

Nyt mietitään . Totta : $q_{2} = 3$ $x$

x \equiv x_{0} + x_{1}\cdot3 \pmod{3^2}

Analogisesti löydämme : $x_{{0}}$ $x_{1}$

2^{x_0\cdot\frac{37 - 1}{3}} \equiv 28 ^ {\frac{37-1}{3}} \equiv 28^{12} \equiv 26 \pmod{37} \Rightarrow x_0 = 1

2^{x_1\cdot\frac{37 - 1}{3}} \equiv (28\cdot 2^{-1}) ^ {\frac{37 - 1}{3^2}} \equiv 14 ^ { 4} \equiv 10 \pmod{37} \Rightarrow x_{1} = 2

Saamme : $x$

x \equiv 1 + 2 \cdot 3 \equiv 7\pmod{9}

Saamme järjestelmän:

\begin{cases} x \equiv 2 \pmod{4} \\ x \equiv 7 \pmod{9} \\ \end{cases}

Ratkaistaan järjestelmä. Muutamme ensimmäisen vertailun tasa-arvoksi, jonka korvaamme toisella vertailulla:

x = 2 + 4 \cdot t \Rightarrow 2 + 4\cdot t \equiv 7 \pmod{9} \Rightarrow 4\cdot t \equiv 5 \pmod{9} \Rightarrow

t \equiv 5\cdot (4)^{-1} \equiv 5 \cdot (-2) \equiv -10 \equiv 8 \pmod{9}

Korvaamme löytämämme ja saamme etsimämme : $t$ $x$

x \equiv 2 + 4 \cdot 8 \equiv 34 \pmod{36} \equiv 34 \pmod{37}

Vastaus :. [kahdeksan] $x = 34$

Algoritmin monimutkaisuus

Jos laajennus (2) tunnetaan, niin algoritmin monimutkaisuus on

O\left(\sum\limits_{i=1}^{k}\alpha_{i}\left(\log_2{p} + q_{i}^{1 - r_i}(1 + \log_{2}{ q_{i}^{r_{i}}}})\right)\right)

, missä .

0\leq r_{i}\leq1

Tämä vaatii vähän muistia. [9] $O\left(\log_2{p}\sum\limits_{i=1}^{k}\left(1 + p_i^{r_i}\oikea)\oikea)$

Yleensä algoritmin monimutkaisuus voidaan myös arvioida seuraavasti

O\left(\sum\limits_{i=1}^{k}\alpha_i q_i + \log{p}\oikea)

. [kymmenen]

Jos jokaisen q i :n käsittelyssä käytetään nopeutettuja menetelmiä (esimerkiksi Shanks-algoritmi ), kokonaispistemäärä laskee

O\left(\sum\limits_{i=1}^{k}\alpha_i \sqrt{q_i} + \log{p}\oikea)

Näissä arvioissa oletetaan, että aritmeettiset operaatiot modulo p suoritetaan yhdessä vaiheessa. Itse asiassa näin ei ole - esimerkiksi modulo p -lisäys vaatii O (log p ) perusoperaatioita. Mutta koska samanlaisia tarkennuksia tehdään mille tahansa algoritmille, tämä tekijä hylätään usein.

Polynomin monimutkaisuus

Kun alkutekijät ovat pieniä, niin algoritmin monimutkaisuus voidaan arvioida muodossa . [yksitoista] $\left\{q_{i}\oikea\}_{i=1}^{k}$ $O\left((\log_2p)^2\oikea)$

Algoritmilla on yleensä polynomimonimutkaisuus siinä tapauksessa, että kaikki alkutekijät eivät ylitä , missä ovat positiivisia vakioita. [yksi] $O\left((\log p)^{c_1}\oikea)$ $\left\{q_{i}\oikea\}_{i=1}^{k}$ $(\log p)^{c_2}$
$c_1, c_2$

Esimerkki

Totta yksinkertaisille lajeille . $s$ $p=2^{\alpha} + 1,\;p=2^{\alpha_1}3^{\alpha_2} + 1$

Eksponentiaalinen monimutkaisuus

Jos on olemassa alkutekijä , jossa . [yksi] $q_{i}$ $q_i\geq p^{c}$ $c\geq 0$

Sovellus

Polig-Hellman-algoritmi on erittäin tehokas, kun se jaetaan pieniin alkutekijöihin. Tämä on erittäin tärkeää ottaa huomioon valittaessa salausmenetelmien parametreja. Muuten järjestelmä on epäluotettava. $p-1$

Huomautus

Polig-Hellman-algoritmin soveltamiseksi sinun on tiedettävä tekijöiden jako. Yleisesti ottaen tekijöiden jakamisen ongelma on melko aikaa vievä, mutta jos luvun jakajat ovat pienet (yllä mainitussa mielessä), niin tämä luku voidaan nopeasti tekijöihin lisätä jopa peräkkäisen jaon menetelmällä. Näin ollen siinä tapauksessa, että Polig-Hellman-algoritmi on tehokas, tekijöiden jakamisen tarve ei vaikeuta ongelmaa. $p-1$

Muistiinpanot

↑ 1 2 3 Vasilenko, 2003 , s. 131.
↑ Pohlig et ai, 1978 .
↑ Odlyzko, 1985 , s. 7.
↑ 1 2 Koblitz, 2001 , s. 113.
↑ Koblitz, 2001 , s. 113-114.
↑ Pohlig et ai., 1978 , s. 108.
↑ Vasilenko, 2003 , s. 130-131.
↑ Koblitz, 2001 , s. 114.
↑ Odlyzko, 1985 , s. kahdeksan.
↑ Hoffstein et al, 2008 , s. 87.
↑ Pohlig et ai., 1978 , s. 109.

Kirjallisuus

venäjäksi

N. Koblitz. Lukuteorian ja kryptografian kurssi . - M . : Tieteellinen kustantaja TVP, 2001. - 254 s. (Venäjän kieli)
O.N. Vasilenko. Numeroteoreettiset algoritmit kryptografiassa . - M .: MTSNMO, 2003. - 328 s. - 1000 kappaletta. — ISBN 5-94057-103-4 . (Venäjän kieli) Arkistoitu 27. tammikuuta 2007 Wayback Machinessa

englanniksi

SC Pohlig ja ME Hellman. Parannettu algoritmi GF(p):n logaritmien laskemiseen ja sen kryptografinen merkitys // IEEE Transactions on Information Theory. - 1978. - Voi. 1 , ei. 24 . - s. 106-110 .
A. M. Odlyzko. Diskreetit logaritmit äärellisissä kentissä ja niiden kryptografinen merkitys // T.Beth , N.Cot, I.Ingemarsson Proc. EUROCRYPT 84 -työpajan aiheesta Advances in cryptology: theory and application of cryptographic techniks. - NY, USA: Springer-Verlag New York, 1985. - P. 224-314 . - ISBN 0-387-16076-0 . (linkki ei saatavilla)
J. Hoffstein, J. Pipher, J. H. Silverman. Johdatus matemaattiseen kryptografiaan . - Springer, 2008. - 524 s. — ISBN 978-0-387-77993-5 .