RSA

Question 1

What is the key generation for RSA?

Answer 1

1. Pick two large prime numbers p and q
2. Let n = pq (the modulus)
3. Compute (p-1)(q-1)
4. Find a number e which is coprime/relatively prime with (p-1)(q-1). e is also called the public exponent.
5. Compute the multiplicative inverse d of e modulo (p-1)(q-1). d is also called the private exponent.

Question 2

How do you encrypt a message (m) using RSA?

Answer 2

m^e mod n
Where:
m = message
e = public exponent
n = the modulus

Question 3

How do you decrypt a ciphertext (c) using RSA?

Answer 3

c^d mod n
Where:
d = private exponent
n = the modulus

Question 4

If x is the multiplicative inverse of y then:

Answer 4

x * y = 1

Question 5

If x is y’s multiplicative inverse modulo n if:

Answer 5

(x * y) mod n = 1

Question 6

Is RSA secure?

Answer 6

Brute force attacks are infeasible for large numbers.
The most efficient way to attack RSA is by factoring n the modulus as this would get you p and q and allow you to calculate everything else. However factoring integers is intracteable

Question 7

Define relatively prime for x and y:

Answer 7

Two integers x and y are relatively prime if their greatest common divisor is 1

Question 8

What are the two types of MACs for hashing?

Answer 8

1. Combine hashing with a secret key. Constructed with help from a hashing function
2. Build the MAC from a block cipher