RA1 and RA2: ModMath and RSA

Question 1

N divides (x - y) iff …

Answer 1

x === y mod N

Question 2

If x === y mod N and a === b mod N, then …

Answer 2

(x + y) === (a + b) mod N

and

xy === ab mod N

Question 3

Euclid’s Rule: If x >= y > 0, then gcd(x, y) = …

Answer 3

gcd(y, x mod y)

Question 4

How do we use Euclid’s Rule to to find gcd(x, y)?

Answer 4

Euclid(x, y):
if y = 0: return x
return Euclid(y, x mod y)

So we recursively use that last line to make the problem smaller until y is 0.

Question 5

What is the key lemma for the Extended Euclid algorithm (with alpha and beta)?

Answer 5

If d divides both x and y and d = x * alpha + y * beta for integers alpha and beta, then d = gcd(x, y)

Question 6

What is the Extended Euclid algorithm for computing d = gcd(x, y) and returning the integers alpha and beta such that d = xalpha + ybeta?

Answer 6

ExtEuclid(x, y):
Input: x >= y >= 0
Output: Ints d, alpha, and beta such that d = gcd(x, y) and d = xalpha = ybeta

if y = 0: return (x, 1, 0)
d, alpha’, beta’ = ExtEuclid(y, x mod y)
return (d, beta’, alpha’ - floor(x/y) * beta’)

Question 7

Modular Exponentiation Algorithm

Answer 7

ModExp(x, y, N):

inputs: x, y, and N such that x, y, N >= 0
output: x^y mod N

if y = 0: return 1
z = ModExp(x, floor(y/2), N)
if y is even: return z^2 mod N
else: return x * z^2 mod N

Question 8

How do we compute the multiplicative inverse of x mod N, i.e. x^(-1) mod N?

Answer 8

Run ExtEuclid(x, N). This gives you d, alpha, beta. x^(-1) === alpha mod N.

Question 9

Fermat’s Little Theorem (!!!!)

Answer 9

If p is prime then for every z in 1…p-1, z^(p-1) === 1 mod P, i.e. gcd(z, p) = 1.

Question 10

What is Euler’s totient function?

Answer 10

phi(N) = (p-1)(q-1) for primes p and q such that N = pq. It gives the number of integers in 1…N-1 that are relatively prime to N.

Question 11

Euler’s Theorem

Answer 11

Generalization of Fermat’s Little Theorem to all integers.

For N, z such that gcd(z, N) = 1, then z^phi(N) === 1 mod N.

Question 12

What is the key idea of the RSA algorithm?

Answer 12

Let p be prime. Take b and c such that bc === 1 mod (p-1). This implies bc = 1 + k(p-1) where k is some integer.

This implies we can take a number z in 1…p-1 and do z^(bc) === z^(1 + k(p-1)) === z * z^((p-1)^k) === z mod p. This is because z^(p-1) === 1 mod p, so z^((p-1)^k) === 1^k === 1 mod p.

You can therefore encrypt z by raising to the power b and decrypt by raising that to the power c! However, you need to share the key p.

For a better approach, we replace Fermat’s Little Theorem with Euclid’s Theorem. For primes p and q, let N = pq. Choose d, e such that d*e === 1 mod (p-1)(q-1).

Then z^(de) === z * (z^((p-1)(q-1)))^k === z mod N. This is because z^((p-1)(q-1)) === 1 mod N.

Now we can encrypt by raising z to e, decrypt by raising that to d, and we only have to share N and e! And no one can work out d from that, because they’d need to find p and q from N.

Question 13

What are the public and private keys for RSA?

Answer 13

Public: (N, e)
Private: d

Question 14

What is a (relatively) quick way to check whether a number is prime?

Answer 14

If we want to know whether N is prime, we check whether it is divisible by each m s.t. 1 < m <= sqrt(N)

Question 15

When does a multiplicative inverse exist?

Answer 15

There exists some x^(-1) mod N iff gcd(x, N) = 1.