Computer Security and Cryptography

10.4 PUBLIC-KEY CRYPTOSYSTEMS: EASY AND HARD COMPUTATIONAL PROBLEMS

Diffie and Hellman proposed a new type of cryptosystem that would alleviate but not eliminate the problem of key distribution and also provide a mechanism for digital signatures. The characteristic property of conventional cryptosystems = {T_k : k ∈ } is that T_k determines the inverse transformation . Normally, the key k determines a second key k⁻¹ so that . Diffie and Hellman proposed (public-key) cryptosystems that used two keys: a public key PuK for encipherment and a private key PrK for decipherment.

Encipher : x → y = E_puK{x}

Decipher : y → x = E_PrK{x}.

In addition to the usual properties required of a strong cryptosystem, it was crucial that the computation of PrK with knowledge of PuK would be infeasible. User_ID[A] would publish the public key PuK(ID[A]) and thereby enable every user to encipher information intended only for User_ID[A]. Knowledge of PrK(ID[A]), known only by User_ID[A], would permit User_ID[A] to decipher such messages. How can such pairs (PuK(ID[A]), (PrK(ID[A])) be found?

Diffie and Hellman argued ...