Cryptography Reference
In-Depth Information
public key in this cipher is
n
. What is not made public is the prime factorization of
n
; that
is, the two primes
are kept secret. These two values are necessary for decryption;
thus, they are the private key.
The enciphering process is described in (†). Anyone knowing the value of
p
and
q
n
can send mes-
sages. Now, in order to decipher, we must solve the congruence
2
(mod
C
P
n
)
for the plaintext
. We know from previous work that these solutions are obtained by form-
ing the two congruences
P
2
(mod
C
P
p
)
2
(mod
C
P
q
)
and solving them. We then combine these solutions using CRT to obtain solutions for
P
. Thus,
we can only solve (†) for
(at least, no other way to solve
these congruences is known). This is why the prime factors of
P
by factoring the modulus
n
=
pq
are kept secret. Only the
individual possessing them can decipher. From proposition 31, we get the solution(s) to (†)
as
n
P
(
zqq
p
wpp
q
) (mod
n
)
(
p
1)/4
,
(
q
1)/4
,
where
z
=
C
w
=
C
q
p
is an inverse of
q
modulo
p
, and
p
q
is an inverse of
p
modulo
.
The obvious drawback to this method is that solving such congruences can produce four
distinct square roots
q
. That is, it reports four possible plaintext messages during the
decryption phase. If the message is text, it is easy to identify the correct one; it's the one that
doesn't look like garbage! However, if the message is some type of binary stream, for exam-
ple, the messages must be tagged in some way so this tag will reappear in the decryption
process.
Why is it that we can reveal the value of
P
for
C
n
to everyone? We know that if someone man-
ages to factor
, our cryptosystem and we will be, metaphor-
ically, up the creek without a paddle! Anyone knowing
n
into its prime factors
p
and
q
p
and
q
can decrypt; the question is,
how easy is it to factor
is the product of two sufficiently large primes (say a few
hundred digits each), then it is nearly impossible to factor
n
? If
n
in a reasonable period of time.
In fact, it will take somewhere on the order of a few billion years! We may find this hard to
believe since we routinely factor integers in our math classes, but we simply don't appre-
ciate the size of the numbers involved here. Indeed, factoring has become a huge study
involving many techniques, some of which we shall study in upcoming chapters.
n
E
XAMPLE
.
To see how the Rabin cipher works, we use the ordinary alphabet A = 00, B = 01,
. . . , Z = 25. We will use a block size of four characters. With our choice of alphabet and
block size, the largest possible block corresponds to ZZZZ = 25252525. We must pick a mod-
ulus
n
greater than this, and furthermore,
n
must be the product of 2 primes congruent to 3
modulo 4. Let
p
= 6911 and
q
= 6947. (You may wish to verify that
p
and
q
are both primes
of the form 4
k
+ 3.) These two values are the private key, and must not be made public. We
Search WWH ::
Custom Search