Cryptography/Mathematical Background

See Talk page for other suggestions.

IntroductionEdit

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

a^2 + b^2 = c^2 \

where c \ 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.

Pythagorean Triplets
a \ b \ c \
3 4 5
5 12 13
7 24 25
8 15 17

Prime NumbersEdit

DescriptionEdit

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. - a | b means "b divides into a"), a prime number strictly adheres to the following mathematical definition

p \ |  b \ Where b = 1 \ or p \ 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

c \ | b \ where ultimately b =  p^{e_0}_{0} p^{e_1}_{1} \cdot \cdot \cdot p^{e_n}_{n} \

in which p_n \ is a unique prime number and e_n \ is the exponent.

Numerical ExamplesEdit

543,312 = 24 \cdot 32 \cdot 50 \cdot 73 \cdot 111
553,696 = 25 \cdot 30 \cdot 50 \cdot 70 \cdot 113 \cdot 131

As can be seen, according to this systematic decomposition, each factorization is unique.

In order to deterministically verify whether an integer a \ is prime or composite, only the primes p \le \sqrt c \ 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 PrimesEdit

Fermat numbers take the following form

F_n = 2^{2^n} + 1 \

If Fn is prime, then it is called a Fermat prime.

Numerical ExamplesEdit

F_0 = 2^{2^0} + 1= 3 \ F_1 = 2^{2^1} + 1= 5 \ F_2 = 2^{2^2} + 1= 17 \ F_3 = 2^{2^3} + 1= 257 \ F_4 = 2^{2^4} + 1= 65,537 \ F_5 = 2^{2^5} + 1= 4,294,967,297 \ 


The only Fermat numbers known to be prime are F_0-F_4 \ . Moreover, the primality of all Fermat numbers was disproven by Euler, who showed that F_5 = 641 \cdot 6,700,297.

Mersenne PrimesEdit

Mersenne primes - another type of formulaic prime generation - follow the form

M_p = 2^p - 1 \

where p \ is a prime number. The [1] Wolfram Alpha engine reports Mersenne Primes, an example input request being "4th Mersenne Prime".

Numerical ExamplesEdit

The first four Mersenne primes are as follows

M_2 = 2^2 - 1 = 3 \ M_3 = 2^3 - 1 = 7 \ M_5 = 2^5 - 1 = 31 \ M_7 = 2^7 - 1 = 127 \ 

Numbers of the form Mp = 2p without the primality requirement are called Mersenne numbers. Not all Mersenne numbers are prime, e.g. M11 = 211−1 = 2047 = 23 · 89.

Coprimes (Relatively Prime Numbers)Edit

Two numbers are said to be coprime if the largest integer that divides evenly into both of them is 1. Mathematically, this is written

\gcd(a,b) = 3 \

where \gcd \ is the greatest common divisor. Two rules can be derived from the above definition

If ab \ | c \ and \gcd(b,c) = 1 \ , then a \ | c \
If ab = c^2 \ with \gcd(a,b) = 1 \ , then both a \ and b \ are squares, i.e. - a = a^2_{0} \ , b = b^2_{0} \

The Prime Number TheoremEdit

The Prime Number Theorem estimates the probability that any integer, chosen randomly will be prime. The estimate is given below, with \pi (x) \ defined as the number of primes \le x \

\pi (x) \approx \frac {x}{\ln x} \

\pi (x) \ is asymptotic to \frac {x}{\ln x} \ , that is to say \quad\lim_{x\to \infty} \frac {\pi (x)}{\ln x} = 1 \ . What this means is that generally, a randomly chosen number is prime with the approximate probability \tfrac {1}{x} \ .

The Euclidean AlgorithmEdit

IntroductionEdit

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. - \gcd (a,b) = 1 \ .

In order to find \gcd (a,b) \ where a > b \ efficiently when working with very large numbers, as with cryptosystems, a method exists to do so. The Euclidean algorithm operates as follows - First, divide a \ by b \ , writing the quotient q_1 \ , and the remainder r_1 \ . Note this can be written in equation form as a = q_1b + r_1 \ . Next perform the same operation using b \ in a \ 's place: b = q_2r_1 + r_2 \ . 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 DescriptionEdit

a = q_1b + r_1 \ b = q_2r_1 + r_2 \ r_1 = q_3r_2 + r_3 \ r_2 = q_4r_3 + r_4 \ \cdot \ \cdot \ \cdot \ r_{n-2} = q_nr_{n-1} + r_n \ 

