RSA

기본 개요
        공개키 암호화 방식으로 공개키와, 비밀키를 가지고 암호화 하는 방식이다.
        공개키로 누구나 사용하여 파일을 암호화 시킬 수 있지만, 복호화(해독) 하기 위해선 비밀키가 필요한 암호화 방식이다.

RSA의 키를 생성하는 방법

1. 서로 다른 두 소수 p , q 를 구한다.
2. 값이 p × q인 N(=p × q)을 구한다.
3. (N) = (p-1)(q-1)를 구한다.                                          = phi
4. (N)보단 작고, (N)와 서로소인 정수 e를 찾는다.
5. 확장된 유클리드 호제법을 이용하여 d·e ≡ 1 (mod (N))

이를 통해 필요한 함수를 생각해 본다면

1. 소수를 찾는 함수
2. N=p×q, (N) = (p-1)(q-1)를 구하는 함수.
3. 제곱 승을 구할 수 있는 함수.
4. 서로소를 찾는 함수. 즉, 최대공약수를 구하는 함수.
5. mod (나머지 연산)을 구하는 함수.
6. 확장된 유클리드 호제법 함수.

이렇게 6가지 이다.

RSA의 키를 생성하는 순서에 따라
그에 필요한 함수 코드를 가지고 공부해보자.