by Neal R. Wagner
Copyright © 2002 by Neal R. Wagner. All rights reserved.
NOTE: This site is obsolete. See book draft (in PDF):
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.
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:
Beginning programmers learn how to exchange the values in two variables a and b, using a third temporary variable temp and the assignment operator = :
The same result can be accomplished using xor without an extra temporary location, regarding a and b as bit strings:
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.]
By definition, y = log_{b}x 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_{b}x (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.
Here is a little table of logs base 2:
Logarithms base 2 | |
---|---|
x = 2^{y} = 2^{log2x} | y = log_{2}x |
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:
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:
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_{2}x = log_{10}x / log_{10}(2), and log_{10}(2) = 0.30102 99956 63981 14.) [A Java program that demonstrates these formulas is here.]
Law LOG2: The log base 2 of an integer x tells how many bits it takes to represent x in binary.
Similarly, log_{10}(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.
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:
+ + | 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}.
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:
Law FIELD1: The cryptographer's favorite field is the integers mod p, denoted Z_{p}, where p is a prime number.
There is also a unique finite field with p^{n} elements for any integer n greater than 1, denoted GF(p^{n}). Particularly useful in cryptography is the special case with p = 2, that is, with 2^{n} elements for n greater than 1. The special case 2^{8} = 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_{2} (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^{n}).
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
a^{p-1} mod p = 1
Law FERMAT1: The cryptographer's favorite theorem is Fermat's Theorem..
Values p^{a} for p = 13, a < 13 | ||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
p | a | a^{1} | a^{2} | a^{3} | a^{4} | a^{5} | a^{6} | a^{7} | a^{8} | a^{9} | a^{10} | a^{11} | a^{12} | |
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,
a^{x} mod p = a^{x 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
a^{29} mod 13 = a^{29 mod 12} mod 13 = a^{5} 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
a^{phi(n)} mod n = 1,
where phi(n) is the Euler phi function:
phi(n) = n*(1 - 1/p_{1})* ... *(1 - 1/p_{m}),
and p_{1}, ... , 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 n^{a} for n = 15, a < 15 | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
n | a | a^{1} | a^{2} | a^{3} | a^{4} | a^{5} | a^{6} | a^{7} | a^{8} | a^{9} | a^{10} | a^{11} | a^{12} | a^{13} | a^{14} | |
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
a^{x} mod n = a^{x 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
a^{28} mod 15 = a^{28 mod 8} mod 15 = a^{4} mod 15.
The proof that the RSA cryptosystem works depends on the above fact.