When r_n = 0 \ , stop with \gcd (a,b) = r_{n-1} \ .

Numerical ExamplesEdit

Example 1 - To find gcd(17,043,12,660)

17,043 = 1 \cdot 12,660 + 4383
12,660 = 2 \cdot 4,383 + 3894
 4,383 = 1 \cdot 3,894 + 489
 3,894 = 7 \cdot 489 + 471
   489 = 1 \cdot 471 + 18
   471 = 26 \cdot 18 + 3
    18 = 6 \cdot 3 + 0

gcd (17,043,12,660) = 3 \ </math>

Example 2 - To find gcd(2,008,1,963)

2,008 = 1 \cdot 1,963 + 45
1,963 = 43 \cdot 45 + 28
   45 = 1 \cdot 28 + 17
   28 = 1 \cdot 17 + 11
   17 = 1 \cdot 11 + 6
   11 = 1 \cdot 6 + 5
    6 = 1 \cdot 5 + 1
    5 = 5 \cdot 1 + 0

gcd (2,008,1963) = 1 Note: the two number are coprime.

Algorithmic RepresentationEdit

Euclidean Algorithm(a,b)
Input:     Two integers a and b such that a > b
Output:    An integer r = gcd(a,b)
  1.   Set a0 = a, r1 = r
  2.   r = a0 mod r1
  3.   While(r1 mod r \ne 0) do:
  4.      a0 = r1
  5.      r1 = r
  6.      r = a0 mod r1
  7.   Output r and halt

The Extended Euclidean AlgorithmEdit

In order to solve the type of equations represented by Bézout's identity, as shown below

au + bv = \gcd (a,b) \

where a \ , b \ , u \ , and v \ 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 ed + w(p-1)(q-1) = 1 \ where \gcd (e,(p-1)(q-1)) = 1 \ . 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 = 216 + 1, p = 3,217, q = 1,279. Thus, 62,537d + 51,456w = 1.

MethodsEdit

The Iterative MethodEdit

This method computes expressions of the form r_i = ax_i+by_i for the remainder in each step i of the Euclidean algorithm. Each modulus can be written in terms of the previous two remainders and their whole quotient as follows:

r_i = r_{i-2} - \left \lfloor \frac{r_{i-2}}{r_{i-1}} \right \rfloor \cdot r_{i-1}

By substitution, this gives:

r_i = (ax_{i-2} + by_{i-2}) - \left \lfloor \frac{r_{i-2}}{r_{i-1}} \right \rfloor \cdot (ax_{i-1} + by_{i-1})
r_i = a(x_{i-2} - \left \lfloor \frac{r_{i-2}}{r_{i-1}} \right \rfloor \cdot x_{i-1}) + b(y_{i-2} - \left \lfloor \frac{r_{i-2}}{r_{i-1}} \right \rfloor \cdot y_{i-1})

The first two values are the initial arguments to the algorithm:

r_1 = a = a(1) + b(0) \
r_2 = b = a(0) + b(1) \

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.

ExampleEdit
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 \cdot 62 46,754 = (1a + 0b) - (0a + 1b) \cdot 62 46,754 = 1a - 62b
4 1 18,783 = 65,537 - 46,754 \cdot 1 18,783 = (0a + 1b) - (1a - 62b) \cdot 1 18,783 = -1a + 63b
5 2 9,188 = 46,754 - 18,783 \cdot 2 9,188 = (1a - 62b) - (-1a + 62b) \cdot 2 9,188 = 3a - 188b
6 2 407 = 18,783 - 9,188 \cdot 2 407 = (-1a + 63b) - (3a - 188b) \cdot 2 407 = -7a + 439b
7 22 234 = 9,188 - 407 \cdot 22 234 = (3a - 188b) - (-7a + 439b) \cdot 22 234 = 157a - 9,846b
8 1 173 = 407 - 234 \cdot 1 173 = (-7a + 439b) - (157a - 9,846b) \cdot 1 173 = -164a + 10,285b
9 1 61 = 234 - 173 \cdot 1 61 = (157a - 9,846b) - (-164a + 10,285b) \cdot 1 61 = 321a + 20,131b
10 2 51 = 173 - 61 \cdot 2 51 = (-164a + 10,285b) - (321a +20,131b) \cdot 2 51 = -806a + 50,547b
11 1 10 = 61 - 51 \cdot 1 61 = (321a +20,131b) - (-806a + 50,547b) \cdot 1 10 = 1,127a - 70,678b
12 5 1 = 51 -10 \cdot 5 1 = (-806a + 50,547b) - (1,127a - 70,678b) \cdot 5 1 = -6,441a + 403,937b
13 10 0 End of algorithm

