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