[RSA - 1] 모듈로 연산 (Modulo)
모듈로 연산 (Modulo)
암호학을 공부하다 보면 빠지지 않고 나타나는 연산이 있다. 바로 모듈로 연산이다.
RSA에 대해 알아보기 전 알아야 할 기본 개념들부터 알아보자. 처음엔 이런 내용을 굳이 왜 알아야 하지? 라는 생각이 들겠지만 미리 알아두면 RSA를 이해하는데 도움이 될 것이다.
- 모듈로 연산이란?
모듈로 연산은 나머지를 구하는 연산이다. 보통 시간 계산에 비유해서 설명한다.
10시 + 3시 = 1시 (?)
12시간 format을 사용한다고 했을 떄 10시 + 3시는 13시가 아니라 1시가 된다. 일반적인 사칙연산 개념으론 불가능하지만 모듈로 연산으로는 가능하다. 이를 수식으로 표현하면 다음과 같이 표현할 수 있다.
- 모듈러 연산의 필요성
그렇다면 모듈러 연산은 왜 하는걸까? 암호학에서는 매우 큰 정수를 사용한다.
큰 정수를 사용하면 컴퓨터의 자원사용과 연산속도에 영향을 준다. 하지만 모듈러 연산을 정수의 범위를 제한할 수 있다. 큰 정수 a를 N으로 모듈러 연산하면 아래처럼 정수의 범위가 축소되어 사칙연산하기가 쉬워진다.
- 모듈러 역수 (역원)
RSA에서 꼭 필요한 개념이다.
어떤 수 A를 역수 $ \frac1A $와 곱하면 1이 된다. 이때 $ \frac1A $는 A의 역수라고 한다.
모듈러 연산에서 $ (A \times B) \equiv 1 \bmod\,N $이 성립하는 정수 B를 모듈러 역수라고 한다.
이때 모듈러 역수의 범위는 $ 0 \le B \le N-1 $이다.
모듈러 역수를 구하는 방법은 간단하다. B값이 나올 때 까지 하나하나 계산해보는거다.
0 ~ N-1 까지의 값 B에 대해 $(A \times B)\bmod\,N $ 을 계산하여 $(A \times B) \equiv 1 \bmod\,N $가 성립하는 B를 구한다.
1
2
3
4
5
6
7
3 * 0 = 0 (mod 7)
3 * 1 = 3 (mod 7)
3 * 2 = 6 (mod 7)
3 * 3 = 2 (mod 7)
3 * 4 = 5 (mod 7)
3 * 5 = 1 (mod 7)
// 7의 모듈러 역수 B는 5가 된다.
위의 예시는 N이 7로 작은 정수였지만, 실제로 암호에 사용되는 정수 N은 훨씬 크기 때문에
이렇게 하나하나 대입해보는 방식은 느리고 비효율적이다.
그래서 모듈러 역원을 더 빨리 찾기 위해 다음에 포스팅할 확장 유클리드 호제법을 사용한다.