Security/암호학(Cryptography)

Pollard's p-1 algorithm

그믐​ 2023. 5. 3. 09:40
반응형

 

폴라드의 p-1 알고리즘?

폴라드의 p-1알고리즘은 폴라드가 1974년 폴라드가 발견한 소인수분해 알고리즘이다. 특수한 유형에서 어떤 수 n-1의 소인수들이 매우 많거나 작은 소인수들이 많은 자연수에 적합하다고 한다.

 

이름이 p-1인 이유로 주어진 정수 n을 소인수분해 하기 위해 n의 소인수 p를 알아내고자, 페르마의 소정리에서 p-1을 활용하기 때문이다.

 

원리

pollard's p-1 algorithm은 페르마의 소정리를 이용한다.

n이 p라는 소인수를 가진다고 하자. p와 서로소인 a에 대해서,

페르마의 소정리 $a^{p-1} \equiv 1 \pmod p$가 성립한다.

 

a를 보통 2로 많이 사용한다.

$a^{p-1} \equiv 1 \pmod p$ 이므로 $a^{k(p-1)} \equiv 1 \pmod p$도 성립한다.

 

$k(p-1)$을 $E$라고 하자. 즉, $(p-1) | E$ 이다. $a^{E} \equiv 1 \pmod p$.

 

모듈러의 성질에 의해 $a^E - 1 \equiv 0 \pmod p$이고, $p | a^E -1$이다. 동시에, $p | N $ 이므로

$\gcd(a^E -1 , N) = p$이다.

 

p를 모르더라도, $(p-1) | E$가 되도록 숫자 E를 적절하게 고르면 p를 알아낼 수 있다.

 

적절한 E 선택

그러나 알아낼 수 없는 경우가 있는데, 어떤 소인수에 대해서도 $(p-1) \nmid E$일 경우이거나,

N = pq인 두 소수 p, q에 대해서 ${p-1} |  E$ 이고 ${q-1} | E$ 일 때이다.

 

먼저, $(p-1) \nmid E$인 경우에는 $p | a^E -1$이 성립하지 않는다.

그러면 $N$과 $a^E -1$ 도 서로소가 될테고, 값이 1이 나올 것이다.

 

${p-1} |  E$ 이고 ${q-1} | E$ 일 때는 $pq | a^E -1$이고 그러면 $\gcd(a^E -1 , N) = N$일 것이다.

 

E가 너무 작으면 1이 결과로 나올 것이고, 너무 크면 N이 나오기 때문에 적절한 E 선택이 필요하다.

 

또한 E에 들어가는 소인수 종류가 너무 적으면 그것도 $(p-1) \nmid E$ 일 것이다.

이를 해결하기 위해서 팩토리얼, 혹은 lcm을 사용한다.

 

lcm이 팩토리얼에 비해 성능은 더 좋다고 한다.

팩토리얼을 사용할 때는 적절한 수 B를 가지고 $B! = E$를 계산한다.

 

계산과 구현

E는 매우 크기 때문에, $Q \equiv Q_0 \bmod N$일 때, $\gcd(Q, N) = \gcd(Q_0, N)$임을 이용하여 매번 모듈러를 적용한다.

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def pollards_p_1(n, B=10**6):
    a = 2
    for j in range(2, B+1):
        a = pow(a, j, n)
        d = gcd(a - 1, n)
        if 1 < d < n:
            return d
    return None

B는 디폴트로 $10^6$ 이다. 이 코드는 소인수분해라기보다 RSA 문제를 풀기 위해 n = pq인 상황을 가정하고 만들어졌다.

a를 2라고 해두고 a는 반복문을 돌면서 E를 계산해간다. 여기서는 E로 팩토리얼을 적용했다.

 

적절한 E를 선택하기 위해서 팩토리얼 하나하나 곱해질 때 마다 $\gcd(a^E -1 , N) = p$인 값이 나오는지를 if 문으로 확인한다.

정상적인 값이면 1보다 크고 n보다 작을 것이므로 return 한다.

 

 

대응 방안

pollard's p-1 algoritm을 대응하는 방안으로는 p, q 모두 안전 소수를 사용하는 것이다. 둘 중하나라도 안전 소수가 아니라면 하나의 소수를 알고 나눗셈으로 계산 가능하다.

 

안전 소수인 소피 제르멩 소수를 사용하면 된다.

소피 제르멩 소수는 소수 q에 대해서 p = 2q + 1을 만족하는 소수 p를 말한다.

 

p-1을 사용하려면 인수로는 적어도 q라는 소수를 포함해야 한다. q도 40자리 이상의 큰 소수라면, 굉장히 찾기가 까다로워 진다.

디레클레 정리와도 관련이 있다.

 

 

 

틀린 부분 있으면 지적해주십시오.

반응형