Coppersmith's method when the most significant bits are unknown¶

This notebook gives an example on how to apply Coppersmith's method when only the most significant bits of the stereotyped message are unknown. While this is quite similar to the case in which the least significant bits are unknown, there are a few changes and things to take note of.

In [1]:
# First, we generate an RSA public key
n = random_prime(2^160)*random_prime(2^160)
n
Out[1]:
124998952927938977263790587321867926591791093689695359877845073694804509130248149009558770265629
In [2]:
# Next, we define our message
m = Integer('cryptologyismyfavoritesubject',36)
m
Out[2]:
481827643612584161951346703464525443216519789
In [3]:
# We encrypt the message to a ciphertext, with RSA (public) modulus e = 3
c = m^3 % n
c
Out[3]:
59103876412682535046832907636265837054961420193246955469647441108276164527855029713961160578703
In [4]:
# We define the known part of the message
a = Integer('0000000000ismyfavoritesubject',36)
a
Out[4]:
193864677799444806153557062253

Now, we note that the polynomial is a bit different from the one we would have had if the least significant bits were unknown; in that case, we would have had $f(x) = \left(a+x\right)^e - c$. In this case, however, we have that we need to take the known part out of $x$; we are looking for small roots in Coppersmith's method, and, without making any changes, we would get that our roots become very big (since $x$ has a very large constant part).

Hence, we divide this part out of $x$, this leaves us with $$f(x) = \left(a + x_{base}\cdot x\right)^e - c$$ for some $x_{base}$ which makes $x_{base}\cdot x$ equal to the unknown part of the message.

In [5]:
# This factor needs to be multiplied with x in the polynomial f
x_base = Integer('zzzzzzzzzzzzzzzzzzz', 36) + 1
# note: the number of z's is the same as the length of 'ismyfavoritesubject'
# note 2: we need to add 1 to the term a_max, since we want to have the lower_bound on X when read as part of the message

x_base
Out[5]:
371319292745659279662190166016
In [6]:
# Let's see whether this will allow us to reconstruct the string
(x_base * Integer('cryptology', base=36) + a).str(base=36)
Out[6]:
'cryptologyismyfavoritesubject'
In [7]:
# The upper bound on the unknown part of the string
X = Integer('zzzzzzzzzz',36)

At this point, we can use e.g. Mathematica to write out the polynomial and construct the matrix using the following code.

(* The polynomial for recovering parts of a stereotyped message *)
f[x_, e_] := (a + xBase*x)^e - c

(* The public exponent in this case is 3. *)
e = 3

n
n*(x*X) // Expand
n*(x*X)^2 // Expand
f[x*X, e] // Expand

M = {
   Reverse[CoefficientList[%, x, 4]],
   Reverse[CoefficientList[%%, x, 4]],
   Reverse[CoefficientList[%%%, x, 4]],
   Reverse[CoefficientList[%%%%, x, 4]]
   };
M // MatrixForm

This gives us the following matrix: $$ \left( \begin{array}{cccc} X^3 \text{xBase}^3 & 3 a X^2 \text{xBase}^2 & 3 a^2 X \text{xBase} & a^3-c \\ 0 & n X^2 & 0 & 0 \\ 0 & 0 & n X & 0 \\ 0 & 0 & 0 & n \\ \end{array} \right) $$

In [8]:
M = matrix([
    [x_base^3*X^3, 3*x_base^2*X^2*a, 3*x_base*X*a^2, a^3-c],
    [0,n*X^2,0,0],
    [0,0,n*X,0],
    [0,0,0,n]
])
In [9]:
# First, we apply the LLL algorithm to the matrix.
B = M.LLL()

# Next, we take a look at the first row vector of the output matrix.
B[0]
Out[9]:
(0, 0, 0, 124998952927938977263790587321867926591791093689695359877845073694804509130248149009558770265629)
This will lead to problems; any polynomial which only has a non-zero coefficient for $x^0$ will not have any roots.
In [10]:
# We define the polynomial, like we usually do.
Q = B[0][0]*x^3/X^3 + B[0][1]*x^2/X^2 + B[0][2]*x/X + B[0][3]
Q
Out[10]:
124998952927938977263790587321867926591791093689695359877845073694804509130248149009558770265629
In [11]:
Q.roots(ring=ZZ)
Out[11]:
[]
We get that no roots are found. This means that something must have gone wrong when working on this problem.

Let's try the small_roots function¶

SageMath has a function called small_roots for polynomials, which effectively performs Coppersmith's method for us. This method is defined in this source code on GitHub.

Let us try to apply this function to our case to see whether Coppersmith's method will work. This first requires us to define the ring over which the polynomial is defined. This turns out to be a ring of polynomials over the ring of integers mod $n$.

In [12]:
# Define the ring of integers mod n
K = Zmod(n)

