Cryptography Reference
In-Depth Information
between the messages and ciphertexts). One simple proposal for
κ
-bit RSA moduli is to
take a
κ
bit message and pad it by putting (
κ
κ
−
1) ones to the left-hand side of it.
This brings a short message to full length. This padding scheme is sometimes called
fixed
pattern padding
; we discuss it further in Section
24.4.5
.
Suppose short messages (for example, 128-bit AES keys
K
) are being encrypted using
this padding scheme with
κ
−
=
1024. Then
2
1024
2
128
=
−
+
K.
m
Suppose also that the encryption exponent is
e
=
3. Then the ciphertext is
m
3
=
(mod
N
)
.
c
If such a ciphertext is intercepted then the cryptanalyst only needs to find the value for
K
. In this case, we know that
K
is a solution to the polynomial
(2
1024
2
128
x
)
3
F
(
x
)
=
−
+
−
≡
0(mod
N
)
.
c
This is a polynomial of degree 3 with a root modulo
N
of size at most
N
128
/
1024
N
1
/
8
.
=
So Coppersmith's method finds the solution
K
in polynomial-time.
Example 19.4.1
Let
N
8873554201598479508804632335361 (which is a 103 bit inte-
ger) and suppose Bob is sending 10-bit keys
K
to Alice using the padding scheme
m
=
2
100
2
10
=
K
.
Suppose we have intercepted the ciphertext
c
−
+
=
8090574557775662005354455491076
2
10
. We write
F
(
x
)
2
100
2
10
)
3
x
3
a
2
x
2
and wish to find
K
.Let
X
=
=
(
x
+
−
−
=
+
+
c
a
1
x
+
a
0
and define
N
0
0
0
0
NX
0
0
B
=
.
00
NX
2
0
a
0
a
1
X
2
X
2
X
3
Performing lattice reduction and taking the first row vector gives the polynomial with
factorisation
277605904865853
x
2
)
.
−
−
+
+
(
x
987)(
920735567540915376297
726745175435904508
x
One can verify that the message is
K
=
987.
19.4.2 Factoring
N
=
pq
with partial knowledge of
p
Let
N
=
pq
and suppose we are given an approximation
p
to
p
such that
p
=
p
+
x
0
where
<X
. For example, suppose
p
is a 2
κ
-bit prime and
p
is an integer that has the
same
κ
most significant bits as
p
(so that
|
x
0
|
<
2
κ
). Coppersmith used his ideas to get
an algorithm for finding
p
given
N
and
p
. Note that Coppersmith originally used a bivariate
|
p
−
p
|
