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:

An encryption method E is applied to the plaintext P giving E(P), the ciphertext.
A decryption method D can be applied to the ciphertext to yield the plaintext, thus:
```
P = D ( E ( P ) )
    
```
It is exceedingly difficult to deduce D from E.
E cannot be broken by any standard attack.

This system works as follows:

Each user publishes their public key: E_a
to communicate with a, encrypt your message using E_a, giving E_a(P)
This message can only be read by decrypting with D_a, where D_a is secret:
```
D_a ( E_a
    ( P ) ) = P
```

^[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.

Choose two large primes, p and q (typically larger than 10¹⁰⁰).
compute n = p * q and x = (p-1)*(q-1)
Choose a number relatively prime to x and call it d. This means that d is not a prime factor of x or a multiple of it.
Find e such that e * d = 1 mod x.

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 2^k < n is true.

To encrypt: C = P^e (mod n)
To decrypt: P = C^d (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`
`K_p` is then `n` concatenated with `E`	`K_p = 119, 5`

To create the secret key, compute D such that (D * E) mod x = 1 K_s = 119, 77

To compute the ciphertext `C` of plaintext `P`, treat `P` as a numerical value	`P = 19`
`C = P^E mod n`	`C = 66`

To compute the plaintext `P` of plaintext `C`:
`P = C^D mod n`	`P = 19`

Public Key Cryptography In Summary

A public key is used to encrypt and a separate, different private key to decrypt the message.
Each party involved generates a key pair.
Each party publishes their public key.
Each party secures their private key, which must remain secret.
Assuming A desires to send a message to B, it first encrypts the message using B's public key
B can decrypt the message using its private key. Since no one else knows B's private key, this is absolutely secure - no one else can decrypt it.
There still remain difficult problems of authentication of public keys, compromised keys, bogus & out of date keys. Further, Public Key encryption is very, very slow compared to single key systems.
A very useful way of using public key cryptography is as a means of distributing secret keys for conventional single key cryptography.

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.

This turns out to be one of the trickiest problems in cryptography.
Can be done if both parties share a common secret key or keys, however...
Diffie-Hellman key exchange protocol can be used to establish shared secret keys but is complex and unwieldy.
More usefully, trusted Key Distribution Centres perform this function.
It is possible to establish authentication using a public key system.

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:

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 K_S, 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:

The receiver can verify the claimed identity of the sender
The sender cannot later repudiate the contents of the message
The receiver cannot possibly have concocted the message himself.

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:

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:

Given P, it is easy to calculate MD(P).
Given MD(P), it is effectively impossible to find P.
No one can generate two messages that have the same MD(P).

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.

Over the last few years, the USA has proposed several variations of its Clipper encryption systems.
- The original Clipper system was a hardware encryption device based on the (secret) skipjack encryption algorithm. It was originally intended to replace DES.
- Chip users (manufactuers?) register key with government: key escrow. The key is split into two halves, which are stored independently with different government agencies. Current version: key recovery.
- Court-approved "wiretap" (ie, decryption) operations require both halves of the key to access any data transmissions. In addition, a released key can be coded so that it only works for a limited time period.
- Still has many problems: Privacy concerns, Commercial organisations are nervous about trusting the government. In addition, there is some doubt about whether snooping decryption could be avoided by clever users.
- Opinion: it won't fly.

Encryption as Munitions

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

Strong encryption is classified in the USA as munitions, exactly the same as guns, bombs and rockets. None of these may be exported without special permission.
- This is the reason why export editions of Netscape, etc, use a weak ((previously 40 bit key, now 56?) encryption method when communicating with "secure" servers -- see later.
- The ban has been ridiculed in many quarters: encryption algorithms are well known (they can and have been printed on T shirts) and strong encryption is available from many non-US sources. However, if you want to run US-sourced software, you're stuck.
Things could be worse: in France, encryption of any form whatsoever was banned until very recently, unless you gave the government copies of the keys. Other countries permit any encryption with no limits at all.
It's not at all obvious what the current situation is in Australia...

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]