(3) RSA 암호시스템

(3) RSA 암호시스템

13. 감리, 08. 감리 13.2회 기사 14.4회.산기 1) 개요

(가) 기본 개념

① RSA는 공개키 암호 알고리즘의 중의 하나이며, 세계적으로 사실상의(de facto) 표준이다. RSA라는 이름은 개발자 세 사람의 이름 즉, Rivest-Shamir-Adleman의 첫 글자를

따서 붙여졌다.

인수분해 문제(Prime factorization) 해결의 높은 난이도를 이용한 가장 대표적인 공개

키 암호 알고리즘으로 암호화뿐만 아니라 전자서명의 용도로도 사용된다. ④ SSL 프로토콜을 가진 많은 웹 브라우저, PGP 그리고 공개키 암호시스템을 사용하는 정부시스템 등이 RSA를 사용한다.

(나) 암호화와 복호화

15.5회산기

① RSA에서는 두 개의 지수 e와 d를 사용한다. 여기서 e는 공개하는 값이고 d는 비밀로 유지하는 값이다. P는 평문이고 C는 암호문이다.

② 이때 Alice는 C=Pe mod n을 이용하여 평문 P에서 암호문 C를 생성한다. Bob은 암 호문 C에서 P=C" mod n을 구하여 Alice가 보낸 평문을 얻는다. 모듈러 n은 매우 큰 수이고 키 생성 프로세스를 통해서 만들어진다.

RSA의 암호화, 복호화와 키 생성

(다) 키 생성 7.10회 기사 15.6회산기 143회 기사

알고리즘

p와 라고 하는 두 개의 서로 다른 (pq) 소수를 고른다.

두 수를 곱하여 N=pg을 찾는다.

(N)=(p-1)(q-1)를 구한다. o(N)보단 작고, ø(N)과 서로소인 정수 e를 찾는다.

확장된 유클리드 호제법을 이용하여 dxe를 ø(N)로 나누었을 때 나머지가 1인 정수 d를 구한다. (de≡ 1 (modø(N))) .

만약 공개키 n과 e로부터 비밀키 d를 구할 수 있다면 RSA는 해독되게 된다. 이렇게 되기 위해서는 공개키 n으로부터 ø(n) = (p-1) (q-1)을 구해 내야 한다. p(n)을 구하게 되면 유클리드 알고리즘을 이용하여 쉽게 d를 구할 수가 있게 되므로 RSA 알 고리즘의 안전성은 n의 소인수 분해, 즉 p와 q를 구해 내는 것에 달려 있다.