The ability to attack or misuse a digital cash system depends a lot on the cryptography
and cryptographic protocols involved. A good cash system uses good cryptography.
Good cryptography requires strong algorithms, keys of adequate length, and secure key
management. Without these, there can be little privacy.
A good cash system uses good protocols. The digital cash system of Stefan Brands, for
example, is largely based on digital signatures--the Schnorr signature scheme, in
particular. The system, properly implemented, is thus only as secure as the underlying
signature system. If there are flaws in the latter, the attractive features of anonymous
digital cash disappear also--features like untraceability, unlinkability, and security for all
parties.
If we are looking for privacy and security in banking, we can't ignore cryptography and
we can't ignore mathematics. The ability of digital cash systems to give some measure of
security and privacy has more to do with number theory than banking regulations.
Algorithms--such as DES or RSA--are, in general, publicly known. This has the
advantage that any weaknesses in an algorithm can be found by researchers. Any attempt
at "security through obscurity", by keeping an algorithm secret, is usually self-defeating,
because it will most likely simply mask weaknesses in the algorithm itself which could be
exploited by anyone who has figured out what the algorithm is. But when a good
publicly-known algorithm is used, security depends on the length of the
key, which may be thought of as a string of 0s and 1s used in the
algorithm to transform the data.
One example of a key transformation is in connection with the XOR function
used in binary arithmetic. The XOR function follows these rules of binary addition:
Note: In order to read the following text properly, your web browser
must be able to handle subscripts and superscripts; i.e. the html commands “sub” and
“sup”. These commands are used sparingly, but they are used.
| M: | 1011 |
| k: | 1010 |
| C: | 0001 |
But, knowing the key, it is easy to restore the original message. All we have to do is add the key k to the encrypted message C, following the XOR rules of addition, and we are left with the original message M:
| C: | 0001 |
| k: | 1010 |
| M: | 1011 |
Security depends on the length of the key k. Here there are sixteen possible keys of length four. The first binary digit can be either zero or one, so there are 2 possibilities. The second digit can also be either of two values, so there are 2x2 = 4 possible keys of length two. There are 2x2x2 = 8 possibilities for a key of length three. A key of length four has sixteen possibilities. Sixteen is 2 to the 4th power. In general, for a key of length N, there are 2 to the Nth power (2^N) possible keys.
Commercial DES uses keys of length 56, so the key space has 2^56 (2 to the 56th power) possibilities. As large as this key space is, it is no longer large enough for security, given current techniques of cryptanalysis. It is even possible to mount a "brute force" attack on a message. A brute force attack is one that simply tries out every possible key. On the other hand, a key space of 2^128 is quit secure--at least with respect to a brute force attack. A key space of 2^128 is 2^72 times as large as the common DES key space of 2^56.
XOR addition is used in two DES encryption modes. Electronic code-book (ECB) mode encrypts each 64-bit text block individually. Two other, more secure, modes, however, make each encryption block dependent on each of the preceding text blocks. Cipher Block Chaining (CBC) is a mode of DES encryption in which the current 64-bit plaintext block is XORed with the previous cipherblock before encryption with the 56-bit DES key k. If C(t) is the t-th 64-bit cipher block, and M(t) is the current 64-bit message block, then in CBC,
C(t) = Ek(M(t) “+” C(t-1)). (CBC)
Cipher Feedback (CFB) is a mode of DES encryption in which each plaintext block is XORed with the previous cipherblock text after the latter is encrypted with the 56-bit DES key. In CFB,
C(t) = M(t) “+” Ek(C(t-1)). (CFB)
(The block sizes can be smaller than 64-bits in CFB.)
The key k used in the previous XOR example was symmetric. The same key was used to encrypt and decrypt. DES and IDEA are two well-known symmetric key algorithms. Symmetric key algorithms tend to be somewhat ad hoc-- clever cookbook recipes that work. Public key, or asymmetric, systems, by contrast, use two different keys for encryption and decryption. RSA is a well-known asymmetric system. Public key systems are typically based on relationships from number theory, and the process of encryption works by raising the message M to some power a: C = M^a. Decryption works by raising the encrypted message C to another power b: M = C^b. The first key, or power, a will be known to everyone--hence it is called a "public" key-- while the key b will be kept secret by the user--hence it is called a "secret" or "private" key
B. Some Preliminary Mathmatical Notation
In a symmetric encryption system,
Dk(Ek(M)) = M, because the same key
is used to decrypt the message that was used to encrypt it. In a public-key system, one
key must be used to encrypt and the other to decrypt. Hence
Dsk(Epk(M)) = M and also
Dpk(Esk(M)) = M. In the first case, the
message is encrypted with Alice's public key, then decrypted by Alice using her secret
key. In the second case, common in digital signatures, Alice encrypts the message with
her secret key, and then it is decrypted by someone else using Alice's public key.
The sign “^” will be used to mean “raised to the power of”; for example,
2^3 = 8, since 2 raised to the power of 3 equals 8. (Note that in the computer
language Fortran, b^y would be written b**y.) A single *, by
contrast, denotes multiplication: “three times b equals 12” would be
written “3*b = 12”, or perhaps simply as “3b = 12”. The notation
log_b (y) will denote the logarithm of y with respect to base b.
For example, log_2 (8) = 3, since the logarithm of 8 (to the base 2) is 3.
Finally, mod p will denote “arithmetic done modulo p”. By this we
will mean "divide by p, and keep the remainder r, 0<= r < p."
Modulo 3, for example, will divide any positive whole number by 3, and take the
remainder (which will be either 0, 1, or 2). For example, 7 mod 3 = 1, since 3
goes into 7 twice, with 1 left over. The number we divide by (3, in this example) is called
the "modulus". Similarly, 62 mod 25 = 12. That is, when 25 is the modulus,
62 = 25*2 + 12 = 12. But if 3 were the modulus, 62 = 3*20 + 2 = 2.
In general, we will write a = b mod n, meaning that a mod n = b mod
n.
For example, 67 = 11 mod 7, because 67 mod 7 = 4 and also 11 mod 7 = 4. Hence
a= b mod n
means for some integers
k1 and k2,
a = k1*n + r (0<= r < n)
Hence also
a - b = (k1-k2)*n,
so that n divides into
a-b a whole number of times (namely, k1-k2 times). Restated,
“n divides a-b”, which may also be written
Thus, in the previous example,
67 = 11 mod 7
means for integers
k1 = 9 and k2 = 1,
67 = 9*7 + 4 (0<= 4 < 7)
Hence also
67-11 = (k1-k2)*7 = (9-1)*7 = 8*7,
so that 7 divides into 67- 11 a whole number of times (8 times). We could also
write 7|(67-11) or 7|56.
If we do calculations
this way, using whole numbers, dividing by the modulus, and throwing away everything
except the remainder, we are doing modular arithmetic. Most computers
are not constructed to do modular arithmetic very well, because they aren't set up to keep
track of whole numbers beyond a certain length: they would much rather stick in a
decimal point somewhere, and keep track of only a few numbers (floating point
arithmetic). Consider, for example, 3.7B3579D4F6821 x 16^73. This is a very
large number, but the computer essentially just keeps track of 16 hexadecimal numbers
(64 bits): namely 3,7,B,3,5,7,9,D,4,F,6,8,2,1 and the digits in the power: 7 & 3. But
public key cryptography may use "keys" whose length is 2048 bits or more.
Therefore most computer implementations of public key cryptography involve computer
software which works around the hardware limitations, or else use specially constructed
cryptographic chips.
Remember also that by convention exponentiations take place before multiplications.
Hence 3*5^2 = 3*25 = 75. But (3*5)^2 = 15^2 = 225. Note also that (3*5)^2 = 3^2*5^2
= 9*25 = 225. That is, in general, (x*y)^z = x^z*y^z.
C. Modular Arithmetic and the Groups Z(p)* and G(q).
In most of the calculations involving public key cryptography and digital cash, we will be
dealing with the set of integers from 0 to p-1, where p is some
large prime. This follows from the fact that we will be doing multiplication
mod p. We will also be using a set of integer powers from 1 to
q, where q is some large prime number that divides p-1.
That is, multiplication and exponentiation (taking powers) will take place within the
groups Z(p)* and G(q), which we will define and explain in this section.
The two groups Z(p)* and G(q) are very important for public key cryptography and
digital cash. They play roles in Diffie-Hellman key exchange, in the Schnorr signature
scheme, in the Digital Signature Algorithm, and in the digital cash system of Stefan
Brands. That is, the arithmetic is done in Z(p)* or in a group G(q) of powers of prime
order q, where q divides p-1. So it is important to understand
what these groups are.
The set Z(p)* = {1, 2, 3, 4, ..., p-2, p-1}. If we multiply any two
numbers in this set together, and reduce the product mod p, the result is a
number in the set. So the set is closed under multiplication. In addition,
we if take any number k from the set, there exists another number k^-1,
such that k*k^-1 = 1 mod p. That is, any number in the set has
a multiplicative inverse. These two characteristics mean that Z(p)* is a
group under multiplication mod p. Sometimes the term
"multiplicative group" is used. Since Z(p)* is a group under multiplication, it is also a
group under exponentiation (taking powers), since the n-th power of a
number is simply the multiplication of a number by itself n times. (Note that 0 is
omitted from Z(p)* because it doesn't have a multiplicative inverse. If we add 0 to the
set Z(p)*, we get the set Z(p), which consists of all remainders mod p, including
0.)
For example, Z(11)*
= {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. If we multiply 5 and 8 from the set, we have 5*8 = 40 = 7
mod 11, and 7 is an element in the set. Also we have 5*9 = 45 = 1 mod 11, so that 9 is
the multiplicative inverse of 5. Similarly, 5 is the multiplicative inverse of 9. If
k=5, then k^-1 = 9. Similarly, 2 and 6 are multiplicative inverses, as
are 3 and 4. What is the multiplicative inverse of 10? (Answer: 10 is its own
multiplicative inverse, since 10*10 = 100 = 1 mod 11.) Also, if we exponentiate a
number from the set, say 6 to the third power, we have 6^3 = 6*6*6 = 216 = 7 mod 11,
we are again left with an element in the set. The set is closed under multiplication and
exponentiation mod 11, and each element has an inverse, so Z(11)* is a group.
Each element has a
multiplicative inverse in Z(p)* because p is a prime number. And since
p is prime, the only common divisor of p and each of the numbers in the
set Z(p)* = {1, 2, 3, ..., p-1} is 1. Restated, the greatest common divisor
(gcd) of p and any number in the set is 1. That is, gcd(1,p) =1,
gcd(2,p) = 1, gcd(3,p) = 1, . . . , gcd(p-1,p) = 1.
The same is not true if
we do modular multiplication with a composite number (i.e. a number which is
the product of at least two numbers, each greater than 1). For example, the number 15 =
3*5, so it is composite. Suppose we do mutiplication mod 15, using numbers
from the set {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}. What is the inverse of the
number 6 from this set? Answer: there is no inverse for 6, as we can see by multiplying
6 by all numbers less than 15:
6*0 = 6*5 = 6*10 = 0 mod 15
There is no number which
multiplied by 6 equals 1 mod 15. In addition, we obtain 0 as the result of some
multiplications, so the set is not closed. (6 and 5 are in the set, but 6*5 mod 15 = 0,
which is not in the set.) Hence, this set (the set of whole numbers from 1 to 14) is not a
multiplicative group mod 15.
Returning to the set
Z(p)*, we can define some other operations, in addition to multiplication and
exponentiation. We can define division by k as multiplication
by the inverse of k, namely k^-1. Thus 8/k = 8*k^-1,
by definition. If k = 9 in Z(11)*, then 8/9 = 8*9^-1 = 8*5 = 40 = 7 mod 11.
Similarly, 3/10 = 3*10^-1 = 3*10 = 30 = 8 mod 11.
Let g be a
member of Z(p)*. Then g is said to be a generator mod
p if the set of powers of g, namely the set {g^1 mod
p, g^2 mod p, . . ., g^(p-1) mod p},
contains, in some order, all the members of Z(p)*:
{g, g^2, g^3, ... , g^(p-2), g^(p-1)}
mod p
= {1, 2, 3, ... , p-2, p-1}, in some order.
That is, the set Z(p)* = {1, 2, ... , p-1} represents a rearrangement of {g,
g^2, g^3, ... , g^(p-1)}, when all calculations are done mod
p. (For convenience we write mod p outside the brackets when it
applies to each element in the set, or omit it altogether, if it is understood.)
For example, 3 is a generator of Z(7)*, since
3^1 = 3 mod 7
Or, restated,
{3, 3^2, 3^3, 3^4, 3^5, 3^6} = {1, 2, 3, 4, 5, 6}
when calculations are done mod 7. The two sets have the same elements,
although not necessarily in the same order. A rearrangement of the order of the elements
of a set is called a permutation. The powers of the generator 3 give a
permutation of Z(7)*.
A generator-tuple mod p is a set of k generators, which
are all different. That is, {g1, ... , gk} is a
generator-tuple if each
gi is an generator mod p, and also gi
is not equal to gj , if i is not equal to j.
For example, {3, 5} is
a generator-tuple of Z(7)*, because both 3 and 5 are generators of Z(7)*. Each element
in Z(7)* can be represented both as a power of 3 and a power of 5:
1 = 3^6 mod 7 = 5^6 mod 7
The number 2 is not
a generator mod 7, because the powers of 2 only yield 1, 2, or 4, mod 7:
{2, 2^2, 2^3}
= {1, 2, 4}.
Note, however, that the
powers of 2 mod 7 yield a subset of Z(7)*. The set {1, 2, 4} is a subset of {1, 2, 3, 4, 5,
6} = Z(7)*. The number 2 is thus said to "generate the subgroup G(3)" mod 7.
The designation "G(3)" means there are 3 elements in the group. Alternatively stated, 3
is the lowest power of 2 that yields 1 mod 7. G(3) is a group, because it is closed under
multiplication mod 7:
Note that the number 4 is also a generator of G(3) = {1, 2, 4} mod 7, since
{4, 4^2, 4^3} = {4, 2, 1} mod 7 = {1, 2, 4}.
A group generated by an element g is said to have order q mod
p provided
q is the lowest power such that g^q = 1 mod p.
The two
generators of Z(7)* that we saw previously, namely 3 and 5, are said to have order
6 mod 7, because 6 is the smallest power of 3 or 5 that gives 1 mod 7. That
is, 1=3^6=5^6 mod 7, and no smaller power has this property. By contrast, the
generators of G(3), namely 2 and 4, have order 3, because 2^3 = 4^3 = 1 mod 7,
and no lower power of 2 or 4 equals 1.
In general, for
q prime, 1< q < p, we define G(q) as the group
(or subgroup) of prime order q, mod p, if for some generator g,
1 < g < p, we have that {g, g^2, g^3, ...,
g^q} is a subset of Z(p)*. That is, the powers of g yield each of
the elements in the subgroup. Note, by definition, q is the lowest power of g
that gives 1; hence, g^q = 1 mod p. Thus powers larger than
q simply start over and run through the same set of numbers. If g^q =1
mod p, then g^(q+1) = g mod p, g^(q+2) =
g^2 mod p, and so on.
For example, 2^3 = 1
mod 7. So higher powers of 2 yield the same numbers over and over:
2^4 = 2^1 = 2 mod 7
Note that if g
is an element of the group Z(p)*, then g is a generator of Z(p)* if
g is an element of order p-1. That is, if g^(p-1) = 1, and
no lower power equals 1. For then, it would necessarily follow that the powers of g
mod p--namely g^1, g^2, ..., g^(p-1)--run through all the numbers
1, 2, ..., p-1.
b = k2*n + r .
“n|(a-b)” .
11 = 1*7 + 4 .
6*1 = 6*6 = 6*11 = 6 mod 15
6*2 = 6*7 = 6*12 = 12 mod 15
6*3 = 6*8 = 6*13 = 3 mod 15
6*4 = 6*9 = 6*14 = 9 mod 15.
3^2 = 2 mod 7
3^3 = 6 mod 7
3^4 = 4 mod 7
3^5 = 5 mod 7
3^6 = 1 mod
7.
2 = 3^2 mod 7 = 5^4 mod 7
3 = 3^1 mod 7 = 5^5 mod 7
4 = 3^4 mod 7 = 5^2 mod 7
5 = 3^5 mod 7 = 5^1 mod 7
6 = 3^3 mod 7 = 5^3 mod 7.
1*1 = 1 mod 7 2*1 = 2 mod 7 4*1 = 4 mod 7
1*2 = 2 mod 7 2*2 = 4 mod 7 4*2 = 1 mod 7
1*4 = 4 mod 7 2*4 = 1 mod 7 4*4 = 2 mod 7
and because each element in G(3) also has an inverse.
2^5 = 2^2 = 4 mod 7
2^6 = 2^3 = 1 mod 7
etc.
Fermat's theorem says that for any prime p, and number
k not divisible by p, we have
Of course, the integers 1, 2, 3, . . ., p-1 are not divisible by p, so any of these integers raised to the power p-1 equals 1 mod p, by Fermat’s theorem.
Hence for k an element of Z(p)*, we have k^(p-1) = 1 mod p.
For example, for Z(11)*, we have p-1 = 10, and a check shows that, mod 11,
1^10 = 2^10 = 3^10 = 4^10 = 5^10 = 6^10 = 7^10 = 8^10 = 9^10 = 10^10 = 1.
Note that we are not saying that any number k<p has order p-1 mod p. The order of k may be smaller than this. For example, 2 has the order 3 mod 7, as 2^3 =1 mod 7. But it is also true that 2^(7-1) = 2^6 = 1 mod 7, as required by Fermat's theorem. And obviously 2^6 = (2^3)^2 = (1)^2 = 1 mod 7.
For example, in the case p = 7, we have p-1 = 7-1 = 6, so the order of any element must divide into 6 a whole number of times. We saw previously that 3 and 5 have order 6 in Z(7)*, and 6|(7-1). Similarly, we saw that 2 and 4 have order 3 mod 7, and 3|(7-1).
The reason it works this way is because if an element g is of order q mod p, then g^q =1 mod p. But it's also true by Fermat's theorem that g^(p-1) = 1 mod p. So if q didn't divide p-1 a whole number of times, then for some number k, p-1 = k*q + r, where 0 <r <q. Thus we would have that 1 = g^(p-1) = g^(k*q+r) = (g^q)^k*g^r = 1*g^r, which implies g^r = 1. Which in turn implies g has order r less than q, a contradiction.
If n = p is prime, then all positive numbers less than p are relatively prime to p, so t(p) = p-1.
For example, for n = p = 7, the numbers 1, 2, 3, 4, 5, and 6 are all relatively prime to 7, so t(7) = 6. For n = 4, the numbers 1, 3 are relatively prime to 4, so t(4) = 2. For n = 15, the numbers 1, 2, 4, 7, 8, 11, 13, 14 are relatively prime to 15, so t(15) = 8. (The other numbers, namely 3, 5, 6, 9, 10, 12, have divisors in common with 15.)
Note that Euler's theorem applies to composite numbers n, as well as prime numbers. For example let n = 15. The number 2 is relatively prime to 15, so by Euler's theorem we have
2^t(15) = 2^8 = 1 mod 15.
We will use Euler's theorem later when we look at the RSA crypto-system. RSA uses large numbers n which are composite (namely the product of two primes), and hence Fermat's theorem does not apply: it is not true, in general, that k^(n-1) = 1 mod n, for n composite, even if k is relatively prime to n. For example, 2^(15-1) = 2^14 = 4 mod 15. That is, the order of k does not necessarily divide n-1, for n composite. The number 2 is relatively prime to 15, but it has order 4, as 2^4 = 1 mod 15. And 4 does not divide 15-1 = 14. However, the order 4 does divide t(15) = 8.
For example, the number of generators mod 7 is t(7-1) = t(6). Now t(6) is by definition the number of positive integers less than 6 that are relatively prime to 6. There are two such numbers; namely, 1 and 5. So there are a total of two generators mod 7. Both of these generators (namely, 3 and 5) were shown previously. (The significance of the numbers 1 and 5 here is that if we have a generator g, then both g^1 and g^5 will be generators. Thus 3 and 3^5 = 5 mod 7 are generators. Alternatively, since 5 is a generator, both 5 and 5^5 = 3 mod 7 are generators.)
Consider now the group G(q) of prime order q mod p (i.e., both p and q are prime). Since the order of any element mod p must divide p-1, it follows that q must divide p-1. How many generators of the subgroup G(q) are there? The answer is that for each m that divides p-1, there are t(m) generators of order m, where t is Euler's totient function. In the case m=q is prime, there are thus t(q) = q-1 generators. That is, there are q-1 generators of the subgroup G(q) of prime order q mod p. This fact assures us that for large q we have plenty of generators to choose from.
For example, since 3 divides 7-1 = 6, there are t(3) = 2 generators of order 3 mod 7. That is, there are two generators of the subgroup G(3) = {1, 2, 4}. (Note that both 2 and 4 are generators of G(3).) Similarly, since 2 divides 7-1 = 6, there are t(2) = 1 generator of order 2 mod 7. (Check that 6 is a generator of order 2 mod 7, yielding the subgroup G(2) = {1, 6}.)
Notice that since 2, 3, and 6 all divide p-1 = 7-1, the possible subgroups mod 7 are these:
| Generators gi mod 7 | |
| G(2) = {1, 6} | 6 |
| G(3) = {1, 2, 4} | 2, 4 |
| G(6) = {1, 2, 3, 4, 5, 6} | 3, 5 |
For p = 23, and q = 11, there are t(11) = 10 generators of G(11) = {2, 4, 8, 16, 9, 18, 13, 3, 6, 12, 1}. The number 2 is one such generator mod 23. Any member of G(11), except the integer 1, is a generator of the group.
Note in this last example that 2 and 22 also divide p-1 = 23-1. There are thus t(2) = 1 generator of G(2), and t(22) = 10 generators of G(22)=Z(23)*. Thus, of the 22 elements in Z(23)*, 10 are of order 22, 10 of order 11, and 1 is of order 2. (Check that G(2) = {1, 22}.)
| Generators gi mod 23 | |
| G(2) = {1, 22} | 22 |
| G(11) = {1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18} | 2, 3, 4, 6, 8, 9, 12, 13, 16, 18 |
| G(22) = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22} | 5, 7, 10, 11, 14, 15, 17, 19, 20, 21 |
Note for a generator g of G(q) mod p, that since g^q =1, we always have q = log(1) mod p, for any base (generator) g. Hence, for a group of order q, q plays the role of zero, as g^q = g^0 = 1 mod p, and hence q = log(1) = 0 mod q.
So for any power x of g in G(q), g^x mod p may be reduced mod q:
For future reference, note the following fact about powers of g. If we have two numbers X = g^x mod p and Y = g^y mod p, then
X*Y = g^x*g^y = g^(x+y) mod p.
By contrast to this, we have
X^y = (g^x)^y = g^(x*y) mod p,
while
Y^x = (g^y)^x = g^(x*y) mod p.
Knowledge of the first result, g^(x+y) mod p, doesn't tell us anything about the latter result, g^(x*y) mod p. Only if we first took logs to the base g, and calculated x = log X mod p or y = log Y mod p, could we calculate g^(x*y).
For a simple example using small numbers, suppose g = 2 and p = 25307. Suppose also you observe X = 6113 and Y = 7984. Thus you know thatX*Y = 6113*7984 = 2^(x+y) mod 25307.
That is,
14296 = 2^(x+y) mod 25307.
But what is g^(x*y) = 2^(x*y) mod 25307?
To answer this question, you need to know x = log2 6113 mod 25307 or y = log2 7984 mod 25307. The difference between g^(x+y) and g^(x*y) brings us to Diffie-Hellman key agreement.
D. Diffie-Hellman & Discrete Logarithms
Diffie-Hellman key agreement is a key negotiation technique created by
Whitfield Diffie and Martin Hellman in 1976. It provides a secure way for two parties to
agree on (negotiate) a shared symmetric key by which to encrypt their current exchange
of messages. Diffie-Hellman key exchange has as its practical basis the fact that it is
easy to calculate powers in modular arithmetic, but hard to extract
logarithms. That is, it takes considerable computer time and money to calculate
discrete logarithms relative to the calculation of powers.
Discrete logarithms
are believed to be examples of one-way functions. A one-way function
is one which can be calculated or computed relatively efficiently in one direction, as
compared to the reverse direction. That is, a function f(x) is a one-way
function if it is easy to calculate y = f(x), given x, but it is hard to
calculate or find x given y.
For a generator g
of Z(p)*, calculation of = g^x mod p from x is
easy, but computing x from y is difficult--at least as long as the prime
p is sufficiently large. "Sufficiently large" in 1997 meant at least 768 bits, but
preferably 1024 bits (which would allows for prime numbers less than 2^1024). There
are about 10^305 primes less than 2^1024, so there are plenty to choose from. (The
number of primes less than or equal to n is asymptotic to
n/ln(n). So a good approximation to the number of primes less than
n is simply n/ln(n), as long as n is large. Here and
elsewhere "ln" is the natural logarithm, the logarithm to the base e =
2.718281828....)
Now suppose two
people want to exchange infomation, but they want to do so in private. The first thing
they have to do is agree on a cryptographic key to encrypt their messages. Diffie-Hellman
key agreement is a way for two parties to decide on a cryptographic key for their use in
the current message-exchange session, without fear that a third party will be able to
intercept this key, and consequently decrypt their traffic. It relies on the fact that the two
parties who are exchanging messages only have to compute powers in modular arithmetic
in order to know what the key they are agreeing on is, but the eavesdropper will have to
compute discrete logarithms to obtain the same key from their initial message
exchange. (A different attack, called “man in the middle,” will not be discussed at this
point.)
An example of a
Diffie-Hellman calculation is given in Table 1. It might be useful to read
through the steps in the Table, prior to reading the following explanation of this
technique.
Suppose Alice and I decide to use Diffie-Hellman key agreement to establish a session
key. This key will be used to encrypt the messages we send each other, for this occasion
only. Each of us has previously agreed on a generator g of Z(p)* and a prime
number p. As noted in the previous section, the generator g
(1<g<p) has the property that g, g^2, g^3, ... ,
g^(p-1), yield--in some order--all the numbers 1, 2, 3, ..., p-1,
when calculations are done mod p.
For example, Alice
can simply choose g and p herself, and send them to me. It doesn't
matter if anyone else knows what these are. Alice now decides to send me a message.
She needs an encryption key to encrypt this message. So to start the process, Alice first
chooses a random number x, where 1< x < p-1. Alice
keeps x secret and sends me X instead:
A and B agree on two numbers, a generator g of Z(p)* and
a prime p. Alice and I agree g = 7, while p =
23.
A chooses a
secret random integer x. Alice chooses x = 5.
B chooses a
secret random integer y. I choose y = 8.
A computes
X = g ^ x mod p. Alice computes X = 7 ^ 5
mod 23 = 17.
B computes
Y = g ^ y mod p. I compute Y =
7 ^ 8 mod 23 = 12.
A sends
X to B, and B sends Y to
A. Alice sends 17 to me; I send 12 to Alice.
A computes
K = Y ^ x mod p Alice computes K
= 12 ^ 5 mod 23 = 18.
B computes
K = X ^ y mod p
I compute K = 17 ^ 8 mod 23 = 18. K is the
encryption key for this communication session. K = 18 is the
encryption key for this communication session.
If p is a prime about 1000 bits in length (about 300 decimal digits), only about 2000 multiplications of 1000-bit numbers are required to compute the exponentiation of g. By contrast, the fastest techniques for taking logarithms in arithmetic modulo p currently demand more than 2^100 (or approximately 10^30) operations. Using the best supercomputer would take many millions of years to compute the logarithm of g^x mod p.
The length of the Diffie-Hellman key K itself is typically about 128 bytes (1024 bits). This is often further processed (via a hash function, explained later) down to 8 bytes (64 bits) to obtain a DES encryption key.
E. RSA Public-Key System
RSA Data Security, headquartered in Redwood City, CA, is a company founded in 1982
by the inventors of the RSA system (Ron Rivest, Adi Shamir, and Leonard Adleman).
The RSA encryption technology is found in Microsoft Windows, Netscape Navigator,
Intuit's Quicken, and Lotus Notes. It is also found in Apple, Sun, and Novell operating
systems, and on Ethernet network cards. RSA is part of the SWIFT (Society for
Worldwide Interbank Financial Telecommunications) standard for international financial
transfers, as well as the ANSI X9.31 draft standard for the US banking industry.
In the RSA public-key cryptosystem used for electronic cash, both
encryption and decryption are done by raising the message M (and recall that any
computer message can be viewed simply as a binary number) to a power that is the
appropriate key. As noted previously, these exponentiations are done in modular
arithmetic, which saves only the result of division by a fixed number called the modulus.
This modulus needs to be quite large, usually at least 230 decimal digits (768 binary
digits). The example in
Table 2 uses small numbers for illustration.
When the system is set up, the key-making entity (bank, customer, merchant) generates
two large primes p and q. Their product n = p*q will be the
modulus of the exponentiations. Euler's totient function for n is t(n) = t(p*q)
= (p-1)*(q-1). The basis of the RSA system is Euler's
Theorem (covered previously), which says that for any number x relatively prime
to n, we have
Next, the keymaker chooses an e and d with
Consequently, any admissible x encrypted with e can be decrypted with d, since, calculated mod n,
In general, then, in the RSA system, for plaintext message M and its associated ciphertext message C:
M^(e*d) = (M^e)^d = (M^d)^e = M mod n
Encryption: Ee(M) = C = M^e mod n
Decryption: Dd(C) = C^d mod n = (M^e)^d mod n = M mod n.
Notice how, in principle, RSA signatures work. (We will simplify by deferring discussion of hash functions until later.) A bank whose secret key is d will sign a message M by encrypting it with the secret key d, which simply means raising M to the power d:
This message can be verified, and decrypted, by anyone by raising it to the power e, which is the bank's public key:Signature: Ed(M) = M^d mod n.
Thus d = 103, as
7*103 = 721 = 1 mod 120.
To see this last step, note
the following, mod 143:
47^103 = (5^7)^103 = 5^721
Here we have used the result that
5^120 = 5^t = 1 mod 143 by Euler's theorem.
Or, more simply,
x^(e*d) = x; hence,
5^721 = 5.
The RSA system is patented (US Patient 4,405,829). The patent expires Sept. 29, 2000.
The security of RSA depends on the difficulty of factoring large
numbers. For, given n, it is not easy to find the prime factors
p and q such that n = p*q. This difficulty is crucial,
for if p and q were known, then given the public key e also,
finding d--the private key--such that e*d =1 mod (p-
1)(q-1) would not be difficult.
For public key cryptography, it was (in 1997) believed that a modulus of 768 bits (made
up of two prime factors each of around 384 bits) was sufficient for security until the year
2004. That is, a "large enough" modulus was n = 2^768 approximately, with
p, q primes each in the neighborhood of 2^384. The fastest known factoring
algorithm was the number field sieve, which had running time, for
factoring a large number of size n, of order
Choose p and q, where both p and
q are prime.
Choose 11 and 13, which are prime numbers.
Find their product
n = pq. Calculate n = 11*13 = 143. Calculate Euler's totient
function t = (p-1)(q-1).
Calculate
t = (11-1)*(13-1) = 120.
Select an integer
e, where e<t, and the greatest common divisor of e and
t is 1. Let
e = 7. This will work because 7<120, and their greatest common
divisor is 1.
Calculate d
such that e*d = 1 mod t. We want 7*d = 1 mod 120.
The public key is
(e, n). The public key is (7, 143).
The private key is
(d, n). The private key is (103, 143). Plaintext can be any
number M, where M < n,
and neither p nor q divides M Let the numerical
representation of M
be M = 5, for example.
The ciphertext is
C = M^e mod n. The ciphertext is C
= 5^7 mod 143 = 47. The plaintext is C^d mod n
= (M^e)^d mod n = M.
The plaintext is 47^103 mod 143 = 5.
= 5*[5^720] =5*[(5^120)^6]
= 5*[ 1^6] = 5.
RSA uses public keys to encrypt symmetric session keys. The latter are often insecure. A message encrypted with a 40-bit symmetric session key, using RSA's RC4 stream encryption algorithm, takes an average of 64 mips-years to break. That is, a computer operating at 64 million instructions per second would take a year to break the message's encryption. This size (40-bits) was until recently the maximum symmetric-key size allowed for U.S. export software (under the International Traffic in Arms Regulations), although 128-bit keys could be used in domestic software. As of 1997, symmetric keys less than 90-bits in length were not considered secure.
F. Hash Functions & Digital Signatures
Often when one wants
to sign something, such as a long message or document, it is inconvenient to sign the
entire message. One reason is public key cryptography is slow. So the solution is to
create a message digest, which is a number or string of fixed length
which represents the message. The message may be, for example, as long as 50,000 bits,
but the message digest may be only 128 bits. The idea is to sign the message
digest, instead of the message.
For example, the
sender of the message can also create and sign a message digest, encrypting the latter with
her private key. The encrypted digest is sent along with the message. Then the receiver
of the combined message and encrypted message digest can 1) recompute the message
digest from the message received, 2) decrypt the encrypted message digest using the
sender's public key, and 3) compare that the two are the same. If they are, then in all
probability the message received was the same as the message sent, and moreover one can
be confident that it was sent by the owner of the public key used to decrypt the message
digest. This process of recreating a message digest from the received message, and
comparing it to the decrypted version of the received message digest, is sometimes
referred to as a message authenticity check.
Hash functions are
used to create message digests. A hash function H(x) is a
mapping from any variable-length string or message x = M to a string (binary
number) of fixed length h:
If two different messages do map to the same hash value, this is referred to as a collision. So if the hash function uniformly distributes outcomes over the outcome space, it is relatively "collision-free". Of course, no function which maps a larger space into a smaller space can avoid all collisions, so a better term is "collision-resistant". Using collision-resistant hash functions helps prevent message repudiation. No one will be able to deny having signed a given message (repudiate the message) by producing a different message that hashes to the same value, and claiming that this different message was the one intended. For if you could find a second (pseudo) message that hashes to the same value as a signed message (a collision), then you could remove the signature from the signed message, attach it to the pseudo-message, and claim the person had signed the pseudo-message.
In addition to being collision-resistant, a good hash function must also be one-way: one should not be able to feasibly compute the original message given its hash value (message digest). So if you can't compute the original message from its message digest, and you can't find another message that gives the same hash value, then you won't be able to falsify a signed message in transit or in storage.
Hash functions and secret keys are combined to produce digital signatures. First a hash h of the message M is produced. Then this value is encrypted with the sender's secret key, to form Esk(h). This encrypted hash value is sent along with the message itself. The message recipient uses the public key of the sender to decrypt the encrypted hash value: Dpk(Esk(h)) = h. The message recipient then also recomputes h directly from the message M to obtain h = H(M). If the two computations yield the same value for h, then the message must have come from the owner of the public key pk, and moreover the message could not have been altered.
Why? Because if the message has been altered to, say, M+, then the hash value h+ = H(M+) will not be correct (except with a vanishing probability of about 1/(2^128), for a 128-bit hash). Also, if the encrypted hash value was not signed with the supposed sender's secret key sk, but rather with some other secret key sk+, then the decryption will not yield a correct value: Dpk(Esk+(h)) is not equal to h. Thus a digital signature is superior to a handwritten signature, because it verifies both the identity of the signer of the message and the message contents. The slightest change in the message M will cause the signature process to fail.
Two well-known hash functions are RSA's MD5 (Message Digest 5) and NIST's SHA-1 (Secure Hash Algorithm). The hash values for MD5 are 128-bits long, while those of SHA-1 are 160-bits. Two other hash functions are RIPEMD-128 and RIPEMD-160, which yield respectively 128- and 160-bit hashes.
Are these hash functions collision-resistant? In 1994 P. van Oorschot and M. Wiener estimated that for $10 million one could build a special purpose computer to look for MD5 collisions, and these could be found in 24 days on average. MD5 was based on an earlier MD4, which can be considered broken. Neither does RSA recommend use of MD2, an earlier hash function designed for 8-bit machines. As for MD5, RSA recently stated: "Existing signatures formed using MD5 are not at risk and while MD5 is still suitable for a variety of applications (namely those which rely on the one-way property of MD5 and on the random appearance of the output) as a precaution it should not be used for future applications that require the hash function to be collision-resistant". For the present, SHA-1, RIPEMD-128, RIPEMD-160 can all be considered secure.
G. Blind Signatures
Suppose a customer wants a bank to sign a piece of digital cash with the serial number
x, but does not want the bank to know which piece of cash it is signing. This can
be achieved with a blind signature protocol. A simple example, using the
RSA public key system, is as follows (see also Table 3):
1. The customer chooses a blinding factor r, chosen randomly and
independently of x, and presents the bank with
2. The bank signs the digital cash (the blinded number) with its private RSA key d:
3. The customer divides out the blinding factor:
Since r is random, the bank cannot determine x separately from the product originally presented to it, and thus cannot connect the signing for a particular customer with the serial number of the digital cash when it is subsequently spent. The spending of the coin is untraceable. When presented with the coin, the bank can verify that it is valid, but it cannot say to whom the coin was issued.
Table 3: Blind Signature Protocol
To summarize the blind signature protocol, for any message M, the customer
presents the bank with
A piece of digital cash has the serial number
x. A piece of digital cash has the serial number x =
8.
The customer chooses a
blinding factor r. The customer chooses r = 5.
The customer calculates x*r^e mod n, where
(e, n) is the bank's RSA public key. The customer
calculates 8*5^7 mod 143, using the bank's public key (7, 143). This gives 90 as the
result.
The bank signs the
customer-submitted number with its private key d, giving, mod n,
r*x^d .
The bank signs 90 with its private key 103,
which gives, mod 143,
90^103 = (8*5^7)^103 = 8^103*5^721 = 5*8^103. The customer divides
out the blinding factor r, giving (r*x^d)/r =
x^d mod n. The customer divides out the blinding
factor 5, giving (8^103*5)/5 = 8^103 mod 143.
That is, the digital cash bearing the
serial number 8 has now been signed with the bank's private key of 103. Anyone can
verify that the serial number is 8 by using the bank's public key of (7, 143) to calculate
(8^103)^7 mod 143 = 8^721 mod 143 = 8*(8^120)^6 = 8*(1)^6 = 8.
The blind signature protocol was announced by David Chaum in 1982. There are other examples of signature protocols that are conditionally blind--"restrictive blind signatures"-- which reveal the identity of the digital cash owner if he spends it more than once. Restrictive blind signatures will be discussed in connection with Stefan Brands' system of digital cash, as well as next, on double-spending identification.
H. Double-spending Identification
An off-line system of digital cash that
allows for buyer anonymity has the problem that if a buyer is committing a fraudulent
transaction by multiple-spending (trying to spend the same piece of digital cash more than
once), the bank and the seller have no ordinary recourse to take action against the buyer,
since they don't know who he is. (In an on-line system, by contrast, the coin is typically
checked against a spent-coin data base before the good or service is released to the
buyer.) One way the double-spending problem can be handled in off-line systems is to
require the buyer to reveal some information about himself when the cash is withdrawn.
This information will be segmented in such a way that no one piece of the
information will reveal the buyer's identity, but two pieces will. So if the buyer
double-spends, the bank will acquire two pieces of information, the buyer's identity will
be revealed, and the bank can initiate legal action against the buyer.
1. Cut and Choose
In the cut-and-choose method, the buyer creates N pairs of
numbers that are associated with a digitally signed coin at the time it is withdrawn. Any
pair can identify the buyer. The bank is able to check that the N pairs are
present.
When the buyer offers
the coin to the seller, the seller sends a "challenge", which is a sequence of N
random bits: 10001011 . . . If a "0" is present the first number of the corresponding
number pair is sent, while if a "1" is present, the second number of the pair is sent. Note
what this means. If the buyer later offers the same coin to this or another seller, and the
seller challenges the buyer with another sequence of N random bits, it is almost
certain some of the bits in the two sequences will correspond. Hence the buyer will be
identified. In the example in Table 4 we see that three bits differ between
10001011 and 11011010, hence any one of these three pairs may be used to determined
the buyer's identity.
The problem with this cut-and-choose method is its slowness, and relative inefficiency in
implementation, because of the large amount of information that is involved in the
sequence of number pairs. The prevention of double-spending in the Chaum-Fiat-Naor
(1990) scheme is by cut and choose and is inefficient for this reason. Greater efficiency
can be achieved by means of the Schnorr Protocols, covered next.
2. Zero-knowledge Proofs & Schnorr Protocols
A zero-knowledge proof is one whereby, through some protocol or
procedure, you are
able to show knowledge of something (usually a number or set of numbers) without
having to actually make that something known to the other party.
For example, consider a bank vault with a single door, and with a numeric combination
which can be entered from either side of the door. Alice does not know the combination.
To prove to Alice that you do know it, you allow Alice to lock you in the vault.
You then enter the combination from your side, open the door, and exit the vault. Your
reappearance from within the vault proves you know the combination, without your
having to reveal anything about the combination to Alice. You have enacted a zero-
knowledge proof.
One example of a
zero-knowledge proof is found in the Schnorr authentication (identification)
protocol. Schnorr authentication is another example of a system based on
discrete logarithms. Suppose a customer is proving to a merchant that she--the customer--
knows her own secret key x. That is, prove that she is who she claims to
be, as no one else knows this secret key.
First, the customer
sends the merchant a random number w. The merchant responds with a
challenge: namely, a number c. Then, to prove her identity, the
customer responds with a point y on the line
(328,
956) 956 956 No
(1124,
333) 1124 333 Yes
(516,
2251) 516 516 No
(7,
895) 7 895 Yes
(486,
585) 585 585 No
(228,
61) 228 228 No
(1591,
1592) 1592 1592 No (825,
667) 667 825 Yes
Of course, the procedure can't be done exactly like this, because the merchant--now knowing c, w, and y would also be able to determine x. We want to disguise things a little so the merchant can determine that y is the proper response to the challenge c, without the merchant being able to determine x itself.
To do this, we exponentiate the equation y = w + x*c by some generator g in G(q), and take the result modulo some prime p (where q divides p-1):
Table 5: Schnorr Authentication Protocol
Why does this
procedure work? Because in order find y without knowledge of the secret key,
the customer would have to take discrete logarithms:
Choose two primes p, q, where
q is a prime factor of p-1. Choose p = 23, q =
11, where 11 is a prime factor of 22 = 23-1. Choose g (not equal to 1)
such that g^q = 1 mod p. Choose g such that
g^11 = 1 mod 23.
Let g = 2, since 2^11 = 2048 = 1 mod 23.
Generate a secret key by choosing x < q. Generate a
secret key, say x = 9, since 9<11.
Generate a public key by calculating h, where
h = g^x mod p. Generate a public key by calculating
h, where h = 2^9 mod 23 = 6.
Note that p,
q, g, and h are all public. Only x is
secret. Note that
p = 23, q =11, g = 2, and h = 6 are
all public. Only x = 9 is secret.
Customer picks a random number w <
q, and computes a = g^w mod p. Customer picks
w = 3 < 11, and computes
a = g^w = 2^3 mod 23 = 8 mod 23 = 8.
Customer sends
a to merchant. Customer sends a = 8 to merchant.
Merchant sends
customer a random number c, where c is between 0 and 2^t - 1,
where t is about t = 72. Merchant sends customer
c=5.
Customer calculates
y = w + x*c mod q, and returns y to
merchant. Customer
calculates y = 3+9*5 mod 11 = 48 mod 11 = 4, and returns
y = 4 to the merchant. Merchant verifies
g^y = a*h^c mod p Merchant calculates a*h^c mod
p = 8*6^5 mod 23 = 62208 mod 23 = 16. Merchant also calculates g^y
mod p = 2^4 = 16. These are the same so the merchant accepts that the
customer knows x.
The Schnorr signature protocol adds a hash function to this process. Instead of the merchant sending a challenge c, the customer calculates c via the hash function. Suppose the customer wants to send a message M to the merchant. First, she chooses a random number w, and computes a = g^w mod p, as before. She then concatenates M and a, and calculates a hash value c:
The merchant calculates,
In this case, both parties are using the same hash function H. The customer has an incentive to randomize w, because otherwise the paired values of y and c she sends to the merchant from time to time would reveal her secret key x. For two different paired values (c1,y1) and (c2,y2), but with the same w, the merchant can calculate x = (y1- y2)/(c1-c2).
On the other hand, the hash function H must be collision-resistant, because otherwise the customer might be able to manipulate the value of c.
This signature protocol is illustrated in Table 6.
We will see later how the Schnorr signature protocol forms a significant part of Stefan Brands' system of anonymous digital cash.
Table 6: Schnorr Signature Protocol
a = g^w = 2^3 mod
23 = 8 mod 23 = 8.
I. The Representation Problem
As we saw above,
Diffie-Hellman key agreement and Schnorr signatures all hinge on the practical difficulty
of calculating discrete logarithms. So also does the U.S. government's Digital Signature
Standard. The representation problem extends this
computational difficulty to the calculation of a set of numbers related to discrete
logarithms. The ability to draw on a whole set of hard-to-calculate numbers, instead of a
single logarithm, gives us an important degree of flexibility in creating anonymous digital
cash systems.
Let g be an
generator of the subgroup G(q) in Z(p)* (g can be any element from
G(q) other than 1). Recall that the discrete logarithm problem involves
finding some power a such that, for a given h in G(q),
Customer wants to send a message
M. Customer wants to send a message M = 5.
Customer picks a
random number w < q, and computes a = g^w mod
p. Customer picks w = 3 < 11, and computes
Customer has a hash
function H( ). For simplicity, let H(k, j) = (k*j)^7
mod 17. (This is
not a good hash function.)
Customer concatenates
M and a, and calculates a hash value c =
H(M,a). Customer concatenates M = 5 and a =8, and
calculates c
= H(5,8) = (5*8)^7 mod 17 = 14.
Customer calculates
y = w + x*c mod q, and sends (c, y), the signature, along with
a and the message M to merchant. Customer calculates
y = 3 + 9*14 mod 11 =
8, and sends (c, y) =
(14,8) to the merchant, along with M = 5 and a = 8.
Merchant checks if
g^y = a*h^c mod p. Merchant computes g^y mod 23
= 2^8 mod 23 = 3. Merchant computes a*h^c mod 23 = 8*6^14 mod 23 = 3.
The two sides are equal.
Merchant computes
H(M,a). Merchant computes H(5,8) = (5*8)^7 mod
17 = 14.
Merchant accepts the signature if c = H(M,a). Merchant accepts
the signature because c = 14 = H(5,8).
Let k>= 2, and 1<=ai<= q, for i = 1 to k. The representation problem for a given h in G(q) is to find an index-tuple {a1, ... , ak}, for a generator-tuple {g1, ... , gk} from G(q) such that
For example, we saw previously that {2, 3} are two of the numbers that generate G(11) in Z(23)*. So one example of a representation problem is to find a1 and a2 such that for h = 13,
Notice that if there are k elements in the representation, {a1, ... , ak}, then there are
Thus for k=2 in G(11), there are 11^(2-1) = 11 representations of each number h in G(11). For k=3, there are 11^(3-1) = 121 representations of, say, 4 = 2^a1*3^a2*13^a3 mod 23, because 2, 3, 4, 13 are all elements of G(11) in Z(23)*.
J. Proving Knowledge of a Representation
Since knowledge of a
representation cannot be gained without taking discrete logarithms (which is not
practically possible for numbers of sufficient size), one can thus use one's knowledge of a
representation to verify one's identity. The following protocol is designed to
prove knowledge of a representation.
Suppose you, the prover P, know the representation of h =
g1^a1*g2^a2
*...*gk^ak mod p,
where h is an element of G(q). That is, given {g1, ... ,
gk}, you know
{a1, ... , ak}, and you want to prove that fact,
without at the same time
revealing what {a1, ... , ak} are. How do you
do this? You want a zero-knowledge proof whereby you do not give away what you
know, but the other party can
be nevertheless assured that you do know {a1, ... ,
ak}.
Let's call the other
party V, for verifier, and assume that V, who also
knows h and {g1, ... , gk}, is seeking
assurance that you know
{a1, ... , ak}.
Step 1: You,
the prover P, generate k random numbers {w1
, ... , wk} chosen from G(q). You send to V the number
z =
g1^w1*g2^w2
*...*gk^wk mod
p.
Step 2:
V receives z and generates a random number, called a "challenge",
c, and sends it back to you.
Step 3: You
compute, for i = 1 to k, ri = ai +
c*wi mod q, and send
these k numbers back to V. (Note that the numbers are reduced mod
q, because gi ^q = 1 mod p.)
Step 4: V
calculates z*h^c and compares this to
g1^r1*g2^r2
*...*gk^rk mod
p, performed as a separate calculation. (Note that V is only calculating
exponentials, which is not hard to do.) If the two numbers are the same, V
accepts that you know the representation.
The two numbers will be the same if you know ai, and will
otherwise be different, because
z*h^c =
(g1^w1*g2^w2
*...*gk^wk) * (
g1^a1*g2^a2
*...*gk^ak)^c
=
(g1^[w1+
c*a1]*g2^[w2+
c*a2]*...*gk^[wk+
c*ak])
=
g1^r1*g2^r2
*...*gk^rk mod
p .
This process using just two generators is shown again for illustration in Table 7.
K. Certification Authorities and Digital Certificates
The Department of Motor Vehicles is an example of a certification authority. It
issues a certificate, called a driver's license, which certifies the connection
between a person's photograph and the personal information on the license.
Similarly, a
digital certificate verifies the connection between someone's public key
and that person's personal identification (however the latter is defined). A digital
certificate is typically issued by a trusted third party, who is thus called a
certification authority (CA). One example of a private CA is VeriSign
Inc., which runs a CA service for commercial World-Wide Web browsers. Companies
have to give VeriSign certain notarized business documents before obtaining a VeriSign
digital certificate. Other commercial CA services include GTE's CyberTrust and IBM's
Net.Registry. Software packages for CA management include Nortel's WebCA and
BBN's SafeKeyper Certificate Management System.
A digital certificate is
used with a digital signature in the following way. When Bob signs a message
with his private key and sends it to another party, Bob sends a certificate along with the
signature. The message recipient can then verify the message signature using Bob's
public key, but also looks at the certificate for additional security that the public key in
fact belongs to Bob. That is, "Bob" has signed his message with his secret key, which
can be verified with "Bob's" public key. The certificate is intended to show that "Bob" is
really Bob.
The certification
authority, in turn, does its job by binding Bob's identity with Bob's public key, and
signing the joint information with the CA's own private key. This signed message (digital
certificate) from the CA can be read using the CA's public key. Everyone is assumed to
have a tamper-resistant copy of the CA's public key so they can verify signatures on
digital certificates.
If the CA's secret key
is sk-ca, while Bob's public key is pk-bob, then the CA
creates a certificate for Bob of the form:
Knows representation of h =
g1^a1*g2^a2
; namely, knows a1,
a2. Only knows h and g1,
g2; doesn't know a1,
a2.
Generates two random numbers w1,
w2 . Computes z =
g1^w1*g2^w2
.
Sends z to V. Receives z from P. Generates
challenge
c.
Sends challenge c to P. Receives
c. Computes ri = ai + c*wi
mod q, for i = 1 to 2.
Sends these to V. Receives ri. Checks that
z*h^c =
g1^r1*g2^r2
mod p. If the equality holds, the Verifier accepts that the Prover
knows the representation (still unknown
to the Verifier) of h--namely, a1,
a2.
Meanwhile, the value of credentials signed with the CA's private key is only as good as the security of the CA's private key itself. A private (secret) root key of a CA may be split into several parts for security. It might, for example, be split into five parts, any two of which are sufficient to determine the key. (This is similar to a requirement that two people sign a check over a certain amount.)
To understand the splitting of a key, think of a line in a two-dimensional plane. Any two points on the line determine its slope. Suppose the slope represents the secret key. One point on the line will not reveal the secret key (the slope), but any two points will. So, to split up the key, one simply chooses five different, but otherwise arbitrary, points on the line, and gives the location of each point to a different person. Any two of them can determined the secret key needed for signing. Such a process is referred to as secret sharing.
Digital certificates (and CAs) may be used for other things than proofs of identity. A certificate may, for example, verify Bob's spending limit on a particular credit card. So, in the general sense, a digital certificate is a contract between two or more parties that verifies or specifies certain information.
One format for a digital certificate is laid out in ITU-T X.509. An X.509 certification message includes the following fields:
Version: Version number of the X.509 certificate specifications. Version 1 was published in 1988, version 2 in 1993, and version 3 proposed in 1994.
Serial Number: The certificate serial number.
Signature Algorithm ID: The algorithm that will be used to sign the certificate. For example, the Digital Signature Algorithm (DSA). The DSA uses the group of prime order G(q) in Z(p)*, so the prime p, the prime q, and a generator g must all be specified in this part of the certificate.
Issuer Name: The name of the CA body issuing the certificate.
Validity Period: How long the current certificate is good for.
Subject or User Name: The person or entity on whose behalf the present certificate is being issued.
Subject Public Key Information: The public key of the person or entity.
Subject Unique Identifier: Information about the person or entity that is being bound to the person or entity's public key. For example: account XYZ123 at UBS, Berne.
Signature on the Above Fields: The CA's signature.
The X.509 certificate standard is supported by many security protocols, such as S-HTTP, SSL, PEM, and PKCS-7. Version 3 certificates are also used in SET.
Posted here October 10, 1997
J. Orlin Grabbe is the author of International Financial Markets, and is an internationally recognized derivatives expert. He has recently branched out into cryptology, banking security, and digital cash. His home page is located at http://www.aci.net/kalliste/homepage.html.