The Laws of Cryptography:
Cryptographer's Favorites

by Neal R. Wagner

NOTE: This site is obsolete. See book draft (in PDF):

Exclusive-Or.

The function known as Exclusive-Or is also represented as XOR, or xor, or a plus sign in a circle. The function is available in C / C++ / Java for bit strings as a hat character: ^. (Be careful: the hat is often also used to mean exponentiation, as well as to designate a control character. Java, C, and C++ have no exponentiation operator.) In Java ^ also works for boolean type.   The expression a xor b means either a or b but not both. Ordinary inclusive-or in mathematics means either one or the other or both.

Law XOR1: The cryptographer's favorite function is Exclusive-Or.

Exclusive-or comes up constantly in cryptography. For example, the exclusive-or of a pseudo-random bit stream with a message bit stream is one simple form of encryption. (See later chapters.)

Recall that the boolean constant true is often written as a 1 and false as a 0. Exclusive-or is the same as addition mod 2, which means ordinary addition, followed by taking the remainder on division by 2. For single bits 0 and 1, xor is defined as:

Exclusive-Or
a   b   a xor b
000
011
101
110

The xor function has many interesting properties, including the following, which hold for any bit values or bit strings a, b, and c:

a xor a = 0
a xor 0 = a
a xor 1 = ~ a , where  ~  is bit complement.
a xor b = b xor a (commutativity)
a xor (b xor c) = (a xor b) xor c (associativity)
a xor a xor a = a
if a xor b = c, then c xor b = a and c xor a = b.

Beginning programmers learn how to exchange the values in two variables a and b, using a third temporary variable temp and the assignment operator =  :

temp = a;
a = b;
b = temp;

The same result can be accomplished using xor without an extra temporary location, regarding a and b as bit strings:

a = a xor b;
b = a xor b;
a = a xor b;

Exercise: Prove the above result in two ways, one using just the definition of xor in the table, and the other way using the properties of xor listed above. (On computer hardware that has an xor instruction combined with assignment, the above solution may execute just as fast as the previous one and will avoid the extra variable.) [A Java program that demonstrates interchange using exclusive-or is here.]

Logarithms.

By definition, y = logbx means the same as by = x   . One says: ``y is the logarithm of x to base b,'' or ``y is the log base b of x.''   Stated another way, logbx (also known as y) is the exponent you raise b to in order to get x.   Thus   b(logbx) = x. In more mathematical terms, the logarithm is the inverse function of the exponential.

Law LOG2: The cryptographer's favorite logarithm is log base 2.

So y = log2x means the same as 2y = x. Another way to say this is that a logarithm base 2 of x is an exponent, namely it is the exponent you raise 2 to in order to get x. In symbols: if y = log2x, then x = 2y = 2log2x.   In particular 210 = 1024 means the same as log21024 = 10. Notice that 2y > 0 for all y and inversely log2x is not defined for x <= 0.

Here is a little table of logs base 2:

Logarithms base 2
x = 2y = 2log2x   y = log2
1 073 741 824 30
1 048 576 20
1 024 10
1/2 -1
1/4 -2
1/8 -3
1/1024 -10
-infinity
< 0  undefined

One uses logs base 2 in cryptography (as well as in most of computer science) because of the emphasis on binary numbers in these fields.

Here are a few other formulas involving logarithms:

log2(a*b) = log2a + log2b, a, b > 0
log2(ar) = r*log2a, a > 0, r any value
log2(a + b) = no simple formula for this

Some calculators, as well as languages like Java, do not directly support logs base 2. Java does not even support logs base 10, but only logs base e, the ``natural'' log. However, a log base 2 is just a fixed constant times a natural log, so they are easy to calculate if you know the ``magic'' constant. The formulas are:

log2x = logex / loge2,   (mathematics)
= Math.log(x)/Math.log(2.0);   (Java).

Here is the magic constant: loge(2) = 0.69314 71805 59945 30941 72321, or 1 / loge(2) = 1.44269 50408 88963 40735 99246. (Similarly, log2x = log10x / log10(2), and log10(2) = 0.30102 99956 63981 14.) [A Java program that demonstrates these formulas is here.]

[Here is a proof of the above formulas:
2y = x, or  y = log2x    (then take loge of each side of first equation)
loge(2y) = logex    (then use properties of logarithms)
y loge(2) = logex    (then solve for y)
y = logex / loge(2)    (then substitute log2x for y)
log2x = logex / loge(2).]

Law LOG2: The log base 2 of an integer x tells how many bits it takes to represent x in binary.

Thus log210000 = 13.28771238, so it takes 14 bits to represent 10000 in binary. (In fact, 1000010 = 100111000100002.) Exact powers of 2 are a special case: log21024 = 10, but it takes 11 bits to represent 1024 in binary, as 10000000000.