Putting the equation in its original form ed + w(p - 1)(q - 1) = 1 \ yields (65,537)(403,937) + (-6,441)(3,217 - 1)(1,279 - 1) = 1 \ , it is shown that d = 403,937 \ and w = -6,441 \ . 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 MethodEdit

This is a direct method for solving Diophantine equations of the form au + bv = \gcd (a,b) \ . 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.

ExampleEdit

Using the previous RSA vales of (p - 1)(p - 1) = 4,110,048 \ and e = 2^{16} + 1 = 65,537 \

Euclidean Expansion Collect Terms Substitute Retrograde Substitution Solve For dx
4,110,048 w0 + 65,537d0 = 1
(62 \cdot 65,537 + 46,754) w0 + 65,537d0 = 1
65,537 (62w0 + d0) + 46,754w0 = 1 w1 = 62w0 + d0 4,595 = (62)(-6441) + d0 d0 = 403,937
65,537 w1 + 46,754d1 = 1 d1 = w0 w1 = -6,441
(1 \cdot 46,754 + 18,783) w1 + 46,754d1 = 1
46,754 (w1 + d1) + 18,783w1 = 1 w2 = w1 + d1 -1,846 = 4,595 + d1 d1 = -6,441
46,754 w2 + 18,783d2 = 1 d2 = w1
(2 \cdot 18,783 + 9,188) w2 + 18,783d2 = 1
18,783 (2w2 + d2) + 9,188w2 = 1 w3 = 2w2 + d2 903 = (2)(-1,846) + d2 d2 = 4,595
18,783 w3 + 9,188d3 = 1 d3 = w2
(2 \cdot 9,188 + 407) w3 + 9,188d3 = 1
9,188 (2w3 + d3) + 407w3 = 1 w4 = 2w3 + d3 -40 = (2)(903) + d3 d3 = -1846
9,188 w4 + 407d4 = 1 d4 = w3
(22 \cdot 407 + 234) w4 + 407d4 = 1
407 (22w4 + d4) + 234w4 = 1 w5 = 22w4 +d4 23 = (22)(-40) + d4 d4 = 903
407 w5 + 234d5 = 1 d5 = w4
(1 \cdot 234 + 173) w5 + 234d5 = 1
234 (w5 + d5) + 173w5 = 1 w6 = w5 +d5 -17 = 23 + d5 d5 = -40
234 w6 + 173d6 = 1 d6 = w5
(1 \cdot 173 + 61) w6 + 173d6 = 1
173 (w6 + d6) + 61w6 = 1 w7 = w6 +d6 6 = -17 + d6 d6 = 23
173 w7 + 61d7 = 1 d7 = w6
(2 \cdot 61 + 51) w7 + 61d7 = 1
61 (2w7 + d7) + 51w7 = 1 w8 = 2w7 +d7 -5 = (2)(6) + d7 d7 = -17
61 w8 + 51d8 = 1 d8 = w7
(1 \cdot 51 + 10) w8 + 51d8 = 1
51 (w8 + d8) + 10w8 = 1 w9 = w8 +d8 1 = -5 + d8 d8 = 6
51 w9 + 10d9 = 1 d9 = w8
(5 \cdot 10 + 1) w9 + 10d9 = 1
10 (5w9 + d9) + 1w9 = 1 w10 = 5w9 +d9 0 = (5)(1) + d9 d9 = -5
10 w10 + 1d10 = 1 d10 = w9
(1 \cdot 10 + 0) w10 + 1d10 = 1
1 (10w10 + d10) + 0w10 = 1 w11 = 10w10 +d10 1 = (10)(0) + d10 d10 = 1
1 w11 + 0d11 = 1 d11 = w10 w11 = 1, d11 = 0

Euler's Totient FunctionEdit

Significant in cryptography, the totient function (sometimes known as the phi function) is defined as the number of nonnegative integers a \ less than n \ that are coprime to n \ . Mathematically, this is represented as

\phi (n) = \left | \bigg\{ 0 \le a \le n | \gcd (a, n) = 1 \bigg\} \right |

Which immediately suggests that for any prime p \

\phi (p) = p - 1 \

The totient function for any exponentiated prime is calculated as follows

\phi (p^\alpha) \
= p^\alpha - p^{\alpha - 1} \
= p^\alpha \left ( 1 - \tfrac{1}{p} \right ) \

