Polig-Hellman algoritmus

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. április 23-án felülvizsgált verziótól ; az ellenőrzések 2 szerkesztést igényelnek .

A Polyg-Hellman algoritmus (ezt Silver-Polig-Hellman algoritmusnak is nevezik ) egy determinisztikus diszkrét logaritmus -algoritmus a maradékok gyűrűjében, prímszám modulo . Az algoritmus egyik sajátossága, hogy speciális alakú prímszámok esetén a diszkrét logaritmus polinomiális időben található. [egy]

Történelem

Ezt az algoritmust Roland Silver amerikai matematikus találta fel , de először két másik amerikai matematikus , Stephen Pohlig és Martin Hellman tették közzé 1978 -ban „ Egy továbbfejlesztett algoritmus a GF(p) logaritmusszámításhoz és annak kriptográfiai jelentősége” [2] című cikkében. , aki Roland Silvertől függetlenül fejlesztette ki ezt az algoritmust. [3]

Kiinduló adatok

Legyen megadva az összehasonlítás

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

(egy)

és egy szám prímtényezőkre való felbontása ismert: $p-1$

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

(2)

Olyan számot kell találni, amely kielégíti az összehasonlítást (1). [négy] $x,\;0\leq x < p-1$

Az algoritmus ötlete

Az algoritmus lényege, hogy elég mindenkinek modult találni , majd a kínai maradéktétel segítségével megtalálhatjuk az eredeti összehasonlítás megoldását . Az egyes modulok megtalálásához meg kell oldania az összehasonlítást: $x$ $q_i^{\alpha_i}$ $én$
$x$

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

. [5]

Az algoritmus leírása

Egyszerűsített változat

A legjobb módja ennek az algoritmusnak az, ha figyelembe vesszük azt a speciális esetet, amikor . $p = 2^n + 1$

Adva van , és , miközben van egy primitív elem , és meg kell találnunk azt , amelyik kielégíti . $a$ $p$ $b$ $a$ $GF(p)$ $x$ $a^x\equiv b\pmod{p}$

Feltételezzük, hogy mivel nem különböztethető meg a -tól , mert esetünkben a primitív elemnek definíció szerint van foka , ezért: $0\leq x \leq p-2$ $x=p-1$ $x=0$ $a$ $p-1$

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

Mikor , könnyen meghatározható bináris kiterjesztéssel együtthatókkal , például: $p = 2^n + 1$ $x$ $\{q_0, q_1,\pontok, 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}

A legkisebb jelentőségű bitet hatványra emeléssel és a szabály alkalmazásával határozzuk meg $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}

A felső szabály levezetése

Tekintsük a korábban kapott összehasonlítást :

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

de definíció szerint más értéket vesz fel, mint , így már csak egy összehasonlítás maradt : $a$ $(p-1)/2 < p - 1$ $egy$

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

Emelje az (1) összehasonlítást hatványra , és helyettesítse a fent kapott összehasonlítást: $(p-1)/2$

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

Az egyenlőség akkor igaz, ha páros, vagyis a polinom alakjában történő bővítésnél a szabad tag egyenlő -val , ezért igaz, ha . $(-1)^x=1$ $x$ $q_{0}$ $0$ $(-1)^x = -1$ $q_0 = 1$

Most átalakítjuk az ismert dekompozíciót és bevezetünk egy új változót : $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}

ahol

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 -egy}

Nyilvánvaló, hogy osztható mikor -vel , és mikor osztható -vel , de már nem. $x_{1}$ $négy$ $q_1=0$ $q_1=1$ $2$ $négy$

A korábbiakhoz hasonlóan érvelve megkapjuk az összehasonlítást :

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

amelyből azt találjuk . $q_{1}$

A fennmaradó biteket hasonló módon kapjuk meg. Írjuk fel a keresés általános megoldását új jelöléssel: $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}

ahol

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

Tehát a hatalomra emelés a következőket adja: $z_{i}$ $m_i$

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

Következésképpen:

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

amelyből azt találjuk . $q_{i}$

Miután megtaláltuk az összes bitet, megkapjuk a kívánt megoldást . [6] $x$

Példa

Adott:

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

Megtalálja:

x

Megoldás:
megkapjuk . Ezért így néz ki: $p-1=2^4$ $x$

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

Találjuk : $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} \Jobbra q_0 = 1

Számítunk még : $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

Találjuk : $q_{1}$

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

Számítunk még : $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

Találjuk : $q_{2}$

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

Számítunk még : $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 \ ekvivalens (-4) \cdot 4 \equiv -16 \equiv 1 \pmod{17}

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

Találjuk : $q_{3}$

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

Találja meg, amit keres : $x$

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

Válasz: $x=7$

Alapleírás

1. lépés (a táblázat összeállítása). Készítsen értéktáblázatot , ahol

\{r_{i,j}\}

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

2. lépés (számítás ).

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

i -re 1 -től k - ig : Hadd

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)),

ahol

0\leq x_i\leq q_i-1

. Akkor helyes az összehasonlítás:

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

Legjobb összehasonlító kimenet

Emeljük fel az (1) összehasonlítás bal és jobb oldalát a hatványra : $(p-1)/q_i$

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

Helyettesítse és alakítsa át az összehasonlítást: $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}

Mert primitív elem, ezért a forma összehasonlítása: $a$

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

Kapunk

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}

[négy] Az 1. lépésben összeállított táblázatot használva megtaláljuk a For j -t 0-tól

x_{0}.

\alpha_{i}-1

Ha figyelembe vesszük az összehasonlítást

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}

