Creating a good cryptographic algorithm that will stand against all that the best cryptanalysis can throw at it, is hard. Very hard. So, this is why most people design algorithms by first designing the basic system, then refining it, and finally letting it lose for all to see.

Why, do this? Surely, if you let everyone see your code that turns a plain bit of text into garbled rubbish, then they will be able to reverse it! This assumption is unfortunately wrong. Now the algorithms that have been/ are being made are so strong, that just reversing the algorithm is not effective when trying to crack it. And when you let people look at your algorithm, they may spot a security flaw that nobody else could see.
Basic Design Principles#Kerckhoffs’s principle.

AES, one of the newest and strongest (2010) algorithms in the world, was created by a team of two people, and was put forward into a sort of competition, where only the best algorithm would be examined and put forward to be selected for the title of the Advanced Encryption Standard. There were about 35 entrants, and although all of them appeared strong at first, it soon became clear that some of these apparently strong algorithms were in fact, very weak!

AES is a good example of open algorithms.

See Talk page for other suggestions.

## Introduction

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

${displaystyle a^{2}+b^{2}=c^{2} }$

where

${displaystyle 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

${displaystyle a }$

${displaystyle b }$

${displaystyle c }$

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

## Prime Numbers

### Description

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

${displaystyle a|b}$

means “

${displaystyle b}$

divides into

${displaystyle a}$

“), a prime number strictly adheres to the following mathematical definition

${displaystyle p }$

|

${displaystyle b }$

Where

${displaystyle b=1 }$

or

