Number theory for Public key Cryptography Flashcards
What is the chinese remainder theorem?
Pairwise relatively prime: d1, d2,…,dr
n = d1d2…*dr
Given any integer ci there exist a unique integer x (0 <= x < n) such that
x ≡ c1 (mod d1)
x ≡ c2 (mod d2)
…
x ≡ cr (mod dr)
x ≡Sum(n/di) yi ci (mod n)
yi ≡ (n/di)^-1 (mod di)
What does it mean to be pairwise relatively prime?
When two integers have gcd = 1
Define the Euler function
Euler function Q(n) denotes the number of positive integers less than n and relatively prime to n
What is the residue clss Z_n^*
Set of positive integers less than n and relatively prime to n
What are some properties of the Euler function?
- Ø(p) = p-1 for a prime p
- Ø(pq) = (p-1)(q-1), for distinct primes
- See notebook: way to find Ø(n) when prime factoring a number
What is Fermat theorem?
a^(p-1) mod p = 1
p: prime
a: integer 1 < a < p-1
What is Eulers theorem?
a^Ø(n) mod n = 1,
if gcd(a,n) = 1
What is the Fermat primality test?
if p is prime: a^(p-1) mod p = 1
for all a with gcd(a,p) = 1
If we examine a number n and find that a^n-1 mod n is not 1 -> a is not a prime
Fermat primality test: Check if a number satisfies Fermat’s equation
What are the inputs of Fermat primality test?
n: value to test for primality
k: parameter that determines number of times to test for primality
What are the outputs of Fermat primality test?
Composite: If n is composity
Otherwise, probably prime
What is the Fermat primality test algorithm?
Repeat k times:
- pick a value of a randomly in the range 1 < a < n-1
- If a^n-1 mod n is not 1, return composite, if = 1 return probable prime
What does it mean when n is a pseudoprime?
When fermat test output probable prime when n is actually a composite
What are Carmichael numbers?
Compmosite numbers that satisfies:
b^n-1 ≡ 1 mod n
Composite numbers that will always output probable prime from the fermat test.
For every b with gcd(b,n) = 1
What is the Miller-Rabin test?
Can guarantee to detect composites if run sufficiently many times.
Widely used to generate large primes
What is a modular square root of 1?
x^2 mod n = 1
How does the Miller-Rabin test use square roots to find composite numbers?
n = pq gives 4 square roots of 1,
2 trivial: 1, -1
2 non-trivial
If x is non-trivial square root of 1, then gcd(x-1, n) is a non-trivial factor of n
An existence of a non-trivial square root of 1, implies that n is composite
When n = pq, how many square roots are there of 1?
4
What are trivial square roots of 1?
1, -1
What is the Miller-Rabin algorithm?
n, u is odd
u,v such that n - 1 = (2^v)*u
- Pick a value for a randomly in 1 < a < n-1
- Set b = a^u mod n
- if b == 1 -> return probable prime
- for j = 0 to v-1
- b == 1 -> return probable prime
- else set b = b^2 mod n - return composite
Define the effectiveness of Miller-Rabin
Return composite -> n is composite
Return probable prime -> n may be composite
n is composite: test return probable prime with probability of 1/4. Because of this, repeate the algorithm 4 times while output is probable prime
k-times algorithm output probable prime when n is composite with probability (1/4)^k
How can Miller-Rabin be used to generate large primes?
- Choose odd integer r, same number of bits as required prime
- Test if r is divisible of any list of small prime
- Apply Miller-Rabin with 5 random bases
- If r fails, set r = r + 2 and return to step 2
This does not generate completely random primes, to do so, go back to step 1 instead of 2
What are the two aspects of computational complexity?
Algorithm complexity
Problem complexity
What is algorithm complexity?
How long it takes to run an algorithm
What is problem complexity?
What is the best (known) algorithm to solve a particular problem
How do you measure algorithm complexity?
Measured by its time and space requirements as functions of the size of the input m
A positive function is expressed as an “order of magnitude” of the form O(g(m)), where g(m) is another positive function
What is big O notation?
f(m) = O(g(m))
if a constant c>0 and m_0 such that f(m)<c*g(m) for m>=m_0
g is an upper bound for f
What is a polynomial time function?
f(m) = O(m^t), t integer > 0
problems with polynomial time functions are efficient
What is an exponential time function?
f(m) = O(b^m)
b>1,
problems with exponential time functions are hard
How are problem complexity classified?
According to the minimum time and space needed to solve the hardest instances of the problem
What are sub-exponential problems?
Slower than exponential but faster than any polynomial
What is integer factorisation?
Find an integers prime factors
What is the discrete logarithm problem?
Given a prime p and an integer y, 0 < y < p, find x such that:
y = g^x mod p
What is the best known method of integer factorisation?
The number field sieve (sub-exponential algorithm)
Describe discrete logarithm problem (DLP)
G: cyclic group, generator g
The discrete log problem in G is:
y in G, find x with y = g^x
What happens if x is a non-trivial square root of n?
gcd(x-1, n) is a non-trivial factor of n
The existence of a non-trivial square root implies that n is composite