A megoldás ismét a táblázatban található A hurok vége a j -n A hurok vége az i -n 3. lépés (a válasz megtalálása). Minden i -re keresve a kínai maradéktételt kapjuk . [7]

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

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

Példa

Meg kell találni a diszkrét logaritmust a bázishoz , más szóval meg kell keresni : $28$ $2$ $GF(37)$ $x$

2^x \equiv 28 \pmod{37}

Dekompozíciót találunk . $\varphi(37) = 37 - 1 = 36 = 2^{2}\cdot3^{2}$

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

Készítünk egy táblázatot : $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))

fontolgatjuk . Igazság szerint: $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}

Összehasonlításból ezt kapjuk : $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}

A táblázatból azt találjuk, hogy a fenti összehasonlítás igaz. $x_{0}=0$

Összehasonlításból ezt kapjuk : $x_{1}$

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

A táblázatból azt kapjuk, hogy a fenti összehasonlítás igaz. Találjuk : $x_{1} = 1$ $x$

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

Most mérlegeljük . Igazság szerint: $q_{2} = 3$ $x$

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

Analógia alapján a következőket találjuk : $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} \Jobbra 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} \Jobbra x_{1} = 2

Kapunk : $x$

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

Megkapjuk a rendszert:

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

Oldjuk meg a rendszert. Az első összehasonlítást egyenlőséggé alakítjuk, amit a második összehasonlítással helyettesítünk:

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}

Cseréljük, amit találtunk , és azt kapjuk, amit keresünk : $t$ $x$

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

Válasz: . [nyolc] $x=34$

Az algoritmus összetettsége

Ha ismerjük a (2) kiterjesztést, akkor az algoritmus összetettsége igen

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}}}})\jobbra)\jobbra)

, hol .

0\leq r_{i}\leq1

Ez egy kis memóriát igényel. [9] $O\left(\log_2{p}\sum\limits_{i=1}^{k}\left(1 + p_i^{r_i}\right)\right)$

Általánosságban elmondható, hogy az algoritmus bonyolultsága úgy is megbecsülhető

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

. [tíz]

Ha minden q i feldolgozása során gyorsított módszereket használunk (például a Shanks algoritmust ), akkor az összpontszám a következőre csökken.

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

Ezekben a becslésekben feltételezzük, hogy a modulo p aritmetikai műveleteket egy lépésben hajtják végre. Valójában nem ez a helyzet – például a modulo p összeadáshoz O (log p ) elemi műveletek szükségesek . De mivel hasonló finomítások történnek bármely algoritmusnál, ezt a tényezőt gyakran elvetik.

Polinom komplexitás

Ha a prímtényezők kicsik, akkor az algoritmus összetettsége a következőképpen becsülhető meg . [tizenegy] $\left\{q_{i}\right\}_{i=1}^{k}$ $O\left((\log_2p)^2\jobb)$

Az algoritmus általában polinomiális komplexitású abban az esetben, ha az összes prímtényező nem haladja meg a -t , ahol pozitív állandók vannak. [egy] $O\left((\log p)^{c_1}\jobb)$ $\left\{q_{i}\right\}_{i=1}^{k}$ $(\log p)^{c_2}$
$c_1, c_2$

Példa

Igaz az egyszerű fajokra . $p$ $p=2^{\alpha} + 1,\;p=2^{\alpha_1}3^{\alpha_2} + 1$

Exponenciális összetettség

Ha van olyan prímtényező , ahol . [egy] $q_{i}$ $q_i\geq p^{c}$ $c\geq 0$

Alkalmazás

A Polig-Hellman algoritmus kis prímtényezőkre bontva rendkívül hatékony . Ezt nagyon fontos figyelembe venni a kriptográfiai sémák paramétereinek kiválasztásakor. Ellenkező esetben a rendszer megbízhatatlan lesz. $p-1$

Megjegyzés

A Polig-Hellman algoritmus alkalmazásához ismernie kell a faktorizációt. Általános esetben a faktorizációs probléma meglehetősen időigényes, de ha egy szám osztói kicsik (a fent említett értelemben), akkor ez a szám gyorsan faktorizálható akár az egymást követő osztás módszerével is. Így abban az esetben, ha a Polig-Hellman algoritmus hatékony, a faktorizálás szükségessége nem bonyolítja a problémát. $p-1$

Jegyzetek

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

Irodalom

oroszul

N. Koblitz. Számelmélet és kriptográfia tanfolyam . - M . : TVP Tudományos Kiadó, 2001. - 254 p. (Orosz)
O. N. Vaszilenko. Számelméleti algoritmusok a kriptográfiában . - M. : MTSNMO, 2003. - 328 p. - 1000 példányban. — ISBN 5-94057-103-4 . (Orosz) Archiválva 2007. január 27-én a Wayback Machine -nél

angolul

SC Pohlig és ME Hellman. Továbbfejlesztett algoritmus a GF(p) logaritmusok kiszámításához és kriptográfiai jelentősége // IEEE Transactions on Information Theory. - 1978. - 1. évf. 1 , sz. 24 . - 106-110 . o .
A. M. Odlyzko. Diszkrét logaritmusok véges mezőben és kriptográfiai jelentősége // T.Beth , N.Cot, I.Ingemarsson Proc. Az EUROCRYPT 84 műhelymunkája: Fejlődés a kriptológiában: kriptográfiai technikák elmélete és alkalmazása. - NY, USA: Springer-Verlag New York, 1985. - P. 224-314 . - ISBN 0-387-16076-0 . (nem elérhető link)
J. Hoffstein, J. Pipher, J. H. Silverman. Bevezetés a matematikai kriptográfiába . - Springer, 2008. - 524 p. — ISBN 978-0-387-77993-5 .