RSA 알고리즘 문제 - RSA algolijeum munje

공개키 암호 알고리즘1: RSA

7.1.1 가장 많이 사용되고 있는 공개키 암호시스템
- Rivest, Shamir, and Adleman 의 이름에서 RSA
- Clifford Cocks, an English mathematician working for the UK intelligence agency, described an equivalent system in 1973, but it was mostly considered a curiosity and, as far as is publicly known, was never deployed. His discovery, however, was not revealed until 1998 due to its top-secret classification, and Rivest, Shamir, and Adleman devised RSA independently of Cocks' work.

- 이 때, (e, n)은 public-key 이며, (d, n)은 private-key이다.
- e와 d는 서로 역원 관계이다.

1) 메시지 m에 대하여 m^{d}을 수행하는 것은 나만 할 수 있다.
- d는 나만의 개인키이기 때문이다.
- 이것을 사용하여 전자서명을 구현한다.
- m^{e} = c, c^{d} = m이므로, m^{de} = c^{d} = m이다.
=> m^{d}에 대하여 내 공개키를 적용함으로써, 즉 m^{d}에 대하여 ^{e}를 한 것이 m인지 확인할 수 있다.

2) 우리가 사용하는 공인인증서는 "암호화 인증서"가 아니라, 위 (1)과 같은 "서명 검증용 인증서"이다.
- SSL 서버와 같은 보안 서버에 발급하는 인증서가 "암호화 인증서"이다.

7.1.4 RSA 암호의 정확성(Correctness)

7.1.5 RSA 암호의 안전성
- RSA 문제는 c ≡ m^{e}가 주어졌을 때 e-th root를 구하는 문제로 볼 수 있다.

1) 인수분해 문제를 풀 수 있으면, RSA 문제를 풀 수 있다.
- n = p * q를 인수분해 하는 문제는, 오일러 함수 몇 e의 곱셈상의 역원 d를 계산하는 과정을 거쳐 RSA 문제를 푸는 문제로 대응될 수 있다.
- 즉, 인수분해 문제를 푸는 것이 RSA 문제를 푸는 것보다 쉽진 않다.

2) RSA 문제를 풀 수 있으면, 인수분해 문제를 풀 수 있을까?
- Not known yet
- RSA 문제를 푸는 것이 인수분해 문제를 푸는 것보다 쉽지 않다는 것을 아직 보이지 못했다.
- 즉 RSA 문제를 푸는 것이 안전하다고 아직 보이지는 못했다. (그러나 다들 안전하다고 생각한다.)

7.1.6 효율적인 RSA 암/복호화
- 두 소수 와 는 1024비트 이상의 수
=> , > 2048 비트
- 제곱-곱 연산 방법(Square-and-Multiply Method) : 지수가 2048 비트인 경우 2048번의 제곱과 평균 1024번의 곱셈

방법 1) 공개키 로 3, 17, 65537을 사용한다.
- 3 = 11(binary), 17 = 10001(binary), 65537 = 10000000000000001(binary)
- 3은 2번의 (제곱, 혹은 곱셈) 연산, 17은 5번의 연산, 65537은 17 번의 연산을 수행한다.
- 개인키 를 사용하는 복호화 과정을 현저하게 향상시키는 방법은 아직 존재하지 않는다.
- 모두가 똑같은 e를 사용해도, d는 e가 아닌 p, q에 의존하므로 괜찮다.

방법 2) CRT를 이용한 복호화

- 이 비트인 경우 CRT를 이용하는 경우의 연산은 /2 비트 수 들(즉 mod , 혹은 mod )의 제곱과 곱셈연산
- 기존 복호화 과정보다 약 4배 정도 향상
- CRT를 사용하지 않는 경우, p, q를 보관하지 않아도 괜찮았다. 하지만 CRT를 사용하는 경우 p와 q를 안전하게 보관할 필요가 있다.

