Cryptography Reference
In-Depth Information
himself, but this does not necessarily mean he has access to the private key; these values
may be secured inside the hardware in such a way that their retrieval by unauthorized
means is not possible.
Suppose the Rabin decryption machine returns all 4 plaintext message values, and leaves
it up to the application to decide which message is correct. If the Rabin decryption machine
works this way, the analyst can factor
n
. To see this, suppose the analyst chooses a random
integer, say
z
, and encrypts it using the public key value
n
:
2
(mod
C
z
n
).
back through the decryption machine, and receives 4 mes-
sages in return. One of the returned values will be congruent to
He then runs this ciphertext
C
z
modulo
n
, and another will
be congruent to
z
modulo
n
. However, the other 2 roots, say
r
and
r
, are congruent to nei-
ther
z
nor
z
modulo
n
. Take either root, say
r
; he can derive one of the prime factors of
n
by simply noting that since
z
r
(mod
n
),
n
(
z r
), and so
(
z r
,
n
)
≠
n
.
But if he can also show that
z r
and
n
are not relatively prime, he will then have found
a nontrivial divisor of
n
; that is,
p
or
q
. He can do this in the following way; note that
n
can-
not divide
z
+
r
=
z
(
r
) since
z
r
(mod
n
). Hence,
n
divides neither
z
+
r
nor
z r
.
2
2
(mod
However, since
z
r
n
) he has
2
2
), or
n
| (
z
r
n
| (
z
+
r
)(
z r
)
which implies
n
is not relatively prime to
z r
. Thus, (
z r
,
n
) yields a nontrivial divisor
of
n
; namely,
p
or
q
.
E
XAMPLE
.
Here we show a chosen ciphertext attack on Rabin. The adversary does not know
the first two values
p
and
q
listed here; she only knows
n
, the product of
p
and
q
. She sub-
mits a message
m
to the decryption machine and gets four roots:
x
1
,
x
2
,
x
3
, and
x
4
. She is inter-
ested only in a root congruent to neither
m
nor
m
modulo
n
. The first root,
x
1
, is such a
root. She calculates (
m x
1
,
n
), and in this case, obtains the factor
q
. She then derives
p
by
taking
p
=
n
/
q
.
p
is unknown to adversary:
p
=
179769313486231590772930519078902473361797697894230657273430081157732675
805500963132708477322407536021120113879871393357658789768814416622492847
430639474124377767893424865485276302219601246094119453082952085005768838
150682342462881473913110540827237163350510684586298239947245938479716304
835356329624224137859
q
is unknown to adversary:
q
=
359538626972463181545861038157804946723595395788461314546860162315465351
611001926265416954644815072042240227759742786715317579537628833244985694
Search WWH ::
Custom Search