Forging RSA Moduli for X.509 Certificates

File: ssl.png (15KB, 284x231px)

15KB, 284x231px

https://www.win.tue.nl/~bdeweger/CollidingCertificates/CollidingCertificates.pdf

Do any of you guys have experience doing this? I'm following the procedure given, but I can't figure out how to efficiently find the two colliding RSA moduli (step 4).

> generate random primes p1 and p2 of approximately 512 bits, such that e is coprime to p1 − 1 and p2 − 1;
> compute b0 between 0 and p1p2 such that p1|b12 1024 + b0 and p2|b22 1024 + b0 (by the Chinese Remainder Theorem);
> let k run through 0, 1, 2, . . ., and for each k compute b = b0 + kp1p2; check whether both q1 = (b1 * 2^1024 + b)/p1 and q2 = (b2 * 2^1024 + b)/p2 are primes, and whether e is coprime to both q1 − 1 and q2 − 1;
> when k has become so large that b ≥ 2 1024, restart with new random primes p1, p2;
> when primes q1 and q2 have been found, stop, and output n1 = b1 * 2^1024 + b and n2 = b2 * 2^1024 + b (as well as p1, p2, q1, q2).