Similarly, log10(x) gives how many decimal digits are needed to represent x.

Exercises: 1. How many bits are needed to represent a number that is 100 decimal digits long? [Ans: 333.] How many decimal digits are needed to represent a number that is 1000 bits long? [Ans: 302.] How many decimal digits are needed to represent a number that is 100 decimal digits long? [Ans: See Proceedings of the Polish National Academy of Sciences.]

2. Write a Java function to return the log base b of a, where b > 1 and a > 0. Test your function.

Groups.

A group is a set of group elements with a binary operation for combining any two elements to get a unique third element. If one denotes the group operation by #, then the above says that for any group elements a and b, a # b is defined and is also a group element. Groups are also associative, meaning that a # (b # c) = (a # b) # c, for any group elements a, b, and c. There has to be an identity element e satisfying a # e = e # a = a for any group element a. Finally, any element a must have an inverse a' satisfying a # a' = a' # a = e.

If a # b = b # a for all group elements a and b, the group is commutative. Otherwise it is non-commutative. (Notice that even in a non-commutative group, a # b = b # a might sometimes be true -- for example if a or b is the identity.)

A group with only finitely many elements is called finite; otherwise it is infinite.

Examples:

1. The integers (all whole numbers, including 0 and negative numbers) form a group using ordinary addition. The identity is 0 and the inverse of a is -a. This is an infinite commutative group.

2. The positive rationals (all positive fractions, including all positive integers) are a group if ordinary multiplication is the operation. The identity is 1 and the inverse of r is 1/r. This is another infinite commutative group.

3. The integers mod n form a group for any integer n > 0. This group is often denoted Zn. Here the elements are {0, 1, 2, ..., n-1} and the operation is addition followed by remainder on division by n. The identity is 0 and the inverse of a is n-a (except for 0 which is its own inverse). This is a finite commutative group.

4. For an example of a non-commutative group, consider 2-by-2 non-singular matrices of real numbers (or rationals), where the operation is matrix multiplication:
```
+          +
|  a    b  |  , where a, b, c, and d are real numbers (or rationals)
|          |    and a*d - b*c is not zero (non-singular matrices).
|  c    d  |    The operation is matrix multiplication.
+          +

+          +
|  1    0  |
|          |  is the identity.
|  0    1  |
+          +

+          +                            +          +
|  a    b  |                   1        |  d   -b  |
|          |  has inverse  -----------  |          |
|  c    d  |                a*d - b*c   | -c    a  |
+          +                            +          +
```
This is an infinite non-commutative group.

The chapter on decimal numbers gives an interesting and useful example of a finite non-commutative group: the dihedral group with ten elements.

Law GROUP1: The cryptographer's favorite group is the integers mod n, Zn.

Fields.

A field is an object with a lot of structure, which this section will only outline. A field has two operations -- call them + and * (though they will not necessarily be ordinary addition and multiplication). Using +, all the elements of the field form a commutative group. Denote the identity of this group by 0 and denote the inverse of a by -a. Using *, all the elements of the field except 0 must form another commutative group with identity denoted 1 and inverse of a denoted by a-1. (The element 0 has no inverse under *.) There is also the distributive identity, linking + and *: a*(b + c) = (a*b) + (a*c), for all field elements a, b, and c.

Examples:

1. Consider the rational numbers (fractions) Q, or the real numbers R, or the complex numbers C, using ordinary addition and multiplication (extended in the last case to the complex numbers). These are all infinite fields.

2. Consider the integers mod p, denoted Zp, where p is a prime number (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...). Regard this as a group using + (ordinary addition followed by remainder on division by p). The elements with 0 left out form a group under * (ordinary multiplication followed by remainder on division by p). Here the identity is clearly 1, but the inverse of a non-zero element a is not obvious. In Java, the inverse must be an element x satisfying (x*a) % p == 1. It is always possible to find the unique element x, using an algorithm from number theory known as the extended Euclidean algorithm. This is the topic in the next chapter, but in brief: because p is prime and a is non-zero, the greatest common divisor of p and a is 1. Then the extended Euclidean algorithm gives integers x and y satisfying x*a + y*p = 1, or x*a = 1 - y*p, and this says that if you divide x*a by p, you get remainder 1, so this x is the inverse of a.

Law FIELD1: The cryptographer's favorite field is the integers mod p, denoted Zp, where p is a prime number.

The above field is the only one with p elements. In other words, the field is unique up to renaming its elements, meaning that one can always use a different set of symbols to represent the elements of the field, but it will still be essentially the same.

