Lecture 20: Encryption #2 - Public Key Systems


Public Key Systems

DES works well, but relies on both parties having a copy of the same secret key. This can be a big problem. In 1976, Diffie and, Hellman[1] proposed a system called Public Key Cryptography. Details of the underlying theory are outside the scope of this unit, but the basic ideas are:

This system works as follows:

[1] This is the standard story on the origins of Public Key Crypto. It's now apparent that a group of British researchers had come up with the same idea somewhat earlier: see, for example: The Open Secret.

RSA

In 1978, Rivest, Shamir and Adleman of MIT proposed a number-theoretic way of implementing a public-key cryptosystem. Their method has been widely adopted.

To use this technique, divide the plaintext (regarded as a bit string) into blocks so that each plaintext message P falls into the interval 0 <= P < n. This can be done by dividing it into blocks of k bits where k is the largest integer for which 2k < n is true.

To encrypt: C = Pe (mod n)
To decrypt: P = Cd (mod n)
The public key is thus: (e, n) and the private key is (d, n))


RSA Example

To create the public key, select two large positive prime numbers p and q p = 7, q = 17
Large enough for us!
Compute (p-1) * (q-1) x = 96
Choose an integer E which is relatively prime to x E = 5
Compute n = p * q n = 119
Kp is then n concatenated with E Kp = 119, 5
To create the secret key, compute D such that (D * E) mod x = 1 Ks = 119, 77
To compute the ciphertext C of plaintext P, treat P as a numerical value P = 19
C = PE mod n C = 66
To compute the plaintext P of plaintext C:  
P = CD mod n P = 19


Public Key Cryptography In Summary


Authentication

This is the technique by which a process verifies that its communication partner is who it is supposed to be and not an imposter.

Two parties who wish to communicate securely can use public key cryptography to establish a session key, useful for a single transaction. This is useful since single key cryptography is much faster than public key cryptography.


Authentication Example

A wishes to communicate with B:
Secure exchange of session key
In the above, the R's are random numbers. Initially, A says "I am A" and suggests a random number, all encrypted with B's public key.

B responds with A's random number, a random number of her own, and a suggested session key, all encrypted with A's public key.

Finally, A responds to B by encryping B's random number with B's suggested secret key. Because no one else could have the information to know KS, B is now confident that it is talking to A.


Digital Signatures

These are a form of authentication applied to electronic documents. They have three basic functions:

Public key cryptosystems can provide authentication if, in addition to:

P = D ( E ( iP ) )
we also have:
P = E ( D ( P ) )
This is true for RSA. In this case, we can do:
Digital signature operation

Message Digests

A criticism of previous signature methods is that they couple both authentication and secrecy. If authentication only is desired, a message digest is a one-way hash function which has the following characteristics:

The Internet standard for message digests is the MD5 algorithm, invented by Rivest. Software implementations of this algorithm are widely available.

MD5 produces a 128 bit (16 byte) message digest.

It is also possible to use public key cryptography to implement the message digest function. In this case, a sender first computes a message digest using his/her private key, then appends this to the message as sent. A recipient can read the message, and can confidently believe that it originated from the sender.


Clipper (The Politics of Encryption)

The USA and most other governments are very interested in encryption.


Encryption as Munitions

The US government believes that control of encryption is essential in fighting terrorism and organised crime.

Some good Internet resources on cryptography are available here.


This lecture is also available in PostScript format. The tutorial for this lecture is Tutorial #19.
La Trobe Uni Logo [Previous Lecture] [Lecture Index] [Next Lecture]
Copyright © 2000 by Philip Scott, La Trobe University.
Valid HTML 3.2!