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

1. 서론

우선 암호학에 들어가기에 앞서, 암호학은 수학의 '정수론' 분야에 기초를 두고 있다. 수학에 기초를 두고 있는 만큼, 암호학을 공부하기 위해서는 '정수론'에서 사용되는 연산을 적어도 조금은 이해하고 사용할 줄 알아야 한다. 그래서 우선, 암호학에서 사용되는 '정수론'을 잠깐 소개하고자 한다.

2. 정수 연산(Integer Arithmetic)

1) 정수 집합(Set of Integers)

앞서 말했듯이 우리가 암호학에서 관심이 있는 수학 분야는 '정수론'이다. 그렇기에 우선 가장 먼저 '정수 집합(Set of Integers)'를 정의하자. 간단히 Z라고 표시하며, 음의 무한대부터 양의 무한대까지의 (소수가 없는) 진정수(Integral number)로 이루어져있는 집합이라고 한다. 쉽게 말해, 아래의 집합과 같다.

Z={......,-2, -1, 0, 1, 2, ......}

2) 정수의 나눗셈(Integer Division)

정수의 연산 덧셈, 뺄셈, 곱셈, 나눗셈 중 어쩌면 가장 특이하다고 할 수 있는 연산이 나눗셈이다. 정수의 나눗셈을 수식으로 나타내면 다음과 같이 나타낼 수 있다. 예를 들어 a를 b로 나누는 경우를 생각해보자.(a,b∈Z)

a = q X b + r

우리는 이 때의 a를 피제수(Dividend), q를 몫(Quotient), b를 제수(Divisor), 그리고 r을 나머지(Remainder)라고 부른다.

암호학에서는 나눗셈에 두가지의 제한을 두고 있다.

① 제수(Divisor)는 항상 양의 정수이다. (b>0)

② 나머지는 항상 0이상의 정수이다. (r>=0)

ex) 위의 제한에 의해서 -159를 13으로 나누어보자.

-153=(-11)X13+(-10)

이 때, 나머지는 양수이어야 하므로, 다시 나타내면,

-153=(-12)X13+3

으로 나타낼 수 있다. 즉 -153 나누기 13 은 몫 -12, 나머지 3 의 결과를 얻을 수 있다.

※ 간단하게, 나머지가 음수로 나온 경우, 그 나머지에 + b를 해주어라. 그러면 양의 나머지를 얻을 수 있다! (ex. -10+13=3)