정수론(Number theory)
: 수학의 한 분야로, 정수와 관련된 다양한 성질을 다루는 학문이다.
암호학에서는 특정 값을 나누는 나머지 연산이 높은 비중을 차지한다. 큰 지수를 가진 거듭제곱을 특정 값을 나눈 나머지 게산을 하는 연산, Python에서 pow 함수와 동일한 기능을 기능을 담당하는 연산은 대부분의 암호 체계나 전자 서명에서 사용된다.
최대공약수(GCD)
: 둘 이상의 주어진 수들에 대하여 공약수, 즉 모든 주어진 수들의 공통의 약수인 수들 중에서 가장 큰 값을 의미한다.
84와 102의 최대 공약수를 구해보자.
84 = 2^2 x 3 x 7 이고, 102 = 2 x 3 x 17 이다. 각 소수 별로 공통된 더 작은 지수 만을 모아서 2 x 3 = 6임을 알 수 있다.
하지만, 이와 같은 방법은 수가 커지면 오래 걸리기 때문에 효율적이지 못하다. 유클리드 알고리즘으로 접근해보자.
유클리드 알고리즘(Euclidean Algorithm)
: 소인수분해 과정 없이도 두 수의 최대 공약수를 구할 수 있는 방법이다. 유클리드 호제법이라고도 불린다.
다음과 같은 2가지 정의를 만족한다.
- a > b인 양의 정수 a, b에 대해서 a를 b로 나눈 나머지를 r로 정의하면, a, b의 최대 공약수와 b, r의 최대 공약수는 같다
즉, gcd(a,b) = gcd(b,r) 이다. - a > 0일 때, a, 0의 최대공약수는 a로 정의된다.
즉, gcd(a,0) = a이다.
위의 정의 중 1번을 Python으로 gcd 함수를 구현할 수 있다.
def gcd(a,b):
if b ==0 :
return a
return gcd(b, a % b)
하지만, math 내장 모듈의 gcd 함수, PyCryptodome의 GCD 함수, SageMath의 GCD, gcd 함수 등이 존재하여 위와 같이 직접 구현할 필요는 없다.
확장 유클리드 알고리즘(Extended Euclidean Algorithm)
: g = gcd(a, b)라고 하면, 다음을 만족하는 정수 x,y는 항상 존재한다.
a * x = b * y = g
이를 만족하는 정수해 x, y는 앞서 언급한 유클리드 알고리즘을 구하는 방식과 동일하게 재귀적으로 구할 수 있다.
def xgcd(a, b):
if b == 0 :
# a = g = a * 1 + b * 0
return a, 1, 0
g, x1, y1 = xgcd(b, a % b)
# g = x1 * b + y1 * (a % b)
x = x1
y = (g - a * x) // b
assert a * x + b * y == g
return g, x, y
단, x,y 값은 유일하지 않다.
서로소
: 양의 정수 a, b의 최대 공약수 값이 1인 경우, 즉 gcd(a, b) = 1 이면, a, b는 서로소(Coprime, Relatively prime) 관계에 있다고 표현한다.
합동(Congruence)
: 두 정수 a, b를 각각 양의 정수 m으로 나눈 나머지가 동일할 경우, "a, b는 m에 대하여 합동" 이라고 표현한다.
다음과 같이 수식으로도 작성할 수 있다.
a ≡ b (mod m)
여기서, m을 법(Modulus)이라고 부른다. 또한, a - b 를 하면 이는 양의 정수 m의 배수라는 특징을 발견할 수 있다.
합동식에 관한 성질 중에서 암호학에서 중요한 4가지가 있다.
- 교환법칙이 성립한다. 즉, a ≡ b (mod m) 이면, b ≡ a (mod m) 이다.
- a ≡ b (mod m), c ≡ d (mod m) 이면, a ± c ≡ b ± d (mod m) 이다.
- a ≡ b (mod m), c ≡ d (mod m) 이면, a x c ≡ b x d (mod m) 이다.
- a ≡ b (mod m) 이면, 정수 k에 대하여 a^k ≡ b^k (mod m) 이다.
곱셈의 항등원과 역원
- 항등원 : 일반적인 곱셈에 대한 항등원과 동일한 1이다.
a x 1 ≡ a (mod m) - 역원: 상황에 따라 존재하거나 존재하지 않을 수 있다. 존재한다고 가정하면 다음을 만족한다.
a x a^(-1) ≡ 1 (mod m)
a, m이 서로소일 경우, 즉 gcd(a, m) = 1일 경우 a의 역원은 항상 존재한다.
확장 유클리드 알고리즘을 사용하여 a * x = m * y = 1을 만족하는 정수쌍 x, y를 찾을 수 있다.
역원을 구하고, a^7 x (a^(-1))^3 ≡ a^4 (mod m)과 같은 일반적인 역원의 성질을 잘 만족하는지 아래의 코드로 확인할 수 있다.
def inverse(a, m):
g, x, y = xgcd(a, m)
if g != 1:
return None
return x
if __name__ == "__main__":
a, m = 7, 26
a_inverse = inverse(a, m)
assert (a**7 * a_inverse ** 3) % m == (a**4) % m
assert inverse(8, m) == None
중국인의 나머지 정리
x ≡ 2 (mod 6) 을 만족하는 x는 -4, 2, 8 ... 이 가능하고, x ≡ 3 (mod 5) 을 만족하는 x는 -2, 8, 13, ... 이 가능하다. 두 식을 모두 만족하는 x는 8, 38, 68, ... 임을 알 수 있고, 이는 x ≡ 8 (mod 30) 과 완전히 동일하다는 것을 알 수 있다.
위의 예시와 같이 합동식들을 새로운 합동식으로 합칠 수 있는지 알아보자.
서로소인 두 modulus p, q 위에서 각각 x의 값이 유일하게 정해지는 경우, x는 modulus p x q 위에서의 modulus 위에서 항상 유일하게 해가 존재한다. 이를 중국인의 나머지 정리(Chinese Remainder Theorem, CRT)라고 한다.
- 해의 존재성
일 때, 의 p.q가 서로소이기 때문에 p x α + q x β = 1 을 만족하는 정수 α, β를 구할 수 있고, 다음이 성립한다.- 이때, c = a x q x β + b x p x α로 정의하면 c ≡ a(mod p), c ≡ b(mod q)이 성립함을 다음과 같이 확인할 수 있다.
- 해의 유일성
c0 값이 존재해서 c와 c0는 p x q로 나눈 나머지가 서로 다르고, c0 ≡ a (mod p), c0 ≡ b (mod q)을 만족한다고 하자.
c0 ≡ a ≡ c (mod p)이고, c0 ≡ b ≡ c (mod q)이므로, c0 - c는 p,q의 배수이다. p,q가 서로소이기 때문에, c0-c는 p x q의 배수이어야 하고, 이는 c와 c0는 p x q로 나눈 나머지가 서로 다르다는 가정에 모순이다.
따라서, c = a x q x β + b x p x α 는 유일하다.
아래는 중국인의 나머지 정리를 python으로 구현한 것이다.
def crt(rem, mod):
a, b = rem
p, q = mod
g, alpha, beta = xgcd(p, q)
assert g == 1
c = a * q * beta + b * p * alpha
final_mod = p * q
c %= final_mod
assert c % p == a
assert c % q == b
return c, final_mod
예시의 경우에 다음과 같이 호출해서 값을 구할 수 있다.
if __name__ == "__main__":
print(crt([2,3], [6,5]))
또한, 둘 이상의 여러 서로소인 modulus들에 대해서 중국인의 나머지 정리를 적용하기 위해서 하나씩 순차적으로 진행하면 해결할 수 있다.
def crt_multi(rem, mod):
c = 0
final_mod = 1
for a, p in zip(rem, mod):
c, final_mod = crt([c,a], [final_mod, p])
for a, p in zip(rem, mod):
assert c % p == a
return c, final_mod
아래는 예시의 경우에 하나의 식을 더 추가한 경우에서 호출하는 예제이다.
x ≡ 2 (mod 6), x ≡ 3(mod 5), x ≡ 11(mod 13)
if __name__ == "__main__":
print(crt([2,3,11], [6,5,13]))
출력을 해보면 (128, 390)이 나와서, x ≡ 128 (mod 390)일 때 만족하는 것을 알 수 있다.
Exponentiation by Squaring
: 큰 지수에 대한 거듭제곱을 연산할 때 사용되는 방법이다.
e ≥ 0에 대하여
Pow 함수
: Python의 내장 pow 함수는 modulus 위에서의 거듭제곱을 연산해주는 함수이다. pow(n, e, m)의 결과는 modulus m위에서의 n^e 값을 계산해준다. 여기서 e는 음의 정수도 가능하다.
아래는 앞서 언급한 pow 함수를 python으로 직접 구현한 코드이다.
def mypow(n,e,m):
if e<0 :
if gcd(n,m) == 1 :
return mypow(inverse(n,m), -e, m)
else :
return None
elif e == 0:
return 1
elif e % 2 == 0 :
return mypow(n, e // 2, m)**2 % m
elif :
return n * mypow(n, (e-1)//2, m) ** 2 % m
