Polig-Hellman algoritm

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 23 april 2020; kontroller kräver 2 redigeringar .

Polyg-Hellman-algoritmen (även kallad Silver-Polig-Hellman-algoritmen ) är en deterministisk diskret logaritmalgoritm i ringen av rester modulo ett primtal . En av funktionerna i algoritmen är att för primtal av en speciell form kan du hitta den diskreta logaritmen i polynomtid . [ett]

Historik

Denna algoritm uppfanns av den amerikanske matematikern Roland Silver , men publicerades först av två andra amerikanska matematiker Stephen Pohlig och Martin Hellman 1978 i artikeln " En förbättrad algoritm för att beräkna logaritmer över GF(p) och dess kryptografiska betydelse" [2] , som utvecklade denna algoritm oberoende av Roland Silver. [3]

Inledande data

Låt jämförelsen ges

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

(ett)

och nedbrytningen av ett tal till primfaktorer är känd: $p-1$

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

(2)

Det är nödvändigt att hitta ett tal som uppfyller jämförelsen (1). [fyra] $x,\;0\leq x < p-1$

Idén med algoritmen

Kärnan i algoritmen är att det räcker med att hitta moduler för alla , och sedan kan lösningen på den ursprungliga jämförelsen hittas med hjälp av den kinesiska restsatsen . För att hitta för var och en av dessa moduler måste du lösa jämförelsen: $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]

Beskrivning av algoritmen

Förenklad version

Det bästa sättet att hantera denna algoritm är att överväga det speciella fallet där . $p = 2^n + 1$

Vi är givna , och medan det finns ett primitivt element och vi måste hitta ett som tillfredsställer . $a$ $sid$ $b$ $a$ $GF(p)$ $x$ $a^x\equiv b\pmod{p}$

Det antas att , eftersom det inte går att skilja från , eftersom det primitiva elementet i vårt fall per definition har en grad , därför: $0\leq x \leq p-2$ $x=p-1$ $x=0$ $a$ $p-1$

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

När , är det lätt att bestämma genom binär expansion med koefficienter , till exempel: $p = 2^n + 1$ $x$ $\{q_0, q_1,\dots, 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}

Den minst signifikanta biten bestäms genom att höja till en potens och tillämpa regeln $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}

Härledning av den övre regeln

Tänk på den tidigare erhållna jämförelsen :

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

men per definition antar ett annat värde än , så det finns bara en jämförelse kvar : $a$ $(p-1)/2 < p - 1$ $ett$

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

Höj jämförelsen (1) till en potens och ersätt jämförelsen som erhållits ovan: $(p-1)/2$

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

Jämlikheten är sant om det är jämnt, det vill säga i expansionen i form av ett polynom, är den fria termen lika med , Därför är det sant när . $(-1)^x=1$ $x$ $q_{0}$ $0$ $(-1)^x = -1$ $q_0 = 1$

Nu transformerar vi den kända nedbrytningen och introducerar en ny variabel : $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}

var

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

Det är klart att det är delbart med när , och när är delbart med , men inte längre. $x_{1}$ $fyra$ $q_1=0$ $q_1=1$ $2$ $fyra$

Om vi argumenterar som tidigare får vi jämförelsen :

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

som vi finner . $q_{1}$

De återstående bitarna erhålls på liknande sätt. Låt oss skriva den allmänna lösningen för att hitta med ny notation: $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}

var

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

Så att höja till en makt ger: $z_{i}$ $mi$

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

Följaktligen:

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

som vi finner . $q_{i}$

Efter att ha hittat alla bitar får vi den nödvändiga lösningen . [6] $x$

Exempel

Given:

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

Hitta:

x

Lösning:
Vi får . Därför ser det ut som: $p-1=2^4$ $x$

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

Vi finner : $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

Vi räknar även : $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

Vi finner : $q_{1}$

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

Vi räknar även : $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

Vi finner : $q_{2}$

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

Vi räknar även : $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

Vi finner : $q_{3}$

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

Hitta det du letar efter : $x$

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

Svar: $x=7$

Grundläggande beskrivning

Steg 1 (sammanställning av tabellen). Gör en värdetabell , där

\{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 -ett\}.

Steg 2 (beräkning ).

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

För i från 1 till k : Låta

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

var

0\leq x_i\leq q_i-1

. Då är jämförelsen korrekt:

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

Topp jämförelseutgång

Låt oss höja de vänstra och högra delarna av jämförelsen (1) till makten : $(p-1)/q_i$

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

Ersätt och transformera jämförelsen: $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}

Därför att är ett primitivt element, därför jämförelser av formen: $a$

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

Vi får

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}

[fyra] Med hjälp av tabellen sammanställd i steg 1 hittar vi For j från 0 till

x_{0}.

\alpha_{i}-1

Funderar på en jämförelse

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}

Lösningen återfinns i tabellen End of loop on j End of loop on i Steg 3 (att hitta svaret). Att hitta för allt i , finner vi genom den kinesiska restsatsen . [7]

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

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

Exempel