The Euler totient function is also multiplicative

\phi (ab) = \phi (a) \phi (b) \

where \gcd (a,b) = 1 \

Finite Fields and GeneratorsEdit

A field is simply a set \mathbb{F} which contains numerical elements that are subject to the familiar addition and multiplication operations. Several different types of fields exist; for example, \mathbb{R}, the field of real numbers, and \mathbb{Q}, the field of rational numbers, or \mathbb{C}, the field of complex numbers. A generic field is usually denoted \mathbb{F}.

Finite FieldsEdit

Cryptography utilizes primarily finite fields, nearly exclusively composed of integers. The most notable exception to this are the Gaussian numbers of the form a + bi \ which are complex numbers with integer real and imaginary parts. Finite fields are defined as follows

\left( \mathbb{Z} / n \mathbb{Z} \right) = \mathbb{Z}_n \  The set of integers modulo n \
\left( \mathbb{Z} / p \mathbb{Z} \right) = \mathbb{Z}_p \  The set of integers modulo a prime p \

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, \mathbb{Z}.

A finite field \mathbb{F}_n \ contains exactly n \ elements, of which there are n - 1 \ nonzero elements. An extension of \mathbb{Z}_n \ is the multiplicative group of \mathbb{Z}_n \ , written \left( \mathbb{Z} / n \mathbb{Z} \right)^* = \mathbb{Z}^*_n \ , and consisting of the following elements

a \in \mathbb{Z}^*_n \ such that \gcd (a,n) = 1 \

in other words, \mathbb{Z}^*_n \ contains the elements coprime to n \

Finite fields form an abelian group with respect to multiplication, defined by the following properties

\centerdot The product of two nonzero elements is nonzero \left( ab = c | c \ne 0 \right) \ \centerdot The associative law holds \left( \left( ab \right) c = a \left( bc \right) \right) \ \centerdot The commutative law holds \left( ab = ba \right) \ \centerdot There is an identity element \left( I \cdot a = a \right) \ \centerdot Any nonzero element has an inverse \left( a \cdot a^{-1} = 1 \right) \ 

A subscript following the symbol for the field represents the set of integers modulo n \ , and these integers run from 0 \ to n - 1 \ as represented by the example below

\mathbb{Z}_{12} = \{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 \} \

The multiplicative order of \mathbb{Z}_n is represented \mathbb{Z}^*_n and consists of all elements a \in \mathbb{Z}_n such that \gcd (a,n) = 1 \ . An example for \mathbb{Z}_{12} is given below

\mathbb{Z}^*_{12} = \{ 1, 5, 7, 11 \} \

If p \ is prime, the set \mathbb{Z}^*_p consists of all integers a \ such that 1 \le a \le p \ . For example

Composite n Prime p
\mathbb{Z}_9 = \{ 0, 1, 2, 3, 4, 5, 6, 7, 8 \} \mathbb{Z}_{11} = \{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 \}
\mathbb{Z}^*_9 = \{ 1, 2, 4, 5, 7, 8 \} \mathbb{Z}^*_{11} = \{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 \}

GeneratorsEdit

Every finite field has a generator. A generator g \ is capable of generating all of the elements in the set \mathbb{Z}_n by exponentiating the generator g\,\bmod\,n \ . Assuming g \ is a generator of \mathbb{Z}^*_n, then \mathbb{Z}^*_n contains the elements g^i\,\bmod\,n \ for the range 0 \le i \le \phi (n) - 1. If \mathbb{Z}^*_n has a generator, then \mathbb{Z}_n is said to be cyclic.

The total number of generators is given by

\phi \left( \phi \left( n \right) \right)

ExamplesEdit

For n = p = 13 \  (Prime)

\mathbb{Z}_{13} = \{ 0,1,2,3,4,5,6,7,8,9,10,11,12 \}\mathbb{Z}^*_{13} = \{ 1,2,3,4,5,6,7,8,9,10,11,12 \}

Total number of generators \phi \left( \phi \left( 13 \right) \right) = \phi \left( 12 \right) = 4 generators

Let g = 2 \ , then g = \{ 2,4,8,3,6,12,11,9,5,10,7,1 \} \ , g = 2 \  is a generator

Since 2 \  is a generator, check if \gcd (i, p - 1) = 1 \ 2^2 = 4 \ , and i = 2 \ , \gcd \left( 2, 12 \right) = 2 \ne 1 \ , therefore, 4 \  is not a generator
2^3 = 8 \ , and i = 3 \ , \gcd \left( 3, 12 \right) = 3 \ne 1 \ , therefore, 4 \  is not a generator

