항등원과 역원, 그리고 합동식

서론

암호학은 수학적으로 공부해야할 것들이 많기 때문에

다른 분야에 대비해서 어렵기도 하지만, 뭔가 공부한다는 느낌이 팍팍 드는게 은근 마음에 든다.

 

이론

항등원

항등원은 임의의 수 a에 대해 e를 연산 했을 때 그 결과 값이 a가 되는 e를 항등원이라고 한다.

예를 들어 덧셈 연산을 하면

a + e = a

가 되고 이를 만족하기 위한 e는 0이 된다.

 

잠시 생각해보면

더하기, 빼기 = 0
곱하기, 나누기 = 1
행렬의 덧셈 = 역행렬
행렬의 곱셈 = 단위행렬

이 된다.

우선 행렬은 내비두고,

사칙연산에 의한 항등원은 직관적으로 알 수 있을 것이다.

 

이를 수학적 기호로

a △ b = b △ a = e

로 표현하고, 왼쪽을 만족하는 경우 왼쪽 항등원, 오른쪽을 만족하는 경우 오른쪽 항등원,

양쪽을 만족하면 양쪽 항등원 또는 항등원이라고 한다.

 

역원

역원은 a와 x를 연산한 결과가 항등원 e가 될 때를 이야기한다.

찬가지로 예를 들어 a + x = e일 때 덧셈에 대한 항등원 e는 0 이기에 x는 -a가 된다.

ax = e 일 때 곱셈에 대한 항등원 e는 1 이기에 x는 1/a가 된다.

 

항등원과 역원의 계산

각자 설명할 수도 있겠지만 모아서 보면 이해가 쉬울 것 같아 모아보았다.

기본적인 수식은

a △ b = b △ a = e

에서 시작한다.

 

항등원의 계산

위에서 항등원의 정의를 a + e = a라고 했다.

이를 위 수식에 넣어보면

a △ e = e △ a = a가 된다.

 

예를 들어보자.

a △ b = a + b - 3

일때 연산 △에 대한 항등원은

a △ e = e △ a = a

=> a + e - 3 = a

=> e = 3

즉 항등원은 3이 된다.

 

역원의 계산

역원의 정의는 a + x = e 였다.

예를 들어

a △ b = a + b - 3

일 때 5의 역원을 구해보자.

 

마찬가지로

a △ b = b △ a

에 넣어보면

5 △ x = x △ 5 = e

=> 5 + x - 3 = e

=> x = e + 3 - 5

항등원 계산에서 e = 3임을 알 수 있었으니 역원은 1이 된다.

 

합동식

위의 원리를 이해했다면 합동식의 이해가 쉽다.

위의 식

a △ b

를 다시 풀어서 이야기해보면 "a와 b가 임의의 연산을 한 결과"라고 이야기할 수 있다.

합동식은 a와 b가 임의의 연산을 한 결과가 c와 b를 같은 연산을 했을 때 그 값이 같으면 합동식이라고 한다.

 

이것도 예를 들어보자.

10을 3으로 나눈 나머지와 7을 3로 나눈 나머지는 모두 1로 같으며, 이는 합동식이 된다.

이를 식으로 다시 표현해보면

10 % 3 == 7 % 3

10 mod 3 == 7 mod 3

가 된다.

 

이를 다시 표현하면

10 ≡ 7 (mod 3)

10 ≡ 7

이 된다.

 

그냥

10 ≡ 7

만 보면 이게 무슨 개소린가 할텐데, 3으로 나눴을 때 같은 나머지를 가지는 "성질"으로 인한 것이다.

 

합동식의 성질

이 합동식은 성질이 있다.

a ≡ b (mod m)과 c ≡ d (mod m)을 만족하면

a + c ≡ b + d (mod m)

a - c ≡ b - d (mod m)

ac ≡ bd (mod m)

a^n ≡ b^n (mod m)

c^n ≡ d^n (mod m)

를 만족한다.

다만 나누기에서는 만족하지 않는다.

 

그래서 이걸 어디 써먹느냐

큰 수의 나머지를 계산할 때 유용하게 써먹을 수 있다.

 

예를 들어 4^23을 9로 나눈 나머지는 얼마인지 계산한다고 가정하자.

이를 식으로 나타내보면

4^23 % 9

가 되고,

4^23 mod 9

로 표현할 수 있다.

 

이는 합동식의 성질에서와 같이

4^3 mod 9 = 64 mod 9 = 1 = 1 mod 9

이므로

4^3 ≡ 1 mod 9

가 성립하므로

(4^3) ^ 7 ≡ 1^7 mod 9

4^21 ≡ 1 mod 9

가 성립한다.

 

또한 합동식의 성질에서

a ≡ b (mod m)과 c ≡ d (mod m)을 만족하면

ac ≡ bd (mod m)

인데, c = c라 가정하면 양변에 같은 값을 곱해줄 수 있으므로

ac ≡ bc (mod m)

로 표현할 수 있기 때문에

4^21 * 4^2 ≡ 1 * 4^2 mod 9

4^23 ≡ 16 mod 9

가 되며, 결국

4^23 ≡ 7

이 된다.

 

곱셈에서의 역원 - 확장된 유클리드 호제법 (- RSA)

이거 설명하려고 지금까지 어그로 끌었다.

 

아직 RSA까지는 조금 더 가야하니 일단 생략하지만

RSA는 서로소인 a와 b가 있을 때 a와 b의 곱셈의 역원을 이용하는 암호화 방식이다.

 

이 때 두 수가 서로소라는 의미는 GCD(a, b) = 1이라는 것과 같기 때문에

결국

as + bt = 1

의 꼴로 나타낼 수 있다.

위에서 설명한 것과 같이 a와 b를 알고 있기 때문에 역원을 구할 수 있게 된다.

이 때 각각을 b로 나눈 나머지를 표현해보면

as mod b + bt mod b = 1 mod b

가 되고, bt mod b는 0이기에

as mod b = 1 mod b

as ≡ 1 mod b

가 된다.

 

즉, 서로소인 경우 두 정수는

as ≡ 1 mod b

라 할 수 있고 이를 풀어 이야기하면

소수 a에 임의의 값을 곱해서 b로 나눈 나머지가 1이

이라는 의미가 된다.