RSA Weaknesses: Powersmooth and Pollard’s p-1 Method

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…
Photo by Alp Duran on Unsplash

RSA Weaknesses: Powersmooth and Pollard’s p-1 Method

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. Here is a background on n-smooth: [link].

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³ x 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:

M = 2 × 3 × 5

Next, we select a = 2, and use:

g = gcd(a^M − 1, n)

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)

The code using [here] is:

# 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 [here]:

Number of bits in prime=16 and 233-powersmooth
Result:  True
Factors found: 10037, 31469
The originally generator factors were: p=10037, q=31469

The implementation is here:

https://asecuritysite.com/rsa/rsa_04

Conclusions

While it is unlikely that your software will have weaknesses in the generation of RSA keys, it is always best to check them, as a breach of the trust infrastructure of software can be one of the most costly of all the cybersecurity attacks. Here’s the method:

https://asecuritysite.com/rsa/rsa_04

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.