E-CES, 212-81, Module 3, Number Theory and Asymmetric Cryptography

Asymmetric Cryptography

AKA public key cryptography. Slower than symmetric key cryptography. Developed to overcome weaknesses in symmetric cryptography. Uses a public and a private key.

N

Denotes the natural numbers. 1, 2, 3, etc.

Z

Denotes the integers. These are whole numbers -1, 0, 1, 2 etc.

Q

Denotes the rational numbers (ratio of integers). Any number that can be expressed as a ratio of two integers 3/2, 17/4, 1/5 etc.

R

Denotes the real numbers. This includes the rational numbers as well as numbers that cannot be expressed as a ratio of two integers, for example √2

i

Denotes imaginary numbers. These are numbers whose square is a negative. √-1 = 1i

Entropy

A measure of the uncertainty associated with a random variable.

Prime Number

Any number whose factors are 1 and itself. Example 2, 3, 5, 7, 11, 13, 17, 23

Prime Number Theorem

If a random number N is selected, the chance of it being prime is approx. 1/ln(N), where ln(N) denotes the natural logarithm of N.

Mersenne Primes

Uses a formula, Mn = 2n − 1 where n is a prime number, to generate primes. Works for 2, 3, 5, 7 but fails on 11 and on many other n values.

Co-prime Numbers

A number that has no factors in common with another number. For example, 3 and 7 are this.

Euler's Totient

The number of positive integers less than or equal to n that are co-prime to n is called the ***** ***** of n. For example the number 6; 4 and 5 are co-prime with 6. Therefore, **** ******=2. Symbolized by ϕ(n). For a prime number p, ϕ(n) is always p-1.
Part of the RSA algorithm!

Modulus Operator

Used in a number of cryptography algorithms. Simply divide A by N and return the remainder.
-So 5 mod 2 = 1
-So 12 mod 5 = 2
-Sometimes symbolized as % as in 5 % 2 = 1

Fibonacci Numbers

Named after Leonardo of Pisa who was also known a *********. Sequence of numbers are derived by adding the last two numbers to create the next number, N1 + N2 = n3. Example, 0, 1, 1, 2, 3, 5, 8, 13, 21, 35, 56. Some random number generators use this.

Birthday Theorem

The number of people you would have to invite to a party so that two will have the same birthday (with high probability). √365
You need √N to have a high probability of collision.
Answer is approximately 1.174 √365 to have a high probability of collision.

Birthday Paradox

The number of people you need to have a high likelihood that two share the same birthday. The answer is 23. This is a classic math problem that relates to hashes.

Birthday Attack

Name used to refer to a class of brute force attacks against hashes. Attempts to find a collision.

The three types of random number generators

-Table look-up
-Hardware
-Algorithmic (software) - this category is most often used in cryptography and produces a pseudo random number.

K1

A sequence of random numbers with a low probability of containing identical consecutive elements.

K2

A sequence of numbers which is indistinguishable from true random according to statistical tests.

K3

It should be impossible for an attacker to calculate any previous or future values.

K4

It should be impossible for an attacker to calculate or guess from an inner state of the generator any previous numbers in the sequence or any previous inner generator states.

Traits of a good Pseudorandom Number Generator (PRNG)

Uncorrelated sequences and Long period

Naor-Reingold pseudorandom function

Created in 1997 by Moni Naor and Omer Reingold. The mathematics of this function are complex for non-mathematicians.

Mersenne Twistter pseudorandom function

Originally not suitable for cryptography but permutations of it are. Created by Makoto Matsumoto and Takuji Nishimura. Has a very large period, greater than many other generators.

Linear Congruential Generator

Determined by the following four integer values:
m the modulus m>0
a the multiplier 0, 0<a<m
c the increment 0, 0<c<m
X0 the starting value 0, 0,X0<m
The algorithm is : Xn + 1 = (aXn + C)mod m

Lehmer Random Number Generator

Created by D. H. Lehmer. It is a classic example of a Linear congruential generator. A PRNG type of linear congruential generator (LCG) that operates in multiplicative group of integers modulo n.
The basic algorithm is Xi+1=(aXi + c) mod m, with 0 ≤ Xi ≤ m

Lagged Fibonacci Generator

A type of pseudorandom number generator. If addition is used, then it is an ALFG. If multiplication is used then it is a MLFG. If XOR is used it is called a two-gap generalized feedback shift register, or GFS.

Blum Blum Shub

Created in 1986 by Lenore Blum, Manuel Blum, and Michael Shub. Format is Xn+1 = Xn2 Mod M
The main difficulty of predicting the output of this is the difficulty of the "quadratic residuosity problem". As difficult as breaking the RSA public-key cryptosystem.

Yarrow

Algorith that was created by Bruce Schneier, John Kelsey, and Niels Ferguson. No longer recommended, Fortuna is recommended instead. Consists of four parts:
-Entropy Accumulator
-Generation Mechanism
-Reseed Mechanism
-Reseed Control

Fortuna

A group of PRNGs that has many options for whoever implements the algorithm. Consists of three parts:
-A generator
-An entropy accumulator
-A seed file

Diffie-Hellman

A cryptographic protocol that allows two parties to establish a shared key over an insecure channel. Released in 1976, developed earlier by British Intelligence Service. Used for the exchange of symmetric keys.

RSA

Created in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT. Most widely used public key cryptography algorithm. Based on relationships with prime numbers. This algorithm is secure because it is difficult to factor a large integer composed of two or more large prime factors.

Menezes-Qu-Vanstone (MQV)

A protocol for key aggreement based on Diffie-Hellman. Created in 1995. Incorporated into the public key standard IEEE P1363.

Digital Signature Algorithm (DSA)

Filed July 26, 1991 under U.S. Patent 5,231,668. Adopted by the U.S. Government in 1993 with FIPS186.
Choose a hash function (traditionally SHA1). Select a key length L and N. Choose a prime number q that must be less than or equal to the hash output length. Choose a prime number p such that p-1 is a multiple of q. Choose g, this number must be a number whose multiplicitive order modulo is q. Choose a random number x, where 0<x<q. Calculate y=gx mod p. Public Key is (p, q, g, y). Private key is x.

Signing with DSA

Let H be the hashing function and m the message. Generate a random value for each message k where 0<k<q. Calculate r = (gk mod p) mod q. Calculate s = (k-1 (H (m) + x*r )) mod q. If r or s = zero, then recalculate for a non-zero result (i.e pick a different K). The signature is (r,s).

Elliptic Curve

Created in 1985 by Victor Miller, IBM. Endorsed by the NSA, schemes based on it for Suite B. Protects information classified up to top secret with 384bit keys. Based on y2 = x3 + Ax + B.

Elliptic Curve Variations

-Elliptic Curve Diffe-Hellman (used for key exchange)
-Elliptic Curve Digital Signature Algorith (ECDSA)
-Elliptic Curve MQV key agreement protocol

ElGamal

Created in 1984 by Taher *******. Used in some PGP implementations as well as GNU Privacy Guard software. Consists of three parts: key generator, encryption algorithm, decryption algorithm. This encryption is probabilistic.