Det är nödvändigt att hitta den diskreta logaritmen till basen i , med andra ord, hitta för: $28$ $2$ $GF(37)$ $x$

2^x \equiv 28 \pmod{37}

Vi finner en nedbrytning . $\varphi(37) = 37 - 1 = 36 = 2^{2}\cdot3^{2}$

Vi får . $q_{1} = 2, \alpha_{1} = 2, q_{2} = 3, \alpha_{2} = 2$

Vi gör ett bord : $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))

Vi överväger . För sant: $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}

Vi finner från jämförelse: $x_{{0}}$

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

Från tabellen finner vi att jämförelsen ovan är sann. $x_{0}=0$

Vi finner från jämförelse: $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}

Från tabellen får vi att jämförelsen ovan är sann. Vi finner : $x_{1} = 1$ $x$

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

Nu funderar vi på . För sant: $q_{2} = 3$ $x$

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

I analogi finner vi : $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

Vi får : $x$

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

Vi får systemet:

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

Låt oss lösa systemet. Vi omvandlar den första jämförelsen till jämlikhet, som vi ersätter med den andra jämförelsen:

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}

Vi ersätter det vi hittat och får det vi letar efter : $t$ $x$

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

Svar: . [åtta] $x=34$

Algoritmens komplexitet

Om expansion (2) är känd, är algoritmens komplexitet det

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)

, var .

0\leq r_{i}\leq1

Detta kräver lite minne. [9] $O\left(\log_2{p}\sum\limits_{i=1}^{k}\left(1 + p_i^{r_i}\right)\right)$

I allmänhet kan algoritmens komplexitet också uppskattas som

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

. [tio]

Om accelererade metoder används vid bearbetning av varje qi (till exempel Shanks -algoritmen ), kommer den totala poängen att minska till

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

I dessa uppskattningar antas det att aritmetiska operationer modulo p utförs i ett steg. I själva verket är detta inte fallet - till exempel kräver addition modulo p O (log p ) elementära operationer. Men eftersom liknande förbättringar äger rum för någon algoritm, förkastas denna faktor ofta.

Polynom komplexitet

När primfaktorerna är små kan algoritmens komplexitet uppskattas till . [elva] $\left\{q_{i}\right\}_{i=1}^{k}$ $O\vänster((\log_2p)^2\höger)$

Algoritmen har polynomkomplexitet i allmänhet i fallet när alla primtalsfaktorer inte överstiger , där är positiva konstanter. [ett] $O\vänster((\log p)^{c_1}\höger)$ $\left\{q_{i}\right\}_{i=1}^{k}$ $(\log p)^{c_2}$
$c_1, c_2$

Exempel

Sant för enkla arter . $sid$ $p=2^{\alpha} + 1,\;p=2^{\alpha_1}3^{\alpha_2} + 1$

Exponentiell komplexitet

Om det finns en primtal faktor så att , var . [ett] $q_{i}$ $q_i\geq p^{c}$ $c\geq 0$

Applikation

Polig-Hellman-algoritmen är extremt effektiv när den sönderdelas i små primfaktorer. Detta är mycket viktigt att tänka på när du väljer parametrarna för kryptografiska system. Annars kommer systemet att vara opålitligt. $p-1$

Notera

För att tillämpa Polig-Hellman-algoritmen måste du känna till faktoriseringen. I det allmänna fallet är faktoriseringsproblemet ganska tidskrävande, men om divisorerna för ett tal är små (i den mening som nämnts ovan), kan detta tal snabbt faktoriseras även med metoden för successiv division. Således, i det fall där Polig-Hellman-algoritmen är effektiv, komplicerar inte behovet av faktorisering problemet. $p-1$

Anteckningar

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

Litteratur

på ryska

N. Koblitz. En kurs i talteori och kryptografi . - M . : Vetenskapligt förlag TVP, 2001. - 254 sid. (ryska)
O. N. Vasilenko. Talteoretiska algoritmer i kryptografi . - M. : MTSNMO, 2003. - 328 sid. - 1000 exemplar. — ISBN 5-94057-103-4 . (ryska) Arkiverad 27 januari 2007 på Wayback Machine

på engelska

SC Pohlig och ME Hellman. En förbättrad algoritm för att beräkna logaritmer över GF(p) och dess kryptografiska betydelse // IEEE-transaktioner på informationsteori. - 1978. - Vol. 1 , nej. 24 . - S. 106-110 .
A. M. Odlyzko. Diskreta logaritmer i finita fält och deras kryptografiska betydelse // T.Beth , N.Cot, I.Ingemarsson Proc. av EUROCRYPT 84-workshopen om framsteg inom kryptologi: teori och tillämpning av kryptografiska tekniker. - NY, USA: Springer-Verlag New York, 1985. - P. 224-314 . - ISBN 0-387-16076-0 . (inte tillgänglig länk)
J. Hoffstein, J. Pipher, J.H. Silverman. En introduktion till matematisk kryptografi . - Springer, 2008. - 524 sid. — ISBN 978-0-387-77993-5 .