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

Question

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 {E_K}_K∈{K} and {D_K}_K∈{K} algorithms representing invertible transformations,

E_K:{M} → {M}
D_K:{M} → {M}

on a finite message space {M}, such that

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

---

What I understood is as follows.

1. E_K is a public key and D_K is a private key, therefore E_K is the inverse of D_K.

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

3. D_K should be computationally infeasible to derive from E_K, such that it is not possible to derive D_K(a private key) from E_K(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 D_K from E_K? What is the exact meaning of for 'almost' every K? There could be an exception where it is feasible to derive D_K from E_K?

Answer 1

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.

That being said, here are answers to your questions:

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.

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

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.