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 algorithm. An encryption algorithm must be associated with a reverse procedure that restores the original message. The reverse process is called decryption. Taken together, the techniques of encryption and decryption are called cryptography.

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:

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:

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) = E_k(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) “+” E_k(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

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 E_k(x) or D_k(x) will be used. If a public-key system is involved, then the public key will be denoted pk, while the private (secret) key will be denoted sk.

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 D_sk(E_pk(M)) = M and also D_pk(E_sk(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)
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 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
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 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
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₁, ... , g_k} is a generator-tuple if each g_i is an generator mod p, and also g_i is not equal to g_j , 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
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 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
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 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.

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