# Define the ring of polynomials over the ring of integers mod n
P.<x> = PolynomialRing(K, implementation='NTL')
In [13]:
# Define the polynomial. This will automatically be taken over the correct ring, since we defined `x` as a variable for that polynomial ring.
f = ((a + x_base*x)^3 - c)/x_base^3
f
Out[13]:
x^3 + 29240907499729765756511419421878183165136542634990113774242165459688700327765427999584788600405*x^2 + 97018779214485406300593466962844298806462045477325636091951454708267568823848077273314305120362*x + 52735537751845005138356400430317051565961330901728614828098487676374165180600708325036234446395
In [14]:
# Apply the small_roots function to find solutions according to Coppersmith's method.
found_small_roots = f.small_roots()
found_small_roots
Out[14]:
[1297610043501346]
In [15]:
# Turn the result back into a string
Integer(found_small_roots[0]).str(base=36)
Out[15]:
'cryptology'
This is the correct result; hence, we must have done something wrong earlier on.

Looking at the source code of SageMath's small_roots function, we see that this function requires our polynomial to be monic; that is, its leading coefficient (i.e. the one for the term with $x^3$) should be 1. Earlier on, this was obviously not the case (since we had that the leading coefficient was $x_{base}^3$). Hence, it seems like a useful idea to try to change our polynomial a bit so that it is monic.

Making the polynomial monic¶

Before we continue, we need to revert x back to its usual meaning; that is, it should be interpreted as a polynomial variable (but not one taken over the integers $\bmod n$).

In [16]:
# restore `x` to its usual meaning (i.e. a 'regular' symbolic variable, instead of one over the polynomials over Zmod(n))
var('x');

To make our polynomial $f(x)$ monic, we divide all terms by $x_{base}^3$. This will give us a leading coefficient of $1$. Note that doing this does not change the roots of the polynomial; dividing all terms by a constant does not change the values of $x$ for which the entire polynomial attains the value $0$.

However, there are a few problems to watch out for in this case:

  • we cannot simply divide by $x_{base}$ in the usual way; this would leave us with rational coefficients (i.e. coefficients in $\mathbb{Q}$), while we need a polynomial with integer coefficients;
  • another issue is that our polynomial should be defined $\bmod n$; this means that the coefficients of the polynomial should be reduced $\bmod n$. This can be done by wrapping the coefficients like Zmod(n)(coefficient);
  • using the trick on the last line, there is another problem to watch out for: that is, if we do not explicitly cast back the result to an integer, SageMath will reduce anything multiplied with that result $\bmod n$ as well, which is not intended;
  • finally, note that $X$ is not part of the coefficients; the $X$ comes from the fact that we are evaluating the function for the value $xX$. This means we only need to reduce the other parts of the matrix cell $\bmod n$.

All of these caveats eventually leave us with the following matrix:

In [17]:
M = matrix([
    [int(Zmod(n)((x_base^3)/x_base^3))*X^3, int(Zmod(n)((3*x_base^2*a)/x_base^3))*X^2, int(Zmod(n)((3*x_base*a^2)/x_base^3))*X, int(Zmod(n)((a^3-c)/x_base^3))],
    [0,n*X^2,0,0],
    [0,0,n*X,0],
    [0,0,0,n]
])
M[0]
Out[17]:
(48873677980689217386839135742583368824443109375, 390877671313472216239450750851378620331321020855717549421440120344247299283837240076303295465357115052341168664396199044503125, 354716028469647146123776199706844223069113253828924900339891509134800852393846171147282116104833710520234796950, 52735537751845005138356400430317051565961330901728614828098487676374165180600708325036234446395)
In [18]:
# First, we apply the LLL algorithm to the matrix.
B = M.LLL()

# Next, we take a look at the first row vector of the output matrix.
B[0]
Out[18]:
(-1157954038280810404553144233807348417397738940158948682864344699056025250866302141071360000000, -496065177572064955631601543738812845194282052026242729928270232976625402165625, 98483219119196310863051046695705012159764199418486141162616514180985393706855619099760934200, 16813754717520370762520697491976447725966203868277298034287215082098161953231670169727736788)
This time, we do not get a polynomial which is constant. This suggests we may be able to find roots.
In [19]:
# We define the polynomial, like we usually do.
Q = B[0][0]*x^3/X^3 + B[0][1]*x^2/X^2 + B[0][2]*x/X + B[0][3]
Q
Out[19]:
-23692795102065713578325283803059154229720514560*x^3 - 37109809630412165151699430974742284118362995065*x^2 + 26936255836194013559151645707076479232492194221982334340928391679837985424072*x + 16813754717520370762520697491976447725966203868277298034287215082098161953231670169727736788
In [20]:
Q.roots(ring=ZZ)
Out[20]:
[(1297610043501346, 1)]
In [21]:
Q.roots(ring=ZZ)[0][0].str(base=36)
Out[21]:
'cryptology'
Thus, we find that the missing part of the string is 'cryptology', as expected.

To verify our result, we can re-encrypt the recovered message and see whether the result matches the ciphertext.

In [22]:
(a + x_base*Q.roots(ring=ZZ)[0][0])^3 % n == c
Out[22]:
True