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

Contents
 The RSA cipher and its algorithmic foundations
 Cryptanalysis of RSA
 Primality Tests
 The discrete logarithm with cryptographic applications
 Hard number theoretic problems
 Equivalences of basic cryptographic functions
This part has two mathematical appendices:
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 derivation of the decryption function from the encryption function is a »oneway« process.
As an everyday analog
think of a postbox: Who can insert letters in it is not able to get something out of the box,
except when she has the key. In this situation for every participant there exists a pair of
functions. The first part of this pair is the encryption function—represented by a
parameter called »public key«—and is publically available and usable by everyone.
The second part is the decryption function—represented by a »private key«—and
is a personal secret shared by no one else.
The existence of a strictly personal secret has further interesting applications:
 secure proof of identity (»strong authentication«),
 digital signature.
The latter is simply the reverse application of private and public keys:
 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.
Author: Klaus Pommerening, 1997Apr09;
last change: 2021Mar06