📂정수론

폴리그-헬맨 알고리즘 증명

알고리즘

그룹 $G$ 의 원소 $g$ 가 오더 $N = q_{1}^{r_{1}} q_{2}^{r_{2}} \cdots q_{t}^{r_{t}}$ 이라고 하자. 그러면 이산로그 문제 $g^{x} = h$ 는 다음의 알고리즘에 따라 많아도 $\displaystyle O \left( \sum_{i=1}^{t} S_{q_{i}^{r_{i}}} + \log N \right)$ 스텝 안에 풀린다.

---

Step 1.

$\displaystyle g_{i} : = g^{N / q_{i}^{r_{i}}}$ 와 $\displaystyle h_{i} := h^{N / q_{i}^{r_{i}}}$ 을 계산한다.

---

Step 2.

샹크스 알고리즘을 통해 이산로그 문제 $g_{i}^{y} = h_{i}$ 의 해 $y_{i}$ 를 구한다.

---

Step 3.

중국인의 나머지 정리를 통해 $\begin{cases} x \equiv y_{1} \pmod{ q_{1}^{r_{1}} } \\ \qquad \vdots \\ x \equiv y_{t} \pmod{ q_{t}^{r_{t}} } \end{cases}$ 를 만족하는 $1 \le x \le N$ 를 구한다.

---

• $S_{q_{i}^{r_{i}}}$ 은 샹크스 알고리즘에서 걸리는 시간으로써 $\displaystyle O \left( S_{q_{i}^{r_{i}}} \right) \approx O \left( q_{i}^{r_{i} / 2} \right) $ 정도로 보면 된다.

샹크스 알고리즘은 오더를 알고 있을 때 사용할 수 있는 공격법이다. 폴리그-헬맨 알고리즘은 $p$ 가 스무스하다면 $(p-1)$ 의 소인수분해가 쉬워져서 $\displaystyle g_{i} = g^{N / q_{i}^{r_{i}}}$ 를 찾기 쉽다는 사실을 이용한다. 이렇게 만들어진 $g^{i}$ 의 오더는 자명하게도 $q_{i}^{r_{i}}$ 이므로 샹크스 알고리즘을 사용하는 제약이 없어진다. 이렇게 원래의 문제를 작은 문제로 만들어서 각개격파한 뒤 중국인의 나머지 정리로 답을 구하는 것이다.

증명

Part 1. 존재성

$x$ 가 $g^{x} = h$ 의 해라는 것은 모든 $i = 1, \cdots , t$ 에 대해 $x = y_{i} + q_{i}^{r_{i}} z_{i}$ 를 만족하는 $z_{i}$ 가 존재한다는 의미다.

• Part 1-1. $\displaystyle {{N} \over { q_{i}^{r_{i}} } } x \equiv {{N} \over { q_{i}^{r_{i}} } } \log_{g} ( h ) \pmod{N} $
  $N$ 과 $g_{i} , y_{i} , h_{i}$ 의 정의에 의해 $$ \begin{align*} \left( g^{x} \right)^{N / q_{i}^{r_{i}} } =& \left( g^{y_{i} + q_{i}^{r_{i}} z_{i}} \right)^{N / q_{i}^{r_{i}} } \\ =& \left( g^{ N / q_{i}^{r_{i}} } \right)^{ y_{i} } \cdot g^{N z_{i} } \\ =& \left( g^{ N / q_{i}^{r_{i}} } \right)^{ y_{i} } \\ =& g_{i}^{ y_{i} } \\ =& h_{i} \\ =& h^{N / q_{i}^{r_{i}} } \end{align*} $$ 이다. 정리하면 $$ \left( g^{x} \right)^{N / q_{i}^{r_{i}} } = h^{N / q_{i}^{r_{i}} } $$ 이고, 로그를 취하면 다음을 얻는다. $$ {{N} \over { q_{i}^{r_{i}} } } x \equiv {{N} \over { q_{i}^{r_{i}} } } \log_{g} ( h ) \pmod{N} $$
