The RSA cryptosystem was invented by Ron Rivest, Adi Shamir, and Len Adleman in 1977. It is a public-key encryption system, i.e. each user has a private key and a public key.
Key Generation
To generate a key, pick two random primes of the same bitlength, and compute their product.
p = random_prime(2^512)
q = random_prime(2^512)
N = p * q
Pick an integer e, typically 3 or 17 or 65537 which is coprime to (p-1)*(q-1).
e = 65537
d = inverse_mod(e,(p-1)*(q-1))
The public key is (N,e), the private key is (N,d).
The computation of d will fail if e is not coprime.
Encryption (textbook version)
To encrypt a message, encode it as an integer between 0 and N.
Then compute
ciphertext = pow(message,e,N)
Decryption (textbook version)
To decrypt, compute
message = pow(ciphertext,d,N)
Attacks
The private key is easily computed from the public key (N,e)
if one can get the factors p and q.
At 29C3 we gave a talk FactHacks reviewing methods to factor integers without further information. Please see that webpage for scripts for the different factorization methods.
Here we focus on attacks using lattices.
Coppersmith's attack for factoring with bits of p known
These attacks assume that we know some part of one of the
factors of N. For example, if we know the most significant bits
of p; more precisely, let a match p on all but the bottom 86 bits.
p = random_prime(2^512); q = random_prime(2^512)
N = p*q
a = p - (p % 2^86)
With this value of a, the polynomial f(x) = a + x has a small root
r modulo p, where r is the least significant 86 bits of p. This means
that both, f(x) and N are divisible by p, and of course also any
multiple or power of f(x).
The lattice we construct satisfies that every vector is zero mod p.
Applying LLL we will get a small element of that lattice which hopefully
matches r.
Here is how we set up the lattice
X = 2^86
M = matrix([[X^2, 2*X*a, a^2], [0, X, a], [0, 0, N]])
B = M.LLL()
We access the first vector of the resulting basis, interpret it as a
polynomial and check whether the constant term matches r, i.e. that
a+r matches p:
Q = B[0][0]*x^2/X^2+B[0][1]*x/X+B[0][2]
a+Q.roots(ring=ZZ)[0][0] == p
This should output true.
Coppersmith's small public RSA exponent attack with partially known message
What's wrong with this RSA example?
message = Integer('squeamishossifrage',base=35)
N = random_prime(2^512)*random_prime(2^512)
c = message^3 % N
Take the cube root of the ciphertext c:
Integer(c^(1/3)).str(base=35)
and translate to base 35 to get squeamishossifrage.
This worked because the message was so small, that message^3
was smaller than N, so that no reduction took place.
N = random_prime(2^150)*random_prime(2^150)
message = Integer('thepasswordfortodayisswordfish',base=35)
c = message^3 % N
int(c^(1/3))==message
The last part outputs false, meaning that reduction mod N did
take place. However, this is an example of a stereotyped message.
We know that it starts with thepasswordfortodayis and probably there
is a fixed length for the password itself.
We put zeros for the unknown part and define:
a = Integer('thepasswordfortodayis000000000',base=35)
X = Integer('xxxxxxxxx',base=35)
Again we set up a basis of polynomials, this time related to the partially known message.
M = matrix([[X^3, 3*X^2*a, 3*X*a^2, a^3-c],[0,N*X^2,0,0],[0,0,N*X,0],[0,0,0,N]])
B = M.LLL()
Q = B[0][0]*x^3/X^3+B[0][1]*x^2/X^2+B[0][2]*x/X+B[0][3]
Q.roots(ring=ZZ)[0][0].str(base=35)
B is the output of running LLL and Q takes the first basis vector
and interprets it as a polynomial. The last line computes a root of Q
and indeed we get swordfish after proper character encoding.
Automating the factoring with bits known attack
class partial_factoring:
def __init__(self,N,a,X):
self.N = N
self.a = a
self.X = X
self.R = ZZ['x']
x = self.R.0
self.f = x+a
# k is the multiplicity of the desired roots mod N
# kd+t-1 is the degree of the polynomial that is produced
def gen_lattice(self,t=1,k=1):
dim = k+t
A = matrix(IntegerRing(),dim,dim)
x = self.R.0
X = self.X
monomial_list = [x^i for i in range(dim)]
for i in range(k):
g = self.f(X*x)^i*self.N^(k-i)
A[i] = [g.monomial_coefficient(mon) for mon in monomial_list]
for j in range(t):
g = self.f(X*x)^k*(X*x)^j
A[k+j] = [g.monomial_coefficient(mon) for mon in monomial_list]
weights = [X^i for i in range(dim)]
def getf(M,i):
return sum(self.R(b/w)*mon for b,mon,w in zip(M[i],monomial_list,weights))
return A,getf
def solve(self,t=1,k=1):
A,getf = self.gen_lattice(t,k)
B = A.LLL()
factors = []
for r,multiplicity in getf(B,0).roots():
if r not in ZZ:
continue
if gcd(Integer(self.f(r)),self.N) != 1:
p = gcd(self.f(r),self.N)
factors.append(p)
return factors
def gen_random_modulus(nlen=1024,rlen=80):
p = random_prime(2^ceil(nlen/2),False)
q = random_prime(2^floor(nlen/2),False)
N = p*q
r = lift(mod(p,2^rlen))
a = p-r
X = 2^rlen
return (N,a,X),r
def test_factoring():
(N,a,X),r = gen_random_modulus()
u = partial_factoring(N,a,X)
if a+r in u.solve(2,1):
print "Success!"
else:
print "Failure. :("
Automating the small RSA exponent attack
class univariate_coppersmith:
# degree d polynomial f
# integer modulus N
# X is the bound on the absolute value of the root
def __init__(self, f, N, X):
self.f = f
self.N = N
self.X = X
self.R = QQ['x']
# k is the multiplicity of the desired roots mod N
# kd+t-1 is the degree of the polynomial that is produced
def gen_lattice(self,t=1,k=1):
d = self.f.degree()
dim = k*d+t
A = matrix(IntegerRing(),dim,dim)
x = self.R.0
X = self.X
monomial_list = [x^i for i in range(dim)]
for i in range(k):
for j in range(d):
g = self.f(X*x)^i*(X*x)^j*self.N^(k-i)
A[d*i+j] = [g.monomial_coefficient(mon) for mon in monomial_list]
for j in range(t):
g = self.f(X*x)^k*(X*x)^j
A[k*d+j] = [g.monomial_coefficient(mon) for mon in monomial_list]
weights = [X^i for i in range(dim)]
def getf(M,i):
return sum(self.R(b/w)*mon for b,mon,w in zip(M[i],monomial_list,weights))
return A,getf
def solve(self,t=1,k=1):
A,getf = self.gen_lattice(t,k)
B = A.LLL()
roots = []
for r,multiplicity in getf(B,0).roots():
if mod(self.f(r),self.N) == 0:
roots.append(r)
return roots
# can solve up to rlen < nlen/d
def gen_random_coppersmith(nlen=1024, rlen=150, d=3):
p = random_prime(2^floor(nlen/2),False)
q = random_prime(2^ceil(nlen/2),False)
N = p*q
a = ZZ.random_element(0,2^(N.nbits()-rlen))
r = ZZ.random_element(0,2^rlen)
m = a+r
c = lift(mod(m,N)^d)
x = ZZ['x'].0
f = (x+a)^d-c
X = 2^rlen
return (f,N,X),r
def test_coppersmith():
(f,N,X),r = gen_random_coppersmith()
u = univariate_coppersmith(f,N,X)
if r in u.solve():
print "Success!"
else:
print "Failure. :("
Version: This is version 2017.12.28 of the "RSA" web page.