Cryptography/Mathematical Background
A Wikibookian believes this page should be split into smaller pages with a narrower subtopic. You can help by splitting this big page into smaller ones. Please make sure to follow the naming policy. Dividing books into smaller sections can provide more focus and allow each one to do one thing well, which benefits everyone. |
See Talk page for other suggestions.
Introduction[edit | edit source]
Modern public-key (asymmetric) cryptography is based upon a branch of mathematics known as number theory, which is concerned solely with the solution of equations that yield only integer results. These type of equations are known as diophantine equations, named after the Greek mathematician Diophantos of Alexandria (ca. 200 CE) from his book Arithmetica that addresses problems requiring such integral solutions.
One of the oldest diophantine problems is known as the Pythagorean problem, which gives the length of one side of a right triangle when supplied with the lengths of the other two side, according to the equation
where is the length of the hypotenuse. While two sides may be known to be integral values, the resultant third side may well be irrational. The solution to the Pythagorean problem is not beyond the scope, but is beyond the purpose of this chapter. Therefore, example integral solutions (known as Pythagorean triplets) will simply be presented here. It is left as an exercise for the reader to find additional solutions, either by brute-force or derivation.
3 | 4 | 5 |
5 | 12 | 13 |
7 | 24 | 25 |
8 | 15 | 17 |
Prime Numbers[edit | edit source]
Description[edit | edit source]
Asymmetric key algorithms rely heavily on the use of prime numbers, usually exceedingly long primes, for their operation. By definition, prime numbers are divisible only by themselves and 1. In other words, letting the symbol | denote divisibility (i.e. - means " divides into "), a prime number strictly adheres to the following mathematical definition
- | Where or only
The Fundamental Theorem of Arithmetic states that all integers can be decomposed into a unique prime factorization. Any integer greater than 1 is considered either prime or composite. A composite number is composed of more than one prime factor
- | where ultimately
in which is a unique prime number and is the exponent.
Numerical Examples[edit | edit source]
543,312 = 2^{4} 3^{2} 5^{0} 7^{3} 11^{1} 553,696 = 2^{5} 3^{0} 5^{0} 7^{0} 11^{3} 13^{1}
As can be seen, according to this systematic decomposition, each factorization is unique.
In order to deterministically verify whether an integer is prime or composite, only the primes need be examined. This type of systematic, thorough examination is known as a brute-force approach. Primes and composites are noteworthy in the study of cryptography since, in general, a public key is a composite number which is the product of two or more primes. One (or more) of these primes may constitute the private key.
There are several types and categories of prime numbers, three of which are of importance to cryptography and will be discussed here briefly.
Fermat Primes[edit | edit source]
Fermat numbers take the following form
If F_{n} is prime, then it is called a Fermat prime.
Numerical Examples[edit | edit source]
The only Fermat numbers known to be prime are . Moreover, the primality of all Fermat numbers was disproven by Euler, who showed that .
Mersenne Primes[edit | edit source]
Mersenne primes - another type of formulaic prime generation - follow the form
where is a prime number. The [1] Wolfram Alpha engine reports Mersenne Primes, an example input request being "4th Mersenne Prime".
Numerical Examples[edit | edit source]
The first four Mersenne primes are as follows
Numbers of the form M_{p} = 2^{p} without the primality requirement are called Mersenne numbers. Not all Mersenne numbers are prime, e.g. M_{11} = 2^{11}−1 = 2047 = 23 · 89.
Coprimes (Relatively Prime Numbers)[edit | edit source]
Two numbers are said to be coprime if the largest integer that divides evenly into both of them is 1. Mathematically, this is written
where is the greatest common divisor. Two rules can be derived from the above definition
- If | and , then |
- If with , then both and are squares, i.e. - ,
The Prime Number Theorem[edit | edit source]
The Prime Number Theorem estimates the probability that any integer, chosen randomly will be prime. The estimate is given below, with defined as the number of primes
is asymptotic to , that is to say . What this means is that generally, a randomly chosen number is prime with the approximate probability .
The Euclidean Algorithm[edit | edit source]
Introduction[edit | edit source]
The Euclidean Algorithm is used to discover the greatest common divisor of two integers. In cryptography, it is most often used to determine if two integers are coprime, i.e. - .
In order to find where efficiently when working with very large numbers, as with cryptosystems, a method exists to do so. The Euclidean algorithm operates as follows - First, divide by , writing the quotient , and the remainder . Note this can be written in equation form as . Next perform the same operation using in 's place: . Continue with this pattern until the final remainder is zero. Numerical examples and a formal algorithm follow which should make this inherent pattern clear.
Mathematical Description[edit | edit source]
When , stop with .
Numerical Examples[edit | edit source]
Example 1 - To find gcd(17,043,12,660)
17,043 = 1 12,660 + 4383 12,660 = 2 4,383 + 3894 4,383 = 1 3,894 + 489 3,894 = 7 489 + 471 489 = 1 471 + 18 471 = 26 18 + 3 18 = 6 3 + 0
gcd (17,043,12,660) = 3 \ </math>
Example 2 - To find gcd(2,008,1,963)
2,008 = 1 1,963 + 45 1,963 = 43 45 + 28 45 = 1 28 + 17 28 = 1 17 + 11 17 = 1 11 + 6 11 = 1 6 + 5 6 = 1 5 + 1 5 = 5 1 + 0
gcd (2,008,1963) = 1 Note: the two number are coprime.
Algorithmic Representation[edit | edit source]
Euclidean Algorithm(a,b)
Input: Two integers a and b such that a > b
Output: An integer r = gcd(a,b)
1. Set a_{0} = a, r_{1} = r
2. r = a_{0} mod r_{1}
3. While(r_{1} mod r 0) do:
4. a_{0} = r_{1}
5. r_{1} = r
6. r = a_{0} mod r_{1}
7. Output r and halt
The Extended Euclidean Algorithm[edit | edit source]
In order to solve the type of equations represented by Bézout's identity, as shown below
where , , , and are integers, it is often useful to use the extended Euclidean algorithm. Equations of the form above occur in public key encryption algorithms such as RSA (Rivest-Shamir-Adleman) in the form where . There are two methods in which to implement the extended Euclidean algorithm; the iterative method and the recursive method.
As an example, we shall solve an RSA key generation problem with e = 2^{16} + 1, p = 3,217, q = 1,279. Thus, 62,537d + 51,456w = 1.
Methods[edit | edit source]
The Iterative Method[edit | edit source]
This method computes expressions of the form for the remainder in each step of the Euclidean algorithm. Each modulus can be written in terms of the previous two remainders and their whole quotient as follows:
By substitution, this gives:
The first two values are the initial arguments to the algorithm:
The expression for the last non-zero remainder gives the desired results since this method computes every remainder in terms of a and b, as desired.
Example[edit | edit source]
Step | Quotient | Remainder | Substitute | Combine terms | |
---|---|---|---|---|---|
1 | 4,110,048 = a | 4,110,048 = 1a + 0b | |||
2 | 65,537 = b | 65,537 = 0a + 1b | |||
3 | 62 | 46,754 = 4,110,048 - 65,537 62 | 46,754 = (1a + 0b) - (0a + 1b) 62 | 46,754 = 1a - 62b | |
4 | 1 | 18,783 = 65,537 - 46,754 1 | 18,783 = (0a + 1b) - (1a - 62b) 1 | 18,783 = -1a + 63b | |
5 | 2 | 9,188 = 46,754 - 18,783 2 | 9,188 = (1a - 62b) - (-1a + 62b) 2 | 9,188 = 3a - 188b | |
6 | 2 | 407 = 18,783 - 9,188 2 | 407 = (-1a + 63b) - (3a - 188b) 2 | 407 = -7a + 439b | |
7 | 22 | 234 = 9,188 - 407 22 | 234 = (3a - 188b) - (-7a + 439b) 22 | 234 = 157a - 9,846b | |
8 | 1 | 173 = 407 - 234 1 | 173 = (-7a + 439b) - (157a - 9,846b) 1 | 173 = -164a + 10,285b | |
9 | 1 | 61 = 234 - 173 1 | 61 = (157a - 9,846b) - (-164a + 10,285b) 1 | 61 = 321a + 20,131b | |
10 | 2 | 51 = 173 - 61 2 | 51 = (-164a + 10,285b) - (321a +20,131b) 2 | 51 = -806a + 50,547b | |
11 | 1 | 10 = 61 - 51 1 | 61 = (321a +20,131b) - (-806a + 50,547b) 1 | 10 = 1,127a - 70,678b | |
12 | 5 | 1 = 51 -10 5 | 1 = (-806a + 50,547b) - (1,127a - 70,678b) 5 | 1 = -6,441a + 403,937b | |
13 | 10 | 0 | End of algorithm |
Putting the equation in its original form yields , it is shown that and . During the process of key generation for RSA encryption, the value for w is discarded, and d is retained as the value of the private key In this case
d = 0x629e1 = 01100010100111100001
The Recursive Method[edit | edit source]
This is a direct method for solving Diophantine equations of the form . Using this method, the dividend and the divisor are reduced over a series of steps. At the last step, a trivial value is substituted into the equation, and is then worked backward until the solution is obtained.
Example[edit | edit source]
Using the previous RSA vales of and
Euclidean Expansion | Collect Terms | Substitute | Retrograde Substitution | Solve For d_{x} | |
---|---|---|---|---|---|
4,110,048 | w_{0} | + 65,537d_{0} = 1 | |||
(62 65,537 + 46,754) | w_{0} | + 65,537d_{0} = 1 | |||
65,537 | (62w_{0} + d_{0}) | + 46,754w_{0} = 1 | w_{1} = 62w_{0} + d_{0} | 4,595 = (62)(-6441) + d_{0} | d_{0} = 403,937 |
65,537 | w_{1} | + 46,754d_{1} = 1 | d_{1} = w_{0} | w_{1} = -6,441 | |
(1 46,754 + 18,783) | w_{1} | + 46,754d_{1} = 1 | |||
46,754 | (w_{1} + d_{1}) | + 18,783w_{1} = 1 | w_{2} = w_{1} + d_{1} | -1,846 = 4,595 + d_{1} | d_{1} = -6,441 |
46,754 | w_{2} | + 18,783d_{2} = 1 | d_{2} = w_{1} | ||
(2 18,783 + 9,188) | w_{2} | + 18,783d_{2} = 1 | |||
18,783 | (2w_{2} + d_{2}) | + 9,188w_{2} = 1 | w_{3} = 2w_{2} + d_{2} | 903 = (2)(-1,846) + d_{2} | d_{2} = 4,595 |
18,783 | w_{3} | + 9,188d_{3} = 1 | d_{3} = w_{2} | ||
(2 9,188 + 407) | w_{3} | + 9,188d_{3} = 1 | |||
9,188 | (2w_{3} + d_{3}) | + 407w_{3} = 1 | w_{4} = 2w_{3} + d_{3} | -40 = (2)(903) + d_{3} | d_{3} = -1846 |
9,188 | w_{4} | + 407d_{4} = 1 | d_{4} = w_{3} | ||
(22 407 + 234) | w_{4} | + 407d_{4} = 1 | |||
407 | (22w_{4} + d_{4}) | + 234w_{4} = 1 | w_{5} = 22w_{4} +d_{4} | 23 = (22)(-40) + d_{4} | d_{4} = 903 |
407 | w_{5} | + 234d_{5} = 1 | d_{5} = w_{4} | ||
(1 234 + 173) | w_{5} | + 234d_{5} = 1 | |||
234 | (w_{5} + d_{5}) | + 173w_{5} = 1 | w_{6} = w_{5} +d_{5} | -17 = 23 + d_{5} | d_{5} = -40 |
234 | w_{6} | + 173d_{6} = 1 | d_{6} = w_{5} | ||
(1 173 + 61) | w_{6} | + 173d_{6} = 1 | |||
173 | (w_{6} + d_{6}) | + 61w_{6} = 1 | w_{7} = w_{6} +d_{6} | 6 = -17 + d_{6} | d_{6} = 23 |
173 | w_{7} | + 61d_{7} = 1 | d_{7} = w_{6} | ||
(2 61 + 51) | w_{7} | + 61d_{7} = 1 | |||
61 | (2w_{7} + d_{7}) | + 51w_{7} = 1 | w_{8} = 2w_{7} +d_{7} | -5 = (2)(6) + d_{7} | d_{7} = -17 |
61 | w_{8} | + 51d_{8} = 1 | d_{8} = w_{7} | ||
(1 51 + 10) | w_{8} | + 51d_{8} = 1 | |||
51 | (w_{8} + d_{8}) | + 10w_{8} = 1 | w_{9} = w_{8} +d_{8} | 1 = -5 + d_{8} | d_{8} = 6 |
51 | w_{9} | + 10d_{9} = 1 | d_{9} = w_{8} | ||
(5 10 + 1) | w_{9} | + 10d_{9} = 1 | |||
10 | (5w_{9} + d_{9}) | + 1w_{9} = 1 | w_{10} = 5w_{9} +d_{9} | 0 = (5)(1) + d_{9} | d_{9} = -5 |
10 | w_{10} | + 1d_{10} = 1 | d_{10} = w_{9} | ||
(1 10 + 0) | w_{10} | + 1d_{10} = 1 | |||
1 | (10w_{10} + d_{10}) | + 0w_{10} = 1 | w_{11} = 10w_{10} +d_{10} | 1 = (10)(0) + d_{10} | d_{10} = 1 |
1 | w_{11} | + 0d_{11} = 1 | d_{11} = w_{10} | w_{11} = 1, d_{11} = 0 |
Euler's Totient Function[edit | edit source]
Significant in cryptography, the totient function (sometimes known as the phi function) is defined as the number of nonnegative integers less than that are coprime to . Mathematically, this is represented as
Which immediately suggests that for any prime
The totient function for any exponentiated prime is calculated as follows
The Euler totient function is also multiplicative
where
Finite Fields and Generators[edit | edit source]
A field is simply a set which contains numerical elements that are subject to the familiar addition and multiplication operations. Several different types of fields exist; for example, , the field of real numbers, and , the field of rational numbers, or , the field of complex numbers. A generic field is usually denoted .
Finite Fields[edit | edit source]
Cryptography utilizes primarily finite fields, nearly exclusively composed of integers. The most notable exception to this are the Gaussian numbers of the form which are complex numbers with integer real and imaginary parts. Finite fields are defined as follows
- The set of integers modulo
- The set of integers modulo a prime
Since cryptography is concerned with the solution of diophantine equations, the finite fields utilized are primarily integer based, and are denoted by the symbol for the field of integers, .
A finite field contains exactly elements, of which there are nonzero elements. An extension of is the multiplicative group of , written , and consisting of the following elements
- such that
in other words, contains the elements coprime to
Finite fields form an abelian group with respect to multiplication, defined by the following properties
The product of two nonzero elements is nonzero The associative law holds The commutative law holds There is an identity element Any nonzero element has an inverse
A subscript following the symbol for the field represents the set of integers modulo , and these integers run from to as represented by the example below
The multiplicative order of is represented and consists of all elements such that . An example for is given below
If is prime, the set consists of all integers such that . For example
Composite n | Prime p |
---|---|
Generators[edit | edit source]
Every finite field has a generator. A generator is capable of generating all of the elements in the set by exponentiating the generator . Assuming is a generator of , then contains the elements for the range . If has a generator, then is said to be cyclic.
The total number of generators is given by
Examples[edit | edit source]
For (Prime) Total number of generators generators Let , then , is a generator Since is a generator, check if , and , , therefore, is not a generator , and , , therefore, is not a generator Let , then , is a generator Let , then , is a generator Let , then , is a generator There are a total of generators, as predicted by the formula
For (Composite) Total number of generators generators Let , then , is a generator Let , then , is a generator There are a total of generators as predicted by the formula
Congruences[edit | edit source]
Description[edit | edit source]
Number theory contains an algebraic system of its own called the theory of congruences. The mathematical notion of congruences was introduced by Karl Friedrich Gauss in Disquisitiones (1801).
Definition[edit | edit source]
If and are two integers, and their difference is evenly divisible by , this can be written with the notation
This is expressed by the notation for a congruence
where the divisor is called the modulus of congruence. can equivalently be written as
where is an integer.
Note in the examples that for all cases in which , it is shown that . with this in mind, note that
Represents that is an even number.
Represents that is an odd number.
Examples[edit | edit source]
Properties of Congruences[edit | edit source]
All congruences (with fixed ) have the following properties in common
- if and only if
- If and then
- implies that
- Given there exists a unique such that
These properties represent an equivalence class, meaning that any integer is congruent modulo to one specific integer in the finite field .
Congruences as Remainders[edit | edit source]
If the modulus of an integer , then for every integer
which can be understood to mean is the remainder of divided by , or as a congruence
Two numbers that are incongruent modulo must have different remainders. Therefore, it can be seen that any congruence holds if and only if and are integers which have the same remainder when divided by .
Example[edit | edit source]
is equivalent to implies is the remainder of divided by
The Algebra of Congruences[edit | edit source]
Suppose for this section we have two congruences, and . These congruences can be added or subtracted in the following manner
If these two congruences are multiplied together, the following congruence is obtained
or the special case where
Note: The above does not mean that there exists a division operation for congruences. The only possibility for simplifying the above is if and only if and are coprime. Mathematically, this is represented as
- implies that if and only if
The set of equivalence classes defined above form a commutative ring, meaning the residue classes can be added, subtracted and multiplied, and that the operations are associative, commutative and have additive inverses.
Reducing Modulo m[edit | edit source]
Often, it is necessary to perform an operation on a congruence where , when what is desired is a new integer such that with the resultant being the least nonnegative residue modulo m of the congruence. Reducing a congruence modulo is based on the properties of congruences and is often required during exponentiation of a congruence.
Algorithm[edit | edit source]
Input: Integers and from with Output: Integer such that 1. Let 2. 3. 4. Output
Example[edit | edit source]
Given ∴
Note that is the least nonnegative residue modulo
Exponentiation[edit | edit source]
Assume you begin with . Upon multiplying this congruence by itself the result is . Generalizing this result and assuming is a positive integer
Example[edit | edit source]
This simplifies to implies implies
Repeated Squaring Method[edit | edit source]
Sometimes it is useful to know the least nonnegative residue modulo of a number which has been exponentiated as . In order to find this number, we may use the repeated squaring method which works as follows:
1. Begin with 2. Square and so that 3. Reduce modulo to obtain 4. Continue with steps 2 and 3 until is obtained. Note that is the integer where would be just larger than the exponent desired 5. Add the successive exponents until you arrive at the desired exponent 6. Multiply all 's associated with the 's of the selected powers 7. Reduce the resulting for the desired result
Example[edit | edit source]
To find : Adding exponents: Multiplying least nonnegative residues associated with these exponents: Therefore:
Inverse of a Congruence[edit | edit source]
Description[edit | edit source]
While finding the correct symmetric or asymmetric keys is required to encrypt a plaintext message, calculating the inverse of these keys is essential to successfully decrypt the resultant ciphertext. This can be seen in cryptosystems Ranging from a simple affine transformation
Where
To RSA public key encryption, where one of the deciphering (private) keys is
Definition[edit | edit source]
For the elements where , there exists such that . Thus, is said to be the inverse of , denoted where is the power of the integer for which .
Example[edit | edit source]
Find This is equivalent to saying First use the Euclidean algorithm to verify . Next use the Extended Euclidean algorithm to discover the value of . In this case, the value is . Therefore, It is easily verified that
Fermat's Little Theorem[edit | edit source]
Definition[edit | edit source]
Where is defined as prime, any integer will satisfy the following relation:
Example[edit | edit source]
When and
- implies that
Conditions and Corollaries[edit | edit source]
An additional condition states that if is not divisible by , the following equation holds
Fermat's Little Theorem also has a corollary, which states that if is not divisible by and then
Euler's Generalization[edit | edit source]
If , then
Chinese Remainder Theorem[edit | edit source]
If one wants to solve a system of congruences with different moduli, it is possible to do so as follows:
A simultaneous solution exists if and only if with , and any two solutions are congruent to one another modulo .
The steps for finding the simultaneous solution using the Chinese Remainder theorem are as follows:
- 1. Compute
- 2. Compute for each of the different 's
- 3. Find the inverse of for each using the Extended Euclidean algorithm
- 4. Multiply out for each
- 5. Sum all
- 6. Compute to obtain the least nonnegative residue
Example[edit | edit source]
Given: Using the Extended Euclidean algorithm:
Quadratic Residues[edit | edit source]
If is prime and , examining the nonzero elements of , it is sometimes important to know which of these are squares. If for some , there exists a square such that . Then all squares for can be calculated by where . is a quadratic residue modulo if there exists an such that . If no such exists, then is a quadratic non-residue modulo . is a quadratic residue modulo a prime if and only if .
Example[edit | edit source]
For the finite field , to find the squares , proceed as follows:
The values above are quadratic residues. The remaining (in this example) 9 values are known as quadratic nonresidues. the complete listing is given below.
Quadratic residues: Quadratic nonresidues:
Legendre Symbol[edit | edit source]
The Legendre symbol denotes whether or not is a quadratic residue modulo the prime and is only defined for primes and integers . The Legendre of with respect to is represented by the symbol . Note that this does not mean divided by . has one of three values: .
Jacobi Symbol[edit | edit source]
The Jacobi symbol applies to all odd numbers where , then:
If is prime, then the Jacobi symbol equals the Legendre symbol (which is the basis for the Solovay-Strassen primality test).
Primality Testing[edit | edit source]
Description[edit | edit source]
In cryptography, using an algorithm to quickly and efficiently test whether a given number is prime is extremely important to the success of the cryptosystem. Several methods of primality testing exist (Fermat or Solovay-Strassen methods, for example), but the algorithm to be used for discussion in this section will be the Miller-Rabin (or Rabin-Miller) primality test. In its current form, the Miller-Rabin test is an unconditional probabilistic (Monte Carlo) algorithm. It will be shown how to convert Miller-Rabin into a deterministic (Las Vegas) algorithm.
Pseudoprimes[edit | edit source]
Remember that if is prime and , Fermat's Little Theorem states:
However, there are cases where can meet the above conditions and be nonprime. These classes of numbers are known as pseudoprimes.
is a pseudoprime to the base , with if and only if the least positive power of that is congruent to evenly divides .
If Fermat's Little Theorem holds for any that is an odd composite integer, then is referred to as a pseudoprime. This forms the basis of primality testing. By testing different 's, we can probabilistically become more certain of the primality of the number in question.
The following three conditions apply to odd composite integers:
- I. If the least positive power of which is congruent to and divides which is the order of in , then is a pseudoprime.
- II. If is a pseudoprime to base and , then is also a pseudoprime to and .
- III. If fails , for any single base , then fails for at least half the bases .
An odd composite integer for which holds for every is known as a Carmichael Number.
Miller-Rabin Primality Test[edit | edit source]
Description[edit | edit source]
Examples[edit | edit source]
Factoring[edit | edit source]
The Rho Method[edit | edit source]
Description[edit | edit source]
Algorithm[edit | edit source]
Example[edit | edit source]
Fermat Factorization[edit | edit source]
Example[edit | edit source]
Random Number Generators[edit | edit source]
RNGs vs. PRNGs[edit | edit source]
ANSI X9.17 PRNG[edit | edit source]
Blum-Blum-Shub PRNG[edit | edit source]
RSA PRNG[edit | edit source]
Entropy Extractors[edit | edit source]
Whitening Functions[edit | edit source]
Large Integer Multiplication[edit | edit source]
Karatsuba Multiplication[edit | edit source]
Example[edit | edit source]
Furers Multiplication[edit | edit source]
Elliptic Curves[edit | edit source]
Description[edit | edit source]
As I Have Gone Alone in the, and with my treasures Bold, i can keep my secrets where and hint of riches new and old, Begin it where warm waters halt, and take it in the canyon down, not too far, but too far to walk, put in below the home of brown, from there it's no place for the meek, the end is ever drawing neigh, there'll be no paddle up your creek, just heavy loads and water high,