7.1.7 RSA 암호에 대한 공격
1) 선택 암호문 공격(Chosen Ciphertext Attack)
- RSA가 갖는 "곱셈에 대한 준동형사상 (Homomorphism) 성질"을 이용한 공격이다.
=> Ciphertext 두 개를 곱하면, 평문 두개의 곱을 암호화한 것과 그 결과가 같다.

- Textbook-RSA에서만 가능한 공격이다.
- 공격자는 암호문 ∗의 평 문을 목표

2) 암호화 지수 e에 대한 공격
- 특정한 환경에서만 가능한 공격이며, Textbook-RSA에서만 가능한 공격이다.

3) 복호화 지수 d에 대한 공격
- d가 노출되면, 오일러 함수를 알 수 있다.
- 즉, 모든 파라미터(p, q, n, e, d)를 재생성해야 한다.

4) 평문 공격(Plaintext Attack), 순환 공격(Cyclic Attack)

- RSA는 mod 연산을 사용하여 평문 집합과 암호문 집합이 동일하다. 즉, mod 4를 사용하는 경우 평문 집합도 1, 2, 3 이며 암호문 집합도 1, 2, 3이다.
=> 암호는 평문 공간에 대한 치환이기 때문에 ck가 반드시 존재한다.
- 소인수분해와 동일한 복잡도를 가진다.
=> 이론적인 공격일 뿐이지, n의 크기가 굉장히 크기 때문에 사실상 불가능하다.

5) 공통 법 공격(Common Modulus Attack)
- 공격자는 두 수신자의 동일한 메시지의 두 암호문 1, 2 와 수신자의 공개키 1, 2가 서로소임을 알고 있다.

6) 부채널 공격
- difference를 측정한다.
(1) 시간차 공격(Timing Attack)

* 시간차 공격에 대한 방어 방법
1) 지수 계산 할 때 각각의 지수 계산에 동일한 시간을 걸리도록 만든다.
2) 암호문을 복호화하기 전에 난수를 곱하는 블라인딩 기법을 사 용한다.

(2) 전력차 공격(Power Analysis Attack)

7.1.8 RSA 이용 시 권고사항
1) n의 비트는 적어도 (서명의 경우) 2048비트가 되어야 한다.
2) 서로 다른 두 소수 p와 q는 적어도 1024비트 이상이 되어야 한다.
3) 서로 다른 두 소수 p와 q가 너무 가까이 있는 소수를 선택하지 않는다.
4) p − 1과 q − 1은 적어도 하나의 큰 소인수를 가져야 한다.
5) 비율 p/q 가 작은 분자나 작은 분모를 갖는 유리수와 가까이 있으면 안 된다.
6) n을 공통적으로 이용하지 않는다.
7) 공개키 e는 2^{16} + 1 = 65537을 이용하거나 혹은 65537과 가까이 있 는 값을 이용한다.
8) 만약 개인키 d가 노출되었을 경우, 수신자는 반드시 공개키 n과 e, 개인키 d를 즉시 교체해야 한다.
9) OAEP를 이용

7.1.9 OAEP(Optimal Asymmetric Encryption Padding)

7.1.10 RSAES-PKCS#1(v1.5)
1) 개요 및 특징
- Public-Key Cryptography Standard published by RSA Laboratories
- RSA를 사용하는 방법 등을 제시하는 de facto standard이다.
- 초기 PKCS#1 기술규격 공개키로 평문을 암호화하기 위한 EM(암호메시지) 구조 및 RSA 연산 방법이 기술되어 있다.

2) 보안성
- 1998년 Bleichenbacher는 선택된 암호문 공격을 통해 평문을 얻어낼 수 있는 확률을 높일 수 있었다.
- 실제 암호 공간이 1/2로 줄어드는 보안 취약점이 존재
- 현재 RSA를 가지고 암호화를 할 때에는 PKCS를 더 이상 쓰지는 않는다.