Pollard-Rho Algorithmus in primer Untergruppe |
19.05.2018, 19:41 | Heino | Auf diesen Beitrag antworten » |
Pollard-Rho Algorithmus in primer Untergruppe 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. |
||
20.05.2018, 12:12 | 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). |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|