Intro

General Scheme

M–H PKCSThe RSA PKCS

The D–H PKCS

End

Complexity and Cryptography
Thomas Zeugmann
Hokkaido University
Laboratory for Algorithmics
https://www-alg.ist.hokudai.ac.jp/∼thomas/COCRB/

Lecture 13: Public Key Cryptography

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCS

End

Motivation I
QuestionWhy do we need public key cryptography?

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCS

End

Motivation I
QuestionWhy do we need public key cryptography?

So far, we mainly considered two-way cryptosystems. In such
cryptosystems the security of the communication has been
mainly established by a private key.
This classical key management requires the exchange of the secret
key which may be well imaginable if the number of participants
is small.

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCS

End

Motivation I
QuestionWhy do we need public key cryptography?

So far, we mainly considered two-way cryptosystems. In such
cryptosystems the security of the communication has been
mainly established by a private key.
This classical key management requires the exchange of the secret
key which may be well imaginable if the number of participants
is small.
Imagine a bank with tens of thousands customers all over theword who like to access their accounts via their computers at
home. It seems absolutely hopeless to exchange frequently
secret keys with all customers.
Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCS

End

Motivation II
Most customers have a much larger range of applications thansimply accessing their bank accounts over the internet, e.g.;
shopping over the net using a credit card, frequently exchangeof email with varying addressees, or using different computersover a net.

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCS

End

Motivation II
Most customers have a much larger range of applications thansimply accessing their bank accounts over the internet, e.g.;
shopping over the net using a credit card, frequently exchangeof email with varying addressees, or using different computersover a net.
Another important problem is authentication. The main problem
addressed here is to ensure that a message received indeed
originates from the source it pretends to have been sent out.
In classical communication via letters, this problem has beensolved by using hand written signatures (in the western
hemisphere) or a “hanko,” i.e., a personal seal (e.g., in China,
Japan). Thus, we need something equivalent, i.e., an electronic
signature.
Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCS

End

Motivation III
All those real and potential applications stimulated a hugeamount of research during the last three decades.
The key observation to be made is that a key in classicaltwo-way cryptosystems has actually two separate tasks, i.e.,
enciphering and deciphering.

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCS

End

Motivation III
All those real and potential applications stimulated a hugeamount of research during the last three decades.
The key observation to be made is that a key in classicaltwo-way cryptosystems has actually two separate tasks, i.e.,
enciphering and deciphering.
Diffie and Hellman (1976) proposed a new approach, i.e., publickey cryptography.
They proposed to replace the secrete key by two keys. One key
is used for encryption, and one key for decryption. The
revolutionary idea, however, was to make the key forencryption publicly available. The key for decryption is kept
secret by the receiver.

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe General Scheme of Public Key Cryptography I

The general scenario can be described as follows: Assume `communicating parties P1 , . . . , P` . Each party Pi chooses andpublishes its public key ki , and keeps its secret key e
ki private.
Suppose, party Pi wishes to send a message to party Pj .
Then Pi looks for Pj ’s public key in the list of all public keys.
Next, Pi enciphers its message using kj and sends it out. The
receiver Pj exploits her private key e
kj and deciphers themessage received from Pi .

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe General Scheme of Public Key Cryptography I

The general scenario can be described as follows: Assume `communicating parties P1 , . . . , P` . Each party Pi chooses andpublishes its public key ki , and keeps its secret key e
ki private.
Suppose, party Pi wishes to send a message to party Pj .
Then Pi looks for Pj ’s public key in the list of all public keys.
Next, Pi enciphers its message using kj and sends it out. The
receiver Pj exploits her private key e
kj and deciphers themessage received from Pi .
The only problem is how to realize this nice idea.

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe General Scheme of Public Key Cryptography II
There must be some connection between the public and theprivate key, since otherwise it is very hard to imagine how thedeciphering can be performed. This leads to the following

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe General Scheme of Public Key Cryptography II
There must be some connection between the public and theprivate key, since otherwise it is very hard to imagine how thedeciphering can be performed. This leads to the following
Requirements:
Given the public key, it must be extremely hard to computethe private one.
Computing the cipher must be easy, while deciphering has
to remain extremely hard, too, without knowing theprivate key.

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe General Scheme of Public Key Cryptography II
There must be some connection between the public and theprivate key, since otherwise it is very hard to imagine how thedeciphering can be performed. This leads to the following
Requirements:
Given the public key, it must be extremely hard to computethe private one.
Computing the cipher must be easy, while deciphering has
to remain extremely hard, too, without knowing theprivate key.

These requirements directly lead to the idea of one-way
functions.
Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCS

End

One-Way Functions
Definition 1 (One-Way Functions)
Let X, Y be non-empty sets. A one-way function f is an injectivefunction f : X → Y such that f(x) can be computed in timepolynomial in the length |x| of x for all x ∈ X but there is noalgorithm computing f−1 (y) efficiently for any interesting
fraction of arguments y ∈ range(f).

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCS

End

One-Way Functions
Definition 1 (One-Way Functions)
Let X, Y be non-empty sets. A one-way function f is an injectivefunction f : X → Y such that f(x) can be computed in timepolynomial in the length |x| of x for all x ∈ X but there is noalgorithm computing f−1 (y) efficiently for any interesting
fraction of arguments y ∈ range(f).
Unfortunately, no one has yet proved the existence of one-way
functions. Complexity theory is still not ready to handle thisextremely difficult problem. Moreover, classical complexity
theory mainly deals with worst-case complexity what is by nomeans ideal from the viewpoint of cryptology. The reasons forthis are as follows:
Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCS

