[암호학] 공개키 암호 시스템, RSA

인트로

안녕하세요. 오늘은 공개키 암호 시스템인 RSA에 대해 포스팅해보겠습니다. 

RSA는 전자서명이 가능한 최초의 알고리즘인데요. 아래에 더 자세히 설명해드리겠습니다. 

 

목차
1) RSA 유래 
2) RSA 개념
3) RSA 알고리즘 배경, 소인수 분해는 어렵다.
4) RSA 구성 
- 목표, 과정, 예시

 

1) RSA 유래 
공개키 암호 시스템이고, 전자서명 (sign)이 가능한 최초의 알고리즘입니다.

RSA를 만든 사람들 Rivest/Shamir/Adleman 약자를 따서 RSA입니다. 

2) RSA 개념 
RSA알고리즘은 두개의 키 e,d를 사용한다. 공개키 e는 메세지를 암호화 할때 쓰이고, 비공개키 d는 메세지를 복호화할 때 쓰입니다.
공개키 알고리즘은 누구나 어떤 메시지를 암호화 할 수 있지만, 그것을 열 수 있는 사람은 비공개키를 지닌 단 한사람만 존재하는 알고리즘입니다.

3) RSA 알고리즘 배경, 소인수 분해

n = p × q라고 하자. (이때, n은 엄청나게 큰 합성수)
엄청나게 큰 수의 소인수 분해는 어렵다. 
그 소인수분해가 어렵기 때문에, 공개키 p 를 가지고 있더라도 q를 알아내기 어렵다.
RSA는 여기서부터 디자인되었다.

4) RSA 구성 
1) [n 구하기]

n = p × q   (이때, p와 q는 서로 다른 두개의 큰 소수)
e = public key (공개키)

2) 공개키와 개인키 구하기 [e, d 구하기]

목표  : 궁극적으로, gcd(e, (p-1)(q-1) = 1 인 e를 구하고 (e는 공개키), e × d = 1 mod (p-1) 인  d(개인키)를 구한다.

과정

(1) Φ(n) = (p - 1) * (q - 1) 식을 이용하여 Φ(n)을 구한다.

(2) Φ(n)과 서로소인 e를 정한다. 

(3) e × d = 1 mod (p-1) 를 이용해서 d를 구한다. 

 

[예시] p = 3, q = 17일때  e, d를 구해보자. 

이때 공개키는 (e, N), 즉 (e , 51) 이다.

(1) Φ(n) = (p - 1) * (q - 1) 에 의해  Φ(n)  = 2 * 16 = 32 이다.

(2) 32와 서로소인 임의의 e를 구한다.  

서로소란 , 1 이외에 공약수를 가지지 않는 수이다.

예를 들어, e = 13이라 하자. 

(3) e × d = 1 mod (p-1) 에서 d를 구한다.

e × d = 1 mod (p-1)를 이용하여 e × d 를

Φ(n)으로 나누었을 때, 나머지가 1인 d를 구한다.( 13 * d ) % 32  = 1 에서 d를 구할 수 있다. 

 

 

대칭암호 , 비대칭 암호 글 보러가기

https://life-with-coding.tistory.com/26?category=799521

[보안] 대칭 암호화, 비대칭 암호화 방식