Cryptography Reference
In-Depth Information
Rather than diagonalising using the method of the proof of Theorem
19.3.1
we compute
the Hermite normal form of
B
. This gives the matrix
aX
2
Y
2
∗
∗
∗
∗
∗
∗
∗
∗
aX
2
Y
∗
∗
∗
∗
∗
∗
∗
aXY
2
∗
∗
∗
∗
∗
∗
aXY
∗
∗
∗
∗
∗
16129
X
2
16129
Y
2
100125
X
1064641
Y
202558777
2048383
Y
2
∗
∗
∗
B
=
2048383
X
∗
∗
260144641
Y
∗
260144641
where blanks are zeroes and
∗
denotes an entry whose value we do not bother to write
5 diagonal matrix formed of columns 5 to 9 of rows 5 to 9 of
B
.
Performing LLL-reduction on
L
gives a matrix whose first row is
down. Let
L
be the 5
×
16129
X
2
,
16129
Y
2
,
1048258
X,
983742
Y,
−
−
−
(
28446222)
corresponding to the polynomial
16129
x
2
16129
y
2
G
(
x,y
)
=−
−
+
1048258
x
+
983742
y
−
28446222
.
Clearly,
G
(
x,y
) is not a multiple of
F
(
x,y
) since it has no
xy
term. Computing resultants
and factoring gives the solutions (
x,y
)
=
(21
,
21) and (23
,
19).
Exercise 19.3.3
The polynomial
F
(
x,y
)
=
131
xy
−
1400
x
+
20
y
−
1286
has an integer solution with
|
x
|
<
30 and
|
y
|
<
20. Use Coron's method as in Exam-
ple
19.3.2
to find (
x,y
).
The results of this section can be improved by taking into account the specific shape of
the polynomial
F
(
x,y
). We refer to Blomer and May [
67
] for details.
Finally, we remark that results are also known for integer polynomials having three
or more variables, but these are heuristic in the sense that the method produces a list of
polynomials having small roots in common, but there is no guarantee that the polynomials
are algebraically independent.
19.4 Some applications of Coppersmith's method
19.4.1 Fixed padding schemes in RSA
As discussed in Chapter
1
, it is necessary to use padding schemes for RSA encryption (for
example, to increase the length of short messages and to prevent algebraic relationships
