E
is applied to the plaintext
P
giving E(P)
, the ciphertext.
D
can be applied to the ciphertext
to yield the plaintext, thus:
P = D ( E ( P ) )
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.
p
and
q
.
n = p * q
and x =
(p-1)*(q-1)
x
and call it
e
. This means that e
is not a prime
factor of x
or a multiple of it.
d
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:The public key, used to encrypt, is thus:C = Pe (mod n)
To decrypt:P = Cd (mod n)
(e, n)
and the private key, used to decrypt, is
(d, n)
)
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 from
ciphertext C : |
|
P = CD mod n |
P = 19 |
n = p * q
. The security
of the system relies on the fact that n
is hard to
factor -- that is, given a large number (even one which is known to
have only two prime factors) there is no easy way to discover what they are.
This is a well known mathematical fact. If a fast method of factorisation
is ever discovered then RSA will cease to be useful.
It is obviously possible to break RSA with a brute
force attack -- simply factorise n
. To make this
difficult, it's usually recommended that p
and
q
be chosen so that n
is (in 2003
numbers) at least 1024 bits.
One excellent feature of RSA is that it is symmetrical. We already know that if you encrypt a message with my public key then only I can decrypt that ciphertext, using my secret key. However, it also turns out that a message encrypted with my secret key can only be decrypted with my public key. This has important implications, see later.
The RSA algorithm operates with huge numbers, and involves lots of
exponentiation (ie, repeated multiplication) and modulus arithmetic. Such
operations are computationally expensive (ie, they take a long
time!) and so RSA encryption and decryption are incredibly
slow, even on fast computers. Compare this to the
operations involved in DES (and other single-key systems) which
consist of repeated simple XOR
s and transpositions. Typical
numbers are that DES is 100 times faster than RSA on equivalent hardware.
Furthermore, DES can be easily implemented in dedicated hardware (RSA is,
generally speaking, a software-only technology) giving a speed improvement of up
to 10,000 times.
Public key cryptosystems can provide authentication if, in addition to:
we also have:P = D ( E ( P ) )
This is true for RSA. Now consider Alice, who wishes to authenticate herself to a communications partner Bob. Bob already knows Alice's public key.P = E ( D ( P ) )
Alice announces to Bob that she wishes to communicate. Bob responds by choosing a large, single-use random number![]()
R
(sometimes called a
nonce) which he sends to Alice. Alice encrypts the random
number using her private key, da
and returns the encrypted value to Bob. Bob applies Alice's public
key to the returned value, and if it decrypts to R
then he can be certain of the identity of his communication partner. It's
obvious that this protocol could be extended to verify the identity of Bob as
well.
The recipient's public key can (optionally) be used to encrypt the message, so that only the recipient can read it. This step is only necessary if both authentication and secrecy are needed. We can take a plaintext message P, and encode it thus:
P
, it is easy to calculate
MD(P)
. MD(P) is much shorter than the message itself.
MD(P)
, it is effectively impossible to find
P
.
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 which can be appended to the message. Message digests such as MD5 are often referred to as cryptograhic checksums, because they reveal whether the message has been altered.
Typical usage of message digests combines public key cryptography with the message digest function. In this case, a sender first computes an MD5 digest as above, then encrypts it using her private key, and finally appends the encrypted digest to the message. A recipient can read the message, and can be confident that it originated from the sender.
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 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 new world of Internet-based business.
C
, the ciphertext, from
P
, the plaintext using the secret key
Kp
, defined as n
concatenated
with E
.
To decrypt, simply replace
C := 1 begin for i := 1 to E do C := MOD( C * P, n ) end
E
with D
and P
with
C
in the above algorithm. Exercise: implement this in your
favourite programming language, and prove it works...