[암호학] 1. 암호학에서 사용되는 수학(3)

1. 나머지 연산(Modular Arithmetic)

흔히 모듈러 연산이라고도 부르는 이 연산은, 나눗셈 과정에 있어 오로지 나머지에만 관심을 가지는 연산이다. 모듈러 연산의 연산자는 mod를 사용한다. 나누는 값을 Modulus라고 하며, 그에 따른 결과를 Residue라고 부른다.

1) Set of Residues

모듈러 연산에서 특정 n에 대한 모듈러 연산의 결과(Residues)를 모아놓은 집합을 Set of Residues라고 말한다. 이를 으로 표기한다.

즉 7에 대한 Set of Residues는 이 된다.

Set of Residues 내의 원소들에 대한 이진 연산(Binary Operation)의 결과에는 모두 mod n 을 이용한다.

ex) 의 4와 6을 더하라. => (4+6) mod 7 = 3

의 8과 10을 곱하라. => (8X10) mod 9 = 8

※ Modular 연산의 성질

① (a + b) mod n = [(a mod n) + (b mod n)] mod n

② (a - b) mod n = [(a mod n) - (b mod n)] mod n

③ (a X b) mod n = [(a mod n) X (b mod n)] mod n

ex) 의 123과 -10을 곱하라. => [(123 mod 19) X (-10 mod 19)] mod 19 = (9 X 9) mod 19 = 5

※ ③ 성질의 응용

2) 합동(Congruence)

모듈러 연산에 있어서 합동은 두 정수가 동일한 n 에 대해 mod n 의 결과가 같다는 것을 의미 한다. 그리고 두 정수에 대해 두 정수가 합동이라는 것을 나타내기 위해서, ≡ 를 이용해 합동을 나타낸다.

ex) 

3) 역(Inverses)

암호학에서 모듈러 연산을 사용하면서, 많이 사용하게 되는 것이 역(Inverses)이다. 특정 수의 역 중 Additive inverse와 Multiplicative inverse에 대해 정리해보자.

① Additive Inverse

에서 a와 b가 Additive Inverse 관계에 있다면, mod n 에 대해 0과 a+b가 congruent 하다.

modular 연산에 있어서, 특정 수는 항상 Additive Inverse를 가지고 있으며, 각 수에 대한 역은 유일하다. 또한 Additive Inverse는 자기자신이 되는 것도 가능하다.

ex) 의 모든 Additive Inverse 쌍을 구하여라.

(0,0), (1,9), (2,8), (3,7), (4,6), (5,5)

② Multiplicative Inverse

에서 a와 b가 Multiplicative Inverse 관계에 있다면, mod n 에 대해 1과 aXb가 congruent 하다.

modular 연산에 있어서, 특정 수에 대한 Multiplicative Inverse는 존재할 수도, 그렇지 않을 수도 있다. 만약 의 특정 수 a에 대한 Multiplicative Inverse가 존재한다면, gcd(n,a)=1 인 경우이다. 다시말해, a와 n이 서로소인 경우에만 a에 대한 Multiplicative Inverse가 존재한다.

ex) 의 모든 Multiplicative Inverse 쌍을 구하여라.

(1,1), (3,7), (9,9)

※ Multiplicative Inverse를 찾는 방법

앞서 나온 확장 유클리드 알고리즘을 이용한다. 특정 수 a에 대한 Multiplicative Inverse는 gcd(n,a)=1인 경우에만 존재한다고 했다. 즉, 확장 유클리드 알고리즘에 의해

를 만족하는 s와 t를 찾을 수 있을 것이다. 이 때, 아래와 같은 과정으로 정리해보자.

마지막 결과로부터, 우리는 결국 확장 유클리드 알고리즘을 통해 t를 구하면 됨을 알 수 있다.

ex) 에서 11의 Multiplicative Inverse를 찾아라.

이를 통해 t1=-7이라는 결과를 얻을 수 있다. 에 -7은 존재하지 않는다. 따라서 을 만족하는 x를 찾아보자. -7+26=19이므로, 11에 대한 Multiplicative Inverse는 19임을 알 수 있다.

암호학에서 Additive Inverse를 사용하는 경우 을, Multiplicative Inverse를 사용하는 경우 를 사용한다.

는 에서 Multiplicative Inverse가 존재하는 원소들의 집합이다.