• Part 1-2. $\displaystyle \sum_{i=1}^{t} {{N} \over { q_{i}^{r_{i}} } } c_{i} = 1$
  $N$ 의 정의에 따라 $\displaystyle \gcd \left( {{N} \over { q_{1}^{r_{1}} } } , \cdots , {{N} \over { q_{t}^{r_{t}} } } \right) = 1$ 이 성립함은 자명하고, 확장된 유클리드 정리에 의해 $$ {{N} \over { q_{1}^{r_{1}} } } c_{1} + \cdots + {{N} \over { q_{t}^{r_{t}} } } c_{t} = 1 $$ 을 만족하는 $c_{1} , \cdots , c_{t} \in \mathbb{Z}$ 가 존재한다.
• Part 1-3. $x = \log_{g} (h) \pmod{N}$
  Part 1-1에서 얻은 $$ {{N} \over { q_{i}^{r_{i}} } } x \equiv {{N} \over { q_{i}^{r_{i}} } } \log_{g} ( h ) \pmod{N} $$ 의 양변에 $c_{i}$ 를 곱하면 $$ {{N} \over { q_{i}^{r_{i}} } } c_{i} x \equiv {{N} \over { q_{i}^{r_{i}} } } c_{i} \log_{g} ( h ) \pmod{N} $$ 이를 $i=1$ 부터 $t$ 까지 모두 더하면 $$ \sum_{i=1}^{t} {{N} \over { q_{i}^{r_{i}} } } c_{i} x \equiv \sum_{i=1}^{t} {{N} \over { q_{i}^{r_{i}} } } c_{i} \log_{g} ( h ) \pmod{N} $$ $x$ 와 $log_{g} (h)$ 는 인덱스 $i$ 에 독립이므로 $$ x \sum_{i=1}^{t} {{N} \over { q_{i}^{r_{i}} } } c_{i} \equiv \log_{g} ( h ) \sum_{i=1}^{t} {{N} \over { q_{i}^{r_{i}} } } c_{i} \pmod{N} $$ Part 1-2에서 $\displaystyle \sum_{i=1}^{t} {{N} \over { q_{i}^{r_{i}} } } c_{i} = 1$ 이므로 다음을 얻는다. $$ x \equiv \log_{g} (h) \pmod{N} $$

---

Part 2. 시간복잡도

$i = 1, \cdots , t$ 에 마다 Step 2가 반복되므로 $\displaystyle O \left( S_{q_{i}^{r_{i}}} \right) $ 만큼의 시간이 걸린다. 또한 Step 3에서 중국인의 나머지 정리를 사용할 때 $O ( \log N )$ 만큼의 시간이 걸리므로, $\displaystyle O \left( \sum_{i=1}^{t} S_{q_{i}^{r_{i}}} + \log N \right)$

■

코드

다음은 폴리그-헬맨 알고리즘을 R 언어로 구현한 코드다. 소인수분해 코드와 오더를 구하는 코드, 샹크스 알고리즘, 연속제곱법, 중국인의 나머지 정리를 사용하는 코드가 쓰였다.

