Baby-steps giant-steps-algoritme

Het baby-steps giant-steps-algoritme is een algoritme om de discrete logaritme zoals die in een cyclische groep is gedefinieerd, te berekenen. Het grote nadeel ten opzichte van Pollards rho-algoritme is dat voor deze methode opslagruimte nodig is.

Theorie

Het algoritme is gebaseerd op het inruilen van rekentijd voor dataopslag en is een tamelijk eenvoudige modificatie van de brute force attack, de primitieve methode voor het berekenen van een discrete logaritme.

Laat $G$ een cyclische groep van orde $q$ zijn, $g\in G$ een voortbrenger van $G$ en $h\in G$ een willekeurig element. Gezocht wordt het positieve getal $n<q$, zodat $g^{n}=h{\pmod {q}}$.

Stel $n\leq N$ en herschrijf $n=im+j$, met $0\leq i<m$ en $0\leq j<m$, zodat

$g^{j}=h(g^{-m})^{i}{\pmod {q}}$.

Kies voor $m$ een waarde in de ordegrootte ${\sqrt {N}}$. Vervolgens wordt er een gesorteerde lijst gemaakt met daarin de berekende waarden voor $g^{j}$, de zogenaamde baby-steps. Daarna worden de waarden $h(g^{-m})^{i}$ berekend, de zogenaamde giant-steps en getest of een van deze waarden in de tabel met baby-steps voorkomt. Als dat niet zo is, kan een volgende waarde van $m$ gekozen worden.

Werking van het algoritme

Input: een cyclische groep G van orde n met een voortbrenger g en een groepelement h.

Output: een waarde n die voldoet aan de congruentie $g^{n}$=h.

1. m $\leftarrow$ bovengrens ${\sqrt {N}}$
2. voor alle j met 0$\leq$j<m: bereken $g^{j}$ en bewaar het paar $(j,g^{j})$ in een tabel
3. bereken $g^{-m}$
4. q $\leftarrow$ h
5. voor i = 0 tot m-1:
   1. controleer om te zien of q de tweede component $g^{j}$ is van elk paar in de tabel
   2. als dat zo is, geef im + j terug
   3. als dat niet zo is, q $\leftarrow$q·${g}^{-m}$

In de praktijk

De beste manier op het algoritme sneller te laten verlopen, is gebruik te maken van een efficiënte tabel. In dit geval is een hashtabel de beste. De hashing wordt uitgevoerd op de tweede component en de tabel wordt gesorteerd naar deze waarden. Om de controle in stap 1 uit te voeren van de hoofdloop, wordt de hashwaarde van q berekend en met de hashtabel vergeleken. Het is efficiënter niet de tabel te berekenen, maar het paar (j,$g^{j}$)in het geheugenadres hash($g^{j}$) op te slaan. Voor elke waarde van ${hg}^{-im}$ wordt het geheugenadres hash($g^{j}$) gecontroleerd. Omdat de hashtabel elementen kan terugvinden en optellen in tijdorde O(1) (constante tijd), zal dit het algoritme niet langzamer doen verlopen, maar juist sneller.

De complexiteit van het algoritme is O(${\sqrt {N}}$). De keuze van m is hiervoor van belang en hiermee hangt de maximale waarde van i direct samen en de maximale waarde van j indirect. Als m in de ordegrootte ${\sqrt {N}}$ is, dan i ook, want het product m·i moet maximaal n zijn.

Voorbeelden

Hier volgt eerst een algemeen voorbeeld en daarna volgen enkele voorbeelden met kleine getallen om met behulp van het algoritme een discrete logaritme op te lossen. In de praktijk rekent men uiteraard met veel grotere getallen om de aanvallen van krakers af te slaan.

Stel we willen oplossen h = n·g, met h en g bekend en n een positief geheel getal kleiner dan 100. We kunnen dan voor n = 0, 1, 2, ... gaan rekenen hoe groot n·g is en dat vergelijken met h. In het slechtste geval zijn we pas klaar in 100 stappen (als n = 99); gemiddeld duurt het 50 stappen. We kunnen n echter zien als het getal ab, waarbij a de tientallen voorstelt en b de eenheden, m.a.w. n = 10a + b. In plaats van n te vinden, kunnen we a en b vinden. We schrijven het probleem op als h = (10a + b)g ofwel h - bg = 10ag. We kunnen nu het linkerlid uit gaan rekenen voor alle mogelijke waarden van b. Dit zijn de waarden 0 t/m 9. Dit zijn de zogenaamde baby-steps. We weten dat een van deze waarden van b degene is die we zoeken. We slaan alle uitkomsten van het linkerlid op in een tabel. Daarna gaan we het rechterlid uitrekenen voor verschillende waarden van a. Dit zijn ook de waarden 0 t/m 9 en één ervan is de juiste, die samen met de juiste b de oplossing geeft voor n. De juiste a maakt van h - bg = 10ag een ware bewering. We moeten dus bij elke waarde van a het rechterlid berekenen en kijken of de uitkomst in de tabel staat. Als dat zo is, dan zijn we klaar en weten we welke a en b we moeten hebben om n = 10a + b te vinden. Hierin zien we de snelheid van het algoritme. Het is in gemiddeld 1,5${\sqrt {n}}$ stappen klaar. In het slechtste geval zijn 2${\sqrt {n}}$ nodig.

Gegeven $2^{n}$ = 28 (mod 37). Bereken n. Aanpak: We maken eerst een tabel voor de baby-steps. We kiezen m = 6 (ordegrootte ${\sqrt {36}}$). We laten j dus lopen vanaf 0 t/m 6.

j	1	2	3	4	5	6
$2^{j}$	2	4	8	16	32	27

We berekenen $2^{-6}$ = 11 (mod 37) en maken voor de giant-steps:

i	0	1	2	3	4	5
$2^{-6i}$·$2^{n}$ = 28·$2^{-6i}$	28	12	21	9	25	16

We zien in de tweede tabel bij i = 5 voor het eerst een waarde die ook in de eerste tabel staat en concluderen: $2^{4}=2^{n}$·$2^{-30}$. Hier is -30 = -6·5. We zijn nu in staat n te berekenen: n = mi + j = 6·5 + 4 = 34. Bij gemiddeld aantal stappen 1,5${\sqrt {37}}$ hadden we 1,5·6 = 15 nodig gehad. 6 voor de baby-steps en ongeveer 3 voor de giant-steps. Het werden er 5 voor de giant-steps

Gegeven is $6^{n}$ = 7531 (mod 8101). Bereken n. Aanpak: We maken eerst een tabel voor de baby-steps. We kiezen m = 90 (ordegrootte ${\sqrt {8101}}$). We laten j lopen vanaf 0 t/m 90.

j	1	2	3	4	5	6	...	28	29	...	90
$6^{j}$	6	36	216	1296	7776	6151	...	1144	6864	...	7997

We berekenen $6^{-90}$ = 6621 (mod 8101) en maken voor de giant-steps:

i	...	73	74
$6^{-90i}$·$2^{n}$ = 6621·$2^{-6i}$	...	7133	6864

We zien in de tweede tabel bij i = 74 voor het eerst een waarde die ook in de eerste tabel staat en concluderen: n = mi + j = 90·74 + 29 = 6689. Bij gemiddeld aantal stappen 1,5${\sqrt {8101}}$ hadden we 1,5·90 = 135 nodig gehad. 90 voor de baby-steps en ongeveer 45 voor de giant-steps. Het werden er nog 74 voor de giant-steps.

Zie ook

• Indexcalculusalgoritme
• Pohlig-Hellman-algoritme
• Pollards lambda-algoritme
• Pollards rho-algoritme