[컴퓨터 보안] Basic Number Theory

Basic Number Theory

 

[ Euclidean Algorithm ]

  : GCD(Greatest Common Divisor; 최대공약수)를 구하는 알고리즘.

#include <iostream>

// a > b라고 가정
int gcd(int a, int b) {
    while(b != 0) {
    	int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

[ Modular Arithmetic ]

  · a ≡ b (mod m) : a와 b가 m에 의해 나누어졌을 때 나머지가 동일.

  · (a ± b) mod m = (a mod m ± b mod m) mod m

  · (a * b) mod m = (a mod m * b mod m) mod m

  · 나눗셈의 경우 Modular Inverse를 이용하여 계산하며, 이를 해결하기 위해 Extended Euclidean Algorithm을 사용.

 

[ Extended Euclidean Algorithm ]

  : 확장된 유클리드 호제법.

  : Modular Inverse를 구하기 위한 알고리즘. (a * a^(-1) ≡ 1)

  : Modular b와 구하려는 수 a가 서로소일 때만 역원이 존재.

     ( ax + by = GCD(a, b) )를 만족하며, 이때 GCD(a, b)가 1인 경우 a의 Modular Inverse x를 구할 수 있다. )

#include <iostream>
#include <tuple>

using namespace std;

tuple <int, int, int> extended_gcd(int a, int b) {
    if (a == 0 || a == b) {
        return { b, 0, 1 };
    }

    int gcd, x, y;
    tie(gcd, x, y) = extended_gcd(b % a, a);

    return { gcd, y - (b / a) * x, x };
}

     이때 결과값이 음수가 나올 수 있지만, x = (x % b + b) % b의 과정을 거쳐 양수로 만들어주고, 이에 따른 y를 구할 수 있다.

 

[ Fermat's Theorm ]

  : a^(p-1) ≡ 1 (mod p)

    ( p는 소수이고, a가 p의 배수가 아닌 경우에 성립 )

  : 임의의 정수 a를 선택하여 a^(n-1)을 n으로 나눈 나머지가 1이면 소수일 가능성이 높음을 이용해 Fermat test 진행.

    → n회 통과하였을 때 합성수일 확률이 1/(2^n)정도의 신뢰성을 가지게 됨.

 

[ Euler's Theorm ]

  : a^Φ(m) ≡ 1 (mod m)

    ( a와 m은 서로소이고, Φ(m)은 m보다 작은 모든 양의 정수 중 m과 서로소인 수의 갯수 )

 

[ Cyclic Group ]

  : a와 p가 서로소일 때 a^m ≡ 1 (mod p)인 모든 양의 정수 m에 대하여 a는 순환군을 생성.

  : 최초로 a^m ≡ 1 (mod p)를 만족하는 m을 위수(order)라고 하며, 이는 Fermat's Theorem에 따라 p보다 작은 수가 된다.

  : 위수는 p-1의 약수가 된다.

  : 위수가 p-1인 경우를 generator 또는 primitive root라고 하며, 1~p-1까지의 모든 원소를 가진다.

 

[ Discrete Logarithm ]

  : Cyclic Group을 통해 a^m ≡ k (mod p)에서 k값을 만드는 m값을 구하는 문제.

  : Diffie-Hellman Algorithm에서 사용.

 

[ Integer Factorization ]

  : 큰 정수를 소인수분해 하는 문제.

  : RSA 암호화 알고리즘에서 실제로 사용하고 있는 방식.

  : 보통 매우 큰 소수 2개를 곱해 이용하며, 작은 소수를 이용하거나 짧은 키를 이용하게 되면 보안에 취약해짐.