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.