So far all the cryptosystems discussed have been private/secret/single key (symmetric) systems. All classical, and modern block and stream ciphers are of this form.
Will now discuss the radically different public key systems, in which two keys are used. Anyone knowing the public key can encrypt messages or verify signatures, but cannot decrypt messages or create signatures, counter-intuitive though this may seem. It works by the clever use of number theory problems that are easy one way but hard the other. Note that public key schemes are neither more secure than private key (security depends on the key size for both), nor do they replace private key schemes (they are too slow to do so), rather they complement them.
Note here the keys are created by the receiver not the sender (as is more common in private key systems, though either party can do so). In public key systems, the owner of the keys is the receiver, since they need to decrypt the message.
Public key schemes utilise problems that are easy (P type) one way but hard (NP type) the other way, eg exponentiation vs logs, multiplication vs factoring. Consider the following analogy using padlocked boxes: traditional schemes involve the sender putting a message in a box and locking it, sending that to the receiver, and somehow securely also sending them the key to unlock the box. The radical advance in public key schemes was to turn this around, the receiver sends an unlocked box to the sender, who puts the message in the box and locks it (easy - and having locked it cannot get at the message), and sends the locked box to the receiver who can unlock it (also easy), having the key. An attacker would have to pick the lock on the box (hard). There is one problem - how does the sender know they have the correct unlocked box for the person they wish to send a message to? Thats the key distribution problem, which we'll talk about soon.
Distinguish between 3 classes of public key algorithms, depending on their use. We will consider each of these classes of algorithms in turn.
Public key schemes are no more or less secure than private key schemes - in both cases the size of the key determines the security. Note also that you can't compare key sizes - a 64-bit private key scheme has very roughly similar security to a 512-bit RSA - both could be broken given sufficient resources. But with public key schemes at least there's usually a firmer theoretical basis for determining the security since its based on well-known and well studied number theory problems.
The idea of public key schemes, and the first practical scheme, which was for key distribution only, was published in 1977 by Diffie & Hellman. The concept had been proeviously described in a classified report in 1970 by James Ellis (UK CESG) - and subsequently declassified in 1987. See History of Non-secret Encryption (at CESG). Its interesting to note that they discovered RSA first, then Diffie-Hellman, opposite to the order of public discovery!
Diffie-Hellman key exchange is widely used in a number of products to establish a common secret key, which is then used in a block cipher to encrypt a communications link (cf SSH). Is secure against passive eavesdropping, though additional steps are needed to secure against active attack.
p
(~200
digits)
a
a primitive root mod p
xA < p
xB < p
yA = axA mod p yB = axB mod p
yA
and
yB
respectively The prime p and primitive root a can be common to all using
some instance of the D-H scheme. Note that the primitive root a
is a number whose powers successively generate all the elements mod p. Alice
and Bob choose random secrets x
's, and then "protect" them
using exponentiation to create the y
's. For an attacker
monitoring the exchange of the y
's to recover either of the
x
's, they'd need to solve the discrete logarithm problem, which
is hard.
KAB = axA.xB mod p = yAxB mod p (which B can compute) = yBxA mod p (which A can compute)
KAB
may then be used as a session key in a
private-key cipher to secure communications between Alice and Bob
The actual key exchange for either party consists of raising the others "public key' to power of their private key. The resulting number (or as much os as is necessary) is used as the key for a block cipher or other private key scheme. For an attacker to obtain the same value they need at least one of the secret numbers, which means solving a discrete log, which is computationally infeasible given large enough numbers.
p=97
with primitive root a=5
xA=36
& computes public
key yA=536=50 mod 97
xB=58
& computes public
key yB=558=44 mod 97
K=4436=75 mod
97
K=5058=75 mod 97
xA=log550=36 mod 97
(hard), and then
doing Alice's key computation K=4436=75 mod 97
This examples illustrates the use of DH key exchange. Note that the "square and multiply" algorithm, with suitable modulo reductions would be used to do the calculations. Also see how an attacker would have to solve the "hard" discrete log problem in order to obtain the shared secret.
Implementation of public key crypto requires the use of multi-precision arithmetic libraries. A number of these are now commonly available. Show slides illustrating multi-digit calcs.
a0, ... ,
an-1
of base bb
is the "most convenient" word size n-1 A = SUM ai.bi i=0
n-2 A = { SUM ai.bi + an-1.bn-1 (mod jm) } mod m i=0
Idea here is that, as always, can modulo reduce numbers at
any time. In particular if think of a number as the sum
A=Atop+Arest
can freely replace
Atop
with its modulo reduced equivalent. And keep
doing this till the number is "small enough".
FOR i = n-1 to d do WHILE A[i] != 0 do j = A[i]; A[i] = 0; A = A + bi-d.R[j]; END WHILE END FOR
A[i]
is the ith character of number
AR[j]
is the jth integer residue from the array
Rn
is the number of symbols in Ad
is the
number of symbols in the modulusTo implement Chivers Algorithm first compute an array of all
possible Atop
values (obviously trade-off size of
digit with size of array - 4 to 8 bits is most likely). Then while doing
calculations simply replace the top "digit" with its modulo reduced
equivalent. Can even do this process in stages (ie if need a "top digit"
thats too large, could do in halves etc, with separate arrays). Show slides
illustrating multi-digit calcs with modulo reductions.