Let g = 6 \ , then g = \{ 6,10,8,9,2,12,7,3,5,4,11,1 \} \ , g = 6 \  is a generator
Let g = 7 \ , then g = \{ 7,10,5,9,11,12,6,3,8,4,2,1 \} \ , g = 7 \  is a generator
Let g = 11 \ , then g = \{ 11,4,5,3,7,12,2,9,8,10,6,1 \} \ , g = 11 \  is a generator

There are a total of 4 \  generators, \left( 2,6,7,11 \right) as predicted by the formula \phi \left( \phi \left( n \right) \right).
For n = 10 \  (Composite)

\mathbb{Z}_9 = \{ 0,1,2,3,4,5,6,7,8,9 \} \ \mathbb{Z}^*_9 = \{ 1,3,7,9 \} \ 

Total number of generators \phi \left( \phi \left( 10 \right) \right) = \phi \left( 4 \right) = 2 \  generators

Let g = 3 \ , then g = \{ 3,9,7,1,3,9,7,1,3 \} \ , g = 3 \  is a generator
Let g = 7 \ , then g = \{ 7,9,3,1,7,9,3,1,7 \} \ , g = 7 \  is a generator

There are a total of 2 \  generators \left( 3,7, \right) \  as predicted by the formula \phi \left( \phi \left( n \right) \right).

CongruencesEdit

DescriptionEdit

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).

DefinitionEdit

If a \ and b \ are two integers, and their difference is evenly divisible by m \ , this can be written with the notation

\left( a - b \right) | m \

This is expressed by the notation for a congruence

a \equiv b\,\bmod\,m

where the divisor m \ is called the modulus of congruence. a \equiv b\,\bmod\,m can equivalently be written as

a - b = mk \

where k \ is an integer.

Note in the examples that for all cases in which a \equiv 0\,\bmod\,m, it is shown that a | m \ . with this in mind, note that

a \equiv 0\,\bmod\,2 Represents that a \ is an even number.

a \equiv 1\,\bmod\,2 Represents that a \ is an odd number.

ExamplesEdit

a \equiv b\,\bmod\,m a - b = mk \
14 \equiv 5\,\bmod\,3 14 - 5 = 3 \cdot 3 \
-13 \equiv 7\,\bmod\,4 (-13) - 7 = 4 \cdot (-5) \
90 \equiv 0\,\bmod\,18 90 - 0 = 18 \cdot 5 \

Properties of CongruencesEdit

All congruences (with fixed m \ ) have the following properties in common

a \equiv a\,\bmod\,m
a \equiv b\,\bmod\,m if and only if b \equiv a\,\bmod\,m
If a \equiv b\,\bmod\,m and b \equiv c\,\bmod\,m then a \equiv c\,\bmod\,m
a \equiv b\,\bmod\,1 implies that a = b \
Given a \equiv a\,\bmod\,m there exists a unique b \ such that  0 \le b \le m - 1 \

These properties represent an equivalence class, meaning that any integer is congruent modulo m \ to one specific integer in the finite field \mathbb{Z}_m.

Congruences as RemaindersEdit

If the modulus of an integer m > 2 \ , then for every integer a \

a = mk + r \, \left( r \in \mathbb{Z}_m \right)

which can be understood to mean r \ is the remainder of a \ divided by m \ , or as a congruence

a \equiv r\,\bmod\,m

Two numbers that are incongruent modulo m \ must have different remainders. Therefore, it can be seen that any congruence a \equiv b\,\bmod\,m holds if and only if a \ and b \ are integers which have the same remainder when divided by m \ .

ExampleEdit

10 \equiv 3\,\bmod\,7 is equivalent to
10 = \left( 7 \cdot 1 \right) + 3 \  implies
3 \  is the remainder of 10 \  divided by 7 \ 

The Algebra of CongruencesEdit

Suppose for this section we have two congruences, a \equiv a\,\bmod\,m and c \equiv d\,\bmod\,m. These congruences can be added or subtracted in the following manner

a + c \equiv b + d\,\bmod\,m
a - c \equiv b - d\,\bmod\,m

If these two congruences are multiplied together, the following congruence is obtained

ac \equiv bd\,\bmod\,m

or the special case where c = d \

ac \equiv bc\,\bmod\,m

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 c \ and m \ are coprime. Mathematically, this is represented as

