RSA 암호화 원리

created at 2024-09-01

RSA 암호화/복호화 과정 설명함.

1. 기본 설정

소수 p, q: 53, 59
n: p*q = 3127
Φ(n): (p-1)*(q-1) = 3016
k: 임의 숫자, 2로 설정함.
공개 지수 e: 작은 홀수로 n과 공약수 없게 설정만 하면 됨. 여기서는 3으로 설정해봄
비밀 키 d: (k * Φ(n) + 1) / e = 2011

공개 키 e와 n (3, 3127). 비밀 키 d = 2011.

2. RSA 암호화

평문 m -> 암호화 c(m) : c(m) = m^e (mod n)

3. RSA 복호화

암호문 c(m) -> 평문 복호화 : m = c^d (mod n)

d 비밀 키. e*d ≡ 1 mod n 만족함.

4. RSA 복호화 원리

복호화 과정 수학적으로 증명함.

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)

즉, d = (k(p-1)(q-1)+1)/e (mod n)

이렇게 생긴 d 를 m = c^d (mod n) 식에 대입하면?

= m^(e*d) (mod n)
= m^(k(p-1)(q-1)+1) (mod n)
= (m^(k(p-1)(q-1)) mod n) * (m mod n)

여기에 페르마의 소정리, 중국인의 나머지 정리 적용

m^(k(p-1)(q-1)) (mod p) = 1 (mod p)
m^(k(p-1)(q-1)) (mod q) = 1 (mod q)

결론:

m^(k(p-1)(q-1)) = 1 (mod pq)
m = c^d (mod n) = m mod n

결국, m = c^d (mod n) 성립, 평문 m 얻을 수 있음.

5. Example

Apple oauth 를 예시로 들면, apple 은 idToken 을 주고 RSA 로 사이닝해서 보냄. 이때, idToken 을 받은 서버는 Apple 공개키로 사인을 확인해야함.

Apple 은 자신의 공개키를 아래처럼 제공함. (RSA-SHA256 으로 제공)

{
  "keys": [
    {
      "kty": "RSA",
      "kid": "T8tIJ1zSrO",
      "use": "sig",
      "alg": "RS256",
      "n": "teUbLrwScsjVrcFAvSrfben3eQaEca3ESBegGh_wdGuLKw6QgwDxY3fC1_WeSVnkJXx72ddw3j2inoADnTyzuNa_PwDSmvJhOhmzOmoltmtKHteGdaXrqMohO6A85WxVKbN7pzDqwZJNrdY12LOltlI8PHIG-elAbKM2XOHiJaZnLpAVckKy6MQYsEExpPB3plGxWZElqwNZY6SUDVeN-o9qg5FJOFg7T7iTVVEagws4DM6uZNMDQGtqg9V9VqPQkUzC-sYd5eqbB9LqH4iN5F6OB7BmD3g3jCu9zgh3O9V24N43EruBCNrmP0xLP5ZliKqozoAcd1nv71HuVm6mgQ",
      "e": "AQAB"
    },
    {
      "kty": "RSA",
      "kid": "FftONTxoEg",
      "use": "sig",
      "alg": "RS256",
      "n": "wio-SFzFvKKQ9vl5ctaYSi09o8k3Uh7r6Ht2eJv-hSaZ6A6xTXVIBVSm0KvPxaJlpjYPTCcl2sdEyXlD2Uh1khUKU7r9ON3rpN8pFHAere5ig_JGVEShxmt5E_jzMymYnSfkoSW44ulevQeUwP_MiC5VC1KJjTfD73ghX0tQ0-_RjTJJ2cLyFC4VFNboBMCVioUrz8IA3c0KIOl507qswQvMsh2vBTMDDSJfippAGLzUiWXxUlid-vyOC8GCtag61taSorxCw14irk-tsh7hWjDDkSTFn2gChPMfXXj10_lCv0UG29TVUVCAsay4pszzgmc4zwhgSsqQRd939BJexw",
      "e": "AQAB"
    },
    {
      "kty": "RSA",
      "kid": "pggnQeNCOU",
      "use": "sig",
      "alg": "RS256",
      "n": "xyWY7ydqTVHRzft5fPZmTuD9Ahk7-_2_IekZGy07Ovhj5IhYyVU8Hq5j0_c9m9tSdJTRdKmNjMURpY4ZJ_9rd3EOQ_WnYHM2cZIQ5y3f_WxeElnv_f2fKDruA-ERaQ6duov-3NAXC3oTWdXuRGRLbbfOVCahTjvnAA8YBRUe3llW7ZvTG14g-fAEQVlMYDxxCsbjtBJiUzKxbH-8KvhIhP9AJtiLDfiK1yzVJ7Qn6HNm5AUsFQKOAgTqxDMJkhi7pyntTyxhpkLYTEndaPRXth_LM3hVmaoFb3P3TsPCbDjSEbKy1wAndfPSzUk6qjyyBYhdXH0sgVpKMBAdggylLQ",
      "e": "AQAB"
    }
  ]
}

여기서 Apple 은 주기적으로 키쌍을 바꾸고, 여러개의 키로 관리하기떄문에 각 키 별 유니크판 kid 가 있음. 그래서 idToken 헤더에 kid 값이 같이 오는데 이에 해당되는 e, n 값으로 증명하면 됨.

이제 증명 과정은 다음과 같이 간단하게 가능.

idToken 을 base64 decode 하면 m, c(m), kid 를 알 수 있음
apple pubKey 중 kid 일치하는 e, n 값 가져옴.
c(m) 에 ^e (mod n) 하면 m’ 값이 나옴. 여기서 m’ == sha256(m) 값이면 사인이 valid 하다고 판단 후 신뢰하면 됨.