📂정수론

샹크스 알고리즘 증명

알고리즘 ¹

항등원이 $e$ 인 그룹 $G$ 의 원소 $g$ 가 오더 $N$ 이라고 하자. 그러면 이산로그 문제 $g^{x} = h$ 는 다음의 알고리즘에 따라 많아도 $O \left( \sqrt{N} \log N \right)$ 스텝 안에 풀린다.

---

Step 1.

$n: = 1 + \lfloor \sqrt{N} \rfloor $

---

Step 2.

두 개의 리스트 $A := \left\{ e , g , g^{2} , \cdots , g^{n} \right\}$ 와 $B := \left\{ h , hg^{-n} , hg^{-2n} , \cdots , hg^{-n^2} \right\}$ 를 만든다.

---

Step 3.

$g^{i} = h g^{-jn} \in A \cap B$ 를 찾는다.

---

Step 4.

$x = i + jn$ 은 $g^{x} = h$ 의 솔루션이다.

설명

기본적으로 그룹 $G$ 의 원소 $g$ 가 오더 $N$ 이라고 하면 이산로그문제 $g^{x} = h$ 는 많아도 $O (N) $ 스텝 안에 풀린다. $g$ 가 오더 $N$ 이라는 것은 못해도 $g^{N} = e$ 이 성립한다는 것이다. 따라서 $ 0, 1, \cdots , N-1$ 중에는 $g^{x} = h$ 을 만족시키는 $x$ 가 있음을 쉽게 확인할 수 있다.

샹크스 알고리즘은 이 계산량을 $O \left( \sqrt{N} \log N \right)$ 까지 떨어뜨려준다. 암호에 응용되는 이산로그문제라면 $N$ 이 상당히 큰 수일텐데, 절반보다도 적게 계산을 줄일 수 있으므로 큰 의미가 있다.

베이비스텝과 자이언트스텝이라는 것은 $g$ 를 곱해서 만들어지는 리스트 $A$ 와 $g^{-n}$ 를 곱해서 만들어지는 리스트 $B$ 에서 나온 말이다.

증명

Part 1. 존재성

$\left( A \cap B \right) \ne \emptyset$ 임을 보여야한다.

$x$ 를 $n$ 으로 나눈 몫을 $q$, 나머지를 $r$ 이라고 하면 $x = nq + r$ 와 같이 나타낼 수 있다.

그러면 $\sqrt{N} < n$ 이므로 $$ q = {{ x - r } \over { n }} < {{ N } \over { n }} < n $$ 이고 $$ \begin{align*} & g^{x} = h \\ \implies & g^{ nq + r } = h \\ \implies & g^{ r } = h g^{ - nq } \end{align*} $$ 이다. $r < n$ 이므로 $g^{r} \in A$ 이고, $q < n$ 이므로 $h g^{ - nq } \in B$ 이다.

---

Part 2. 시간복잡도

$A \cap B$ 를 찾기 위해 리스트를 소팅해야하고, $|A| = |B| = n$ 이므로 가장 알맞는 비교 정렬 알고리즘을 사용하면 $O ( n \log n )$ 번의 계산이 필요하다.

$n \approx \sqrt{N}$ 이므로 $$ \begin{align*} O \left( n \log n \right) =& O \left( \sqrt{N} \log \sqrt{N} \right) \\ =& O \left( {{1} \over {2}} \sqrt{N} \log N \right) \\ =& O \left( \sqrt{N} \log N \right) \end{align*} $$

■

코드

다음은 샹크스 알고리즘을 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)
}
 
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))
}
 
shanks(11,21,71)
FPM(11,37,71)
 
shanks(156,116,593)
FPM(156,59,593)
 
shanks(650,2213,3571)
FPM(650,319,3571)

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

같이보기

• 이산로그 문제

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

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

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

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