Number theory for Public key Cryptography

Question 1

What is the chinese remainder theorem?

Answer 1

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)

Question 2

What does it mean to be pairwise relatively prime?

Answer 2

When two integers have gcd = 1

Question 3

Define the Euler function

Answer 3

Euler function Q(n) denotes the number of positive integers less than n and relatively prime to n

Question 4

What is the residue clss Z_n^*

Answer 4

Set of positive integers less than n and relatively prime to n

Question 5

What are some properties of the Euler function?

Answer 5

1. Ø(p) = p-1 for a prime p
2. Ø(pq) = (p-1)(q-1), for distinct primes
3. See notebook: way to find Ø(n) when prime factoring a number

Question 6

What is Fermat theorem?

Answer 6

a^(p-1) mod p = 1

p: prime
a: integer 1 < a < p-1

Question 7

What is Eulers theorem?

Answer 7

a^Ø(n) mod n = 1,

if gcd(a,n) = 1

Question 8

What is the Fermat primality test?

Answer 8

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

Question 9

What are the inputs of Fermat primality test?

Answer 9

n: value to test for primality

k: parameter that determines number of times to test for primality

Question 10

What are the outputs of Fermat primality test?

Answer 10

Composite: If n is composity
Otherwise, probably prime

Question 11

What is the Fermat primality test algorithm?

Answer 11

Repeat k times:

1. pick a value of a randomly in the range 1 < a < n-1
2. If a^n-1 mod n is not 1, return composite, if = 1 return probable prime

Question 12

What does it mean when n is a pseudoprime?

Answer 12

When fermat test output probable prime when n is actually a composite

Question 13

What are Carmichael numbers?

Answer 13

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

Question 14

What is the Miller-Rabin test?

Answer 14

Can guarantee to detect composites if run sufficiently many times.

Widely used to generate large primes

Question 15

What is a modular square root of 1?

Answer 15

x^2 mod n = 1

Question 16

How does the Miller-Rabin test use square roots to find composite numbers?

Answer 16

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

Question 17

When n = pq, how many square roots are there of 1?

Answer 17

4

Question 18

What are trivial square roots of 1?

Answer 18

1, -1

Question 19

What is the Miller-Rabin algorithm?

Answer 19

n, u is odd
u,v such that n - 1 = (2^v)*u

1. Pick a value for a randomly in 1 < a < n-1
2. Set b = a^u mod n
3. if b == 1 -> return probable prime
4. for j = 0 to v-1
   - b == 1 -> return probable prime
   - else set b = b^2 mod n
5. return composite

Question 20

Define the effectiveness of Miller-Rabin

Answer 20

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

Question 21

How can Miller-Rabin be used to generate large primes?

Answer 21

1. Choose odd integer r, same number of bits as required prime
2. Test if r is divisible of any list of small prime
3. Apply Miller-Rabin with 5 random bases
4. 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

Question 22

What are the two aspects of computational complexity?

Answer 22

Algorithm complexity

Problem complexity

Question 23

What is algorithm complexity?

Answer 23

How long it takes to run an algorithm

Question 24

What is problem complexity?

Answer 24

What is the best (known) algorithm to solve a particular problem

Question 25

How do you measure algorithm complexity?

Answer 25

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

Question 26

What is big O notation?

Answer 26

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

Question 27

What is a polynomial time function?

Answer 27

f(m) = O(m^t), t integer > 0

problems with polynomial time functions are efficient

Question 28

What is an exponential time function?

Answer 28

f(m) = O(b^m)

b>1,

problems with exponential time functions are hard

Question 29

How are problem complexity classified?

Answer 29

According to the minimum time and space needed to solve the hardest instances of the problem

Question 30

What are sub-exponential problems?

Answer 30

Slower than exponential but faster than any polynomial

Question 31

What is integer factorisation?

Answer 31

Find an integers prime factors

Question 32

What is the discrete logarithm problem?

Answer 32

Given a prime p and an integer y, 0 < y < p, find x such that:

y = g^x mod p

Question 33

What is the best known method of integer factorisation?

Answer 33

The number field sieve (sub-exponential algorithm)

Question 34

Describe discrete logarithm problem (DLP)

Answer 34

G: cyclic group, generator g

The discrete log problem in G is:

y in G, find x with y = g^x

Question 35

What happens if x is a non-trivial square root of n?

Answer 35

gcd(x-1, n) is a non-trivial factor of n

The existence of a non-trivial square root implies that n is composite