Cryptography Reference
In-Depth Information
9.1.1 Public-Key Cryptosystems
Formally, a public-key cryptosystem is defined by
a pseudorandom key generator Gen: this is a probabilistic algorithm which out-
puts a key pair (
K
p
,
K
s
) where
K
p
is a
public key
and
K
s
is a
secret key
;
an encryption algorithm Enc: this is an algorithm (which can be probabilistic)
which outputs a ciphertext
Y
from an input plaintext
X
and a public key
K
p
;
a decryption algorithm Dec: this is an algorithm (which necessarily implements
a deterministic function) which outputs the plaintext
X
from a ciphertext
Y
and
a secret key
K
s
.
As it will be seen later, the encryption is not necessarily deterministic: we can have
several ciphertexts which correspond to the same plaintext. Of course, the cryptosystem
should complete the following requirements:
For any generated key pair (
K
p
,
K
s
), any plaintext
x
, and any possible output
y
x
.
Given the access to specifications,
K
p
, and a Dec
K
s
oracle, it is intractable to
decrypt a generated ciphertext
y
without sending the query
y
to the decryption
oracle.
of Enc
K
p
(
x
), we have Dec
K
s
(
y
)
=
Note that the latter requirement is stated in a very informal way. Indeed, it is very hard
to agree on a precise definition of security for public-key cryptosystems. Therefore
we first commit on an intuitive notion of security. As we will see several examples of
attacks, definitions will become more and more precise (and counterintuitive).
Fig. 9.1 is the Shannon model of encryption revisited for public-key cryptosystems.
We can transform an insecure channel into a confidential one with the help of public-
key cryptography and an extra channel in order to transmit the public key (usually, the
key generator is run by the receiver). It is important to notice that the property required
Adversary
Ciphertext
Y
Plaintext
X
Encryption
Decryption
Y
X
Secret key
Public key
K
p
AUTHENTICATED
K
p
K
s
Generator
Figure 9.1.
Asymmetric Encryption.
Search WWH ::
Custom Search