End

Points of Concern I(1) A problem having high worst-case complexity may beanyway easily solvable for most of its instances. And nonon-linear lower bound for a particular problem is known.
(2) For all practical purposes it is sufficient to possess anefficient probabilistic algorithm computing f−1 . That means,even if we would know that no deterministic algorithm
computes f−1 for almost all inputs in polynomial time, wecannot conclude the relevant cryptosystem to be secure.
(3) Even worse, having a proof that no probabilistic algorithm
computes f−1 for almost all inputs in polynomial time is
not sufficient to derive reasonable conclusions concerning
the security of the relevant cryptosystem. Still, it may bepossible to invert f for almost all inputs of practical length;e.g., given a proved tight lower bound of nlog log n , then for10
all inputs y of length |y| 6 22 the inversion of f can be
performed in time less than or equal to |y|10 .
Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCS

End

Points of Concern I(1) A problem having high worst-case complexity may beanyway easily solvable for most of its instances. And nonon-linear lower bound for a particular problem is known.
(2) For all practical purposes it is sufficient to possess anefficient probabilistic algorithm computing f−1 . That means,even if we would know that no deterministic algorithm
computes f−1 for almost all inputs in polynomial time, wecannot conclude the relevant cryptosystem to be secure.
(3) Even worse, having a proof that no probabilistic algorithm
computes f−1 for almost all inputs in polynomial time is
not sufficient to derive reasonable conclusions concerning
the security of the relevant cryptosystem. Still, it may bepossible to invert f for almost all inputs of practical length;e.g., given a proved tight lower bound of nlog log n , then for10
all inputs y of length |y| 6 22 the inversion of f can be
performed in time less than or equal to |y|10 .
Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCS

End

Points of Concern I(1) A problem having high worst-case complexity may beanyway easily solvable for most of its instances. And nonon-linear lower bound for a particular problem is known.
(2) For all practical purposes it is sufficient to possess anefficient probabilistic algorithm computing f−1 . That means,even if we would know that no deterministic algorithm
computes f−1 for almost all inputs in polynomial time, wecannot conclude the relevant cryptosystem to be secure.
(3) Even worse, having a proof that no probabilistic algorithm
computes f−1 for almost all inputs in polynomial time is
not sufficient to derive reasonable conclusions concerning
the security of the relevant cryptosystem. Still, it may bepossible to invert f for almost all inputs of practical length;e.g., given a proved tight lower bound of nlog log n , then for10
all inputs y of length |y| 6 22 the inversion of f can be
performed in time less than or equal to |y|10 .
Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCS

End

Points of Concern II(4) Since all practically appearing inputs are below somelength, even non-uniform families of different algorithms
inverting f may be interesting for a cryptanalyst.
There are, however some functions f which are widely
considered to be good candidates for one-way functions, e.g.;
modular exponentiation (the inverse is computing the discrete
logarithm), computing the product of prime numbers (theinverse is factoringandP a given number into its prime factors),
m+1 andcomputing M = m
x
a
,
where
(a
,
.
.
.
,
a
)
∈
N
m
0
i=0 i i(x0 , . . . , xm ) ∈ {0, 1}m+1 (the inverse is the general subset-sum
problem).

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCS

End

Points of Concern II(4) Since all practically appearing inputs are below somelength, even non-uniform families of different algorithms
inverting f may be interesting for a cryptanalyst.
There are, however some functions f which are widely
considered to be good candidates for one-way functions, e.g.;
modular exponentiation (the inverse is computing the discrete
logarithm), computing the product of prime numbers (theinverse is factoringandP a given number into its prime factors),
m+1 andcomputing M = m
x
a
,
where
(a
,
.
.
.
,
a
)
∈
N
m
0
i=0 i i(x0 , . . . , xm ) ∈ {0, 1}m+1 (the inverse is the general subset-sum
problem).

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe General Scheme of Public Key Cryptography III
Next we describe how to apply one-way functions to thesolution of public key cryptography.
Clearly, we cannot directly apply one-way functions f for
enciphering messages. Additionally, we have to incorporate anidea how the receiver can circumvent the difficulty of
inverting f. As outlined above, solely the receiver possesses the
additional information provided by her secret key. Thisadditional information should enable her to decrypt the
ciphertext.

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe General Scheme of Public Key Cryptography III
Next we describe how to apply one-way functions to thesolution of public key cryptography.
Clearly, we cannot directly apply one-way functions f for
enciphering messages. Additionally, we have to incorporate anidea how the receiver can circumvent the difficulty of
inverting f. As outlined above, solely the receiver possesses the
additional information provided by her secret key. Thisadditional information should enable her to decrypt the
ciphertext.
The following definition formalizes this idea: Furthermore, we
use Kp and Ks to denote the set of public keys and private(secret) keys, respectively.

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe General Scheme of Public Key Cryptography IV

