Subjects -> Computer Networks -> Lectures -> Lecture #20

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

The original algorithm proposed by Diffie and Hellman for implementing Public Key Cryptography turned out to be insufficiently strong to implement a secure system. However, the idea of this type of cryptosystem was considered worthy of further work.

^[1] This is the standard story on the origins of Public Key Cryptography. 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. The basic technique is:

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, used to encrypt, is thus: (e, n) and the private key, used to decrypt, is (d, n))

RSA Example -- Key Generation

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

RSA Example -- Encryption and Decryption

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 from ciphertext 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. The most common example of this, which most of us have probably used, is the Secure Sockets Layer (SSL) cryptography used in the World Wide Web, see later.

Authentication

This is the technique by which a process verifies that its communication partner is who it is believed 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. Each already has the other's public key in their possession.

In the above, the R's are random numbers. Initially, A says "I am A" and suggests a random number, the entire message being 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 (such as that given on the previous slide) is that they combine 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 as above, then encrypts it using her private key, then finally appends this to the message as sent. A recipient can read the message, and can be confident that it originated from the sender.

We shall see more applications of Digital Signatures, and Public Key Crypto in general, when we look at technical aspects of E-Commerce a little later in the subject.

The Politics of Encryption

Most of the governments of the world are very interested in encryption.The problem for governments is that strong (ie, unbreakable) encryption can be used by criminals (or political enemies?) to communicate securely, so there is a an obvious vested interest in restricting it. On the other hand, strong encryption is absolutely necessary to enable Internet-based commerce (we see some applications later), so a government which restricts its use is limiting its people from participating in the world of Internet-based business.

Over the past 20 years, the USA government has proposed and/or mandated a variety of encryption laws to either restrict the use of strong encryption, or to force developers to provide a "back door" to their systems, which would allow officials to read encrypted data. In addition, for many years they have classified all forms of strong encryption as munitions, and restricted export of encryption products.

Within Australia, the position is not so clear. Apparently, export of cryptographic software is still restricted, but private use is unrestricted. Correct, up-to-date, information is hard to find!

Other governments (eg France, Malaysia, China, etc) have, at various times, simply banned the private use of strong encryption. In most cases, these policies have subsequently been reversed.

The tutorial for this lecture is Tutorial #20.
La Trobe Uni Logo

[Previous Lecture] [Lecture Index] [Next Lecture]

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