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.

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.

**A. Some Preliminary Definitions**

** Encryption** is the process of transforming data or a message into
some unintelligible form, but in such a way that the transformation is reversible, so that it
is possible to restore the original data or message. The process of encryption involves
some recipe, or set of instructions, which gives the step-by-step procedure for
transforming the data. This recipe is called an

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:

0 + 1 = 1

1 + 0 = 1

1 + 1 = 0

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 **N**th 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.

**C(t) = E_{k}(M(t) “+” C(t-1))**.

** Cipher Feedback** (CFB) is a mode of DES encryption in which each
plaintext block is XORed with the previous cipherblock text

**C(t) = M(t) “+” E_{k}(C(t-1))**.

(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.

**B. Some Preliminary Mathmatical Notation**

A message to be encrypted or sent will be generally denoted as **M**. Remember
that, to the computer, the string of 1s and 0s that make up **M** can be treated as a
binary number, whether **M** is “I love you” or “You owe me $500” or “Bank
number 437695B.” Encryption may involve raising this number to a power. The notation
**E(x)** will denoted an *encryption* algorithm or function,
while **D(x) **will denote a *decryption* algorithm or
function. An encrypted message would thus be designated as **E(M), **while a
decryption of this encrypted message would be shown as **D(E(M)). **Of course
this latter term is just the original message, so **D(E(M)) = M. ** If a message is
encrypted or decrypted using the symmetric key ** k**, then the notation

In a symmetric encryption system,
**D_{k}(E_{k}(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

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**)

**b** = **k2*****n** + **r** .

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

“**n**|**(a-b**)” .

Thus, in the previous example,

67 = 11 mod 7

means for integers
**k1** = 9 and **k2** = 1,

67 = 9*7 + 4 (0<= 4 < 7)

11 = 1*7 + 4 .

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

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

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

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.

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

Let **g** be a
member of Z(p)*. Then **g** is said to be a ** generator** mod

{**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

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.

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, {**g _{1}**, ... ,

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

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.

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:

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 7and because each element in G(3) also has an inverse.

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

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

2^5 = 2^2 = 4 mod 7

2^6 = 2^3 = 1 mod 7

etc.

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

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.

It is easy to see that, as a consequence of Fermat's theorem, the order

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

Another result from number theory (the proof of which will not be explored here) is that, for

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

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 g_{i} 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
g_{i} 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, supposeg= 2 andp= 25307. Suppose also you observeX= 6113 andY= 7984. Thus you know that

X*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 =log_{2}6113 mod 25307 or y = log_{2}7984 mod 25307. The difference betweeng^(x+y)andg^(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

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**.

**Table 1: Steps in Negotiating Diffie-Hellman Key Agreement**

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.

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:

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

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 = Mmodn

Encryption: Emod_{e}(M) = C = M^en

Decryption: Dmod_{d}(C) = C^dn=(M^e)^dmodn=Mmodn.

Notice how, in principle, ** RSA signatures** work. (We will simplify by
deferring discussion of

This message can be verified, and decrypted, by anyone by raising it to the powerSignature:Emod_{d}(M) = M^dn.

Thus
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,
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.
**d** = 103, as
7*103 = 721 = 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. *To see this last step, note
the following, ***mod 143**:

= 5*[5^720] =5*[(5^120)^6]

= 5*[ 1^6] = 5.
**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

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

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

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

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-

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

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

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

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**

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.

To summarize the blind signature protocol, for any message **M**, the customer
presents the bank with

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

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.

**Table 4: Cut and Choose Matching**

(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

**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

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

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**

**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**.

Why does this
procedure work? Because in order find **y** without knowledge of the secret key,
the customer would have to take discrete logarithms:

The ** Schnorr signature protocol** adds a hash function to this process.
Instead of the merchant sending a challenge

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**

**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**a = g^w = **2^3 mod
23 = 8 mod 23 = 8.
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**)**.

**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),

Let **k**>= 2, and 1<=**a _{i}**<= q, for

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
**a _{1}** and

Notice that if there are **k** elements in the representation,
{**a _{1}**, ... ,

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^**a _{1}***3^

**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 =
g _{1}**^

Let's call the other
party **V**, for ** verifier**, and assume that

**Step 1:** You,
the prover **P**, generate **k** random numbers {**w _{1}**
, ... ,

**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**, **r _{i} = a_{i} +
c*w_{i} **mod

**Step 4: V**
calculates **z*h^c **and compares this to
**g _{1}**^

The two numbers will be the same if you know **a _{i}**, and will
otherwise be different, because

**z*h^c =
(g _{1}**^

** =
(g _{1}**^[

=
**g _{1}**^

This process using just two generators is shown again for illustration in **Table 7**.

**Table 7: Proving Knowledge of a Representation **

Knows representation of ** h =
g _{1}**^

**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

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

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://orlingrabbe.org/ .