There is also a unique finite field with pn elements for any integer n greater than 1, denoted GF(pn). Particularly useful in cryptography is the special case with p = 2, that is, with 2n elements for n greater than 1. The special case 28 = 256 is used, for example, in the new U.S. Advanced Encryption Standard (AES). It is more difficult to describe than the field Zp. The section about the AES will describe this field in more detail, but in brief for now, it has 256 elements. Each element can be represented as a string of 8 bits. Addition in the field is just the same as bitwise exclusive-or (or bitwise addition mod 2). The zero element is 00000000, and the identity element is 00000001. So far, so good, but multiplication is more problematic: one has to regard an element at a degree 7 polynomial with coefficients in the field Z2 (just a 0 or a 1) and use a special version of multiplication of these polynomials. The details will come in a later section on the AES.

Law FIELD2: The cryptographer's other favorite field is GF(2n).

Fermat's Theorem.

In cryptography, one often wants to raise a number to a power, modulo another number. For the integers mod p where p is a prime (denoted Zp), there is a result know as Fermat's Theorem, discovered by the 17th century French mathematiciam Pierre de Fermat, 1601-1665.

Theorem (Fermat): If p is a prime and a is any non-zero number less than p, then

```
ap-1 mod p = 1
```

Law FERMAT1: The cryptographer's favorite theorem is Fermat's Theorem..

Here is a table illustrating Fermat's Theorem for p = 13. Notice below that the value is always 1 by the time the power gets to 12, but sometimes the value gets to 1 earlier. The initial run up to the 1 value is shown in red boldface in the table. The lengths of these runs are always numbers that divide evenly into 12, that is, 2, 3, 4, 6, or 12. A value of a for which the whole row is red is called a generator. In this case 2, 6, 7, and 11 are generators.

Values pa for p = 13, a < 13
pa a1a2a3a4a5a6a7a8a9a10a11a12
132248361211951071
133391391391391
1344312910143129101
135512815128151281
136610892127354111
137710591112638421
138812518125181251
139931931931931
13101091234110912341
1311114537122981061
1312121121121121121121

Because a to a power mod p always starts repeating after the power reaches p-1, one can reduce the power mod p-1 and still get the same answer. Thus no matter how big the power x might be,

```
ax mod p = ax mod (p-1) mod p.```

Thus modulo p in the expression requires modulo p - 1 in the exponent. So, for example, if p = 13 as above, then

```
a29 mod 13 = a29 mod 12 mod 13 = a5 mod 13.
```

The Swiss mathematician Leonhard Euler (1707-1783) came up with a generalization of Fermat's Theorem which will come up later in the discussion of the RSA cryptosystem.

Theorem (Euler): If n is any positive integer and a is any positive integer less than n with no divisors in common with n, then

```
aphi(n) mod n = 1,
```

where phi(n) is the Euler phi function:

```
phi(n) = n*(1 - 1/p1)* ... *(1 - 1/pm),
```

and p1, ... , pm are all the prime numbers that divide evenly into n, including n itself in case it is a prime. If n is a prime, then phi(n) = n - 1, so Euler's result is a special case of Fermat's. Another special case needed for the RSA cryptosystem comes when the modulus is a product of two primes: n = p*q. Then phi(n) = n*(1 - 1/p)*(1 - 1/q) = (p - 1)*(q - 1). Below is a table illustrating Euler's theorem for n = 15 = 3*5, with phi(15) = 15*(1 - 1/3)*(1 - 1/5) = (3 - 1)*(5 - 1) = 8. Notice here that a 1 is reached when the power gets to 8 (actually in this simple case when the power gets to 2 or 4), but only for numbers with no divisors in common with 15. For other base numbers, the value never gets to 1.

Values na for n = 15, a < 15
na a1a2a3a4a5a6a7a8a9a10a11a12a13a14
15224812481248124
15339126391263912639
15441414141414141
155510510510510510510510
15666666666666666
15774131741317413174
15884218421842184
15996969696969696
15101010101010101010101010101010
1511111111111111111111111
1512129361293612936129
1513134711347113471134
1514141141141141141141141

The tables above were generated by the following Java program: Fermat table generating program.

In a way similar to Fermat's Theorem, arithmetic in the exponent is taken mod phi(n), so that, assuming a has no divisors in common with n

```
ax mod n = ax mod phi(n) mod p.
```

For example, if n = 15 as above, and if neither 3 nor 5 divides evenly into a, then phi(n) = 8, and

```
a28 mod 15 = a28 mod 8 mod 15 = a4 mod 15.
```

The proof that the RSA cryptosystem works depends on the above fact.

Revision date: 2002-02-20. (Please use ISO 8601, the International Standard.)