B1b5

Het Baby-steps giant-steps algoritme is een algoritme om het Discrete Logaritme Probleem (DLP) zoals dat is gedefinieerd in een cyclische groep te berekenen. Het grote nadeel ten opzichte van de Pollard's rho algoritme is dat voor deze methode opslagruimte nodig is.

Theorie

Het algoritme is gebaseerd op een space time tradeoff, een tamelijk eenvoudige modificatie van de brute force attack, de ongekunstelde methode voor een DLP.

Laat G een cyclische groep van orde q zijn. Laat g Є G voortbrenger zijn van G en h Є G. We zoeken het positieve getal n dat kleiner is dan q zodat gⁿ=h.
Laat n bovengrens N hebben.
Het algoritme herschrijft n als n = im + j, met m = |√N| en 0≤i<men 0≤j<m. Hierdoor wordt de congruentie gⁿ=h gewijzigd in h(g^-m) ^j =g^j. Er wordt een waarde voor m gekozen in de ordegrootte √N. Vervolgens wordt er een gesorteerde tabel met daarin berekende waarden voor g ^j, de zogenaamde baby-steps en daarna wordt een waarde h(g^-m) ^j berekend, de zogenaamde giant-steps. Er wordt getest of de waarde h(g^-m) ^j in de tabel met baby-steps voorkomt. Als dat niet zo is, dan kan een volgende waarde h(g^-m) ^j worden berekend.

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ⁿ=h.

1. m ← bovengrens √N
2. voor alle j met 0≤j<m: bereken g ^j en bewaar het paar (j,g^j) in een tabel
3. bereken g ^{− m}
4. q ← 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 ←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(√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 √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 m.b.v. het algoritme een DLP 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 één 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√n stappen klaar. In het slechtste geval zijn 2√n nodig.

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

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

We zien in de tweede tabel bij i = 5 voor het eerst een waarde die ook in de eerste tabel staat en concluderen: 2⁴ = 2 ⁿ·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√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 ⁿ = 7531 (mod 8101). Bereken n. Aanpak: We maken eerst een tabel voor de baby-steps. We kiezen m = 90 (ordegrootte √8101). We laten j lopen vanaf 0 t/m 90.

We berekenen 6 ^{− 90} = 6621 (mod 8101)

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 stappen1,5√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.