Module 3- Number Theory and Asymmetric Crypography Flashcards
AKA public key cryptography.
Uses a public and a private key.
Asymmetric Cryptography
Denotes the natural numbers. 1, 2, 3, etc.
N
Denotes the integers. These are whole numbers -1, 0, 1, 2 etc.
Z
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.
Q
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
R
Denotes imaginary numbers. These are numbers whose square is a negative. √-1 = 1i
i
A measure of the uncertainty associated with a random variable
Entropy
Any number whose factors are 1 and itself. Example 2, 3, 5, 7, 11, 13, 17, 23
Prime Number
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.
Prime Number Theorem
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.
Mersenne Primes
A number that has no factors in common with another number. For example, 3 and 7 are this.
Co-prime Numbers
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!
Euler’s Totient
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
Modulus Operator
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.
Fibonacci Numbers
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 Theorem
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 Paradox
Name used to refer to a class of brute force attacks against hashes. Attempts to find a collision.
Birthday Attack
random number generator is most often used in cryptography and produces a pseudo random number.
-Algorithmic (software)
The three types of random number generators
- Table look-up
- Hardware
- Algorithmic (software)
A sequence of random numbers with a low probability of containing identical consecutive elements.
K1
A sequence of numbers which is indistinguishable from true random according to statistical tests.
K2
It should be impossible for an attacker to calculate any previous or future values.
K3
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.
K4
Traits of a good Pseudorandom Number Generator (PRNG)
Uncorrelated sequences
Long period
Created in 1997 by Moni Naor and Omer Reingold. The mathematics of this function are complex for non-mathematicians.
Naor-Reingold 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.
Mersenne Twistter pseudorandom function
Determined by the following four integer values:
m the modulus m>0
a the multiplier 0, 0
Linear Congruential 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
Lehmer Random Number 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.
Lagged Fibonacci Generator
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.
Blum Blum Shub
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
Yarrow
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
Fortuna
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.
Diffie-Hellman
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.
RSA
A protocol for key aggreement based on Diffie-Hellman. Created in 1995. Incorporated into the public key standard IEEE P1363.
Menezes-Qu-Vanstone (MQV)
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
Digital Signature Algorithm (DSA)
Let H be the hashing function and m the message. Generate a random value for each message k where 0
Signing with DSA
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
Elliptic Curve Variations
- Elliptic Curve Diffe-Hellman (used for key exchange)
- Elliptic Curve Digital Signature Algorith (ECDSA)
- Elliptic Curve MQV key agreement protocol
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.
ElGamal
