Number theory for Public key Cryptography

Question 2

What is the chinese remainder theorem?

Answer 2

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 3

What does it mean to be pairwise relatively prime?

Answer 3

When two integers have gcd = 1

Question 4

Define the Euler function

Answer 4

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

Question 5

What is the residue clss Z_n^*

Answer 5

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

Question 6

What are some properties of the Euler function?

Answer 6

1. Ø(p) = p-1 for a prime p
2. Ø(pq) = (p-1)(q-1), for distinct primes
3. See L8 slide 7

Question 7

What is Fermat theorem?

Answer 7

a^(p-1) mod p = 1

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

Question 8

What is Eulers theorem?

Answer 8

a^Ø(n) mod n = 1,

if gcd(a,n) = 1

Question 9

What is the Fermat primality test?

Answer 9

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 10

What are the inputs of Fermat primality test?

Answer 10

n: value to test for primality

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

Question 11

What are the outputs of Fermat primality test?

Answer 11

Composite: If n is composity
Otherwise, probably prime

Question 12

What is the Fermat primality test algorithm?

Answer 12

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 13

What does it mean when n is a pseudoprime?

Answer 13

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

Question 14

What are Carmichael numbers?

Answer 14

Compmosite numbers that satisfies:

b^n-1 ≡ 1 mod n

Composite numbers that will always output probable prime from the fermat test.

For every a with gcd(a,n) = 1

Question 15

What is the Miller-Rabin test?

Answer 15

Can guarantee to detect composites if run sufficiently many times.

Widely used to generate large primes

Question 16

What is a modular square root of 1?

Answer 16

x^2 mod n = 1

Question 17

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

Answer 17

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 18

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

Answer 18

4

Question 19

What are trivial square roots of 1?

Answer 19

1, -1

Question 20

What is the Miller-Rabin algorithm?

Answer 20

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

1. Pick a value for a randomly in 1 < a < n-1
2. Set b = aû 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 21

Define the effectiveness of Miller-Rabin

Answer 21

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 ocmposite with probability (1/4)^k

Question 22

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

Answer 22

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 23

What are the two aspects of computational complexity?

Answer 23

Algorithm complexity

Problem complexity

Question 24

What is algorithm complexity?

Answer 24

How long it takes to run an algorithm

Question 25

What is problem complexity?

Answer 25

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

Question 26

How do you measure algorithm complexity?

Answer 26

Measured by its tima 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 27

What is big O notation?

Answer 27

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 28

What is a polynomial time function?

Answer 28

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

problems with polynomial time functions are efficient

Question 29

What is an exponential time function?

Answer 29

f(m) = O(b^m)

b>1,

problems with exponential time functions are hard

Question 30

How are problem complexity classified?

Answer 30

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

Question 31

What are sub-exponential problems?

Answer 31

Slower than polynomial but faster than any exponential

Question 32

What is integer factorisation?

Answer 32

Find an integers prime factors

Question 33

What is the discrete logarithm problem?

Answer 33

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

y = g^x mod p

Question 34

What is the best known method of integer factorisation?

Answer 34

The number field sieve (sub-exponential algorithm)

Question 35

Describe discrete logarithm problem (DLP)

Answer 35

G: cyclic group, generator g

The discrete log problem in G is:

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