prime = read.table("../attachment
                   /cfile8.uf@25411C3C5968BBE322F0D4.txt"); prime = prime[,1]
 
factorize<-function(p)
{
  q=p
  factors<-numeric(0)
  i=1; j=1
  while(q!=1)
  {
    if(q%%prime[i]) {i=i+1}
    else
    {
      q<-q/prime[i]
      factors[j]<-prime[i]
      i=1
      j=j+1
    }
  }
  return(factors)
}
 
order<-function(g,p,h=1) #Calculate a order of g in modulo p
{
  qe<-table(factorize(p-1))
  qe<-rbind(as.numeric(names(qe)),qe)
  divisor<-qe[1,1]^(0:qe[2,1])
  if((length(qe)/2)==1) {return(qe[1,1]^qe[2,1])}
  for(i in 2:(length(qe)/2)) {divisor=c(divisor%*%t(qe[1,i]^(0:qe[2,i])))}
  for(i in divisor) {if((FPM(g,i,p))%%p==1) break;}
  return(i)
}
 
FPM<-function(base,power,mod) #It is equal to (base^power)%%mod
{
  i<-0
  if (power<0) {
    while((base*i)%%mod != 1) {i=i+1}
    base<-i
    power<-(-power)}
  
  if (power==0) {return(1)}
  if (power==1) {return(base%%mod)}
  
  n<-0
  while(power>=2^n) {n=n+1}
  
  A<-rep(1,n)
  A[1]=base
  
  for(i in 1:(n-1)) {A[i+1]=(A[i]^2)%%mod}
  
  for(i in n:1) {
    if(power>=2^(i-1)) {power=power-2^(i-1)}
    else {A[i]=1} }
  
  for(i in 2:n) {A[1]=(A[1]*A[i])%%mod}
  
  return(A[1])
}
 
shanks<-function(g,h,p)
{
  N<-order(g,p)
  n<-1+floor(sqrt(N))
  gn<-FPM(g,-n,p) #gn := g^{-n}
  x<-p
  
  List_1<-numeric(n+1)
  List_1[1]=1
  for(i in 1:n) {List_1[i+1]=(List_1[i]*g)%%p}
  
  List_2<-numeric(n+1)
  List_2[1]=h
  for(i in 1:n) {List_2[i+1]=(List_2[i]*gn)%%p}
  
  for(i in 0:n+1) {
    for(j in 0:n+1) {
      if (List_1[i]==List_2[j]) {x[length(x)+1]<-((i-1)+(j-1)*n)}
    }
  }
  
  return(min(x))
}
 
CRA<-function(S)  #Algorithm of chinese remainder theorem
{
  r<-S[,1]      # matrix S express below sysyem.
  mod<-S[,2]    # x = r[1] (mod mod[1])
  n<-length(r)  # x = r[2] (mod mod[2])
  # x = r[3] (mod mod[3])
  
  A<-seq(r[1],to=mod[1]*mod[2],by=mod[1])
  
  for(i in 2:n)
  {
    B=seq(r[i],to=mod[1]*mod[i],by=mod[i])
    r[1]=min(A[A %in% B])
    mod[1]=mod[1]*mod[i]
    if (i<n) {A=seq(r[1],to=mod[1]*mod[i+1],by=mod[1])}
  }
  
  return(r[1])
}
 
PHA<-function(g,h,p){
  N<-order(g,p)
 
  m_<-table(factorize(N))
  m_<-rbind(as.numeric(names(m_)),m_)
  m_<-c(data.frame(m_)[1,]^data.frame(m_)[2,])
 
  y_<-numeric(0)
  for(i in 1:length(m_)){
    g_i<-FPM(g,N/m_[i],p)
    h_i<-FPM(h,N/m_[i],p)
    y_[i]<-shanks(g_i,h_i,p)
  }
  return(CRA(cbind(y_,m_)))
}
 
PHA(7,166,433)
FPM(7,47,433)
 
PHA(10,243278,746497)
FPM(10,223755,746497)
 
PHA(2,39183497,41022299)
FPM(2,33703314,41022299)

위 코드를 실행시킨 결과는 다음과 같으며, 연속제곱법으로 검산을 해서 제대로 작동함을 확인했다.

같이보기

• 이산로그 문제

이산로그 문제의 어려움을 이용한 보안 알고리즘

• 디피-헬만 키 교환 알고리즘
• 엘가말 공개 키 암호체계

이산로그 문제에 대한 공격 알고리즘

• 샹크스 알고리즘
• 폴리그-헬맨 알고리즘
• 이산로그 문제가 쉽게 풀리는 조건