created at 2022-05-10

Generate A’s RSA public/private key

1. A generate random prime number p,q = 53, 59
2. n = p*q = 3127
3. Φ(n) = (p-1)*(q-1) = 3016
4. A generate random number k = 2
5. A generate small public exponent e (must be odd number and not share factors with n) = 3
6. d(priv_key) = (k * Φ(n) + 1) / e
7. pub_key = e, n = 3, 3127
8. priv_key = d = 2011

• Notation
  • m : plain text
  • c(m) : cipher text
  • e,n : public key

    n = p * q

  • d : private key, = (k * Φ(n) + 1) / e

    which is e*d ≡ 1 mod n
( k(p-1)(q-1)+1 ) mod n ≡ ( 1 mod n + k(p-1)(q-1) mod n ) mod n

  • e : odd number and not share factors with n, { gcd(e,n) = 1 }
  • k : random number
  • φ(n)≡ ∣ { m : 1 ≤ m ≤ n, gcd(m,n) = 1 } ∣ ( n ∈ N )

    if n = prime_number_1 * prime_number_2, then φ(n) = φ(prime_number_1)*φ(prime_number_2) = (prime_number_1 - 1) * (prime_number_2 - 1)

How can we get m(plain text) from c(m)(cipher text)?

Remind that in RSA, c(m) = m^e (mod n). From now, I will say c(m) is c. We can simply power d to c and add mod n.

c^d (mod n)

= m^(e*d) (mod n)[1]

d = (kΦ(n)+1)/e
= (kΦ(pq)+1)/e (mod n)
= (kΦ(q)Φ(q)+1)/e (mod n)
= (k(p-1)(q-1)+1)/e (mod n)

= m^(k(p-1)(q-1)+1) (mod n)[2]
= [ (1)(m (mod n)) * (2)m^(k*(p-1)*(q-1))(mod n) ] (mod n)[3]

(2-1)m^(k*(p-1)*(q-1))(mod n) = m^(k*(p-1)*(q-1))(mod pq) With chinese remainder theory, we should know pq (mod p), pq (mod q)
x ≡ a (mod m) and x ≡ a(mod n) implies x ≡ a (mod mn) if m and n are two relative prime positive integers.
in our case, x will be m^ed, a will be m
(we want to show that m^ed = m mod n).

(2-2)m^(k*(p-1)*(q-1)) (mod p) = 1 (mod p)
(2-2)m^(k*(p-1)*(q-1)) (mod q) = 1 (mod q) Fermat’s little theorem
Thus, m^(k*(p-1)*(q-1)) = 1 (mod pq), so (2) = 1 (mod n)

Finally!!,

[3] = (1) * (2) = ( m mod n * 1 mod n ) mod n

= m mod n !!!!!

Its a long journey to proving RSA encryption/decryption!

# Final equation is m = c^d (mod n)

So can attacker decrypt message or change cipher text that encrypted with RSA? The answer is YES! Here is an example.

A,B are communicating each other and ‘Me’ wants to seize and decrpyt message.

1. A send c = encrypt(m, B’s pub_key:n,e) to B
2. B get m = decrypt(c, B’s priv_key:d)
3. Here ‘Me’ seize c. and send c' = c * r^e(r:arbitrary value) to B.
4. ‘Me’ get c'^d = (c * r^e)^d = (m*r)^(e*d) from B. Because B can not understand the message.

   Plz remind that, ed = (k * Φ(n) + 1) and

5. message from B = (mr)^(ed), now with mod n, => m*r.
6. we can get m! as we already know about r value.

To prevent these attack, message is padded with arbitrary number. This is called OAEP. OAEP make same sequence of message with different paddings, so attacker cannot see the plain text(because it is salted!).

Padding Scheme(RSA- OAEP) Optimal Asymmetric Encryption Padding

MGF : mask generating function

Input words(variable length) -> Output string(desired length)

ex) MGF1

1. Hash the label L using the chosen hash function Hash(L)

   L is an optional label to be associated with the message (the label is the empty string by default)

2. Generate a padding string PS. length : k-mLen -2*hLen -2, value : 0x00
3. Concatenate! DB = Hash(L) || PS || 0x01 || m

   m is the message to be padded.

However, OAEP has an vulnerability such as Padding Oracle Attack. In RSA-PKCSv1.5, it is seriously issued. PKCS#1 v1.5 padding should be replaced wherever possible!.

Now secure padding schemes such as RSA-PSS are as essential for the security of message signing as they are for message encryption.

Padding Scheme(RSA-PSS) probabilistic signature scheme

Padding Scheme3(RSAES-PKCS1.5)

Encoding

1. Pain Text = ‘HI’
2. Convert letters to numbers : H = 8 and I = 9
3. Encrypted Data c(m) = m^e (mod n) = 89^3 (mod 3127) = 1394
4. Decrypted Data m(c) = c^d (mod n) = c^2011 (mod 3127) = 89

Notice!

1. The padded message(in this case, 89) cannot be longer than the modulus(3127), which implies a strict maximum length on the raw message.
2. 2 padding scheme : RSAES-OAEP, [RSAES-PKCS1-v1_5]

References

1. RSA-OAEP choosen cyphertext attack