ac \equiv bc\,\bmod\,m implies that a \equiv b\,\bmod\,m if and only if \gcd \left( c,m \right) = 1

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 mEdit

Often, it is necessary to perform an operation on a congruence a \equiv b\,\bmod\,m where b > m \ , when what is desired is a new integer d \ such that 0 \le d \le m - 1 \ with the resultant d \ being the least nonnegative residue modulo m of the congruence. Reducing a congruence modulo m \ is based on the properties of congruences and is often required during exponentiation of a congruence.

AlgorithmEdit

Input: Integers b \  and m \  from a \equiv b\,\bmod\,m with b > m \ 
Output: Integer d \  such that 0 \le d \le m - 1 \ 

1. Let q = \left \lfloor \tfrac{b}{m} \right \rfloor
2.     c = qm \ 
3.     d = b - c \ 
4. Output d \ 

ExampleEdit

Given 289 \equiv 49\,\bmod\,59 = \left \lfloor \tfrac{49}{5} \right \rfloor45 = 9 \cdot 5 \ 4 = 49 - 45 \ 289 \equiv 49 \equiv 4\,\bmod\,5

Note that 4 \ is the least nonnegative residue modulo 5 \

ExponentiationEdit

Assume you begin with a \equiv b\,\bmod\,m. Upon multiplying this congruence by itself the result is a^2 \equiv b^2\,\bmod\,m. Generalizing this result and assuming n \ is a positive integer

a^n \equiv b^n\,\bmod\,m

ExampleEdit

9 \equiv 4\,\bmod\,1381 \equiv 16\,\bmod\,13729 \equiv 64\,\bmod\,13

This simplifies to

81 \equiv 16\,\bmod\,13 implies 16 \equiv 3\,\bmod\,13729 \equiv 64\,\bmod\,13 implies 256 \equiv 9\,\bmod\,13

Repeated Squaring MethodEdit

Sometimes it is useful to know the least nonnegative residue modulo m \ of a number which has been exponentiated as a^2 \equiv\,\bmod\,m. In order to find this number, we may use the repeated squaring method which works as follows:

1. Begin with a \equiv\,\bmod\,m
2. Square a \  and b \  so that a^2 \equiv b^2\,\bmod\,m
3. Reduce b \  modulo m \  to obtain a^ \equiv b_1\,\bmod\,m
4. Continue with steps 2 and 3 until a^{2^n} \equiv b_n\,\bmod\,m is obtained.
   Note that n \  is the integer where 2^{n+1} \  would be just larger than the exponent desired
5. Add the successive exponents until you arrive at the desired exponent
6. Multiply all b_i \ 's associated with the a \ 's of the selected powers
7. Reduce the resulting b\,\bmod\,m for the desired result

ExampleEdit

To find 6^{149}\bmod\,11:

6 \equiv 6\,\bmod\,116^2 = 36 \equiv 3\,\bmod\,116^4 \equiv 9\,\bmod\,116^8 \equiv 81 \equiv 4\,\bmod\,116^{16} \equiv 16 \equiv 5\,\bmod\,116^{32} \equiv 25 \equiv 3\,\bmod\,116^{64} \equiv 9\,\bmod\,116^{128} \equiv 81 \equiv 4\,\bmod\,11

Adding exponents:

128 + 16 + 4 + 1 \ 

Multiplying least nonnegative residues associated with these exponents:

4 \cdot 5 \cdot 9 \cdot 6 = 1080 \ 1080\,\bmod\,11 = 2

Therefore: 

6^{149} \equiv 2\,\bmod\,11

Inverse of a CongruenceEdit

DescriptionEdit

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

C \equiv aP + b\,\bmod\,N

Where

P \equiv a^{-1}C + b^{-1}\,\bmod\,N

To RSA public key encryption, where one of the deciphering (private) keys is

d_A = e^{-1}_A\,\bmod\,\phi \left( n_A \right)

DefinitionEdit

For the elements a \in \mathbb Z_m where \gcd \left( a, m  \right) = 1, there exists b \in \mathbb Z_m such that ab \equiv 1\,\bmod\,m. Thus, b \ is said to be the inverse of a \ , denoted a^{-n}\,\bmod\,m where n \ is the n^{th} \ power of the integer b \ for which ab \equiv 1\,\bmod\,m.

ExampleEdit
Find 633^{-1}\,\bmod\,2801

This is equivalent to saying 633b \equiv 1\,\bmod\,2801