Definition 2 (Trap-Door Function)
A trap-door function f : Pt × Kp → Ct is a function satisfying thefollowing requirements:(i) hkp = f( · , kp ) is a one-way function for every kp ∈ Kp ;(ii) there exists a polynomial q such that the time to computehkp (x) is uniformly bounded by q(|x|) for all kp ∈ Kp ;(iii) there exist a one-way function d : Ks → Kp and apolynomial time computable function g : Ks × Ct → Pt
such that y = f(x, kp ) implies x = g(d−1 (kp ), y) for allx ∈ Pt, kp ∈ Kp , and y ∈ Ct.

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe General Scheme of Public Key Cryptography V

The information d−1 (kp ) constitutes the trap-door enabling thereceiver to decipher the message obtained. Thus, the generalscenario for public key cryptography outlined above can berealized as follows:

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe General Scheme of Public Key Cryptography V

The information d−1 (kp ) constitutes the trap-door enabling thereceiver to decipher the message obtained. Thus, the generalscenario for public key cryptography outlined above can berealized as follows:
Each party P1 , . . . , P` is equipped with algorithms forcomputing f, g, and d. Furthermore, we assume |Ks | > `. Now,
party Pi chooses its private key e
ki ∈ Ks such that e
ki , ekj fori , j, where i, j ∈ {1, . . . , `}. How to realize this requirement is
discussed later. Then, she computes ki = d(eki ) and publishes it.

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe General Scheme of Public Key Cryptography VI

The message exchange is performed using the following
protocol: Suppose Pi wishes to send a message x to Pj .
(1) Pi computes y = f(x, kj ) using Pj ’s public key kj , andsends y over a public channel to Pj .
(2) Pj receives y and uses her private key e
kj to computeex = g(kj , y).

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe General Scheme of Public Key Cryptography VI

The message exchange is performed using the following
protocol: Suppose Pi wishes to send a message x to Pj .
(1) Pi computes y = f(x, kj ) using Pj ’s public key kj , andsends y over a public channel to Pj .
(2) Pj receives y and uses her private key e
kj to computeex = g(kj , y).
We proceed by providing an example for a concrete public key
cryptosystem.

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCS

End

Merkle and Hellman’s Public Key Cryptosystem I

Within the Merkle and Hellman’s public key cryptosystem
plaintext is encoded into bit-vectors of length n, i.e.,b = (b0 , . . . , bn−1 ), bi ∈ {0, 1}.
For example, we may encode the 26 letters of the Latin alphabet
by using 00000 for A, 00001 for B, . . . , and 11001 for Z. Thus,
each letter comprises 5 bits. For error detecting, it may berecommendable to add some check bits using, for example, aHamming code. For keeping our examples small, we neglect
the issue of error detecting here and use the bit strings given
above.

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCS

End

Merkle and Hellman’s Public Key Cryptosystem II
The public key is a knapsack vector a = (a0 , . . . , an−1 ), ai ∈ N.
How to choose a is described below. The enciphering c of aplaintext b is computed by>c = ab =

n−1
X

aj bj

(1)

j=0

(* b> denotes the transpose of b *).

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCS

End

Merkle and Hellman’s Public Key Cryptosystem II
The public key is a knapsack vector a = (a0 , . . . , an−1 ), ai ∈ N.
How to choose a is described below. The enciphering c of aplaintext b is computed by>c = ab =

n−1
X

(1)

aj bj

j=0

(* b> denotes the transpose of b *).
The result is a number c between 0 and

Pn−1

j=0 aj . This numberP
c is represented as a bit string of length ` = dlog(1 + n−1
j=0 aj )eincluding leading zeros.

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCS

End

Merkle and Hellman’s Public Key Cryptosystem III
We describe the trap-door information and how to choose a. The
trap-door is a pair (w, m) ∈ N × N which should be large and has tosatisfy
w

<

m

and

gcd(w, m) = 1 ,(2)

Next, we choose n values â = (â0 , . . . , ân−1 ) such that
m

>

n−1
X
i=0

âi

and

âj >

j−1
X

âi

for all j = 1, . . . , n − 1 . (3)i=0So, party P chooses w, m, and â such that Conditions (2) and (3) aresatisfied. Then P computes a = (a0 , . . . , an−1 ), whereai = (âi w) mod m for all i = 0, . . . , n − 1. The vector a is P’s public
key and the pair (w, m) and the vector â is P’s private key.
The public key is published, and the private key (w, m) is kept secret.
Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCS

End

Merkle and Hellman’s Public Key Cryptosystem IV

Let c be a ciphertext received. The deciphering is done using
the following procedure dec:
(1) Compute ĉ = (w−1 c) mod m,(2) Compute b = (b0 , . . . , bn−1 ) as follows:
If ĉ > ân−1 then set bn−1 = 1 else set bn−1 = 0
For j = n − 2, n − 3, . . . , 0, if
n−1
P
ĉ −
âi bi > âj then set bj = 1 else set bj = 0.
i=j+1

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCS

End

Merkle and Hellman’s Public Key Cryptosystem V
Example 3
Party P chooses n = 5, (w, m) = (2550, 8443), andâ = (171, 196, 457, 1191, 2410). So Conditions (2) and (3) aresatisfied. The modular inverse of 2550 in Z8443 is 3950. So P’s
public key is a = (5457, 1663, 216, 6013, 7439). Let x = L;then b = (0, 1, 0, 1, 1); thus c = 1663 + 6013 + 7439 = 15115, andthe message sent is c in binary, i.e., 11101100001011.
Suppose P has received c. So, P computes successively

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCS

End

Merkle and Hellman’s Public Key Cryptosystem V
Example 3
Party P chooses n = 5, (w, m) = (2550, 8443), andâ = (171, 196, 457, 1191, 2410). So Conditions (2) and (3) aresatisfied. The modular inverse of 2550 in Z8443 is 3950. So P’s
public key is a = (5457, 1663, 216, 6013, 7439). Let x = L;then b = (0, 1, 0, 1, 1); thus c = 1663 + 6013 + 7439 = 15115, andthe message sent is c in binary, i.e., 11101100001011.
Suppose P has received c. So, P computes successively(1) ĉ = (w−1 c) ≡ 3950 · 15115 ≡ 3797 mod 8443.

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCS

End

Merkle and Hellman’s Public Key Cryptosystem V
Example 3
Party P chooses n = 5, (w, m) = (2550, 8443), andâ = (171, 196, 457, 1191, 2410). So Conditions (2) and (3) aresatisfied. The modular inverse of 2550 in Z8443 is 3950. So P’s
public key is a = (5457, 1663, 216, 6013, 7439). Let x = L;then b = (0, 1, 0, 1, 1); thus c = 1663 + 6013 + 7439 = 15115, andthe message sent is c in binary, i.e., 11101100001011.
Suppose P has received c. So, P computes successively(1) ĉ = (w−1 c) ≡ 3950 · 15115 ≡ 3797 mod 8443.
(2) Since 3797 > 2410 we set b4 = 1.

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCS

End

Merkle and Hellman’s Public Key Cryptosystem V
Example 3
Party P chooses n = 5, (w, m) = (2550, 8443), andâ = (171, 196, 457, 1191, 2410). So Conditions (2) and (3) aresatisfied. The modular inverse of 2550 in Z8443 is 3950. So P’s
public key is a = (5457, 1663, 216, 6013, 7439). Let x = L;then b = (0, 1, 0, 1, 1); thus c = 1663 + 6013 + 7439 = 15115, andthe message sent is c in binary, i.e., 11101100001011.
Suppose P has received c. So, P computes successively(1) ĉ = (w−1 c) ≡ 3950 · 15115 ≡ 3797 mod 8443.
(2) Since 3797 > 2410 we set b4 = 1.
(3) Next, we compute 3797 − 2410 = 1387 > 1191. So, b3 = 1.
Now, 3797 − (2410 + 1191) = 196 < 457, so b2 = 0.
Since 3797 − (2410 + 1191) = 196 we set b1 = 1.
Finally, 3797 − (2410 + 1191 − 196) = 0, and thus b0 = 0.
Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCS

End

Merkle and Hellman’s Public Key Cryptosystem VI
We continue with some remarks concerning the complexity ofthe problems involved. The difficult problem used in thedesign of the trap-door function f is the knapsack orsubset-sum problem which is known to be NP-complete.
However, several subclasses of this problem are known forwhich it is easy to solve the decision problem. For example, if
ai < ai+1 for all i = 0, . . . , n − 2, then the knapsack problem
can be solved by using at most n subtractions as outlined in our
deciphering procedure. Another subclass consists of all vectors(a0 , . . . , an−1 ) ∈ Nn for which all ai are powers of 2. In thelatter case, one has simply to compute the binary representationof M. A more sophisticated subclass has been described in
Lagarias and Odlyzko (1983).
Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCS

End

Merkle and Hellman’s Public Key Cryptosystem VI
We continue with some remarks concerning the complexity ofthe problems involved. The difficult problem used in thedesign of the trap-door function f is the knapsack orsubset-sum problem which is known to be NP-complete.
However, several subclasses of this problem are known forwhich it is easy to solve the decision problem. For example, if
ai < ai+1 for all i = 0, . . . , n − 2, then the knapsack problem
can be solved by using at most n subtractions as outlined in our
deciphering procedure. Another subclass consists of all vectors(a0 , . . . , an−1 ) ∈ Nn for which all ai are powers of 2. In thelatter case, one has simply to compute the binary representationof M. A more sophisticated subclass has been described in
Lagarias and Odlyzko (1983).
Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCS

End

Merkle and Hellman’s Public Key Cryptosystem VII
Thus, special care has to be taken. In particular, Merkle andHellman (1978) hoped that the modular transformation of the
trap-door knapsack â will result in almost all cases in a hard
one. But A. Shamir (1982) proposed a polynomial time method
for breaking the Merkle and Hellman (1978) public key
cryptosystem.

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCS

End

Merkle and Hellman’s Public Key Cryptosystem VII
Thus, special care has to be taken. In particular, Merkle andHellman (1978) hoped that the modular transformation of the
trap-door knapsack â will result in almost all cases in a hard
one. But A. Shamir (1982) proposed a polynomial time method
for breaking the Merkle and Hellman (1978) public key
cryptosystem.
Since then, more sophisticated methods have been proposed todesign public key cryptosystem that are based on the difficultyof the subset-sum problem. Since all proposed systems are notvery satisfying we continue by looking at the most widely usedpublic key cryptosystems that are based on the difficulty of
number theoretic problems.

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe RSA Public Key Cryptosystem I
This system is based on the difficulty of factoring and/or taking
discrete roots modulo a composite modulus. It has been
invented by by R. Rivest, A. Shamir and L. Adleman in 1977.
Let A (= Alice) be anybody wishing to participate at the RSA
cryptosystem. Then, Alice has to do the following:

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe RSA Public Key Cryptosystem I
This system is based on the difficulty of factoring and/or taking
discrete roots modulo a composite modulus. It has been
invented by by R. Rivest, A. Shamir and L. Adleman in 1977.
Let A (= Alice) be anybody wishing to participate at the RSA
cryptosystem. Then, Alice has to do the following:(1) Choose randomly two huge primes pA and qA (at least
1000 bits each, and the bigger prime should preferably
have some more digits than the smaller one).

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe RSA Public Key Cryptosystem I
This system is based on the difficulty of factoring and/or taking
discrete roots modulo a composite modulus. It has been
invented by by R. Rivest, A. Shamir and L. Adleman in 1977.
Let A (= Alice) be anybody wishing to participate at the RSA
cryptosystem. Then, Alice has to do the following:(1) Choose randomly two huge primes pA and qA (at least
1000 bits each, and the bigger prime should preferably
have some more digits than the smaller one).
(2) Compute nA = pA qA and calculate ϕ(nA ) =ϕ(pA )ϕ(qA ) = (pA − 1)(qA − 1) = nA − pA − qA + 1.

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe RSA Public Key Cryptosystem I
This system is based on the difficulty of factoring and/or taking
discrete roots modulo a composite modulus. It has been
invented by by R. Rivest, A. Shamir and L. Adleman in 1977.
Let A (= Alice) be anybody wishing to participate at the RSA
cryptosystem. Then, Alice has to do the following:(1) Choose randomly two huge primes pA and qA (at least
1000 bits each, and the bigger prime should preferably
have some more digits than the smaller one).
(2) Compute nA = pA qA and calculate ϕ(nA ) =ϕ(pA )ϕ(qA ) = (pA − 1)(qA − 1) = nA − pA − qA + 1.
(3) Choose randomly any number eA ∈ {1, . . . , ϕ(nA )} suchthat gcd(eA , ϕ(nA )) = 1.

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe RSA Public Key Cryptosystem I
This system is based on the difficulty of factoring and/or taking
discrete roots modulo a composite modulus. It has been
invented by by R. Rivest, A. Shamir and L. Adleman in 1977.
Let A (= Alice) be anybody wishing to participate at the RSA
cryptosystem. Then, Alice has to do the following:(1) Choose randomly two huge primes pA and qA (at least
1000 bits each, and the bigger prime should preferably
have some more digits than the smaller one).
(2) Compute nA = pA qA and calculate ϕ(nA ) =ϕ(pA )ϕ(qA ) = (pA − 1)(qA − 1) = nA − pA − qA + 1.
(3) Choose randomly any number eA ∈ {1, . . . , ϕ(nA )} suchthat gcd(eA , ϕ(nA )) = 1.
(4) Compute dA = e−1
A mod ϕ(nA ). Publish KA = (nA , eA )and keep pA , qA , and dA secret.
Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe RSA Public Key Cryptosystem II
Now, assume any other participant B (=Bob) wishing tocommunicate secretly with Alice.

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe RSA Public Key Cryptosystem II
Now, assume any other participant B (=Bob) wishing tocommunicate secretly with Alice.
Then, Bob codes his plaintext into a binary number w.

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe RSA Public Key Cryptosystem II
Now, assume any other participant B (=Bob) wishing tocommunicate secretly with Alice.
Then, Bob codes his plaintext into a binary number w.
Using Alice’s public key KA = (nA , eA ) Bob calculates the
cipher c = weA mod nA and sends c to Alice.

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe RSA Public Key Cryptosystem II
Now, assume any other participant B (=Bob) wishing tocommunicate secretly with Alice.
Then, Bob codes his plaintext into a binary number w.
Using Alice’s public key KA = (nA , eA ) Bob calculates the
cipher c = weA mod nA and sends c to Alice.
Alice deciphers c by computing cdA mod nA .

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe RSA Public Key Cryptosystem II
Now, assume any other participant B (=Bob) wishing tocommunicate secretly with Alice.
Then, Bob codes his plaintext into a binary number w.
Using Alice’s public key KA = (nA , eA ) Bob calculates the
cipher c = weA mod nA and sends c to Alice.
Alice deciphers c by computing cdA mod nA .
The correctness of this protocol ist established by the following
theorem:Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe RSA Public Key Cryptosystem II
Now, assume any other participant B (=Bob) wishing tocommunicate secretly with Alice.
Then, Bob codes his plaintext into a binary number w.
Using Alice’s public key KA = (nA , eA ) Bob calculates the
cipher c = weA mod nA and sends c to Alice.
Alice deciphers c by computing cdA mod nA .
The correctness of this protocol ist established by the following
theorem:
Theorem 1
w = cdA mod nA .

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCS

End

Proof
Proof. By assumption, c = weA mod nA . First, assume
gcd(w, nA ) = 1; then applying the Theorem of Euler
cdA ≡ (weA )dA ≡ weA dA ≡ w(eA dA ) mod ϕ(nA ) ≡ w mod nA ,since eA dA ≡ 1 mod ϕ(nA ).

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCS

End

Proof
Proof. By assumption, c = weA mod nA . First, assume
gcd(w, nA ) = 1; then applying the Theorem of Euler
cdA ≡ (weA )dA ≡ weA dA ≡ w(eA dA ) mod ϕ(nA ) ≡ w mod nA ,since eA dA ≡ 1 mod ϕ(nA ).
What can be said if gcd(w, nA ) , 1?

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCS

End

Proof
Proof. By assumption, c = weA mod nA . First, assume
gcd(w, nA ) = 1; then applying the Theorem of Euler
cdA ≡ (weA )dA ≡ weA dA ≡ w(eA dA ) mod ϕ(nA ) ≡ w mod nA ,since eA dA ≡ 1 mod ϕ(nA ).
What can be said if gcd(w, nA ) , 1?
Suppose that exactly one of the two primes pA and qA does
divide w, say pA . The Little Theorem of Fermat is telling us
wqA −1 ≡ 1 mod qA .
Since ϕ(nA ) = (pA − 1)(qA − 1), we can concludewϕ(nA ) ≡ (wqA −1 )pA −1 ≡ 1pA −1 ≡ 1 mod qA .
Moreover, eA dA ≡ 1 mod ϕ(nA ), and thus eA dA = jϕ(nA ) + 1
for some positive integer j.
Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCS

End

Proof – continued

Consequently,
weA dA ≡ w mod qA .
But the last congruence is also true modulo pA , since, byassumption, pA divides w, and thus weA dA − w ≡ 0 mod pA .
Hence, we can conclude weA dA ≡ w mod nA .

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCS

End

Proof – continued

Consequently,
weA dA ≡ w mod qA .
But the last congruence is also true modulo pA , since, byassumption, pA divides w, and thus weA dA − w ≡ 0 mod pA .
Hence, we can conclude weA dA ≡ w mod nA .
Finally, if both pA and qA divide w, then we trivially have
weA dA − w ≡ 0 mod pA as well as weA dA − w ≡ 0 mod qA ,and thus weA dA ≡ w mod nA .

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe RSA Public Key Cryptosystem III
Question
What can be said concerning the security of the RSA
cryptosystem?

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe RSA Public Key Cryptosystem III
Question
What can be said concerning the security of the RSA
cryptosystem?

By its construction, breaking the RSA cipher is as most as hard
as finding discrete roots modulo the composite number nA .
Computing discrete roots must be judged as feasible if theprime factorization of nA is known. Therefore, thecryptanalysis of the RSA cryptosystem is as most as hard asfactoring. However, there is no known efficient algorithm forfactoring a large composite number except for quantum
computers which are currently not available.
Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe RSA Public Key Cryptosystem IV
However, some care must be taken be choosing the primes p
and q. Obviously, the chosen primes should be nowhere listed.
Thus, testing primality is such an important problem.

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe RSA Public Key Cryptosystem IV
However, some care must be taken be choosing the primes p
and q. Obviously, the chosen primes should be nowhere listed.
Thus, testing primality is such an important problem.
Moreover, one has to avoid primes of special form, e.g.,
p = 2e ± 1.

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe RSA Public Key Cryptosystem IV
However, some care must be taken be choosing the primes p
and q. Obviously, the chosen primes should be nowhere listed.
Thus, testing primality is such an important problem.
Moreover, one has to avoid primes of special form, e.g.,
p = 2e ± 1.
As mentioned above, the difference between p and q should belarge. For seeing this, we prove the following theorem:

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe RSA Public Key Cryptosystem IV
However, some care must be taken be choosing the primes p
and q. Obviously, the chosen primes should be nowhere listed.
Thus, testing primality is such an important problem.
Moreover, one has to avoid primes of special form, e.g.,
p = 2e ± 1.
As mentioned above, the difference between p and q should belarge. For seeing this, we prove the following theorem:
Theorem 2
Let p and q be primes such that p > q and p − q = O((log p)c ) for a“moderate” constant c ∈ N. Then, there exists an efficient algorithm
for factoring n = pq.

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe RSA Public Key Cryptosystem V

Proof. Consider
p2 + 2pq + q2 − 4pq(p − q)2(p + q)2
−n=
=
4
4
4

(4)

Thus, the left side is a perfect square. Then the following
method may be applied for factoring n:Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe RSA Public Key Cryptosystem V

Proof. Consider
p2 + 2pq + q2 − 4pq(p − q)2(p + q)2
−n=
=
4
4
4

(4)

Thus, the left side is a perfect square. Then the following
method may be applied for factoring n:√(1) Compute n within a precision of b(log n + 2)/2c bits.

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe RSA Public Key Cryptosystem V

Proof. Consider
p2 + 2pq + q2 − 4pq(p − q)2(p + q)2
−n=
=
4
4
4

(4)

Thus, the left side is a perfect square. Then the following
method may be applied for factoring n:√(1) Compute n within a precision of b(log n + 2)/2c bits.
√√(2) Check for x = b nc + 1, b nc + 2, . . . whether or not
x2 − n is a perfect square.
√√
If it is, output p = x + x2 − n and q = x − x2 − n.

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe RSA Public Key Cryptosystem VI
The correctness of the above algorithm can be shown as√
follows: First, assume that n has been computed within a√precision of b(log n + 2)/2c bits. Then we have b nc.
(Exercise). Next, observe that√√p+q
> pq = n2(5)

by applying the well-known inequality between arithmetic and√geometric mean. Consequently, b nc < (p + q)/2 (* note that(p + q)/2 is always an integer *). Thus, the algorithm mustterminate by finding a perfect square and the first x found must2

fulfill x2 6 (p+q)
by (4) and (5). Thus, x 6 p+q
4
2 .

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe RSA Public Key Cryptosystem VII
p+q.
2
Let z2 = x2 − n. By (4) we directly obtain z = p−q
2 . Hence,x + z = p and x − z = q.

Case 1. x =Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe RSA Public Key Cryptosystem VII
p+q.
2
Let z2 = x2 − n. By (4) we directly obtain z = p−q
2 . Hence,x + z = p and x − z = q.
p+q.
Case 2. x <2Since z2 = x2 − n we obtain n = x2 − z2 = (x + z)(x − z). Thus,p = x + z and q = x − z, and therefore, (p + q)/2 = x, acontradiction.
This proves the correctness.

Case 1. x =Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe RSA Public Key Cryptosystem VII
p+q.
2
Let z2 = x2 − n. By (4) we directly obtain z = p−q
2 . Hence,x + z = p and x − z = q.
p+q.
Case 2. x <2Since z2 = x2 − n we obtain n = x2 − z2 = (x + z)(x − z). Thus,p = x + z and q = x − z, and therefore, (p + q)/2 = x, acontradiction.
This proves the correctness.

Case 1. x =Finally, we show that the algorithm above is efficient.

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe RSA Public Key Cryptosystem VIII√
The computation of n up to the desired precision can beeasily performed using the Newton method, i.e.,x`+1 := x` −x2` − n2x`

for ` = 0, . . . , b(log n + 2)/2c

with x0 = n.

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe RSA Public Key Cryptosystem VIII√
The computation of n up to the desired precision can beeasily performed using the Newton method, i.e.,x`+1 := x` −x2` − n2x`

for ` = 0, . . . , b(log n + 2)/2c

with x0 = n. Taking into account that√n > q = p − (p − q) ≈ p − (log p)c we see by (4) that√(log p)c
p+q
p−q
=p−
≈p−
> n.
(6)
2
2
2
√
Hence, (p + q)/2 is only “a bit” greater than n. Consequently,
the algorithm has to try at most (log p)c /2 many candidates
until its search terminates. But this is a polynomial in thelength of the input, and hence we are done.
Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe Diffie–Hellman Public Key Cryptosystem I

Finally, we take a look at the Diffie–Hellman Public Key
Cryptosystem. It is based on discrete logarithms.
Problem: Discrete Logarithms
Input: Prime number p ∈ N, b ∈ Z∗p , and a generator g for Z∗p .
Problem: Compute the index x such that x = dlogg b.

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe Diffie–Hellman Public Key Cryptosystem I

Finally, we take a look at the Diffie–Hellman Public Key
Cryptosystem. It is based on discrete logarithms.
Problem: Discrete Logarithms
Input: Prime number p ∈ N, b ∈ Z∗p , and a generator g for Z∗p .
Problem: Compute the index x such that x = dlogg b.
So far, there is no known algorithm efficiently computing
discrete logarithms for any standard model of sequential orparallel computation. On the other hand, a quantum computer
would be able to compute discrete logarithms in polynomial
time.

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe Diffie–Hellman Public Key Cryptosystem II

The Diffie–Hellman Public Key Cryptosystem requires asystem designer. The system designer chooses a huge prime q(preferably more than 4000 bits) and a generator g for Z∗q .
The prime q and the generator g are global information, andthus known to everybody participating in this public key
cryptosystem.

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe Diffie–Hellman Public Key Cryptosystem II

The Diffie–Hellman Public Key Cryptosystem requires asystem designer. The system designer chooses a huge prime q(preferably more than 4000 bits) and a generator g for Z∗q .
The prime q and the generator g are global information, andthus known to everybody participating in this public key
cryptosystem.
Next, we describe how the public and the secret key,
respectively, are chosen by any participant. Subsequently, we
provide the protocol used.

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe Diffie–Hellman Public Key Cryptosystem III

Let A be any participant.
A chooses randomly a number xA ∈ {2, . . . , q − 1} andcomputes yA = gxA mod q. That is, xA = dlogg yA .
Participant A publishes yA as her public key and keeps xA
secret.

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe Diffie–Hellman Public Key Cryptosystem III

Let A be any participant.
A chooses randomly a number xA ∈ {2, . . . , q − 1} andcomputes yA = gxA mod q. That is, xA = dlogg yA .
Participant A publishes yA as her public key and keeps xA
secret.
Now, let A and B be any two participants who wish tocommunicate. Assume, B likes to send a message to A. Thenthe following key is used:
B computes the key KAB = yxAB mod q.
Assume, A likes to send a message to B. Then, A computes
KBA = yxBA mod q.

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe Diffie–Hellman Public Key Cryptosystem IV

The following theorem shows the usefulness of these keys:
Theorem 3
KAB = KBA

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe Diffie–Hellman Public Key Cryptosystem IV

The following theorem shows the usefulness of these keys:
Theorem 3
KAB = KBA
Proof.
KAB = yxAB ≡ (gxA )xB ≡ gxA xB≡ (gxB )xA ≡ yxBA ≡ KBA mod q .

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCS

End

Remarks
Note, however, that A and B compute KBA and KAB ,respectively, using different information. That is, A computes
KBA using her own secret key xA and the public key yB
published by B while Bob calculates KBA from his secret key xB
and Alice’s public key yA .

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCS

End

Remarks
Note, however, that A and B compute KBA and KAB ,respectively, using different information. That is, A computes
KBA using her own secret key xA and the public key yB
published by B while Bob calculates KBA from his secret key xB
and Alice’s public key yA .
On the other hand, any cryptanalyst does neither possess xA
nor xB , hence she must compute KBA solely from yA and yB .
dlog yB

Since KAB = yA g mod q this is at most as hard ascomputing discrete logarithms. Moreover, so far no easier
method is known for computing KBA from yA and yB .
Therefore, it is widely believed that computing KBA from yA
and yB is hard.

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe Diffie–Hellman Public Key Cryptosystem V
Next, we describe how the parties A and B can communicate.
Taking Theorem 3 into account, two possibilities are
imaginable. First, the system designer additionally provides
any sufficiently advanced classical two-way cryptosystem, forexample the AES. Then, any pair of users wishing to secretly
communicate may use the key KBA . Thus, no key exchange isrequired in advance.

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe Diffie–Hellman Public Key Cryptosystem V
Next, we describe how the parties A and B can communicate.
Taking Theorem 3 into account, two possibilities are
imaginable. First, the system designer additionally provides
any sufficiently advanced classical two-way cryptosystem, forexample the AES. Then, any pair of users wishing to secretly
communicate may use the key KBA . Thus, no key exchange isrequired in advance.
Note that public key cryptosystems are relatively slow
compared to classical cryptosystems (at least to our present
stage of technology and theoretical knowledge). Thus, it issometimes more realistic to use them in the limited role inconjunction with a classical cryptosystem in which the actual
messages are transmitted as described above.

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe Diffie–Hellman Public Key Cryptosystem VI
Second, the communication is performed by using directly the
Diffie–Hellman system. The underlying idea is best explainedusing a bag having two locks.

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe Diffie–Hellman Public Key Cryptosystem VI
Second, the communication is performed by using directly the
Diffie–Hellman system. The underlying idea is best explainedusing a bag having two locks.
Each partner possesses exclusively one key for one of the twolocks. Initially, both locks are unlocked. Now, A puts themessage w into the bag and locks her lock with her key. The bag
is taken by a messenger who delivers the bag to B. Obviously, B
is not able to unlock the bag right now, since he possesses only
the key for the other lock. Therefore, B locks his lock using his
key, and returns the bag to the messenger who is returning it to
A. Now, A may unlock her lock, but the bag remains anyway
locked. Finally, the messenger delivers the bag again to B. Now,
B may unlock the bag using his key, and thus, he finally has
access to the secret message w.
Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe Diffie–Hellman Public Key Cryptosystem VII
The protocol described above has the following advantage: The
public messenger always delivered a locked bag. On the other
hand, A and B could exchange a secret message without
exchanging any key.

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe Diffie–Hellman Public Key Cryptosystem VII
The protocol described above has the following advantage: The
public messenger always delivered a locked bag. On the other
hand, A and B could exchange a secret message without
exchanging any key.
The impact of this method can be hardly overestimated.
Looking back into the history of cryptography, we see that thecryptography community unanimously agreed, for thousandsof years, that the only way for two parties to establish securecommunications was to first exchange a secret key. This was somuch common wisdom that nobody questioned it. If therecipient did not have a secret key giving her the informationneeded to decrypt the message efficiently, how could she be ina better position than an eavesdropper?

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe Diffie–Hellman Public Key Cryptosystem VIII
Now, we outline the formal realization of the idea describedabove to use a bag with two locks. For that purpose, a small
modification of the choices for xA and xB , respectively, has tobe made. Again, A and B randomly choose a number xAand xB between 2 and q − 1.

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe Diffie–Hellman Public Key Cryptosystem VIII
Now, we outline the formal realization of the idea describedabove to use a bag with two locks. For that purpose, a small
modification of the choices for xA and xB , respectively, has tobe made. Again, A and B randomly choose a number xAand xB between 2 and q − 1. Additionally, they must ensurethat gcd(xA , q − 1) = 1 and gcd(xB , q − 1) = 1, respectively.
This can be easily done by using the Euclidean algorithm, i.e., if
the randomly chosen number does not fulfill this requirement a
new number is randomly chosen until one is found that is
relatively prime to q − 1. Moreover, as shown previously the
Euclidean algorithm can be also used for computing−1
x−1
A mod (q − 1) and xB mod (q − 1), respectively.

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEndThe Diffie–Hellman Public Key Cryptosystem IX

Suppose, A wishes to send B a message, and let w be A’s
plaintext.
(i) A sends wxA mod q to B,(ii) B returns wxA xB mod q to A,−1(iii) A computes ŵ ≡ (wxA xB )xA mod q and sends the result ŵ
to B,
−1

(iv) B deciphers ŵ by calculating ŵxB mod q.
The correctness of the above algorithm is an immediate
consequence of the Theorem of Euler.

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCS

End

Thank you!

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCS

Ralph C. Merkle

Complexity and Cryptography

The RSA PKCS

The D–H PKCS

End

Martin Hellmanc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCSThe RSA PKCS

The D–H PKCSEnd

Adi Shamir, Ron Rivest, Leonard Adleman

Complexity and Cryptographyc Thomas Zeugmann

IntroGeneral Scheme

M–H PKCS

Whitfield Diffie

Complexity and Cryptography

The RSA PKCS

The D–H PKCS

End

Martin Hellmanc Thomas Zeugmann