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:
Ea
- to communicate with
a, encrypt your
message using Ea,
giving Ea(P)
- This message can only be read by decrypting with
Da, where
Da is secret:
Da ( Ea ( 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 10100).
- 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
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
- 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 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:
- 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
#20.
[Previous Lecture]
[Lecture Index]
[Next Lecture]
Phil
Scott