ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 암호학 시리즈 #2 모듈러 연산과 암호학
    암호학 시리즈 2024. 2. 24. 18:48

    Author : 최원혁

     

    Intro


    암호학은 엄청나게 큰 숫자를 반복적으로 연산하여 복호화를 아주 어렵게 또는 불가능하게 만드는 수학적 학문이다. 이 과정에서 무한(infinite)한 수를 대상으로 암호 체계를 구성하면 더 안전하리라 생각할 수도 있지만, 아무리 안전해도 만약 현대의 컴퓨터로 서명하거나 암호화하는 데에 너무 긴 시간이 걸린다면 그 활용 범위가 제한적이다. 때문에 수용 가능한 수준의 안전성을 담보하면서 효율적인 수준의 수체계와 연산 방식을 위해 유한(finite)한 개수를 가지는 범위를 선호한다. 이를 위해서 암호학에서는 기초 연산으로 modular 연산을 주로 이용한다.

     

     

    기본 다지기


    modular 연산을 한글로 ‘합동연산’이라 부르며 나머지 연산을 기반으로 하는 수학적 연산이다. 예를 들어 5 \(\div\) 3의 몫은 1, 나머지는 2가된다. 이때, 3 modular 5의 결과는 나머지 값인 2가 된다. 즉, a를 N으로 나누어 나머지 r 을 도출해내는 계산을 modular 연산라고 한다. 일반적으로 "a mod N" 또는 "a % N"와 같이 표현되며, 이때의 N을 modulus(대수)라고 한다. 기본적으로 정수 a와 양의 정수 n으로 정의한다.

     

     

     

    | 잉여류(set of residues) : \(Z {\scriptsize n}\)

     

    잉여류는 대수 n으로 나눈 나머지 값을 전체로 하는 집합이며 아래와 같이 표현된다.

    $$ Z{\scriptsize n} = \{0, 1, 2, … (n-1)\} $$

    예를 들어, a % 5를 연산한다고 했을 때, a에 어떤 숫자를 넣어도 결과는 4보다 큰 숫자가 나오지 않는다. a \( \div \) 5의 나머지가 5이상이 나올 수가 없기 때문이다. 즉, modular 5의 잉여류는 \(Z{\scriptsize 5} \) = { 0, 1, 2, 3, 4 } 가된다.

     

    | 분배법칙(distribution rule)

     

    분배법칙은 수학에서 두 항을 곱하거나 나눌 때, 하나의 항이 다른 항의 각 항에 대해 각각 곱해지거나 나눠지는 규칙을 나타낸다. 모듈러 연산 또한 아래 예시처럼 분배법칙이 성립된다.

    • [덧셈 분배법칙] (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

     

    즉, 모듈러 n에 대한 연산(a,b)을 위와 같이 식을 분배해도 결국 같은 결과에 도달한다는 뜻이다. 암호학에서 곱셈의 분배 법칙을 응용하면 아래와 같은 공식을 성립시킬 수 있다.

    $$ 10^x~mod~n~=~(10~mod~n)^x~mod~n $$

    대표적인 공개키 암호학인 RSA같은 경우 지수의 값을 반복적으로 계산하게 되는데, 분배법칙을 통해 연산식을 쫌더 간단하게 만들어 효율적인 암/복호화가 가능하다.

     

     

    | 항등원(identity)

     

    항등원(identity element)은 어떤 집합의 원소와 이항 연산을 하더라도 그 결과가 항상 원래의 원소와 동일한 값을 가지는 원소를 뜻한다. 즉, a라는 집합의 모든 숫자가 a + b = a일 때, b는 a의 항등원이 된다. 이때, 아래 예시처럼 덧셈의 항등원은 0, 곱셈의 항등원은 1이 된다.

    • 덧셈의 항등원 0 : a + 0 = a
    • 곱셈의 항등원 1 : a x 1 = a

     

     

    | 역원(inverse)

     

    역원(inverse)은 어떤 집합의 원소에 대해서 연산을 통해 다른 원소와 결합했을 때 항등원이 되면, 그 다른 원소를 역원이라고 한다. 즉, a + (-a) = 0(덧셈의 항등원)이 성립함으로, a의 역원은 -a가 된다. 위에서 말한것 처럼 항등원은 덧셈과 곱셈에 따라 다르다. 때문에 역원 또한 항등원에 따라 다르게 된다.

    • 덧셈에 대한 역원 : a + (-a) = 0, a의 역원은 -a
    • 곱셈에 대한 역원 : a x \({\frac 1 a} \) = 1, a의 역원은 \({\frac 1 a}\)

     

     

    모듈러 연산


    지금까지 모듈려 연산에 필요한 기본 개념을 알아봤다. 이러한 개념들이 모듈러 연산에서 어떻게 적용되는지 알아보도록 하자.

     

    | 모듈러 연산의 항등원(identity)과 역원(inverse)

     

    위에서 말했던것처럼 모듈러 연산의 덧셈 항등원과 곱셈 항등원은 0과 1이다. 하지막 역원은 쫌 달라진다.

     

    [ 모듈러 연산 덧셈의 역원 ]

    모듈러 n에 대한 a의 덧셈 역원은 아래와 같이 표현할 수 있다.

    • (a + b) mod n = 0

     

    이때 a의 역원은 분배법칙을 활용하여 구할 수 있다.

    1. (a + b) mod n = 0
    2. (a mod n) + (b mod n) = 0
    3. b mod n = -a mod n
    4. b mod n = (n - a) mod n

    즉, (a + b) mod n = 0 의 a에 대한 역원은 (n - a) mod n가 됩니다.

     

    [ -a mod n = (n - a) mod n 증명  ]

    모듈러연산은 나머지 값을 결과로 도출하는 연산이다. 때문에 a mod n은 (a + kn) mod n로 풀어 해석할 수 있다. 여기서 k는 정수이며 kn은 n의 배수가 된다. 때문에 k에 어떤 숫자가 들어와도 (a + kn) mod n의 결과는 항상 일치하다. 그렇다면, -a mod n 또한 (-a + kn) mod n로 해설이 된다. 마찬가지로 k에 어떤 숫자가 들어와도 결과는 일치하다. 그렇다면 k에 1부터 대입하여 k*n > a가되면 -a mod n는 양의 정수 x mod n으로 표현될 수 있다.

     

    Example : -5 mod 3를 구하라

    • (-5 + 1*3) mod 3 → -2 mod 3 →  3 - 2 mod 3 → 1 mod 3 = 1
    • (-5 + 2*3) mod 3 → 1 mod 3 = 1
    • (-5 + 3*3) mod 3 → 4 mod 3 = 1

     

    [ 모듈러 연산 곱셈의 역원 ]

    a x b가 1이 되면 1 mod n은 1(곱셈의 항등원)이 된다. 때문에 모듈러 n에 대한 a의 곱셈 역원은 아래와 같이 표현할 수 있다.

    • (a x b) mod n = 1 ( a ≤ n )

     

    하지만, 모듈러 연산의 곱셈 역원이 존재하기 위해선 충족되어야 하는 필요 조건이 있다. 바로 a와 n이 서로소 관계일 경우에만 a의 곱셈 역원이 존재한다. 서로소 관계는 a와 n의 최대공약수가 1인 경우를 의미한다. 전 암호학 시리즈 유클리드 알고리즘에서 언급된 적이 있다. a와 n이 서로소 관계라는 충족 조건이 만족한다고 가정되면, 곱셈의 역원은 확장된 유클리드 알고리즘을 활용하여 구할 수 있다.

     

     

    확장된 유클리드 알고리즘을 활용한 곱셈 역원 구하기


    모듈러 연산 곱셈의 역원은 (a x b) mod n = 1 로 표현되며, a x b가 1이 되면 된다. 잠깐 복습하자면, 확장된 유클리드 알고리즘은 두 수의 최대 공약수를 구하고, \( s \times a + t \times b = gcd(a, b) \)가 되는 s와 t를 구하는 알고리즘이다. 이를 풀어 해석하면 a에 대한 모듈러 연산 곱셈의 역원을 구할 수 있다.

     

    \( if~a~≤~n,~gcd(n, a)~=~1 \) (서로소 관계)

    \( \because s \times n + t \times a = 1 \)

    \( \therefore (s \times n + t \times a) ~mod~n = 1 ~mod~n → (s \times n ) ~mod~n + (t \times a) ~mod~n = 1 \)

    \( \because s \times n \)는 n의 정수, \( \therefore (s \times n ) ~mod~n = 0 \)

    \(\therefore (t \times a) ~mod~n = 1 \)

     

    확장된 유클리드 알고리즘을 모듈러 연산에 적용하게 되면 최종적으로 \( (t \times a)~mod~n = 1 \) 식을 도출해낼 수 있다. 현재 우리의 목표는 (a x b) mod n = 1에서 b(역원)를 구하는 것이다. 즉, t가 a에 대한 모듈러 연산 곱셈의 역원이 되는 것이다. 아래 간단한 실습을 통해 확장된 유클리드 알고리즘을 활용하여 직접 모듈러 연산의 곱셈에 대한 역원을 구해보자.

     

    11에 대한 모듈러 연산 mod 26 곱셈의 역원을 구하시오.

     

    확장된 유클리드 알고리즘으로 \( (t \times a)~mod~n = 1 \)의 t만 구하면 되기에, s는 계산할 필요없다. 위 사진처럼 마지막 라운드(round)까지 계산해보니 t = -7라는 값을 구할 수 있었으며, 모듈러 연산에 대입하면 -7 mod 26이 된다. 하지만, 최종적으로 구해야하는 a의 역원은 양수(+)가 되야한다.

    우리는 위에서 모듈러 연산 덧셈의 역원을 통해 -a mod n을 정수로 변환하는 과정을 알아봤다. 이를 그대로 대입하면 된다.

    $$ -7~mod~26 $$

    $$ (26 - 7)~mod~26 $$

    $$ 19~mod~26 $$

    우리의 문제 "11에 대한 모듈러 연산 mod 26 곱셈의 역원"을 수학적으로 표현하면 아래와 같다.

    $$ 11 \times t~mod~26 = 1, t를 구하시오 $$

    우리가 구한 t값 19를 대입하여 곱셈의 항등원 1이 나오는지 확인해보자

    $$ (11 * 19)~mod~26 = 209~mod~26 = 1 $$

    실습처럼 우리는 확장된 유클리드 알고리즘으로 모듈러 연산의 역원을 구할 수 있다.

     

     

    곱셈에 대한 역원을 가지는 수의 집합 : \( Z{\scriptsize n^*} \)


    위에서 잉여류는 모듈러 연산의 대수 n으로 나눈 나머지 값을 전체로 하는 집합을 뜻하며 \( Z{\scriptsize n}\)로 표현된다고 설명했다. 이때, \( Z{\scriptsize n}\) 집합의 모든 수가 역원이 존재한다면, 즉 모든 수가 n과 서로소 관계라면 이를 \( Z{\scriptsize n^*}\)로 표현된다. 암호학에 관련된 문서나 설명에서 자주 등장하는 표현이니 꼭 알아두고 넘어가자.

    마지막으로 모듈러 연산의 대수 N이 소수(prime number)인 경우, \( Z{\scriptsize n}\) 은 \( Z{\scriptsize p} || Z{\scriptsize p} \)로 표현된다. 앞으로 다룰 타원곡선 암호학에서 N이 소수인 사실이 매우 중요하다. 마찬가지로 자주 사용하는 표현이니 알아두자.

     

     

    마무리


    암호학에서 모듈러 연산의 곱셈에 대한 역원은 여러 가지 암호 시스템과 프로토콜에서 중요한 역할이 된다. 특히, 공개키 암호화 시스템과 서명 알고리즘에서 역원은 필요한 복호화 연산 그리고 서명을 생성하거나 검증할 때 자주 활용되기에 암호학 시리즈 두번째로 모듈러 연산에 대해 알아봤다.

     

Designed by Tistory.