Cryptography Reference
In-Depth Information
(
) =
359538626972463181545861038157804946723595395788461314546860162315465351
611001926265416954644815072042240227759742786715317579537628833244985694
861278948248755535786849730970552604439202492188238906165904170011537676
301364684925762947826221081654474326701021369172596479894491876959432609
670712659248448276687.
m x 1 ,
n
n
This is certainly not a trivial divisor of
. We have found one of its prime factors, and in
q
p
n
q
this case, we found
. To find
, the adversary simply divides
by
(of course).
p = n / q =
179769313486231590772930519078902473361797697894230657273430081157732675
805500963132708477322407536021120113879871393357658789768814416622492847
430639474124377767893424865485276302219601246094119453082952085005768838
150682342462881473913110540827237163350510684586298239947245938479716304
835356329624224137859.
You will be asked to write a program to execute such attacks in Java. A slight modifica-
tion to the chosen ciphertext attack yields the adaptive chosen ciphertext attack, described
below.
Homomorphic Property—Adaptive Chosen Ciphertext Attack
Note that
the Rabin cipher has the following behavior: If we encrypt a plaintext message
P
to
C
, note
that if we separate
P
into 2 parts, say
m
and
m
*, which individually encrypt to
c
and
c
*,
respectively, we have
P
2
(
mm
*) 2
m
2
m
* 2
cc
*
C
(mod
n
).
This is referred to as the homomorphic property of the Rabin transformation. This can
be exploited to employ an adaptive chosen ciphertext attack on this cipher. This attack is
when a cryptanalyst has access to the decryption machine, as in the chosen ciphertext attack,
but does not have total freedom to choose any message. That is, suppose the analyst chooses
an integer z and computes
2 (mod n ),
C z
but the decryption machine has been instructed to reject this message. The analyst must
then “adapt” by trying to disguise the message
C
as another message. She can do this by
selecting a random integer
x
relatively prime to
n
, and then computing
C
*
Cx
2 (mod
n
)
and submitting the message C * to the decryption machine. Now, note that
2
2
2
( zx ) 2 (mod n )
Cx
z
x
by the homomorphic property, and so
C
*
(
zx
) 2 (mod
n
).
Search WWH ::




Custom Search