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:
