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:

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:

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


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


RSA Example -- Encryption and Decryption

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 from ciphertext 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 believed 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. Each already has the other's public key in their possession.
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, 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 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 (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:

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]
Copyright © 2001 by Philip Scott, La Trobe University.
Valid HTML 3.2!