First use the Euclidean algorithm to verify \gcd \left( 633, 2801 \right) = 1 \ .
Next use the Extended Euclidean algorithm to discover the value of b \ .
In this case, the value is 177 \ .

Therefore, 633^{-1}\,\bmod\,2801 = 177

It is easily verified that \left( 633 \right) \left( 177 \right) \equiv 1\,\bmod\,2801

Fermat's Little TheoremEdit

DefinitionEdit

Where p \ is defined as prime, any integer will satisfy the following relation:

a^p \equiv a\,\bmod\,p

ExampleEdit

When a = 2 \ and p = 19 \

2^2 \equiv 23\,\bmod\,19
2^4 \equiv 529 \equiv 16\,\bmod\,19
2^8 \equiv 256 \equiv 9\,\bmod\,19
2^{16} \equiv 81 \equiv 5\,\bmod\,19
16 + 2 + 1 = 19 \ implies that 5 \cdot 23 \cdot 2 = 230 \equiv 2\,\bmod\,19

Conditions and CorollariesEdit

An additional condition states that if a \ is not divisible by p \ , the following equation holds

a^{p-1} \equiv 1\,\bmod\,p

Fermat's Little Theorem also has a corollary, which states that if a \ is not divisible by p \ and n \equiv m\,\bmod\,\left( p - 1 \right) then

a^n \equiv a^m\,\bmod\,p

Euler's GeneralizationEdit

If \gcd \left( a, m \right) = 1 \ , then a^{\phi \left( m \right)} \equiv 1\,\bmod\,m

Chinese Remainder TheoremEdit

If one wants to solve a system of congruences with different moduli, it is possible to do so as follows:

x \equiv a_1\,\bmod\,m_1
x \equiv a_2\,\bmod\,m_2
\cdots
x \equiv a_k\,\bmod\,m_k

A simultaneous solution x \ exists if and only if \gcd \left( m_i, m_j \right) = 1 with \left( i \ne j \right) \ , and any two solutions are congruent to one another modulo M = m_1m_2 \ldots m_k \ .

The steps for finding the simultaneous solution using the Chinese Remainder theorem are as follows:

1. Compute M \
2. Compute M_i = M / m_i \ for each of the different i \ 's
3. Find the inverse N \ of M_i\,\bmod\,m_i for each i \ using the Extended Euclidean algorithm
4. Multiply out a_iM_iN_i \ for each i \
5. Sum all a_iM_iN_i \
6. Compute \sum_{i=1}^k a_iM_iN_i\,\bmod\,M to obtain the least nonnegative residue

ExampleEdit

Given:

x \equiv 1\,\bmod\,11x \equiv 2\,\bmod\,7x \equiv 3\,\bmod\,5x \equiv 4\,\bmod\,9M = 3465 \ M_{11} = 315 \ M_7 = 495 \ M_5 = 693 \ M_9 = 385 \ 

Using the Extended Euclidean algorithm:

315N \equiv 1\,\bmod\,11\,\,\,N = -3315N \equiv 1\,\bmod\,7\,\,\,N = 3315N \equiv 1\,\bmod\,5\,\,\,N = 2315N \equiv 1\,\bmod\,9\,\,\,N = 4\sum_{i = 1}^4  = \begin{cases} 1 \cdot 315 \cdot \left( -3 \right) = -945 \\
                                    2 \cdot 495 \cdot 3 = 2970 \\
                                    3 \cdot 639 \cdot 2 = 4158 \\
                                    4 \cdot 385 \cdot 4 = 6160
                      \end{cases} \sum = 12343x = 12343\,\bmod\,3465 = 1948

Quadratic ResiduesEdit

If p \ is prime and  > 2 \ , examining the nonzero elements of \mathbb Z_p = \{ 1, 2, \ldots , p - 1 \}, it is sometimes important to know which of these are squares. If for some a \in \mathbb Z_p^*, there exists a square such that b^2 = a \ . Then all squares for \mathbb Z_p^* can be calculated by b^2\,\bmod\,p where b = 1, 2, \ldots , \left( p - 1 \right) / 2 \ . a \in \mathbb Z_n^* is a quadratic residue modulo n \ if there exists an x \in \mathbb Z_n^* such that a \equiv x^2\,\bmod\,n. If no such x \ exists, then a \ is a quadratic non-residue modulo n \ . a \ is a quadratic residue modulo a prime p \ if and only if a^{\tfrac {p - 1}{2}}\,\mod\,p = 1.

