Cryptography Reference
In-Depth Information
Since the intended recipient is the only one with knowledge of
a
,
b
,
p
, and
q
, she should
be the only individual able to compute
x
0
. For without these values, it appears necessary to
obtain
x
0
by computing the sequence
x
t
, . . . ,
x
2
,
x
1
by taking successive square roots mod-
ulo
x
t
1
. As we have mentioned, this is an intractable problem without
knowledge of the prime factors of
n
beginning with
.
Why is this called a “probabilistic” cipher? It has to do with the apparent “randomness”
of successive squares modulo
n
n
. Note that encryption is done by taking successive squares
modulo
th
plaintext unit. This produces a ciphertext that appears random, in the same sense that squares
modulo
n
, and “masking” (via
) the
h
least significant bits of the
i
th square with the
i
and notice some
pattern in its binary digits, we could use this information to help us find the square root
modulo
n
appear random. That is, if we could examine a square modulo
n
n
. We know of no other way to find solutions to quadratic congruences modulo
n
without factoring
n
into its prime factors; thus, a square modulo
n
looks merely like random
data.
E
XAMPLE
.
;
in practice we would use primes hundreds of digits long. Say the recipient chooses two
primes,
We will do an example of this type of encryption using small values for
p
and
q
are congruent to 3 modulo 4). Using
the extended Euclidean algorithm, she computes two values
p
= 503, and
q
= 563. (Note that both
p
and
q
a
and
b
such that
ap
+
bq
= 1.
These are
a
=
122, and
b
= 109. She computes
n
=
pq
= 503
563 = 283189, and makes
public the value of
.
Now suppose someone wishes to send the message (seen as a binary integer)
n
P
= 10011100001011111010
to this recipient. He knows the value
n
= 283189, and so uses it to select a random square
736
2
(mod 283189). (The value 736 was chosen randomly.) Now, to block
the message, he computes log
2
n
x
0
= 258507
18.11140570189, and so chooses
k
= 18. He then com-
putes log
2
k
= 4. (Note the recipient can also com-
pute these values, so she also knows the appropriate block size.) He then splits the message
up into 4 bit blocks, to get
4.169925001442, and then chooses
h
m
1
= 1001
m
2
= 1100
m
3
= 0010
m
4
= 1111
m
5
= 1010.
Now he must compute the successive squares
x
1
,
x
2
,
x
3
,
x
4
,
x
5
modulo
n
, and mask (via
) the
h
least significant bits of the
i
th square with the
i
th plaintext unit to get the
i
th cipher-
text unit. We show this in Table 10.3.
Finally, the sender must compute
x
6
x
5
2
67738 (mod
n
). He then sends to the recip-
ient the ciphertext message
C
= (1000, 1101, 0001, 1010, 0100, 67738).
Search WWH ::
Custom Search