Pollard-Rho Algorithmus in primer Untergruppe

Neue Frage »

Heino Auf diesen Beitrag antworten »
Pollard-Rho Algorithmus in primer Untergruppe
Meine Frage:
Guten Abend!

Ich versuche aktuell, den Pollard-Rho Algorithmus zum Lösen des diskreten Logarithmusproblems zu programmieren. Hierbei soll alpha^a = beta mod p bei Kenntnis von alpha, beta und p nach a aufgelöst werden. p ist dabei prim mit p = 2n + 1, wobei n wieder prim ist.

Mein ungefähres Problem wird hier beschrieben:
https://crypto.stackexchange.com/questions/40165/issue-implementing-pollards-rho-for-discrete-logarithms
Keine der von mir online gefundenen Implementierungen macht, was sie machen soll - selbst beigefügte Testsätze geben meist falsche Ergebnisse aus.

Meine Beispielzahlen sind p = 1234547, alpha = 2 und beta = 1208341. Das korrekte Ergebnis sollte 654321 sein, da 2^654321 = 1208341 mod 1234547. Einen kurzen Pseudocode habe ich unten angegeben.

Das Problem ist offenbar, dass p - 1 gerade ist, daher hat der Nenner des Ergebnisses a = (x2 - x1) / (y1 - y2) zu 50% keine Inverse mod p - 1. Wie im Link oben gesagt wurde, sollte man daher in der primen Untergruppe rechnen, ich zitiere:

If we do have to do the work in a group with a size that has small factors, say, N=hq, where h is smooth, and q has no small factors, then what we can do is compute a^h and b^h, and use Pollards-Rho to compute x' such that (a^h)x' = (b^h); this is in the q-sized subgroup, and so has a high probability of success. Given x', it's easy to reconstruct x, as x = x' (mod q)

D.h. hier wäre h = 2 und q = n. Aber auch wenn ich meinen Algorithmus auf alpha^2 und beta^2 ansetze, um mit mod n statt mod 2n rechnen zu können, kommt nicht das richtige raus (außer ich habe den "reconstruct" Part falsch interpretiert)...

Meine Ideen:
n = p-1
x1 = 0
y1 = 0
x2 = 0
y2 = 0
k1 = 1
k2 = 1
i = 1

while (i <= n)
{
k1, x1, y1 = f(k1, x1, y1, alpha, beta, p, n)
k2, x2, y2 = f(k2, x2, y2, alpha, beta, p, n)
k2, x2, y2 = f(k2, x2, y2, alpha, beta, p, n)
i = i + 1
if (k1 == k2) break
}

r = (y1 - y2) % n
r = inverse(r,n) // r^-1 mod n
a = ((x2 - x1) * r) % n
return a

f(k, x, y, alpha, beta, p, n)
{
if (k % 3 == 0) return (alpha * k) % p, (x + 1) % n, (y) % n
if (k % 3 == 1) return (beta * k) % p, (x) % n, (y + 1) % n
if (k % 3 == 2) return (k * k) % p, (x + x) % n, (y + y) % n
}

Sorry im Vorfeld für die unsaubere Schreibweise etc, kann gerade leider nur vom Laptop aus schreiben.
Heino Auf diesen Beitrag antworten »

Hat sich erledigt!

Falls jemand den Thread hier findet und das gleiche Problem hat:

gegeben: a, b, p mit a^x = b mod p, gesucht: x
Problem: p - 1 ist gerade -> Inversenberechnung schlägt zu 50% fehl

=> Lösung:
berechne
n = (p - 1) / 2,
a' = a^2,
b' = b^2
und führe den Pollard-Rho Algorithmus normal mit den Parametern a', b', n, p aus

Das Ergebnis x' ist nun kongruent zu dem "richtigen" x mod n, d.h. wir überprüfen:
wenn a^x' = b mod p, ist x' = x
wenn nicht: x = x' + n
dann sollte a^x = b mod p sein, sonst stimmt etwas anderes nicht (zb könnte n immer noch nicht prim sein, dann einfach n, a' und b' weiter anpassen, bis n prim ist).
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »