[RSA 이해를 위한 몸부림 - 2] 모듈러 연산

모듈러 연산

모듈러 연산은 간단히 말하면 나머지를 구하는 연산이라고 볼 수 있다.

위 식에서 a는 피제수, b는 제수, c는 나머지 이다.

예를 들면, 26 mod 5 = 1 이 될 수 있을 것이다.

이해 되었다면 이제 모듈러 연산의 여러 특징을 정리하려 한다.

1. 합동

모듈러 연산에서 26 mod 5 나 36 mod 5 는 모두 똑같이 1로 같다.

이를 합동 이라는 개념으로 부를 수 있으며 표현은 이와 같이 한다.

1 ≡ 6 ≡ 26 ≡ 36 mod 5 = 1 

2. 성질

모듈러 연산에는 아래와 같이 좌변의 덧셈과 곱셈에 대해 분해할 수 있는 성질이 있다.

[1] (a + b) ≡ ((a mod n) + (b mod n)) mod n
[2] (a * b) ≡ ((a mod n) * (b mod n)) mod n

3. 모듈러 역원(역수)

RSA에서 꼭 필요한 개념. 물론 우리는 파이썬이나 openssl같은 툴들이 알아서 해주겠지만, 그래도 개념을 이해해보자.

모듈러 역수에는 덧셈에 대한 역수와 곱셈에 대한 역수 두 가지가 있는데 여기서는 곱셈의 역수에 대해서만 알아보자.

우리가 아는 일반적인 곱셈에서의 역수는 두 수를 곱했을 때, 1이 나오는 수이다.

모듈러에서는 ...

`a mod b = c` 에서 피제수 a가 `p * q` 와 같이 곱셈관계일때, 
어떤 정수 p에 대해 (p * q) ≡ 1 mod n 이 되는 수 q 를 모듈러 역수 또는 역원 이라고 한다.

처음에 이 개념을 배우면서 뭔가 좀 이해가 안되었었는데 예제를 한 번 보자.

모듈러에는 잉여류라는 개념이 있다. 굳이 한 항목으로 설명하지 않고 간단히 설명하자면, 모듈러 연산 mod n은 항상 결과가 0 ~ n-1 사이에서 나오게 되어있다.

이 때, 이 결과의 정수에 대한 집합을 Zn = { 0, 1, ... , n-1 } 로 따로 분류할 수 있는데 이것을 잉여류라고 한다. 모듈러 연산에 사용되는 모든 정수는 이 집합에서만 사용되어야한다.

그러면 다시 역원으로 돌아와서 Z10 에 대한 모든 곱셈 역원쌍을 구하려면,

우선 역원 쌍의 정수는 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } 의 범위 내에서 나와야한다.

그리고 mod 10 의 결과가 1이 되는 정수 쌍이어야한다.

고로, (1,1) ≡ (3,7) ≡ (9,9) mod 10 이 Z10 에 대한 모든 곱셈 역원 쌍이 될 것이다.

조금 이해가 되었는지 모르겠다.

4. 확장된 유클리드 알고리즘으로 모듈러 역원 구하기

마지막으로 앞서 포스팅한 확장된 유클리드 알고리즘과 모듈러 연산으로 모듈러 역원을 빠르게 구해보자.

이는 RSA 암호화 방식에서 핵심이 될 부분일 것이다.

우선, 곱셈의 역원이 존재한다면 모듈러 연산 a mod b = 1 에서 a, b 두 수의 관계가 서로소라는 점을 알고있어야한다!

그렇다는 말은 gcd(a,b)=1, a*s ≡ 1 mod b 이며, 확장된 유클리드 알고리즘에 의해 a*s + b*t = 1 이라는 결론이 나온다.

그러면 a의 역원 s를 구할 수 있다.

저번에 풀었던 System32.kr 의 RSA101 문제도 이 성질을 이용해서 복호화를 할 수 있었다.

System32.kr - RSA101 풀이

음 예제는

(5*s) mod 6 = 1 에 대한 역원 s 를 구해보자.

q	r1	r2	r	s1	s2	s	t1	t2	t
0	5	6	5	1	0	1	0	1	0
1	6	5	1	0	1	-1	1	0	1
5	5	1	0	1	-1	6	0	1	-4

---

결론적으로 결과식은 5*(-1) + 6**(1) = 1 이 된다.

하지만, s는 음수가 되면 안되므로 이런 경우에는 s = (s + b) mod b 로 양수 결과 값으로 만들어서 s를 정해주면 된다.

여기서는, s = (-1 + 6) mod 6 = 5 가 된다.

(5*5) ≡ 1 (mod 6)

이렇게 모듈러 연산에 대해 간략하게나마 알아보았다.

다음에는 RSA 암호화 연산을 정리해보겠다.

.
.
.
.
contact : a42873410@gmail.com