#9. RSA 암호 시스템

 

1. 공개키 암호 & RSA 암호 2. RSA 암호 안전성

 

 

1. RSA 암호

1.1 공개키 암호

- 공개키 암호 (Asymmetric Key Encryption, Public Key Encryption)

  -> 암호화 키와 복호화 키가 다르다

-암호화 방식

  ->  수신자가 암호화 키(공개키)를 공개한다.

  ->  전송자는 해당 공개키로 암호문을 생성한다. 

  ->  수신자는 자신의 개인키(복호화 키)로 암호문을 복호화한다.

- 수신자의 공개키로부터 개인키를 알아내는 것이 어려워야 한다.

- RSA, ElGamal, ECC, ...

 

 

 

1.2 수학적 배경

https://yenas0.tistory.com/55

#2-1. 기초 정수론(2)

 

 

위의 기초 정수론 부분을 기초로 한다.

 

Group

Group의 정의 공집합이 아닌 집합 G와 G의 원소에 대해 다음을 만족하는 연산 ⊗가 정의되면 (G, ⊗)를 Group이라고 부른다 -  [ ⊗에 대한 결합법칙] -  [ ⊗에 대한 항등원 존재] -  [ ⊗에 대한 역원 존재]

 

- Abelian group

: Group (G, ⊗)에서 연산 ⊗에 대해 교환법칙이 성립하는 경우를 말함 ( a⊗b = b⊗a)

- Group order (위수)

: Group G의 원소개수, |G|로 표기

: |G| = l (유한 위수) -> 모든 G에 속한 g에 대해 g^l = 1

 

 

1.3 RSA 암호 시스템

: 소수 p와 q에 대해, n = pq인 경우 아래가 성립

 

- Zn*는 group

- Zn*에 속한 m과 정수 e에 대해, Zn*에서 거듭제곱 m^e 이 잘 정의됨 (mod n 곱셈 연산)

- |Zn*| = ϕ(n) = ϕ(p x q) = (p - 1)(q - 1)

 

 

RSA 에서 m이 메시지, e가 공개키, d(e의 mod ϕ (n)에 대한 곱셈의 역원) 가 개인키가 된다.

암호화 : c = m^e (mod n) 복호화 : c^d = m^(ed) = m^{ed(mod ϕ(n))} = m (mod n)

 

 

예시

공개키와 개인키	p = 5, q = 11 선택 n = 55, ϕ(n) = 4 x 10 = 40 e = 3 선택 (gcd(3,40) = 1) d = 27 = e^(-1) (mod 40) 공개키 = (n, e) = (55, 3) 개인키 = (p, q, d) = (5, 11, 27)
암호화	m = 2에 대해 c = m^e = 2^3 = 8 (mod 55)
복호화	c  = 2^3 = 8 (mod 55)에 대해 c^d = 8^27 = 2 (mod 55)

 

 

 

 

1.4 Zn 에서 지수승 연산

: Zn에 속한 c와 0< 

d < ϕ(n)에 대해, c^d을 빠르게 계산하기

- Square & Multipy (exponentiation by squaring)

  : 약 2logd 번 곱셈으로 지수승 연산

  : c^d에서 d를 이진수로 표현

  : 비트 별로 읽어가면서 제곱 및 곱하기 연산을 통해 계산

 

 

 

2. RSA 암호 안전성

https://yenas0.tistory.com/65

#3-2. 암호 안전성과 공격 모델

공격자 모델에 대한 글을 읽고 오면 용어 이해에 도움이 됨

 

 

2.1 공개키 암호가 기본적으로 고려해야 하는 공격자 모델

- 공개키 암호에서는 공격자가 임의의 메시지에 대해 암호문을 생성할 수 있음

(즉, 공격자는 CPA가 항상 가능)

- RSA의 경우 공개키가 누구에게나 공개되므로 공격자가 임의의 메시지 m에 대해 암호문을 생성할 수 있음

- 따라서 공개키 암호는 기본적으로 CPA공격에 안전하게 설계하는 것이 필요함

 

 

2.2 공개키 암호에 대한 중간자 공격

- 공개키 암호의 가장 큰 문제점

: 공개된 공개키가 진짜 공개키 주인의 것인지 확인할 수 없음

- 공개키 주인을 인증하는 시스템 필요 (공개키 인증서)

 

 

2.3 RSA 암호 안정성 기반 문제

- RSA 암호 안전성은 아래 3가지 문제를 고려하는 것이 필요

RSA 문제 공개키와 암호문이 주어졌을 때, 평문을 찾는 문제

RSA 비밀키 문제 공개키가 주어졌을 때, 개인키를 계산하는 문제

인수분해 문제 두 개의 임의의 큰 소수 p와 q에 대해 n (=p x q) 이 주어졌을 때, n을 소인수 분해하여 p와 q를 계산하는 문제

 

- 인수분해 문제를 해결할 수 있다면, RSA 비밀키 문제와 RSA 문제를 해결할 수 있음

 

 

 

RSA OAEP

- OAEP (Optimal Asymmetric Encryption Padding)

- 결정론적 공개키 암호시스템을 비결정론적 공개키 암호시스템으로 변환하는 메커니즘을 제공 (같은 메시지에 대해서도 다른 암호문이 생성되도록, c.f. Textbook RSA)

- 우리가 실제로 사용하는 RSA임

- CCA 공격에도 안전함이 증명됨

- RSA메시지 파트에 랜덤 비트열을 추가하여 같은 평문에 대해 암호문이 달라지게 되는 구조