Cryptography Reference
In-Depth Information
CHAPTER
10
Quadratic Ciphers
The cryptosystems we are about to cover in this chapter are called public key cryp-
tosystems. All the cipher systems we've looked at so far have been secret key schemes.
This is the classical view of cryptography; it means that both the enciphering key and deci-
phering key must be kept secret, for knowing one is equivalent to knowing the other. For
example, consider a block affine transformation
C
aP
+
b
(mod
m
)
where (
. If an unauthorized user
captured these values, she could certainly encrypt messages to you, but even worse (obvi-
ously), she can easily derive the decryption key
a
,
m
) = 1. The enciphering key are the numbers
a
,
m
, and
b
a
(where
a
is an inverse of a modulo
m
)
and decrypt any messages.
With public key cryptography, the situation is somewhat different. Public key means that
two keys are involved: a public key used for enciphering, and a private key used for deci-
phering. But knowing the encryption key is not equivalent to knowing the decryption key,
and this is the crucial difference. With public key cryptography, each user generates a pub-
lic key, which they distribute to everyone, and a private key, which they do not divulge to
anyone. Anyone who wants to send a message to some user must look up their public encryp-
tion key and use it to encrypt the message. On the receiving end, the user decrypts the mes-
sage with their private key. No one else can decrypt because only the intended recipient
knows the private key, and the private key is very difficult to calculate from the encryption
key.
10.1
THE RABIN CIPHER
The encryption process of the following cipher, known as the Rabin cipher, involves pro-
ducing ciphertext
C
from plaintext
P
as follows:
2
(mod
C
P
n
).
(0
≤
P
< n, 0
≤
C
<n)
(†)
Here
n
is the product of two distinct large primes, say
p
and
q
, both congruent to 3 mod-
ulo 4. At current levels of computing power,
n
should be at least 1024 bits in length. The
Search WWH ::
Custom Search