p => random big prime, below 64bits
q => random big prime, below 64bits
e => random small prime, below 16bits
k => random small integer, below 16 bits
N = p * q
d = (k * ((p - 1) * (q - 1)) + 1) / e
(e, N) => Public key
(e, d, p, q) => Private key
RSAEncode(m, e, N) // m => message, e and N are public key
h ≡ m ^ e mod N
RSADecode(h, d, N) // h => encrypted message, d is part of private key
m ≡ h ^ d mod N
RSACrack_GetPrivateKeyFromPublicKey(e, N, minPrimeBitsLength)
bitLength = GetBitsLength(N)
k = 2
// iterator uses sieve algorithm
primes = all64BitsPrimes.Select(p => GetBitsLength(p) >= minPrimeBitsLength && GetBitsLength(p) <= (bitLength - minPrimeBitsLength))
// Example Primes buffer uses 4GB memory, all below 64Bits primes use 1TB memory
// use only odd numbers bit array
// max 256 cycles
index = -1
for primesBuffer1 of primes
index++
for primesBuffer2 of primes.NextTo(index) // next buffers from index, including index. buffer. if you use ModMul, remove this line
for p of primesBuffer1
for q of primesBuffer2 // if you use ModMul, remove this line
bitLengthA = GetBitsLength(p)
bitLengthB = GetBitsLength(q)
bitSum = bitLengthA + bitLengthB
if (max(bitLengthA, bitLengthB) >= bitLength && bitSum <= bitLength)
if (p * q == N) // or (N % p == 0) or ModMul(N+1, 10, p) == 10
d = (k * ((p - 1) * (q - 1)) + 1) / e
return (e, d, p, q)
For RSA this code results much faster.
I expect you to write basic pseudocode for Kangaroo. Thanks.
k = 2
SqrtN = Sqrt(N)
if((SqrtN & 1) == 0) SqrtN++
for(p = SqrtN; p > 2; p-=2)
if (true/*You can use more filters for p*/ && ModPow(2, p-1, p) == 1 && ModMul(N+1, 10, p) == 10)
q = N / p
d = (k * ((p - 1) * (q - 1)) + 1) / e
return (e, d, p, q)
[moderator's note: consecutive posts merged]