Mod/RSA

Question 1

What does it mean if x mod N = r?

Answer 1

It means that for some q=x/N, qN + r = x

Question 2

What does it mean for two numbers, a and b, to be relative prime?

Answer 2

a and b are relative private if gcd(a,b) = 1

Question 3

What is a greatest common divisor of two numbers, a and b

Answer 3

It is the largest number that evenly divides both a and b. For example, 4 is the GCD of 12 and 16

Question 4

What is x mod 2 for odd and even numbers?

Answer 4

0 for even numbers. 1 for odd numbers.

Question 5

x ≡ y (mod N) means what?

Answer 5

It means that x and y have the same remainder when divided by N. For example 10 ≡ 22 (mod 3) because 10/3 = 3 and 1/3 and 22/3 = 7 and 1/3.

Question 6

What is the additive property of a, b, c, and d if a ≡ b (mod N) and c ≡ d (mod N)?

Answer 6

a ≡ b (mod N) and c ≡ d (mod N), then:

a+c ≡ a+d ≡ b+c ≡ b+d (mod N)

Question 7

What are the subtraction properties of a, b, c, and d if a ≡ b (mod N) and c ≡ d (mod N)?

Answer 7

a ≡ b (mod N) and c ≡ d (mod N), then:

a-c ≡ a-d ≡ b-c ≡ b-d (mod N)

Question 8

What are the multiplicative properties of a, b, c, and d if a ≡ b (mod N) and c ≡ d (mod N)?

Answer 8

a ≡ b (mod N) and c ≡ d (mod N), then:

ac ≡ ad ≡ bc ≡ bd (mod N)

Question 9

True or False? If a ≡ b (mod N), this implies ka ≡ kb (mod N) for any integer k.

Answer 9

True!

Question 10

True or False? If a ≡ b (mod N), this implies a^k ≡ b^k (mod N) for any integer k.

Answer 10

False. This is only true for any natural number k (not integer).

Question 11

If a ≡ b (mod N), what operations can you perform to both a and b after which this equivalence still holds?

Answer 11

• a^k ≡ b^k (mod N) for any natural number k
• ka ≡ kb (mod N) for any int k
• a + k ≡ b + k (mod N) for any int k

Question 12

If a ≡ b (mod N) and c ≡ d (mod N) and a + b = c, what does this imply? What about if a*b = c? Provide an example of each.

Answer 12

• a (mod N) + b (mod N) = c (Mod N)
  example: 5 ≡ 13 (mod 4) and 5 + 13 = 18 => 5 (mod 4) + 13 (mod 4) = 18 (mod4) –> 1 + 1 = 2
• a (mod N) * b (mod N) = c (Mod N)
  example: 5 ≡ 13 (mod 4) and 5 * 13 = 65 => 5 (mod 4) * 13 (mod 4) = 65 (mod4) –> 1*1 = 1

Question 13

Fermat’s Little Theorem

Answer 13

r is a prime number iff a^{r-1} ≡ 1 (mod r) for 1 <=a <= r-1

If p is a prime number:
a^p ≡ a (mod p)
a^{p-1} ≡ 1 (mod p) for 1 <= a <= p-1
a^{p-1} ≡ 1 (mod p) if a mod p != 0
a^{p-1}k ≡ 1 (mod p) if a mod p != 0 and any natural number k

For RSA (leads to Euler's Theorem in RSA)
If p is a prime number:
bc ≡ 1 (mod p-1)
bc = 1 + k(p-1) for some integer k
z^bc = z*z^{p-1}k ≡ z*1 (mod p)

Question 14

What is multiplicative Inverse mod N and when does it exists for some number, x?

Answer 14

Exists iff x and N are relatively prime. This means gcd(x,N) = 1.
It is a number that you can multiply x by such that x * x^{-1} ≡ 1 mod N.

Question 15

Euler’s totient function

Answer 15

N=pq where p and q are distinct prime numbers. Denote phi(N) as number of x’s such that 1<=x<=N such that gcd(N,x) = 1.

• How many numbers from 1 to N are relatively prime to N? (p-1)(q-1)

So phi(N) = (p-1)(q-1)

Question 16

Euler’s Theorem

Answer 16

N=pq where p and q are distinct prime numbers. If a,N are relatively prime:

a^phi(N) ≡ 1 (mod N)
Which means:
a^{(p-1)(q-1)}k ≡ 1 (mod pq)

Question 17

Extended Euclid’s Algorithm

Answer 17

egcd(x,y):
if y=0: return x,1,0
d,a’,b’ = egcd(y,xmody)
return (d,b’,a’ - [x/y]b’)

Question 18

RSA Logic using Euler and Fermat

Answer 18

N=qp where q and p are distinct prime numbers
If z,N are relatively prime:
de ≡ 1 (mod(p-1)(q-1))
de ≡ 1 + k(p-1)(q-1) for some integer k
z^de ≡ z^{1 + k(p-1)(q-1)} ≡ z (mod N)

Encrypt: E = M^e (mod N)
Decrypt: M = E^d (mod N)

Question 19

What does phi(p^k) equal if p is prime and phi=quotient function if k>=1?

Answer 19

phi(p^k) = p^k (1 - 1/p)