Cryptology Part III. Asymmetric Ciphers

a7Hzq .#5r< kÜ\as TâÆK$ ûj(Ö2 ñw%h: Úk{4R f~`z8 ¤˜Æ+Ô „&¢Dø

Contents

1. The RSA cipher and its algorithmic foundations
2. Cryptanalysis of RSA
3. Primality Tests
4. The discrete logarithm with cryptographic applications
5. Hard number theoretic problems
6. Equivalences of basic cryptographic functions

• Primitive elements and quadratic residues
• Complexity theory for cryptology

The complete Part III as PDF file.

Overview

Asymmetric encryption introduces a new idea into cryptography that makes a fundamental difference with the formerly treated classic or bitblock ciphers:

Encryption and decryption are significantly different processes. Who knows the encryption function (including its key) has no means to efficiently derive the decryption function (or key).

The existence of a strictly personal secret has further interesting applications:

• secure proof of identity (»strong authentication«),
• digital signature.

• No one except the owner can encrypt with the private key.
• Everyone can decrypt with the public key, and in this way convince herself without any doubt that the author and the content of the message are authentic.

Historical Notes

• Invented by MERKLE 1974 and DIFFIE/HELLMAN 1976 (in the public science; MERKLEs paper was published only in 1978).
• Best known algorithm: RSA 1978. [Notices of the AMS 50 (2003): Rivest, Shamir, and Adleman receive 2002 Turing award (with pictures).]
• Previously invented by James Ellis (British secret service CESG) in 1970, declassified 1997.
• Potentially known at NSA in 1965.
  • Potential idea: the Codebook paradigm—reversing a function may be difficult.
  • Probable application: Engineers can encrypt the code for operating nuclear weapons. But only the serving commander can decrypt, and release the bomb.