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

The Laws of Cryptography with Java Code.

---

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
0	0		0
0	1		1
1	0		1
1	1		0

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 = log_bx means the same as b^y = x   . One says: ``y is the logarithm of x to base b,'' or ``y is the log base b of x.''   Stated another way, log_bx (also known as y) is the exponent you raise b to in order to get x.   Thus   b^(log_bx) = 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 = log₂x means the same as 2^y = 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 = log₂x, then x = 2^y = 2^log₂x.   In particular 2¹⁰ = 1024 means the same as log₂1024 = 10. Notice that 2^y > 0 for all y and inversely log₂x is not defined for x <= 0.

Here is a little table of logs base 2:

Logarithms base 2
x = 2y = 2log2x	y = log2x
1 073 741 824	30
1 048 576	20
1 024	10
8	3
4	2
2	1
1	0
1/2	-1
1/4	-2
1/8	-3
1/1024	-10
0	-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:

log₂(a*b) = log₂a + log₂b, a, b > 0
log₂(a^r) = r*log₂a, a > 0, r any value
log₂(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:


log₂x = log_ex / log_e2,   (mathematics)
           = Math.log(x)/Math.log(2.0);   (Java).

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

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

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

Thus log₂10000 = 13.28771238, so it takes 14 bits to represent 10000 in binary. (In fact, 10000₁₀ = 10011100010000₂.) Exact powers of 2 are a special case: log₂1024 = 10, but it takes 11 bits to represent 1024 in binary, as 10000000000.

Similarly, log₁₀(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 Z_n. 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, Z_n.

---

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 Z_p, 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 Z_p, 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 pⁿ elements for any integer n greater than 1, denoted GF(pⁿ). Particularly useful in cryptography is the special case with p = 2, that is, with 2ⁿ elements for n greater than 1. The special case 2⁸ = 256 is used, for example, in the new U.S. Advanced Encryption Standard (AES). It is more difficult to describe than the field Z_p. 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 Z₂ (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(2ⁿ).

---

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 Z_p), 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
p	a		a1	a2	a3	a4	a5	a6	a7	a8	a9	a10	a11	a12
13	2		2	4	8	3	6	12	11	9	5	10	7	1
13	3		3	9	1	3	9	1	3	9	1	3	9	1
13	4		4	3	12	9	10	1	4	3	12	9	10	1
13	5		5	12	8	1	5	12	8	1	5	12	8	1
13	6		6	10	8	9	2	12	7	3	5	4	11	1
13	7		7	10	5	9	11	12	6	3	8	4	2	1
13	8		8	12	5	1	8	12	5	1	8	12	5	1
13	9		9	3	1	9	3	1	9	3	1	9	3	1
13	10		10	9	12	3	4	1	10	9	12	3	4	1
13	11		11	4	5	3	7	12	2	9	8	10	6	1
13	12		12	1	12	1	12	1	12	1	12	1	12	1

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 p₁, ... , p_m 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
n	a		a1	a2	a3	a4	a5	a6	a7	a8	a9	a10	a11	a12	a13	a14
15	2		2	4	8	1	2	4	8	1	2	4	8	1	2	4
15	3		3	9	12	6	3	9	12	6	3	9	12	6	3	9
15	4		4	1	4	1	4	1	4	1	4	1	4	1	4	1
15	5		5	10	5	10	5	10	5	10	5	10	5	10	5	10
15	6		6	6	6	6	6	6	6	6	6	6	6	6	6	6
15	7		7	4	13	1	7	4	13	1	7	4	13	1	7	4
15	8		8	4	2	1	8	4	2	1	8	4	2	1	8	4
15	9		9	6	9	6	9	6	9	6	9	6	9	6	9	6
15	10		10	10	10	10	10	10	10	10	10	10	10	10	10	10
15	11		11	1	11	1	11	1	11	1	11	1	11	1	11	1
15	12		12	9	3	6	12	9	3	6	12	9	3	6	12	9
15	13		13	4	7	1	13	4	7	1	13	4	7	1	13	4
15	14		14	1	14	1	14	1	14	1	14	1	14	1	14	1

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.