RSA algorithm (1978) - apply results from number theory, combined with the
difficulty of determining the prime factors of a large number
(e.g. 1024 bits). The fastest known prime factoring algorithm 
runs in exponential time.

Operates with arithmetic mod n. A plaintext block is treated as an
integer P. 

Two keys are used: e = encryption key, d = decryption key.

A plaintext block is encrypted as P^e mod n (the cryptotext). 

Because the exponentiation is performed mod n, it is very difficult to
obtain P from (P^e mod n), without knowing the prime factors of 
n.

The decrypting key is chosen carefully such that P^(ed) mod n = P.
So the legal receiver who knows d simply computes P^(ed) mod n to
recover P.


Digital Signature via public key system

Goal: When A sends a message to B, the message should be signed in
such a way that the parties  get the following two kinds of
protection:

a) both A and B should be protected against messages addressed to B
but fed in the information system by a third party C, who pretends to
be A. 

b) A should be protected against messages forged by B, who claims to
have received them from A, properly signed. 

Note: Digital signatures usually change the whole text, rather than
just being an addition to the end of the text.



Let E_A and E_B be the encryption keys used by A, B
Let D_A and D_B be the decryption keys used by A, B.



Procedure:

1) A sends the message w to B in the form E_B(D_A(w)).

2) B recovers D_A(w) by his/her secret decryption key D_B 
to D_B(E_B(D_A(w))) = D_A(w) .

3) From D_A(w), B recovers w by the publicly known E_A.

The above scheme is secure only for attacks by passive eavesdropper,
but not by active eavesdropper who can plant false messages in the
system. 


Coin flipping by telephone:


A and B both know a (supposedly) one-way function f and not the
inverse f^(-1). B chooses a random number x and tells A the value
f(x). A makes a guess about some 50-50 property of 
the number x, e.g. is x even or odd. B tells A whether or not the
guess was correct. Later on, B tells A the number x.