Paranoid Cryptography: Pollard’s p-1 method and Powersmooth
Paranoid Cryptography: Pollard’s p-1 method and Powersmooth
The Paranoid Cryptography website is cool [2] and has lots of examples of vulnerabilities that could affect your code. One method relates to the Pollard p-1 method, and whether it is power smooth.
RSA is used in many areas of cybersecurity and is often key in proving the identity of a person or a remote Web site. But, the strength of RSA depends on the prime numbers (p and q) selected to provide the modulus (n=p.q). If there are weaknesses in the selection of p and q, it may be possible to factorize the modulus and thus discover the private key. One method that can be used to discover whether we have weak prime numbers is the Pollard p-1 method. John Pollard [1], in 1974, defined a method of factorization which factorized values into their prime number roots. It finds these factors when the value of p-1 is powersmooth.
Smooth numbers are used in cryptography to provide fast factorization methods. A smooth number is defined as a number whose factors are smaller than a given value. For a 5-smooth number, the factors must be equal to five or less. Every value -apart from prime numbers — can be reduced to the multiplication of prime numbers. For example 102 is equal to 2 x 3 x 17 [here]. A value of 56 is 2 x 2 x 2 x 7, and is thus 7-smooth, but not 3-smooth nor 5-smooth.
With powersmooth, we say we are B-powersmooth, if all the prime number powers up to v are:
and where v is the power of a prime number. For example, with 720 (2 ×2 × 2× 2 × 3 ×3× 5×5 =2⁴×3³×5²) will be 5-smooth, but not 5-powersmooth. With this, it will be 16-powersmooth, as the highest prime factors power is 16 (2⁴). For 56, we have 2³×7, and is thus 8-powersmooth (2³).
Let’s say, we want to value of n = 55. First, we select a smoothness bound, such as B=7. We then compute the value of:
Next, we select a = 2, and use:
and where gcd() is the greatest common factor between two values. Two values that do not share any factors, such as 16 (2x2x2x2) and 21 (3x7) have a gcd of 1. The result the computation of g will give us either no result or one of the factors. In this case, we get g=7 , and can then easily find the other factor as 79:
a=2
M=2*3*5*7
n=553
g=math.gcd(a**M-1,n)
print (g)
print (n//g)Coding
The basic algorithm is then [taken from [here][2][here]:
# Code derived from https://github.com/google/paranoid_crypto
from typing import Optional
import gmpy2
from gmpy2 import mpz
import random
import sys
PRIMES = primes = (2,3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999)
def product_of_primes(nprimes):
product_of_primes=1
if (nprimes>len(PRIMES)): nprimes=len(PRIMES)
for i in range(0,nprimes):
product_of_primes *= primes[i]
return product_of_primes
def Pollardpm1(n: int, m: Optional[int] = None,gcd_bound: int = 2**60):
if gmpy2.gcd(n - 1, m) >= gcd_bound:
a = pow(2, n - 1, n)
p = gmpy2.gcd(pow(a, m, n) - 1, n)
if 1 < p < n:
return True, [p, n // p]
if p == n:
return True, []
return False, []
nprimebits=16
nprimes=64
if (len(sys.argv)>1):
nprimebits=int(sys.argv[1])
if (len(sys.argv)>2):
nprimes=int(sys.argv[2])
p = gmpy2.next_prime(random.getrandbits(nprimebits))
q = gmpy2.next_prime(random.getrandbits(nprimebits))
n=p*q
print(f"Number of bits in prime={nprimebits} and {primes[nprimes]}-powersmooth\n")
m=product_of_primes(nprimes)
res, factors = Pollardpm1(n, m, gcd_bound=1)
print(f"Result: ", res)
if (len(factors)>1):
print(f"Factors found: {int(factors[0])}, {int(factors[1])}")
else:
print("No factors discovered")
print(f"\nThe originally generator factors were: p={p}, q={q}")And a sample run is [here]:
Number of bits in prime=16 and 233-powersmooth
Result: True
Factors found: 48337, 23663
The originally generator factors were: p=23663, q=48337Conclusions
Don’t just take your libraries for granted, and assume they have been fully tested.
References
[1] Pollard, J. M. (1974, November). Theorems on factorization and primality testing. In Mathematical Proceedings of the Cambridge Philosophical Society (Vol. 76, №3, pp. 521–528). Cambridge University Press.
[2] Binarbosa, Pedro and Bleichenbacher, Daniel, Paranoid Cryptography, here.