RSA

Question 1

What is Euler’s Totient?

Answer 1

The Euler Totient is the number of integers for which the gcd of two numbers is equal to 1
In normal English - How many numbers less than n don’t share any factors with n, except 1.

Question 2

What is integer factorisation?

Answer 2

It’s the term that governs representing numbers using only their primes e.g. 2, 3, 5 to represent 22 e.g. 2 * 11

Question 3

How do you calculate Euler’s Totient?

Answer 3

• Break down your original number into the smallest prime numbers you can e.g. 240 = 2^4 * 3 * 5
• Then, for each number, subtract the power below it e.g. 2^4 - 2^3, 3 - 1 as 3^1 goes to 3^0 = 1
• Multiply them all together to get Euler’s Totient

Question 4

How does RSA generate their keys?

Answer 4

• Choose two large primes, p and q
• Calculate the modulus n (n = p * q)
• Calculate Euler’s Totient for n, so that euler(n) = (p - 1) * (q - 1)
• Choose a public exponent, called e, where the gcd(euler(n), e) = 1
• Compute d where d * e is equivalent to 1 mod euler(n) using the Extended Euclidean Algorithm
• The public key is then (e, n) and the private key is (d)

Question 5

How does RSA both encrypt and decrypt data?

Answer 5

• Get the data e.g. x = 74
• Set an equation to be: y = x^(e in the public key) mod (n in the public key) = z
• Decrypt to original x by following: x = z^(d from private key) mod (n from public key)

Question 6

How is RSA secure?

Answer 6

• Modular exponentiation is one-way. It’s easy to encrypt data, but extremely difficult to decrypt that data without knowing the private key, which is calculated from knowing Euler(n)
• There is no efficient factoring algorithm out there that could remotely break the factor problem in a reasonable time