L7 (Cryptography and RSA)

Question 1

Suppose Alice wants to encode a message x with her encoding function e(x) so that bob can decode the message with his decoding function d(e(x)) = x to get back x

• What do Alice and Bob have to do in a private key scheme to establish this
• What is a famous example of a private key scheme

Answer 1

• Alice and Bob will have to “meet” beforehand to establish the secret decoding function d(.)
• AES (advanced encryption standard) is a common practice for this

Question 2

What does it mean for a function f : {0, 1, ... , m} → {0, 1, ... , m} to be “invertible”?

Answer 2

A function f is invertible (also called a bijection) if for every y in {0, 1, … , m}, there is an x in {0, 1, … , m} such that

f(x) = y

That is, there is a 1:1 mapping between the domain and range of the function

Question 3

Briefly describe a public key Cryptography scheme (RSA) for Alice and Bob sending private messages

Answer 3

• Each person has a public key known to the world and a private key known only to him/her
• When Alice wants to send Bob a message:
  1. Alice encodes it using Bob’s public Key
  2. Bob decodes it using his private key

Question 4

Suppose we pick two prime numbers p and q, and let N = p*q. Suppose that:
- N = p*q
- e is a number such that GCD(e, (q-1)*p-1)) = 1
- x is in {0, … , N-1}

• What can we now say about the mapping from x → x^e mod N?
• How would you define the inverse mapping of x → x^e mod N given a decoder d?
• How would d be found?

Answer 4

• The mapping x → x^e mod N? is invertible on {0, 1, … , N-1}. This means that there is a bijection from x to x^e mod N
• The inverse mapping is: (x^e)^d mod N = x, so we can get back x from x^e using d, and N.
• d is the multiplicative inverse of e mod (p-1)(q-1). this is true for 0 <= x <= N-1. It is found using the extended euclid algorithm

Question 5

Describe in detail the 3 steps of how RSA works

Answer 5

1. Bob choses public key (N, e) and a secret key d
   
   1. Picks two large n-bit primes p and q
   2. Public key is (N, e) where N = p * q and gcd(e, (p-1) * (q-1)) = 1
   3. secret d is multiplicative inverse of e mod (p-1)(q-1), computed with extended-euclid
2. Alice wishes to send a message x to Bob
   
   1. Looks up the public key (N, e)
   2. sends y = x^e mod N, computed using modexp
3. Bob decodes the message y by computing y^d mod N

Question 6

What are the 3 keys/values which are publicly transmitted in RSA?

Answer 6

1. N
2. e
3. y (encoded message)

Question 7

What assumption does RSA rely on to make it so secure

Answer 7

it is computationally infeasible to determine the original message x from y = x^e mod N without the decoder d