LatticeHacks

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*x^2/X^2+B*x/X+B
a+Q.roots(ring=ZZ) == 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)
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*x^3/X^3+B*x^2/X^2+B*x/X+B
Q.roots(ring=ZZ).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.