Cryptography/Mathematical Background

See Talk page for other suggestions.

Introduction edit

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.

Pythagorean Triplets
3 4 5
5 12 13
7 24 25
8 15 17

Prime Numbers edit

Description edit

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

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

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

Fermat numbers take the following form


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

Numerical Examples edit


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

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

The first four Mersenne primes are as follows


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


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

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

Introduction edit

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


When  , stop with  .

Numerical Examples edit

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

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

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   0) do:
  4.      a0 = r1
  5.      r1 = r
  6.      r = a0 mod r1
  7.   Output r and halt

The Extended Euclidean Algorithm edit

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 = 216 + 1, p = 3,217, q = 1,279. Thus, 62,537d + 51,456w = 1.

Methods edit

The Iterative Method edit

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

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

Using the previous RSA vales of   and  

Euclidean Expansion Collect Terms Substitute Retrograde Substitution Solve For dx
4,110,048 w0 + 65,537d0 = 1
(62   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   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   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   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   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   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   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   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   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   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   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 Function edit

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



Finite Fields and Generators edit

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

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

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

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

Description edit

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

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


Properties of Congruences edit

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

  if and only if  
If   and   then  
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

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

  is equivalent to
  is the remainder of   divided by  

The Algebra of Congruences edit

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

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

Input: Integers   and   from   with  
Output: Integer   such that  

1. Let  
4. Output  

Example edit



Note that   is the least nonnegative residue modulo  

Exponentiation edit

Assume you begin with  . Upon multiplying this congruence by itself the result is  . Generalizing this result and assuming   is a positive integer


Example edit


This simplifies to


Repeated Squaring Method edit

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

To find  :


Adding exponents:


Multiplying least nonnegative residues associated with these exponents:




Inverse of a Congruence edit

Description edit

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




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


Definition edit

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

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  .


It is easily verified that  

Fermat's Little Theorem edit

Definition edit

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


Example edit

When   and  

  implies that  

Conditions and Corollaries edit

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

If  , then  

Chinese Remainder Theorem edit

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





Using the Extended Euclidean algorithm:





Quadratic Residues edit

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

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

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

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

Description edit

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

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

Description edit

Examples edit

Factoring edit

The Rho Method edit

Description edit

Algorithm edit

Example edit

Fermat Factorization edit

Example edit

Random Number Generators edit

RNGs vs. PRNGs edit

ANSI X9.17 PRNG edit

Blum-Blum-Shub PRNG edit


Entropy Extractors edit

Whitening Functions edit

Large Integer Multiplication edit

Karatsuba Multiplication edit

Example edit

Furers Multiplication edit

Elliptic Curves edit

Description edit

Definition edit

Properties edit

Summary edit