${displaystyle 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

${displaystyle c }$

|

${displaystyle b }$

where ultimately

${displaystyle b=p_{0}^{e_{0}}p_{1}^{e_{1}}cdot cdot cdot p_{n}^{e_{n}} }$

in which

${displaystyle p_{n} }$

is a unique prime number and

${displaystyle e_{n} }$

is the exponent.

#### Numerical Examples

```543,312 = 24${displaystyle cdot }$ 32${displaystyle cdot }$ 50${displaystyle cdot }$ 73${displaystyle cdot }$ 111
553,696 = 25${displaystyle cdot }$ 30${displaystyle cdot }$ 50${displaystyle cdot }$ 70${displaystyle cdot }$ 113${displaystyle cdot }$ 131```

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

In order to deterministically verify whether an integer

${displaystyle a }$

is prime or composite, only the primes

${displaystyle pleq {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 Primes

Fermat numbers take the following form

${displaystyle F_{n}=2^{2^{n}}+1 }$

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

#### Numerical Examples

```${displaystyle F_{0}=2^{2^{0}}+1=3 }$
${displaystyle F_{1}=2^{2^{1}}+1=5 }$
${displaystyle F_{2}=2^{2^{2}}+1=17 }$
${displaystyle F_{3}=2^{2^{3}}+1=257 }$
${displaystyle F_{4}=2^{2^{4}}+1=65,537 }$
${displaystyle F_{5}=2^{2^{5}}+1=4,294,967,297 }$
```

The only Fermat numbers known to be prime are

${displaystyle F_{0}-F_{4} }$

. Moreover, the primality of all Fermat numbers was disproven by Euler, who showed that

${displaystyle F_{5}=641cdot 6,700,417}$

.

### Mersenne Primes

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

${displaystyle M_{p}=2^{p}-1 }$

where

${displaystyle p }$

is a prime number. The [8] Wolfram Alpha engine reports Mersenne Primes, an example input request being “4th Mersenne Prime”.

#### Numerical Examples

The first four Mersenne primes are as follows

```${displaystyle M_{2}=2^{2}-1=3 }$
${displaystyle M_{3}=2^{3}-1=7 }$
${displaystyle M_{5}=2^{5}-1=31 }$
${displaystyle 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)

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

${displaystyle gcd(a,b)=1 }$

where

${displaystyle gcd }$

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

If

${displaystyle ab }$

|

${displaystyle c }$

and

${displaystyle gcd(b,c)=1 }$

, then

${displaystyle a }$

|

${displaystyle c }$

If

${displaystyle ab=c^{2} }$

with

${displaystyle gcd(a,b)=1 }$

, then both

${displaystyle a }$

and

${displaystyle b }$

are squares, i.e. –

${displaystyle a=a_{0}^{2} }$

,

${displaystyle b=b_{0}^{2} }$

### The Prime Number Theorem

The Prime Number Theorem estimates the probability that any integer, chosen randomly will be prime. The estimate is given below, with

${displaystyle pi (x) }$

defined as the number of primes

${displaystyle leq x }$

${displaystyle pi (x)approx {frac {x}{ln x}} }$

${displaystyle pi (x) }$

is asymptotic to

${displaystyle {frac {x}{ln x}} }$

, that is to say

${displaystyle quad lim _{xto infty }{frac {pi (x)}{ln x}}=1 }$

. What this means is that generally, a randomly chosen number is prime with the approximate probability

${displaystyle {tfrac {1}{x}} }$

.

## The Euclidean Algorithm

### Introduction

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

${displaystyle gcd(a,b)=1 }$

.

In order to find

${displaystyle gcd(a,b) }$

where

${displaystyle a>b }$

${displaystyle a }$

by

${displaystyle b }$

, writing the quotient

${displaystyle q_{1} }$

, and the remainder

${displaystyle r_{1} }$

. Note this can be written in equation form as

${displaystyle a=q_{1}b+r_{1} }$

. Next perform the same operation using

${displaystyle b }$

in

${displaystyle a }$

‘s place:

${displaystyle b=q_{2}r_{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 Description

```${displaystyle a=q_{1}b+r_{1} }$
${displaystyle b=q_{2}r_{1}+r_{2} }$
${displaystyle r_{1}=q_{3}r_{2}+r_{3} }$
${displaystyle r_{2}=q_{4}r_{3}+r_{4} }$
${displaystyle cdot }$
${displaystyle cdot }$
${displaystyle cdot }$
${displaystyle r_{n-2}=q_{n}r_{n-1}+r_{n} }$
```

When

${displaystyle r_{n}=0 }$

, stop with

${displaystyle gcd(a,b)=r_{n-1} }$

.

### Numerical Examples

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

```17,043 = 1 ${displaystyle cdot }$ 12,660 + 4383
12,660 = 2 ${displaystyle cdot }$ 4,383 + 3894
4,383 = 1 ${displaystyle cdot }$ 3,894 + 489
3,894 = 7 ${displaystyle cdot }$ 489 + 471
489 = 1 ${displaystyle cdot }$ 471 + 18
471 = 26 ${displaystyle cdot }$ 18 + 3
18 = 6 ${displaystyle cdot }$ 3 + 0
```

gcd (17,043,12,660) = 3

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

```2,008 = 1 ${displaystyle cdot }$ 1,963 + 45
1,963 = 43 ${displaystyle cdot }$ 45 + 28
45 = 1 ${displaystyle cdot }$ 28 + 17
28 = 1 ${displaystyle cdot }$ 17 + 11
17 = 1 ${displaystyle cdot }$ 11 + 6
11 = 1 ${displaystyle cdot }$ 6 + 5
6 = 1 ${displaystyle cdot }$ 5 + 1
5 = 5 ${displaystyle cdot }$ 1 + 0
```

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

### Algorithmic Representation

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

## The Extended Euclidean Algorithm

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

${displaystyle au+bv=gcd(a,b) }$

where

${displaystyle a }$

,

${displaystyle b }$

,

${displaystyle u }$

, and

${displaystyle 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

${displaystyle ed+w(p-1)(q-1)=1 }$

where

${displaystyle 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.

### Methods

#### The Iterative Method

This method computes expressions of the form

${displaystyle r_{i}=ax_{i}+by_{i}}$

for the remainder in each step

${displaystyle i}$

of the Euclidean algorithm. Each modulus can be written in terms of the previous two remainders and their whole quotient as follows:

${displaystyle r_{i}=r_{i-2}-leftlfloor {frac {r_{i-2}}{r_{i-1}}}rightrfloor cdot r_{i-1}}$

By substitution, this gives:

${displaystyle r_{i}=(ax_{i-2}+by_{i-2})-leftlfloor {frac {r_{i-2}}{r_{i-1}}}rightrfloor cdot (ax_{i-1}+by_{i-1})}$

${displaystyle r_{i}=a(x_{i-2}-leftlfloor {frac {r_{i-2}}{r_{i-1}}}rightrfloor cdot x_{i-1})+b(y_{i-2}-leftlfloor {frac {r_{i-2}}{r_{i-1}}}rightrfloor cdot y_{i-1})}$

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

${displaystyle r_{1}=a=a(1)+b(0) }$

${displaystyle 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.

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

${displaystyle cdot }$

62

46,754 = (1a + 0b) – (0a + 1b)

${displaystyle cdot }$

62

46,754 = 1a – 62b
4 1 18,783 = 65,537 – 46,754

${displaystyle cdot }$

1

18,783 = (0a + 1b) – (1a – 62b)

${displaystyle cdot }$

1

18,783 = -1a + 63b
5 2 9,188 = 46,754 – 18,783

${displaystyle cdot }$

2

9,188 = (1a – 62b) – (-1a + 62b)

${displaystyle cdot }$

2

9,188 = 3a – 188b
6 2 407 = 18,783 – 9,188

${displaystyle cdot }$

2

407 = (-1a + 63b) – (3a – 188b)

${displaystyle cdot }$

2

407 = -7a + 439b
7 22 234 = 9,188 – 407

${displaystyle cdot }$

22

234 = (3a – 188b) – (-7a + 439b)

${displaystyle cdot }$

22

234 = 157a – 9,846b
8 1 173 = 407 – 234

${displaystyle cdot }$

1

173 = (-7a + 439b) – (157a – 9,846b)

${displaystyle cdot }$

1

173 = -164a + 10,285b
9 1 61 = 234 – 173

${displaystyle cdot }$

1

61 = (157a – 9,846b) – (-164a + 10,285b)

${displaystyle cdot }$

1

61 = 321a + 20,131b
10 2 51 = 173 – 61

${displaystyle cdot }$

2

51 = (-164a + 10,285b) – (321a +20,131b)

${displaystyle cdot }$

2

51 = -806a + 50,547b
11 1 10 = 61 – 51

${displaystyle cdot }$

1

61 = (321a +20,131b) – (-806a + 50,547b)

${displaystyle cdot }$

1

10 = 1,127a – 70,678b
12 5 1 = 51 -10

${displaystyle cdot }$

5

1 = (-806a + 50,547b) – (1,127a – 70,678b)

${displaystyle cdot }$

5

1 = -6,441a + 403,937b
13 10 0 End of algorithm

Putting the equation in its original form

${displaystyle ed+w(p-1)(q-1)=1 }$

yields

${displaystyle (65,537)(403,937)+(-6,441)(3,217-1)(1,279-1)=1 }$

, it is shown that

${displaystyle d=403,937 }$

and

${displaystyle 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 Method

This is a direct method for solving Diophantine equations of the form

${displaystyle 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.

##### Example

Using the previous RSA vales of

${displaystyle (p-1)(p-1)=4,110,048 }$

and

${displaystyle e=2^{16}+1=65,537 }$

Euclidean Expansion Collect Terms Substitute Retrograde Substitution Solve For dx
4,110,048 w0 + 65,537d0 = 1
(62

${displaystyle 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

${displaystyle 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

${displaystyle 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

${displaystyle 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

${displaystyle 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

${displaystyle 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

${displaystyle 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

${displaystyle 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

${displaystyle 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

${displaystyle 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

${displaystyle 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 Function

Significant in cryptography, the totient function (sometimes known as the phi function) is defined as the number of nonnegative integers

${displaystyle a }$

less than

${displaystyle n }$

that are coprime to

${displaystyle n }$

. Mathematically, this is represented as

${displaystyle phi (n)=left|{bigg {}0leq aleq n|gcd(a,n)=1{bigg }}right|}$

Which immediately suggests that for any prime

${displaystyle p }$

${displaystyle phi (p)=p-1 }$

The totient function for any exponentiated prime is calculated as follows

${displaystyle phi (p^{alpha }) }$

${displaystyle =p^{alpha }-p^{alpha -1} }$

${displaystyle =p^{alpha }left(1-{tfrac {1}{p}}right) }$

The Euler totient function is also multiplicative

${displaystyle phi (ab)=phi (a)phi (b) }$

where

${displaystyle gcd(a,b)=1 }$

## Finite Fields and Generators

A field is simply a set

${displaystyle mathbb {F} }$

which contains numerical elements that are subject to the familiar addition and multiplication operations. Several different types of fields exist; for example,

${displaystyle mathbb {R} }$

, the field of real numbers, and

${displaystyle mathbb {Q} }$

, the field of rational numbers, or

${displaystyle mathbb {C} }$

, the field of complex numbers. A generic field is usually denoted

${displaystyle mathbb {F} }$

.

### Finite Fields

Cryptography utilizes primarily finite fields, nearly exclusively composed of integers. The most notable exception to this are the Gaussian numbers of the form

${displaystyle a+bi }$

which are complex numbers with integer real and imaginary parts. Finite fields are defined as follows

${displaystyle left(mathbb {Z} /nmathbb {Z} right)=mathbb {Z} _{n} }$

The set of integers modulo

${displaystyle n }$

${displaystyle left(mathbb {Z} /pmathbb {Z} right)=mathbb {Z} _{p} }$

The set of integers modulo a prime

${displaystyle 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,

${displaystyle mathbb {Z} }$

.

A finite field

${displaystyle mathbb {F} _{n} }$

contains exactly

${displaystyle n }$

elements, of which there are

${displaystyle n-1 }$

nonzero elements. An extension of

${displaystyle mathbb {Z} _{n} }$

is the multiplicative group of

${displaystyle mathbb {Z} _{n} }$

, written

${displaystyle left(mathbb {Z} /nmathbb {Z} right)^{*}=mathbb {Z} _{n}^{*} }$

, and consisting of the following elements

${displaystyle ain mathbb {Z} _{n}^{*} }$

such that

${displaystyle gcd(a,n)=1 }$

in other words,

${displaystyle mathbb {Z} _{n}^{*} }$

contains the elements coprime to

${displaystyle n }$

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

```${displaystyle centerdot }$ The product of two nonzero elements is nonzero ${displaystyle left(ab=c|cneq 0right) }$
${displaystyle centerdot }$ The associative law holds ${displaystyle left(left(abright)c=aleft(bcright)right) }$
${displaystyle centerdot }$ The commutative law holds ${displaystyle left(ab=baright) }$
${displaystyle centerdot }$ There is an identity element ${displaystyle left(Icdot a=aright) }$
${displaystyle centerdot }$ Any nonzero element has an inverse ${displaystyle left(acdot a^{-1}=1right) }$
```

A subscript following the symbol for the field represents the set of integers modulo

${displaystyle n }$

, and these integers run from

${displaystyle 0 }$

to

${displaystyle n-1 }$

as represented by the example below

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

The multiplicative order of

${displaystyle mathbb {Z} _{n}}$

is represented

${displaystyle mathbb {Z} _{n}^{*}}$

and consists of all elements

${displaystyle ain mathbb {Z} _{n}}$

such that

${displaystyle gcd(a,n)=1 }$

. An example for

${displaystyle mathbb {Z} _{12}}$

is given below

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

If

${displaystyle p }$

is prime, the set

${displaystyle mathbb {Z} _{p}^{*}}$

consists of all integers

${displaystyle a }$

such that

${displaystyle 1leq aleq p }$

. For example

Composite n Prime p

${displaystyle mathbb {Z} _{9}={0,1,2,3,4,5,6,7,8}}$

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

${displaystyle mathbb {Z} _{9}^{*}={1,2,4,5,7,8}}$

${displaystyle mathbb {Z} _{11}^{*}={1,2,3,4,5,6,7,8,9,10}}$

### Generators

Every finite field has a generator. A generator

${displaystyle g }$

is capable of generating all of the elements in the set

${displaystyle mathbb {Z} _{n}}$

by exponentiating the generator

${displaystyle g,{bmod {,}}n }$

. Assuming

${displaystyle g }$

is a generator of

${displaystyle mathbb {Z} _{n}^{*}}$

, then

${displaystyle mathbb {Z} _{n}^{*}}$

contains the elements

${displaystyle g^{i},{bmod {,}}n }$

for the range

${displaystyle 0leq ileq phi (n)-1}$

. If

${displaystyle mathbb {Z} _{n}^{*}}$

has a generator, then

${displaystyle mathbb {Z} _{n}}$

is said to be cyclic.

The total number of generators is given by

${displaystyle phi left(phi left(nright)right)}$

#### Examples

```For ${displaystyle n=p=13 }$ (Prime)

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

Total number of generators ${displaystyle phi left(phi left(13right)right)=phi left(12right)=4}$ generators

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

Since ${displaystyle 2 }$ is a generator, check if ${displaystyle gcd(i,p-1)=1 }$
${displaystyle 2^{2}=4 }$, and ${displaystyle i=2 }$, ${displaystyle gcd left(2,12right)=2neq 1 }$, therefore, ${displaystyle 4 }$ is not a generator
${displaystyle 2^{3}=8 }$, and ${displaystyle i=3 }$, ${displaystyle gcd left(3,12right)=3neq 1 }$, therefore, ${displaystyle 4 }$ is not a generator

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

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

${displaystyle mathbb {Z} _{9}={0,1,2,3,4,5,6,7,8,9} }$
${displaystyle mathbb {Z} _{9}^{*}={1,3,7,9} }$

Total number of generators ${displaystyle phi left(phi left(10right)right)=phi left(4right)=2 }$ generators

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

There are a total of ${displaystyle 2 }$ generators ${displaystyle left(3,7,right) }$ as predicted by the formula ${displaystyle phi left(phi left(nright)right).}$
```

## Congruences

### Description

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

If

${displaystyle a }$

and

${displaystyle b }$

are two integers, and their difference is evenly divisible by

${displaystyle m }$

, this can be written with the notation

${displaystyle left(a-bright)|m }$

This is expressed by the notation for a congruence

${displaystyle aequiv b,{bmod {,}}m}$

where the divisor

${displaystyle m }$

is called the modulus of congruence.

${displaystyle aequiv b,{bmod {,}}m}$

can equivalently be written as

${displaystyle a-b=mk }$

where

${displaystyle k }$

is an integer.

Note in the examples that for all cases in which

${displaystyle aequiv 0,{bmod {,}}m}$

, it is shown that

${displaystyle a|m }$

. with this in mind, note that

${displaystyle aequiv 0,{bmod {,}}2}$

Represents that

${displaystyle a }$

is an even number.

${displaystyle aequiv 1,{bmod {,}}2}$

Represents that

${displaystyle a }$

is an odd number.

### Properties of Congruences

All congruences (with fixed

${displaystyle m }$

) have the following properties in common

${displaystyle aequiv a,{bmod {,}}m}$

${displaystyle aequiv b,{bmod {,}}m}$

if and only if

${displaystyle bequiv a,{bmod {,}}m}$

If

${displaystyle aequiv b,{bmod {,}}m}$

and

${displaystyle bequiv c,{bmod {,}}m}$

then

${displaystyle aequiv c,{bmod {,}}m}$

${displaystyle aequiv b,{bmod {,}}1}$

implies that

${displaystyle a=b }$

Given

${displaystyle aequiv a,{bmod {,}}m}$

there exists a unique

${displaystyle b }$

such that

${displaystyle 0leq bleq m-1 }$

These properties represent an equivalence class, meaning that any integer is congruent modulo

${displaystyle m }$

to one specific integer in the finite field

${displaystyle mathbb {Z} _{m}}$

.

### Congruences as Remainders

If the modulus of an integer

${displaystyle m>2 }$

${displaystyle a }$

${displaystyle a=mk+r,left(rin mathbb {Z} _{m}right)}$

which can be understood to mean

${displaystyle r }$

is the remainder of

${displaystyle a }$

divided by

${displaystyle m }$

, or as a congruence

${displaystyle aequiv r,{bmod {,}}m}$

Two numbers that are incongruent modulo

${displaystyle m }$

must have different remainders. Therefore, it can be seen that any congruence

${displaystyle aequiv b,{bmod {,}}m}$

holds if and only if

${displaystyle a }$

and

${displaystyle b }$

are integers which have the same remainder when divided by

${displaystyle m }$

.

#### Example

```${displaystyle 10equiv 3,{bmod {,}}7}$ is equivalent to
${displaystyle 10=left(7cdot 1right)+3 }$ implies
${displaystyle 3 }$ is the remainder of ${displaystyle 10 }$ divided by ${displaystyle 7 }$
```

### The Algebra of Congruences

Suppose for this section we have two congruences,

${displaystyle aequiv b,{bmod {,}}m}$

and

${displaystyle cequiv d,{bmod {,}}m}$

. These congruences can be added or subtracted in the following manner

${displaystyle a+cequiv b+d,{bmod {,}}m}$

${displaystyle a-cequiv b-d,{bmod {,}}m}$

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

${displaystyle acequiv bd,{bmod {,}}m}$

or the special case where

${displaystyle c=d }$

${displaystyle acequiv 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

${displaystyle c }$

and

${displaystyle m }$

are coprime. Mathematically, this is represented as

${displaystyle acequiv bc,{bmod {,}}m}$

implies that

${displaystyle aequiv b,{bmod {,}}m}$

if and only if

${displaystyle gcd left(c,mright)=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 m

Often, it is necessary to perform an operation on a congruence

${displaystyle aequiv b,{bmod {,}}m}$

where

${displaystyle b>m }$

${displaystyle d }$

such that

${displaystyle 0leq dleq m-1 }$

with the resultant

${displaystyle d }$

being the least nonnegative residue modulo m of the congruence. Reducing a congruence modulo

${displaystyle m }$

is based on the properties of congruences and is often required during exponentiation of a congruence.

#### Algorithm

```Input: Integers ${displaystyle b }$ and ${displaystyle m }$ from ${displaystyle aequiv b,{bmod {,}}m}$ with ${displaystyle b>m }$
Output: Integer ${displaystyle d }$ such that ${displaystyle 0leq dleq m-1 }$

1. Let ${displaystyle q=leftlfloor {tfrac {b}{m}}rightrfloor }$
2.     ${displaystyle c=qm }$
3.     ${displaystyle d=b-c }$
4. Output ${displaystyle d }$
```

#### Example

```Given ${displaystyle 289equiv 49,{bmod {,}}5}$

${displaystyle 9=leftlfloor {tfrac {49}{5}}rightrfloor }$
${displaystyle 45=9cdot 5 }$
${displaystyle 4=49-45 }$

∴ ${displaystyle 289equiv 49equiv 4,{bmod {,}}5}$
```

Note that

${displaystyle 4 }$

is the least nonnegative residue modulo

${displaystyle 5 }$

### Exponentiation

Assume you begin with

${displaystyle aequiv b,{bmod {,}}m}$

. Upon multiplying this congruence by itself the result is

${displaystyle a^{2}equiv b^{2},{bmod {,}}m}$

. Generalizing this result and assuming

${displaystyle n }$

is a positive integer

${displaystyle a^{n}equiv b^{n},{bmod {,}}m}$

#### Example

```${displaystyle 9equiv 4,{bmod {,}}13}$
${displaystyle 81equiv 16,{bmod {,}}13}$
${displaystyle 729equiv 64,{bmod {,}}13}$

This simplifies to

${displaystyle 81equiv 16,{bmod {,}}13}$ implies ${displaystyle 16equiv 3,{bmod {,}}13}$
${displaystyle 729equiv 64,{bmod {,}}13}$ implies ${displaystyle 256equiv 9,{bmod {,}}13}$
```

### Repeated Squaring Method

Sometimes it is useful to know the least nonnegative residue modulo

${displaystyle m }$

of a number which has been exponentiated as

${displaystyle 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 ${displaystyle aequiv ,{bmod {,}}m}$
2. Square ${displaystyle a }$ and ${displaystyle b }$ so that ${displaystyle a^{2}equiv b^{2},{bmod {,}}m}$
3. Reduce ${displaystyle b }$ modulo ${displaystyle m }$ to obtain ${displaystyle a^{equiv }b_{1},{bmod {,}}m}$
4. Continue with steps 2 and 3 until ${displaystyle a^{2^{n}}equiv b_{n},{bmod {,}}m}$ is obtained.
Note that ${displaystyle n }$ is the integer where ${displaystyle 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 ${displaystyle b_{i} }$'s associated with the ${displaystyle a }$'s of the selected powers
7. Reduce the resulting ${displaystyle b,{bmod {,}}m}$ for the desired result
```

#### Example

```To find ${displaystyle 6^{149}{bmod {,}}11}$:

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

${displaystyle 128+16+4+1 }$

Multiplying least nonnegative residues associated with these exponents:

${displaystyle 4cdot 5cdot 9cdot 6=1080 }$
${displaystyle 1080,{bmod {,}}11=2}$

Therefore:

${displaystyle 6^{149}equiv 2,{bmod {,}}11}$
```

### Inverse of a Congruence

#### Description

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

${displaystyle Cequiv aP+b,{bmod {,}}N}$

Where

${displaystyle Pequiv a^{-1}C+b^{-1},{bmod {,}}N}$

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

${displaystyle d_{A}=e_{A}^{-1},{bmod {,}}phi left(n_{A}right)}$

#### Definition

For the elements

${displaystyle ain mathbb {Z} _{m}}$

where

${displaystyle gcd left(a,mright)=1}$

, there exists

${displaystyle bin mathbb {Z} _{m}}$

such that

${displaystyle abequiv 1,{bmod {,}}m}$

. Thus,

${displaystyle b }$

is said to be the inverse of

${displaystyle a }$

, denoted

${displaystyle a^{-n},{bmod {,}}m}$

where

${displaystyle n }$

is the

${displaystyle n^{th} }$

power of the integer

${displaystyle b }$

for which

${displaystyle abequiv 1,{bmod {,}}m}$

.

##### Example
```Find ${displaystyle 633^{-1},{bmod {,}}2801}$

This is equivalent to saying ${displaystyle 633bequiv 1,{bmod {,}}2801}$

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

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

It is easily verified that ${displaystyle left(633right)left(177right)equiv 1,{bmod {,}}2801}$
```

### Fermat’s Little Theorem

#### Definition

Where

${displaystyle p }$

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

${displaystyle a^{p}equiv a,{bmod {,}}p}$

#### Example

When

${displaystyle a=2 }$

and

${displaystyle p=19 }$

${displaystyle 2^{2}equiv 23,{bmod {,}}19}$

${displaystyle 2^{4}equiv 529equiv 16,{bmod {,}}19}$

${displaystyle 2^{8}equiv 256equiv 9,{bmod {,}}19}$

${displaystyle 2^{16}equiv 81equiv 5,{bmod {,}}19}$

${displaystyle 16+2+1=19 }$

implies that

${displaystyle 5cdot 23cdot 2=230equiv 2,{bmod {,}}19}$

#### Conditions and Corollaries

An additional condition states that if

${displaystyle a }$

is not divisible by

${displaystyle p }$

, the following equation holds

${displaystyle a^{p-1}equiv 1,{bmod {,}}p}$

Fermat’s Little Theorem also has a corollary, which states that if

${displaystyle a }$

is not divisible by

${displaystyle p }$

and

${displaystyle nequiv m,{bmod {,}}left(p-1right)}$

then

${displaystyle a^{n}equiv a^{m},{bmod {,}}p}$

#### Euler’s Generalization

If

${displaystyle gcd left(a,mright)=1 }$

, then

${displaystyle a^{phi left(mright)}equiv 1,{bmod {,}}m}$

### Chinese Remainder Theorem

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

${displaystyle xequiv a_{1},{bmod {,}}m_{1}}$

${displaystyle xequiv a_{2},{bmod {,}}m_{2}}$

${displaystyle cdots }$

${displaystyle xequiv a_{k},{bmod {,}}m_{k}}$

A simultaneous solution

${displaystyle x }$

exists if and only if

${displaystyle gcd left(m_{i},m_{j}right)=1}$

with

${displaystyle left(ineq jright) }$

, and any two solutions are congruent to one another modulo

${displaystyle M=m_{1}m_{2}ldots m_{k} }$

.

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

1. Compute

${displaystyle M }$

2. Compute

${displaystyle M_{i}=M/m_{i} }$

for each of the different

${displaystyle i }$

‘s

3. Find the inverse

${displaystyle N }$

of

${displaystyle M_{i},{bmod {,}}m_{i}}$

for each

${displaystyle i }$

using the Extended Euclidean algorithm

4. Multiply out

${displaystyle a_{i}M_{i}N_{i} }$

for each

${displaystyle i }$

5. Sum all

${displaystyle a_{i}M_{i}N_{i} }$

6. Compute

${displaystyle sum _{i=1}^{k}a_{i}M_{i}N_{i},{bmod {,}}M}$

to obtain the least nonnegative residue

#### Example

```Given:

${displaystyle xequiv 1,{bmod {,}}11}$
${displaystyle xequiv 2,{bmod {,}}7}$
${displaystyle xequiv 3,{bmod {,}}5}$
${displaystyle xequiv 4,{bmod {,}}9}$

${displaystyle M=3465 }$

${displaystyle M_{11}=315 }$
${displaystyle M_{7}=495 }$
${displaystyle M_{5}=693 }$
${displaystyle M_{9}=385 }$

Using the Extended Euclidean algorithm:

${displaystyle 315Nequiv 1,{bmod {,}}11,,,N=-3}$
${displaystyle 315Nequiv 1,{bmod {,}}7,,,N=3}$
${displaystyle 315Nequiv 1,{bmod {,}}5,,,N=2}$
${displaystyle 315Nequiv 1,{bmod {,}}9,,,N=4}$

${displaystyle sum _{i=1}^{4}={begin{cases}1cdot 315cdot left(-3right)=-945\2cdot 495cdot 3=2970\3cdot 639cdot 2=4158\4cdot 385cdot 4=6160end{cases}}}$

${displaystyle sum =12343}$

${displaystyle x=12343,{bmod {,}}3465=1948}$
```

If

${displaystyle p }$

is prime and

${displaystyle >2 }$

${displaystyle mathbb {Z} _{p}={1,2,ldots ,p-1}}$

, it is sometimes important to know which of these are squares. If for some

${displaystyle ain mathbb {Z} _{p}^{*}}$

, there exists a square such that

${displaystyle b^{2}=a }$

. Then all squares for

${displaystyle mathbb {Z} _{p}^{*}}$

can be calculated by

${displaystyle b^{2},{bmod {,}}p}$

where

${displaystyle b=1,2,ldots ,left(p-1right)/2 }$

.

${displaystyle ain mathbb {Z} _{n}^{*}}$

${displaystyle n }$

if there exists an

${displaystyle xin mathbb {Z} _{n}^{*}}$

such that

${displaystyle aequiv x^{2},{bmod {,}}n}$

. If no such

${displaystyle x }$

exists, then

${displaystyle a }$

${displaystyle n }$

.

${displaystyle a }$

is a quadratic residue modulo a prime

${displaystyle p }$

if and only if

${displaystyle a^{tfrac {p-1}{2}},mod ,p=1}$

.

### Example

```For the finite field ${displaystyle mathbb {Z} _{19}}$, to find the squares ${displaystyle mathbb {Z} _{19}={1,2,ldots ,9},}$, proceed as follows:

${displaystyle {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}=5end{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.

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

### Legendre Symbol

The Legendre symbol denotes whether or not

${displaystyle a }$

is a quadratic residue modulo the prime

${displaystyle p }$

and is only defined for primes

${displaystyle p }$

and integers

${displaystyle a }$

. The Legendre of

${displaystyle a }$

with respect to

${displaystyle p }$

is represented by the symbol

${displaystyle Lleft({tfrac {a}{p}}right)}$

. Note that this does not mean

${displaystyle a }$

divided by

${displaystyle p }$

.

${displaystyle Lleft({tfrac {a}{p}}right)}$

has one of three values:

${displaystyle 0,1,-1 }$

.

${displaystyle Lleft({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 }}pend{cases}}}$

### Jacobi Symbol

The Jacobi symbol applies to all odd numbers

${displaystyle n>3 }$

${displaystyle n=p_{1}^{e_{1}}p_{2}^{e_{2}}ldots p_{m}^{e_{m}} }$

, then:

${displaystyle Jleft({tfrac {a}{n}}right)=Lleft({tfrac {a}{p_{1}}}right)^{e_{1}}Lleft({tfrac {a}{p_{2}}}right)^{e_{2}}ldots Lleft({tfrac {a}{p_{m}}}right)^{e_{m}}}$

If

${displaystyle n }$

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

## Primality Testing

### Description

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

Remember that if

${displaystyle p }$

is prime and

${displaystyle gcdleft(b,mright)=1}$

, Fermat’s Little Theorem states:

${displaystyle a^{p-1}equiv 1,{bmod {,}}p}$

However, there are cases where

${displaystyle p }$

can meet the above conditions and be nonprime. These classes of numbers are known as pseudoprimes.

${displaystyle m }$

is a pseudoprime to the base

${displaystyle a }$

, with

${displaystyle gcdleft(a,mright)=1}$

if and only if the least positive power of

${displaystyle a }$

that is congruent to

${displaystyle 1{bmod {,}}p}$

evenly divides

${displaystyle p-1 }$

.

If Fermat’s Little Theorem holds for any

${displaystyle p }$

that is an odd composite integer, then

${displaystyle p }$

is referred to as a pseudoprime. This forms the basis of primality testing. By testing different

${displaystyle 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

${displaystyle a }$

which is congruent to

${displaystyle 1,{bmod {,}}n}$

and divides

${displaystyle n-1 }$

which is the order of

${displaystyle a }$

in

${displaystyle mathbb {Z} _{n}^{*}}$

, then

${displaystyle n }$

is a pseudoprime.

II. If

${displaystyle n }$

is a pseudoprime to base

${displaystyle a_{1} }$

and

${displaystyle a_{2} }$

, then

${displaystyle n }$

is also a pseudoprime to

${displaystyle a_{1}a_{2},{bmod {,}}n}$

and

${displaystyle a_{1}a_{2}^{-1},{bmod {,}}n}$

.

III. If

${displaystyle n }$

fails

${displaystyle a^{p-1}equiv 1,{bmod {,}}p}$

, for any single base

${displaystyle ain mathbb {Z} _{p}^{*}}$

, then

${displaystyle n }$

fails

${displaystyle a^{p-1}equiv 1,{bmod {,}}p}$

for at least half the bases

${displaystyle ain mathbb {Z} _{p}^{*}}$

.

An odd composite integer for which

${displaystyle a^{p-1}equiv 1,{bmod {,}}p}$

holds for every

${displaystyle ain mathbb {Z} _{p}^{*}}$

is known as a Carmichael Number.

## Elliptic Curves

### Description

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,

## Summary

Computer security has three main elements that can easily be remembered using the acronym CIA: Confidentiality, Integrity, Availability.

• Confidentiality is the task of ensuring that only those entities (persons or systems) cleared for access can read information. Cryptography is a key element in ensuring confidentiality.
• Integrity is the task of ensuring that information is correct, and stays that way.
• Availability is the task of ensuring that systems responsible for delivering, storing and processing information are accessible when needed, by those who need them. This includes, for example, protection against denial of service (DoS) attacks.

In cryptography, an unbroken algorithm is not necessarily an unbreakable one.
There have been many cryptographic algorithms made and deployed in various situations throughout the world, some dating back from the time of Julius Caesar! More recent algorithms, AES Rijndael for example, are very strong, and have survived close scrutiny for many years and have remained secure. But, many other algorithms such as the Vigniere cipher were once believed to be totally unbreakable, but then all of a sudden, they may as well be written in plaintext. It was once thought that the simple XOR cipher could be the answer to an unbreakable algorithm, but new methods of cryptanalysis were born, and now, it can be cracked within moments.

Today’s ‘secure’ ciphers such as AES and Twofish may be secure now, but in the future, with the advent of faster computers, better techniques and even quantum computing, these ciphers will only last so long.

The study of code-breaking is known as Cryptanalysis. This, along with cryptography, constitutes Cryptology.

This page or section of the Cryptography book is a stub. You can help Wikibooks by expanding it.

“The more secret information you know, the more successful the concealment of the plaintext.”

It is important to realize that any crypto system in its design is an exercise in resource allocation and optimization.

If we were to return to the postal analogy used in the discussion of Asymmetric Ciphers. Suppose Alice has a secret message to send to Bob in the mail. Alice could put the message in her lock box and use Bob’s padlock to lock it allowing Bob to open it with his key, as describe earlier. But if it were a really important message or Alice and Bob had a higher expectation of the opponent they wished to thwart (Bob’s girlfriend knows where Bob keeps his keys) Alice and Bob might want to resort to a more complicated crypto system. For example Bob could have multiple keys, one he keeps on his key chain, one he keeps in a rented Post Office box and one that is in a box in a Swiss bank vault. Bob might welcome this sort of security for really serious messages but for day to day messages between Bob and Alice Bob will no doubt find a daily flight to Switzerland rather expensive inconvenient. All crypto systems must face a resource trade-off between convenience and security.

This page or section of the Cryptography book is a stub. You can help Wikibooks by expanding it.

## Key Length

Key length is directly proportional to security. In modern cryptosystems, key length is measured in bits (i.e., AES uses 256 bit keys), and each bit of a key increases the difficulty of a brute-force attack exponentially. It is important to note that in addition to adding more security, each bit slows down the cryptosystem as well. Because of this, key length — like all things security — is a tradeoff. In this case between practicality and security.

Furthermore, different types of cryptosystems require vastly different key lengths to maintain security. For instance, modulo-based public key systems such as Diffie-Hellman and RSA require rather long keys (generally around 1,024 bits), whereas symmetric systems, both block and stream, are able to use shorter keys (generally around 256 bits). Furthermore, elliptic curve public key systems are capable of maintaining security at key lengths similar to those of symmetric systems. While most block ciphers will only use one key length, most public key systems can use any number of key lengths.

As an illustration of relying on different key lengths for the same level of security, modern implementations of public key systems (see GPG and PGP) give the user a choice of keylengths. Usually ranging between 768 and 4,096 bits. These implementations use the public key system (generally either RSA or ElGamal) to encrypt a randomly generated block-cipher key (128 to 256 bits) which was used to encrypt the actual message.

## Entropy

Equal to the importance of key length, is information entropy. Entropy, defined generally as “a measure of the disorder of a system” has a similar meaning in this sense: if all of the bits of a key are not securely generated and equally random (whether truly random or the result of a cryptographically secure PRNG operation), then the system is much more vulnerable to attack. For example, if a 128 bit key only has 64 bits of entropy, then the effective length of the key is 64 bits. This can be seen in the DES algorithm. DES actually has a key length of 64 bits, however 8 bits are used for parity, therefore the effective key length is 56 bits.

## Common Mistakes

The fundamental deficiency in advantages of long block cipher keys when compare it to short cipher keys could be in difficulties to screening physical random entropy in short digits. Perhaps we can’t store screening mechanism of randomness in secret, so we can’t get randomness of entropy 2^256 without energy, which will be liner to appropriate entropy. For example, typical mistake of random generator implementation is simple addiction of individual digits with probability 0.5. This generator could be easy broken by bruteforce by neighbor bits wave functions. In this point of view, using block ciphers with large amount of digits, for ex. 10^1024 and more have a practical sense.[citation needed]

Other typical mistake is using public key infrastructure to encrypt session keys, because in this key more preferable to use Diffie-Hellman algorithm.
Using the Diffie-Hellman algorithm to create session keys gives “forward secrecy”.

“The higher the entropy of a random source, the better the quality of the random data it generates.”

Many cryptographic algorithms call for a random source, either in key-generation, or some other primitive. Implementors must be extremely cautious in selecting that random source, or they will open themselves up to attack. For example, the only formally proven encryption technique, the one time pad, requires a completely random and unbiased key-stream that is at least as long as the message itself, and is never reused. There are many implicit complications presented in this requirement, as the only sources of “true randomness” are in the physical world (silicon decay is an example), and are impossible to implement in software. Thus, it is often only feasible to obtain pseudo-randomness. Pseudo-Random Number Generators, or PRNGs, use multiple sources that are thought to be difficult to predict (mouse movement, least significant digits of the computer clock, network statistics, etc.) in order to generate an entropy pool, which is passed through assorted algorithms which attempt to remove any biases, and then used as a seed for a pre-determined static set of numbers. Even with all of the sources of entropy, a determined attacker can usually reduce the effective strength of an implementation by cutting out some of the factors—for instance making educated guesses on the time. PRNGs that are thought to be acceptable for cryptographic purposes are called Cryptographically-Secure Pseudo-Random Number Generators, or CSPRNGs.

## Entropy

In terms of information theory, entropy is defined as the measure of the amount of information expressed in a string of bits. For example a traditional gender classification contains 1-bit of entropy as it can be represented using a 1 for males and a 0 for females. The quality of a random source is determined by just how much entropy it generates, if the entropy is less than the actual number of bits then there is some repetition of information. The more information that is repeated, or the shorter the period of some PRNG, the lower the entropy and the weaker and more predictable the source of randomness. Therefore in cryptography one seeks to get as close to perfect randomness as possible with the resources available – where a perfect random number generator creates a sequence of bits which are unpredictable no matter how large a sample of previously generated bits is obtained.

## Letter Frequency

Whenever you consider any available language, it gives information about the frequency of letters that occur most frequently in it. The same matter is more enough for cryptanalysis (process of discovering ciphertexts) which is more beneficial when encryption is performed using the Conventional Classical Encryption Techniques.

This gives statistical information of data that cryptanalysts can use in order to decrypt the encrypted data, provided the language in which data is present is known.

The strength of your encryption method is based not only on your encryption method, but also on your ability to use it effectively. A perfect encryption method which is finicky to use and hard to get right is not likely to be useful in building a high quality security system.

For example, the One-Time Pad cypher is the only known provably unbreakable algorithm (in the very strong sense of a more effective than brute force search attack being impossible), but this proof applies ONLY if the key used is completely randomly chosen (there is currently no known method for making such a choice[citation needed] nor is there any known method for demonstrating that any particular choice is random), if the key is a long as the plaintext, if the key is never reused, and if the key never becomes known to the enemy. These conditions are so difficult to ensure that the One-Time Pad is almost never used in actual practice, whatever its theoretical advantages.

Any use of the One-Time Pad violating those assumed requirements is insecure, sometimes trivially so. For instance, statistical analysis techniques may be immediately applicable, under certain kinds of misuse.

This page or section of the Cryptography book is a stub. You can help Wikibooks by expanding it.

“The more people who can examine a cipher, the more likely a flaw will be found. No peer review (a closed algorithm) can result in weak ciphers.”

This page or section of the Cryptography book is a stub. You can help Wikibooks by expanding it.

In encryption, the weakest link is almost always a person.

While you could spend many hours attempting to decipher an encrypted message, or intercept a password, you can easily trick a person into telling you this information.

Suppose Bob works for a large company and encrypts document E with key K. Suppose Eve, wishing to decrypt document E, calls Bob and pretends to work for the company’s information security department. Eve would pretend a problem existed with the computers, servers, etc. and ask Bob for his key, K, which she would use to decrypt E. This is an example of social engineering.

Randall Munroe in an xkcd comic once presented a scenerio in which bad guys find it more convenient to hit Bob with a \$5 wrench until he gives up his key rather than attempt to break the crypto system.

A brute force attack against a cipher consists of breaking a cipher by trying all possible keys. Statistically, if the keys were originally chosen randomly, the plaintext will become available after about half of the possible keys are tried. As we discuss in Basic Design Principles, the underlying assumption is, of course, that the cipher is known. Since A. Kerckhoffs first published it, a fundamental maxim of cryptography has been that security must reside only in the key. As Claude E. Shannon said a few decades later, ‘the enemy knows the system’. In practice, it has been excellent advice.

As of the year 2002, symmetric ciphers with keys 64 bits or fewer are vulnerable to brute force attacks. DES, a well respected symmetric algorithm which uses 56-bit keys, was broken by an EFF project in the late 1990s. They even wrote a book about their exploit—Cracking DES, O’Reilly and Assoc. The EFF is a non-profit cyberspace civil rights group; many people feel that well-funded organisations like the NSA can successfully attack a symmetric key cipher with a 64-bit key using brute force. This is surely true, as it has been done publicly.[citation needed] Many observers suggest a minimum key length for symmetric key algorithms of 128 bits, and even then it is important to select a secure algorithm. For instance, many algorithms can be reduced in effective keylength until it is computationally feasible to launch a brute force attack. AES is recommended for use until at least 2030.

The situation with regard to asymmetric algorithms is much more complicated and depends on the individual algorithm. Thus the currently breakable key length for the RSA algorithm is at least 768 bits (broken publicly since 2009), but for most elliptic curve asymmetric algorithms, the largest currently breakable key length is believed to be rather shorter, perhaps as little as 128 bits or so. A message encrypted with a 109 bit key by an elliptic curve encryption algorithm was publicly broken by brute force key search in early 2003.

As of 2015, a minimum key length of 224 bits is recommended for elliptic curve algorithms, and 2048 bits for such other asymmetric key algorithms as RSA (asymmetric key algorithms that rely on complex mathematical problems for their security always will need much larger keyspaces as there are short-cuts to cracking them, as opposed to direct brute-force).[1]

## Common Brute Force Attacks

The term “brute force attacks” is really an umbrella term for all attacks that exhaustively search through all possible (or likely) combinations, or any derivative thereof.

### Dictionary Attack

A dictionary attack is a common password cracking technique, relying largely on the weak passwords selected by average computer users. For instance, if an attacker had somehow accessed the hashed password files through various malicious database manipulations and educated searching on an online store, he would then write a program to hash one at a time all words in a dictionary (of, for example any or all languages and common derivative passwords), and compare these hashes to the real password hashes he had obtained. If the hashes match, he has obtained a password.

#### Pre-Computation Dictionary Attack

The simple dictionary attack method quickly becomes far too time-consuming with any large number of password hashes, such as an online database would yield. Thus, attackers developed the method of pre-computation. In this attack, the attacker has already hashed his entire suite of dictionaries, and all he need do is compare the hashes. Additionally, his task is made easier by the fact that many users will select the same passwords. To prevent this attack, a database administrator must attach unique 32-bit salts to the users passwords before hashing, thus rendering precompution useless.

The Breaking Hash Algorithms chapter of this books goes into more detail on attacks that specifically apply to hashed password files.

## Responses to Brute Force Attacks

There are a number of ways to mitigate brute force attacks. For example:

• Changing a key frequently in response to an attempt to try all possible keys would require an attacker to start over assuming he knew the key was changed or finish attempting all possible keys before starting the attack again from the beginning.
• A system could rely on a time out or lock out of the system after so many attempts at guessing the key. Systems that time out can simply block further access, lock a user account, contact the account owner, or even destroy the clear text information.
• 2 step verification is a method of requiring a second key to enter the system. This complicates a brute force attack since the attacker must not only guess one key but then guess a second possibly equally complex key. The most common implementation of this is to ask for further authentication “What’s your first dogs name?”. There is a new trend on the horizon for systems to utilize two step verification through a time based key that is emailed or texted and having access to an account or particular electronic device serves as a secondary key.

The Secure Passwords chapter of this book goes into more detail on mitigations and other responses that specifically apply to hashed password files.

In the field of cryptanalysis, frequency analysis is a methodology for “breaking” simple substitution ciphers, not just the Caesar cipher but all monoalphabetic substitution ciphers. These ciphers replace one letter of the plaintext with another to produce the cyphertext, and any particular letter in the plaintext will always, in the simplest and most easily breakable of these cyphers, turn into the same letter in the cypher. For instance, all E’s will turn into X’s.

Graph of the relative frequency of letters in the English language

Frequency analysis is based on the fact that certain letters, and combinations of letters, appear with characteristic frequency in essentially all texts in a particular language. For instance, in the English language E is very common, while X is not. Likewise, ST, NG, TH, and QU are common combinations, while XT, NZ, and QJ are exceedingly uncommon, or “impossible”. Given our example of all E’s turning into X’s, a cyphertext message containing lots of X’s already seems to suggest one pair in the substitution mapping.

In practice the use of frequency analysis consists of first counting the frequency of cypher text letters and then assigning “guessed” plaintext letters to them. Many letters will occur with roughly the same frequency, so a cypher with X’s may indeed map X onto R, but could also map X onto G or M. But some letters in every language using letters will occur more frequently; if there are more X’s in the cyphertext than anything else, it’s a good guess for English plaintext that X stands for E. But T and A are also very common in English text, so X might be either of them. It’s very unlikely to be a Z or Q which aren’t common in English. Thus the cryptanalyst may need to try several combinations of mappings between cyphertext and plaintext letters. Once the common letters are ‘solved’, the technique typically moves on to pairs and other patterns. These often have the advantage of linking less commonly used letters in many cases, filling in the gaps in the candidate mapping table being built. For instance, Q and U nearly always travel together in that order in English, but Q is rare.

Frequency analysis is extremely effective against the simpler substitution cyphers and will break astonishingly short ciphertexts with ease. This fact was the basis of Edgar Allan Poe’s claim, in his famous newspaper cryptanalysis demonstrations in the middle 1800’s, that no cypher devised by man could defeat him. Poe was overconfident in his proclamation, however, for polyalphabetic substitution cyphers (invented by Alberti around 1467) defy simple frequency analysis attacks. The electro-mechanical cypher machines of the first half of the 20th century (e.g., the Hebern? machine, the Enigma, the Japanese Purple machine, the SIGABA, the Typex, …) were, if properly used, essentially immune to straightforward frequency analysis attack, being fundamentally polyalphabetic cyphers. They were broken using other attacks.

Frequency analysis was first discovered in the Arab world, and is known to have been in use by about 1000 CE. It is thought that close textual study of the Koran first brought to light that Arabic has a characteristic letter frequency which can be used in cryptoanalysis. Its use spread, and was so widely used by European states by the Renaissance that several schemes were invented by cryptographers to defeat it. These included use of several alternatives to the most common letters in otherwise monoalphabetic substitution cyphers (i.e., for English, both X and Y cyphertext might mean plaintext E), use of several alphabets—chosen in assorted, more or less, devious ways (Leon Alberti seems to have been the first to propose this), culminating in such schemes as using only pairs or triplets of plaintext letters as the ‘mapping index’ to cyphertext letters (e.g., the Playfair cipher invented by Charles Wheatstone in the mid 1800s). The disadvantage of all these attempts to defeat frequency counting attacks is that it increases complication of both encyphering and decyphering, leading to mistakes. Famously, a British Foreign Secretary is said to have rejected the Playfair cipher because, even if school boys could learn it as Wheatstone and Playfair had shown, ‘our attaches could never learn it!’.

Frequency analysis requires a basic understanding of the language of the plaintext, as well as tenacity, some problem solving skills, and considerable tolerance for extensive letter bookkeeping. Neat handwriting also helps. During WWII, both the British and Americans recruited codebreakers by placing crossword puzzles in major newspapers and running contests for who could solve them the fastest. Several of the cyphers used by the Axis were breakable using frequency analysis (e.g., the ‘consular’ cyphers used by the Japanese). Mechanical methods of letter counting and statistical analysis (generally IBM card machinery) were first used in WWII. Today, the hard work of letter counting and analysis has been replaced by the tireless speed of the computer, which can carry out this analysis in seconds. No mere substitution cypher can be thought credibly safe in modern times.

The frequency analysis method is neither necessary nor sufficient to solve ciphers.
Historically, cryptanalysts solved substitution ciphers using a variety of other analysis methods long before and after the frequency analysis method became well known.
Some people even question why the frequency analysis method was considered useful for such a long time.[2]
However, modern cyphers are not simple substitution cyphers in any guise. They are much more complex than WWII cyphers, and are immune to simple frequency analysis, and even to advanced statistical methods. The best of them must be attacked using fundamental mathematical methods not based on the peculiarities of the underlying plaintext language. See Cryptography/Differential cryptanalysis or Cryptography/Linear cryptanalysis as examples of such techniques.

## References

The index of coincidence for a ciphertext is the probability that two letters selected from it are identical. Usually denoted by I, it is a statistical measure of the redundancy of text. The index of coincidence of totally random collection (uniform distribution) of letters is around 0.0385.[1]

## References

This page or section of the Cryptography book is a stub. You can help Wikibooks by expanding it.

In cryptography, linear cryptanalysis is a general form of cryptanalysis based on finding affine approximations to the action of a cipher. Attacks have been developed for block ciphers and stream ciphers. Linear cryptanalysis is one of the two most widely used attacks on block ciphers; the other being differential cryptanalysis.

The discovery is attributed to Mitsuru Matsui, who first applied the technique to the FEAL cipher (Matsui and Yamagishi, 1992). Subsequently, Matsui published an attack on the Data Encryption Standard (DES), eventually leading to the first experimental cryptanalysis of the cipher reported in the open community (Matsui, 1993; 1994). The attack on DES is not generally practical, requiring 243 known plaintexts.

A variety of refinements to the attack have been suggested, including using multiple linear approximations or incorporating non-linear expressions, leading to a generalized partitioning cryptanalysis. Evidence of security against linear cryptanalysis is usually expected of new cipher designs.

## Overview

There are two parts to linear cryptanalysis. The first is to construct linear equations relating plaintext, ciphertext and key bits that have a high bias; that is, whose probabilities of holding (over the space of all possible values of their variables) are as close as possible to 0 or 1. The second is to use these linear equations in conjunction with known plaintext-ciphertext pairs to derive key bits.

### Constructing linear equations

For the purposes of linear cryptanalysis, a linear equation expresses the equality of two expressions which consist of binary variables combined with the exclusive-or (XOR) operation. For example, the following equation, from a hypothetical cipher, states the XOR sum of the first and third plaintext bits (as in a block cipher’s block) and the first ciphertext bit is equal to the second bit of the key:

${displaystyle P_{1}oplus P_{3}oplus C_{1}=K_{2}.}$

In an ideal cipher, any linear equation relating plaintext, ciphertext and key bits would hold with probability 1/2. Since the equations dealt with in linear cryptanalysis will vary in probability, they are more accurately referred to as linear approximations.

The procedure for constructing approximations is different for each cipher. In the most basic type of block cipher, a substitution-permutation network, analysis is concentrated primarily on the S-boxes, the only nonlinear part of the cipher (i.e. the operation of an S-box cannot be encoded in a linear equation). For small enough S-boxes, it is possible to enumerate every possible linear equation relating the S-box’s input and output bits, calculate their biases and choose the best ones. Linear approximations for S-boxes then must be combined with the cipher’s other actions, such as permutation and key mixing, to arrive at linear approximations for the entire cipher. The piling-up lemma is a useful tool for this combination step. There are also techniques for iteratively improving linear approximations (Matsui 1994).

### Deriving key bits

Having obtained a linear approximation of the form:

${displaystyle P_{i_{1}}oplus P_{i_{2}}oplus cdots oplus C_{j_{1}}oplus C_{j_{2}}oplus cdots =K_{k_{1}}oplus K_{k_{2}}oplus cdots }$

we can then apply a straightforward algorithm (Matsui’s Algorithm 2), using known plaintext-ciphertext pairs, to guess at the values of the key bits involved in the approximation.

For each set of values of the key bits on the right-hand side (referred to as a partial key), count how many times the approximation holds true over all the known plaintext-ciphertext pairs; call this count T. The partial key whose T has the greatest absolute difference from half the number of plaintext-ciphertext pairs is designated as the most likely set of values for those key bits. This is because it is assumed that the correct partial key will cause the approximation to hold with a high bias. The magnitude of the bias is significant here, as opposed to the magnitude of the probability itself.

This procedure can be repeated with other linear approximations, obtaining guesses at values of key bits, until the number of unknown key bits is low enough that they can be attacked with brute force.

## References

Differential cryptanalysis is a general form of cryptanalysis applicable primarily to block ciphers, but also to stream ciphers and cryptographic hash functions. In the broadest sense, it is the study of how differences in an input can affect the resultant difference at the output. In the case of a block cipher, it refers to a set of techniques for tracing differences through the network of transformations, discovering where the cipher exhibits non-random behaviour, and exploiting such properties to recover the secret key.

## History

The discovery of differential cryptanalysis is generally attributed to Eli Biham and Adi Shamir in the late 1980s, who published a number of attacks against various block ciphers and hash functions, including a theoretical weakness in the Data Encryption Standard (DES). It was noted by Bamford in The Puzzle Palace that DES is surprisingly resilient to differential cryptanalysis, in the sense that even small modifications to the algorithm would make it much more susceptible.

In 1994, a member of the original IBM DES team, Don Coppersmith, published a paper stating that differential cryptanalysis was known to IBM as early as 1974, and that defending against differential cryptanalysis had been a design goal.[1]
According to author Steven Levy, IBM had discovered differential cryptanalysis on its own, and the NSA was apparently well aware of the technique.[2]
IBM kept some secrets, as Coppersmith explains: “After discussions with NSA, it was decided that disclosure of the design considerations would reveal the technique of differential cryptanalysis, a powerful technique that could be used against many ciphers. This in turn would weaken the competitive advantage the United States enjoyed over other countries in the field of cryptography.”[1]
Within IBM, differential cryptanalysis was known as the “T-attack”[1], or “Tickle attack”.[3]

While DES was designed with resistance to differential cryptanalysis in mind, other contemporary ciphers proved to be vulnerable. An early target for the attack was the FEAL block cipher. The original proposed version with four rounds (FEAL-4) can be broken using only eight chosen plaintexts, and even a 31-round version of FEAL is susceptible to the attack.

## Attack mechanics

Differential cryptanalysis is usually a chosen plaintext attack, meaning that the attacker must be able to obtain encrypted ciphertexts for some set of plaintexts of his choosing. The scheme can successfully cryptanalyze DES with an effort on the order 247 chosen plaintexts. There are, however, extensions that would allow a known plaintext or even a ciphertext-only attack. The basic method uses pairs of plaintext related by a constant difference; difference can be defined in several ways, but the eXclusive OR (XOR) operation is usual. The attacker then computes the differences of the corresponding ciphertexts, hoping to detect statistical patterns in their distribution. The resulting pair of differences is called a differential. Their statistical properties depend upon the nature of the S-boxes used for encryption, so the attacker analyses differentials

${displaystyle (Delta _{X},Delta _{Y})}$

, where

${displaystyle Delta _{Y}=S(X)oplus S(Xoplus Delta _{X})}$

(and

${displaystyle oplus }$

denotes exclusive or) for each such S-box

${displaystyle S}$

. In the basic attack, one particular ciphertext difference is expected to be especially frequent; in this way, the cipher can be distinguished from randomness. More sophisticated variations allow the key to be recovered faster than exhaustive search.

In the most basic form of key recovery through differential cryptanalysis, an attacker requests the ciphertexts for a large number of plaintext pairs, then assumes that the differential holds for at least r-1 rounds, where r is the total number of rounds. The attacker then deduces which round keys (for the final round) are possible assuming the difference between the blocks before the final round is fixed. When round keys are short, this can be achieved by simply exhaustively decrypting the ciphertext pairs one round with each possible round key. When one round key has been deemed a potential round key considerably more often than any other key, it is assumed to be the correct round key.

For any particular cipher, the input difference must be carefully selected if the attack is to be successful. An analysis of the algorithm’s internals is undertaken; the standard method is to trace a path of highly probable differences through the various stages of encryption, termed a differential characteristic.

Since differential cryptanalysis became public knowledge, it has become a basic concern of cipher designers. New designs are expected to be accompanied by evidence that the algorithm is resistant to this attack, and many, including the Advanced Encryption Standard, have been proven secure against the attack.

## References

• Eli Biham, Adi Shamir, Differential Cryptanalysis of the Data Encryption Standard, Springer Verlag, 1993. ISBN 0-387-97930-1, ISBN 3-540-97930-1.
• Biham, E. and A. Shamir. (1990). Differential Cryptanalysis of DES-like Cryptosystems. Advances in Cryptology — CRYPTO ’90. Springer-Verlag. 2–21.
• Eli Biham, Adi Shamir,”Differential Cryptanalysis of the Full 16-Round DES,” CS 708, Proceedings of CRYPTO ’92, Volume 740 of Lecture Notes in Computer Science, December 1991. (Postscript)
• Eli Biham, slides from “How to Make a Difference: Early History of Differential Cryptanalysis”PDF (850 KB), March 16, 2006, FSE 2006, Graz, Austria

An extremely specialized attack, meet in the middle is a known plaintext attack that only affects a specific class of encryption methods – those which achieve increased security by using one or more “rounds” of an otherwise normal symmetrical encryption algorithm. An example of such a compound system is 3DES.

However, to explain this attack let us begin with a simpler system defined as follows:
Two cryptographic systems denoted

${displaystyle encrypt_{alpha }}$

and

${displaystyle encrypt_{beta }}$

(with inverse functions

${displaystyle decrypt_{alpha }}$

and

${displaystyle decrypt_{beta }}$

respectively) are combined simply (by applying one then the other) to give a composite cryptosystem. each accepts a 64 bit key (for values from 0 to 18446744073709551615) which we can call

${displaystyle key_{alpha }}$

or

${displaystyle key_{beta }}$

as appropriate.

So for a given plaintext, we can calculate a cryptotext as

${displaystyle cryptotext=encrypt_{beta }(key_{beta },encrypt_{alpha }(key_{alpha },plaintext))}$

and correspondingly

${displaystyle plaintext=decrypt_{alpha }(key_{alpha },decrypt_{beta }(key_{beta },cryptotext))}$

Now, given that each has a 64 bit key, the amount of key needed to encrypt or decrypt is 128 bits, so a simple analysis would assume this is the same as a 128 bit cypher.

However, given sufficient storage, you can reduce the effective key strength of this to a few bits larger than the largest of the two keys employed, as follows.

1. Given a plaintext/cyphertext pair, apply
${displaystyle encrypt_{alpha }}$

to the plaintext with each possible key in turn, generating

${displaystyle 2^{64}}$

intermediate cryptotexts

${displaystyle cryptotext_{1}}$

${displaystyle rightarrow }$

${displaystyle cryptotext_{n}}$

where

${displaystyle n=2^{64}}$

2. Store each of the
${displaystyle n}$

cryptotexts in a hash table so that each can be referenced by its cryptotext, and give the key used to generate that cryptotext

3. Apply
${displaystyle decrypt_{beta }}$

to the ciphertext for each possible key in turn, comparing the intermediate plaintext to the hash table calculated earlier. this gives a pair of keys (one for each of the two algorithms employed,

${displaystyle alpha }$

and

${displaystyle beta }$

)

4. Taking the two keys from stage 3, test each against a second plaintext/cryptotext pair. if this also matches, odds are extremely high you have a valid keypair for the message – not in
${displaystyle 2^{128}}$

operations, but a “mere”

${displaystyle 2×2^{64}}$

operations (which nonetheless are significantly longer due to the hash table operations, but not so much as to add more than a couple of extra bits worth of time to the complexity of the task)

The downside to this approach is storage. Assuming you have a 64 bit key, then you will need at least

${displaystyle 2^{64}}$

units of storage – where each unit is the amount of space used by a single hash record. Even given a minimal implementation (say, 64 bits for the key plus four bits hash collision overhead), if you implemented such a system using 160GB hard drives, you would need close to one billion of them to store the hash table alone.

Cryptographic hash functions are one of the more difficult, from a cryptography perspective, things to break.

Cryptographic hash functions are specifically designed to be “one-way”:
If you have some message, it is easy to go forward
to the corresponding hashed value;
but if you only have the hashed value,
cryptographic hashes are specifically designed to be difficult to calculate
the original message that produced that hash value —
or any other message that produces the same hash value.

As we previously mentioned in Hashes,
a cryptographically secure hash is designed to have these properties:

• Preimage resistant: Given H it should be hard to find M such that H = hash(M).
• Second preimage resistant: Given an input m1, it should be hard to find another input, m2 (not equal to m1) such that hash(m1) = hash(m2).
• Collision-resistant: it should be hard to find two different messages m1 and m2 such that hash(m1) = hash(m2).

Cryptographers distinguish between three different kinds of attacks on hash functions:

• collision attack: try to find any two different messages m1 and m2 such that hash(m1) = hash(m2).
• preimage attack: Given only the hash value H, try to recover *any* M such that H = hash(M).
• second-preimage attack: Given an input m1, try to find another input, m2 (not equal to m1) such that hash(m1) = hash(m2).
• Some hash functions (MD5, SHA-1, SHA-256, etc.) are vulnerable to a “length extension attack”.
 To do:is the length extension attack a special case of one of the above 3 attacks, or is it a distinct 4th type?

(Alas, different cryptographers use different and sometimes use contradictory terms for these three kinds of attacks.
Outside of this book,
some cryptographers use “collision” to refer to a successful attack of any of these 3 types, and use the term “free collision” for what this book calls a “successful collision attack”, or “bound collision” for either one of a “successful preimage attack” or a “successful second-preimage attack”.)[1]

When designing a new system that requires some hash function, most cryptographers recommend using hash fuctions that, as far as we know, are resistant to all these attacks (such as SHA-3, BLAKE, Grøstl, Skein, etc.).

 To do:describe the random oracle hash, aka “the ideal hash function”

The collision attack is the easiest kind of attack, and the most difficult to defend against.
Because there are an infinite number of possible files,
the pigeonhole principle
tells us that there are in theory an infinite number of hash collisions,
even for the “ideal” random oracle hash.
Cryptographic hashes are designed to make it difficult —
using only resources available in our solar system, practically impossible —
to find *any* of those messages
that hash to some given hash value.

Some applications require collision resistance.
When a possible attacker generates a message and we want to confirm that the message that person shows Alice is the same as the message that person shows Bob, ensuring message integrity, we need a hash that hash collision resistance.

Many applications do not actually require collision resistance.
For example,
requires preimage and second-preimage resistance (and a few other special characteristics), but not collision resistance.
For example,
de-duplicating file systems, host-proof file systems such as IPFS, digital signatures, etc.
only require second-preimage resistance, not preimage or collision resistance,
because in those applications it is assumed that the attacker
already knows the original message that hashes to the given value.
For example, message authentication using HMAC does not require collision resistance and is immune to length extension; so as of 2011 cryptographers find using HMAC-MD5 message authentication in existing applications acceptable, although they recommend that new applications use some alternative such as HMAC-SHA256 or AES-CMAC.[2][3]

The MD5 and SHA-1 hash functions, in applications that do not actually require collision resistance, are still considered adequate.

Many people criticise MD5 and SHA1 for the wrong reasons.
[4]
There is no known practical or almost-practical preimage attack on MD5 or SHA-1, much less second-preimage attacks, only collision attacks.[5][6]

Such collision attacks include:

• Dobbertin announced a collision of the MD5 compression function in 1996 …
• As of 2009, finding chosen-prefix collisions in MD5 takes about 30 seconds on a laptop.[3]
• Manuel and Peyrin’s SHA-0 attack[7]
• Nat McHugh’s MD5 collision attacks[8]

In the next chapters we will discuss

A hash function is said to collide when two distinct inputs to the hash function yield the same output.

For example, when the following blocks are input into the md5 hash function they both yield the same output.

```d131dd02c5e6eec4693d9a0698aff95c
2fcab58712467eab4004583eb8fb7f89
085125e8f7cdc99fd91dbdf280373c5b
d8823e3156348f5bae6dacd436c919c6
dd53e2b487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080a80d1e
c69821bcb6a8839396f9652b6ff72a70
```
```d131dd02c5e6eec4693d9a0698aff95c
2fcab50712467eab4004583eb8fb7f89
085125e8f7cdc99fd91dbd7280373c5b
d8823e3156348f5bae6dacd436c919c6
dd53e23487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080280d1e
c69821bcb6a8839396f965ab6ff72a70
```

## References

“MD5 Collisions, Visualised”. http://www.links.org/?p=6. Retrieved 2010-03-11.

The “birthday attack” is a method of creating two hash preimages that when hashed have the same output.

Earlier, we discussed how
Permutation cipher and
Transposition ciphers
work for people who know the secret key.
Next, we’ll discuss how, in some cases, it is possible for a person who only has the ciphertext — who doesn’t know the secret key — to recover the plaintext.

The frequency distribution of the letters in any transposition or permutation ciphertext is the same as the frequency distribution for plaintext.

## breaking columnar transposition ciphers

The frequency distribution of digrams can be used to help break columnar transposition ciphers.
[1]

## breaking turning grille ciphers

Turning grilles, also called Fleissner grilles, …

A guess at some sequence of two or more consecutive holes of the grill in one position of the grill (by a “known word” or an expected common digraph)
can be “checked” by seeing if those holes, after the grill is rotated a half-turn,
produce reasonable digraph.[2][3]

## References

Breaking the Caesar cipher is trivial as it is vulnerable to most forms of attack. The system is so easily broken that it is often faster to perform a brute force attack to discover if this cipher is in use or not. An easy way for humans to decipher it is to examine the letter frequencies of the cipher text and see where they match those found in the underlying language.

## Frequency analysis

By graphing the frequencies of letters in the ciphertext and those in the original language of the plaintext, a human can spot the value of the key but looking at the displacement of particular features of the graph. For example in the English language the frequencies of the letters Q,R,S,T have a particularly distinctive pattern.

Computers can also do this trivially by means of an auto-correlation function.

## Brute force

As the system only has 25 non-trivial keys it is easy even for a human to cycle through all the possible keys until they find one which allows the ciphertext to be converted into plaintext.

## Known plaintext attack

If you have a message in both ciphertext and in plaintext it is trivial to find the key by calculating the difference between them.

Plain text is encrypted using the Vigenère cipher by first choosing a keyword consisting of letters from the alphabet of symbols used in the plain text. The keyword is then used to encrypt the text by way of the following example.

Using:
Plain text: I Like A Book
and choosing:
Keyword: cta

1. Map all the plain text to numbers 0-25 or however long your alphabet is

```  ilikewikibooks converts to 8 11 8 10 4 22 8 10 8 1 14 14 10 18
```

2. Map your keyword to numbers the same way

```  cta maps to 2 19 0
```

```  8  11  8  10   4  22  8  10  8  1  14  14  10  18
2  19  0   2  19   0  2  19  0  2  19   0   2  19
resulting in
10 30  8  12  23  22 10 29   8  3  33   14  12  37
```

4. take each resulting number mod 26 ( or for the general case mod the number of characters in your alphabet)

```  resulting in
10 4   8  12  23  22 10 3    8  3  7    14  12   11
```

5. map each number back to a letter to get the resulting cypher text

```  keimxwkdidhoml
```

The message can easily be decrypted with the keyword by reversing the above process.
The keyword can be any length equal to or less than that of the plain text.

Without the keyword the primary method of breaking the Vigenère cipher is known as the Kasiski test, after the Prussian major who first published it. The first stage is determining the length of the keyword.

### Determining the key length

Given an enciphered message such as:

```Plaintext:  TOBEORNOTTOBE
Keyword:    KEYKEYKEYKEYK
Ciphertext: DSZOSPXSRDSZO
```

Upon inspection of the ciphertext, we see that there are a few digraphs repeated, namely DS, SZ, and ZO. It is statistically unlikely that all of these would arise by random chance; the odds are that repeated digraphs in the ciphertext correspond to repetitions in the plaintext. If that is the case, the digraphs must be encoded by the same section of the key both times. Therefore, the length of the key is a factor of the distance in the text between the repetitions.

Digraph First Position Second Position Distance Factors
DS 1 10 9 3
SZ 1 10 9 3
ZO 1 10 3 3

The common factors (indeed, the only factors in this simple example) are 3 and 9. This narrows down the possibilities significantly, and the effect is even more pronounced with longer texts and keys.

### Frequency analysis

Once the length of the key is known, a slightly modified frequency analysis technique can be applied. Suppose the length of the key is known to be three. Then every third letter will be encrypted with the same letter of the key. The ciphertext can be split into three segments – one for each key letter—and the procedure described for the Caesar cipher can be used.