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.
# First, we generate an RSA public key
n = random_prime(2^160)*random_prime(2^160)
n
124998952927938977263790587321867926591791093689695359877845073694804509130248149009558770265629
# Next, we define our message
m = Integer('cryptologyismyfavoritesubject',36)
m
481827643612584161951346703464525443216519789
# We encrypt the message to a ciphertext, with RSA (public) modulus e = 3
c = m^3 % n
c
59103876412682535046832907636265837054961420193246955469647441108276164527855029713961160578703
# We define the known part of the message
a = Integer('0000000000ismyfavoritesubject',36)
a
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.
# 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
371319292745659279662190166016
# Let's see whether this will allow us to reconstruct the string
(x_base * Integer('cryptology', base=36) + a).str(base=36)
'cryptologyismyfavoritesubject'
# 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) $$
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]
])
# 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]
(0, 0, 0, 124998952927938977263790587321867926591791093689695359877845073694804509130248149009558770265629)
# 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
124998952927938977263790587321867926591791093689695359877845073694804509130248149009558770265629
Q.roots(ring=ZZ)
[]
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$.
# 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')
# 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
x^3 + 29240907499729765756511419421878183165136542634990113774242165459688700327765427999584788600405*x^2 + 97018779214485406300593466962844298806462045477325636091951454708267568823848077273314305120362*x + 52735537751845005138356400430317051565961330901728614828098487676374165180600708325036234446395
# Apply the small_roots function to find solutions according to Coppersmith's method.
found_small_roots = f.small_roots()
found_small_roots
[1297610043501346]
# Turn the result back into a string
Integer(found_small_roots[0]).str(base=36)
'cryptology'
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.
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$).
# 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:
Zmod(n)(coefficient)
;All of these caveats eventually leave us with the following matrix:
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]
(48873677980689217386839135742583368824443109375, 390877671313472216239450750851378620331321020855717549421440120344247299283837240076303295465357115052341168664396199044503125, 354716028469647146123776199706844223069113253828924900339891509134800852393846171147282116104833710520234796950, 52735537751845005138356400430317051565961330901728614828098487676374165180600708325036234446395)
# 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]
(-1157954038280810404553144233807348417397738940158948682864344699056025250866302141071360000000, -496065177572064955631601543738812845194282052026242729928270232976625402165625, 98483219119196310863051046695705012159764199418486141162616514180985393706855619099760934200, 16813754717520370762520697491976447725966203868277298034287215082098161953231670169727736788)
# 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
-23692795102065713578325283803059154229720514560*x^3 - 37109809630412165151699430974742284118362995065*x^2 + 26936255836194013559151645707076479232492194221982334340928391679837985424072*x + 16813754717520370762520697491976447725966203868277298034287215082098161953231670169727736788
Q.roots(ring=ZZ)
[(1297610043501346, 1)]
Q.roots(ring=ZZ)[0][0].str(base=36)
'cryptology'
To verify our result, we can re-encrypt the recovered message and see whether the result matches the ciphertext.
(a + x_base*Q.roots(ring=ZZ)[0][0])^3 % n == c
True