ExampleEdit

For the finite field \mathbb Z_{19}, to find the squares \mathbb Z_{19} = \{ 1, 2, \ldots , 9 \},, proceed as follows:

\begin{matrix} 1^2 = 1 & 2^2 = 4 & 3^2 = 9 \\
                      4^2 = 16 & 5^2 = 6 & 6^2 = 2 \\
                      7^2 = 11 & 8^2 = 7 & 9^2 = 5
       \end{matrix}

The values above are quadratic residues. The remaining (in this example) 9 values are known as quadratic nonresidues. the complete listing is given below.

p = 19 \ 
Quadratic residues: 1, 2, 4, 5, 6, 7, 9, 11, 16 \ 
Quadratic nonresidues: 3, 8, 10, 12, 13, 14, 15, 17, 18 \ 

Legendre SymbolEdit

The Legendre symbol denotes whether or not a \ is a quadratic residue modulo the prime p \ and is only defined for primes p \ and integers a \ . The Legendre of a \ with respect to p \ is represented by the symbol L \left( \tfrac{a}{p} \right). Note that this does not mean a \ divided by p \ . L \left( \tfrac{a}{p} \right) has one of three values: 0, 1, -1 \ .

L \left( \tfrac{a}{p} \right) \begin{cases}
     0, & \mbox{if }p\mbox{ divides }a\mbox{ evenly} \\
     1, & \mbox{if }a\mbox{ is a quadratic residue modulo }p \\
     -1, & \mbox{if }a\mbox{ is a quadratic nonresidue modulo }p
\end{cases}

Jacobi SymbolEdit

The Jacobi symbol applies to all odd numbers n > 3 \ where n = p_1^{e_1}p_2^{e_2} \ldots p_m^{e_m} \ , then:

J \left( \tfrac{a}{n} \right) = L \left( \tfrac{a}{p_1} \right)^{e_1} L \left( \tfrac{a}{p_2} \right)^{e_2} \ldots L \left( \tfrac{a}{p_m} \right)^{e_m}

If n \ is prime, then the Jacobi symbol equals the Legendre symbol (which is the basis for the Solovay-Strassen primality test).

Primality TestingEdit

DescriptionEdit

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.

PseudoprimesEdit

Remember that if p \ is prime and gcd \left( b, m \right) = 1, Fermat's Little Theorem states:

a^{p-1} \equiv 1\,\bmod\,p

However, there are cases where p \ can meet the above conditions and be nonprime. These classes of numbers are known as pseudoprimes.

m \ is a pseudoprime to the base a \ , with gcd \left( a, m \right) = 1 if and only if the least positive power of a \ that is congruent to 1 \bmod\,p evenly divides p - 1 \ .

If Fermat's Little Theorem holds for any p \ that is an odd composite integer, then p \ is referred to as a pseudoprime. This forms the basis of primality testing. By testing different a \ '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 a \ which is congruent to 1\,\bmod\,n and divides n - 1 \ which is the order of a \ in \mathbb Z_n^*, then n \ is a pseudoprime.
II. If n \ is a pseudoprime to base a_1 \ and a_2 \ , then n \ is also a pseudoprime to a_1a_2\,\bmod\,n and a_1a_2^{-1}\,\bmod\,n.
III. If n \ fails a^{p-1} \equiv 1\,\bmod\,p, for any single base a \in \mathbb Z_p^*, then n \ fails a^{p-1} \equiv 1\,\bmod\,p for at least half the bases a \in \mathbb Z_p^*.

An odd composite integer for which a^{p-1} \equiv 1\,\bmod\,p holds for every a \in \mathbb Z_p^* is known as a Carmichael Number.

Miller-Rabin Primality TestEdit

DescriptionEdit

ExamplesEdit

FactoringEdit

The Rho MethodEdit

DescriptionEdit

AlgorithmEdit

ExampleEdit

Fermat FactorizationEdit

ExampleEdit

Random Number GeneratorsEdit

RNGs vs. PRNGsEdit

ANSI X9.17 PRNGEdit

Blum-Blum-Shub PRNGEdit

RSA PRNGEdit

Entropy ExtractorsEdit

Whitening FunctionsEdit

Large Integer MultiplicationEdit

Karatsuba MultiplicationEdit

ExampleEdit

Furers MultiplicationEdit

Elliptic CurvesEdit

DescriptionEdit

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,

DefinitionEdit

PropertiesEdit

SummaryEdit

Last modified on 5 April 2014, at 01:09