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
(typically larger than 10100).
n = p * q
and
x = (p-1)*(q-1)
x
and call
it d
. This means that d
is
not a prime factor of x
or a multiple of it.
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: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 |
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.
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.
Public key cryptosystems can provide authentication if, in addition to:
we also have:P = D ( E ( iP ) )
This is true for RSA. In this case, we can do:P = E ( D ( P ) )
P
, it is easy to calculate
MD(P)
.
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.
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.
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.