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

 

where  

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
  implies
  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  
2.      
3.      
4. Output  

Example

edit
Given  

 
 
  

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

  implies  
  implies  

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:

 
 

Therefore: 

 

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

 

Where

 

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

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

 
 
 
 

 

 
 
 
 

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

RSA 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