다메카솔

RSA 암호는 공개키 암호시스템의 한 종류이다.

전자서명이 가능한 최초의 알고리즘으로 알려져 있으며 전자 상거래 등에 널리 사용되고 있다.

방식

RSA는 두 개의 키를 사용한다.

공개키는 모두에게 알려져 있으며 메시지를 암호화 하는데 사용되며, 개인키를 가진 자만이 복호화하여 열어볼 수 있다.

암복호화에 서로 다른 종류의 키를 사용하여 같은 암호를 사용하는 방식과 구분하여 비대칭암호라고 부르기도 한다.

키의 생성에는 소인수 분해의 난해함을 이용하는데, 알고리즘은 다음과 같다.

두 수를 곱하여 N = pq 을 찾는다.
파이(N) = (p-1)(q-1) 를 구한다.
파이(N) 보단 작고, 파이(N)와 서로소인 정수 e를 찾는다.
확장된 유클리드 호제법을 이용하여 d X e를 파이 (N)로 나누었을 때 나머지가 1인 정수 d를 구한다.

알고리즘에 사용하는 파이(n) 함수는 오일러 파이함수라고 하여

n이 양의 정수일 때, n과 서로소인 1부터 n까지의 정수의 개수를 새는 함수이다.

참고자료

https://ko.wikipedia.org/wiki/RSA_%EC%95%94%ED%98%B8

https://ko.wikipedia.org/wiki/%EC%98%A4%EC%9D%BC%EB%9F%AC_%ED%94%BC_%ED%95%A8%EC%88%98