# What is the exact meaning of the public key cryptosystem properties in New Directions In Cryptography by Diffie and Hellman

I'm quite new to cryptography and don't have much mathematical knowledge. I'm studying cryptography, especially public key algorithms. I have some basic knowledge of public key algorithms so I know how the RSA algorithm works. But I found lots of things I don't understand while reading New Directions In Cryptography by Diffie and Hellman.

In section III. PUBLIC KEY CRYPTOGRAPHY in the paper, they defined four properties of a public key cryptosystem which are as follows.

A public key cryptosystem is a pair of families {EK}K∈{K} and {DK}K∈{K} algorithms representing invertible transformations,

EK:{M} → {M}
DK:{M} → {M}

on a finite message space {M}, such that

1. for every K ∈ {K}, EK is the inverse of DK,
2. for every K ∈ {K} and M ∈ {M}, the algorithms EK and DK are easy to compute,
3. for almost every K ∈ {K}, each easily computed algorithm equivalent to DK is computationally infeasible to derive from EK,
4. for every K ∈ {K}, it is feasible to compute inverse pairs EK and DK from K.

What I understood is as follows.

1. EK is a public key and DK is a private key, therefore EK is the inverse of DK.

2. EK and DK are easy to compute, so they can be computed in polynomial time.

3. DK should be computationally infeasible to derive from EK, such that it is not possible to derive DK(a private key) from EK(a public key) in polynomial time.

4. It is easy to compute pairs of a public key and a private key from K.

Here is what I don't understand.

1. What is the K? From what I understand, the K is like p and q in RSA? Because we choose prime numbers p and q first, and then we choose a public key e and derive a corresponding private key d from e using (p-1)(q-1) with the euclidean algorithm.

2. Why is that in property 3, for 'almost' every K, it is computationally infeasible to derive DK from EK? What is the exact meaning of for 'almost' every K? There could be an exception where it is feasible to derive DK from EK?

Well, it's good that you're trying to learn. However, learning from the original seminal papers does have some issues that you need to be aware of.

For one, sometimes the original authors did not anticipate some issues that later contributions found (and for which common practice adjusted for).

For example, it is now recognized that public key encryption needs to be randomized; that is, it isn't in general secure to have a deterministic function $$\text{Encrypt}(E_k, M)$$. After all, if an adversary obtains $$\text{Encrypt}(E_k, M)$$ and has a guess of the message $$M'$$, he can determine whether $$M = M'$$ by computing $$\text{Encrypt}(E_k, M')$$ (and seeing if that matches the ciphertext he has seen). Because of this, we always use a randomized encryption function $$\text{Encrypt}(E_k, M, r)$$ (where $$r$$ is a random input), with the property that $$\text{Decrypt}(D_k, \text{Encrypt}(E_k, M, r)) = M$$, for (almost) all $$M, r$$ (the "almost" is there because we've found some methods that do have a small probability of decryption failure).

The other thing that feels like it needs to be called out (even though it has little to do with your actual question) is signatures - Diffie and Hellman mention signatures in the context of trap door one way functions. It turns that that we have a variety of public key signature methods which are not based on trap door one way functions.

BTW: I'm not criticizing either Diffie or Hellman for not anticipating all possible issues - their work was truly groundbreaking. However, quite a lot of thought has been put into extending this work; it is not surprising that some people found things that were originally missed.

1. What is the K? From what I understand, the K is like p and q in RSA? Because we choose prime numbers p and q first, and then we choose a public key e and derive a corresponding private key d from e using (p-1)(q-1) with the euclidean algorithm.

Well, no. For any public key cryptosystem, there is a randomized process which generates the public key and the private key. This randomized process can be modeled as being based on some 'seed' or 'random coin flips' (more modern terminology is, in fact, 'random coins'). The value K is this seed.

Diffie and Hellman reference this process when they write:

     In practice, the cryptoequipment must contain a true random number generator
(e.g., a noisy diode) for generating K, together with an algorithm for generating
the EK ~- n, pair from its outputs.


Later works have the cryptosystems specifically call out this algorithm as the 'key generation' (Gen) algorithm as one of the algorithms that define the cryptosystem, and assume that the true random number generator output is something generated outside the cryptosystem as an explicit input to the Gen algorithm.

For RSA, what we typically do is take this seed K, and use it to select the random primes p and q (and possibly e; the details depend on the exact algorithm used). The p and q values are really part of the private key and not the original seed.

1. Why is that in property 3, for 'almost' every K, it is computationally infeasible to derive DK from EK? What is the exact meaning of for 'almost' every K? There could be an exception where it is feasible to derive DK from EK?

Well, one issue that cannot be avoided is if the attacker took a guess to the original seed value K', and then fed that into the key generation process (which is public). If his guess is correct, then that'd generate the exact same public key value $$E_k$$, and so he'd know his guess was correct (and he'd also get the private key value $$D_k$$, allowing him to decrypt. This cannot be avoided, and so they need to put in this cavaet about this unavoidable attack (and possibly similar ones as well). Actually, for most public key cryptosystems (no exception comes immediately to mind), there are better attacks than just guessing K; however that attack is still present.

• Thank you for your detailed explanation! So, if the attacker is lucky enough, he takes a guess and finds the exact private key(Dk) by comparing the generated public key with the Ek. – Architectophile Jun 20 at 16:17
• @Architectophile: yes, while it is extremely improbable, we cannot apriori eliminate the possibility – poncho Jun 20 at 21:04