서론
이번에 CTF 문제를 풀면서 한 가지 특이한 문제를 보게 되었습니다. 문제의 핵심 부분은 다음과 같았습니다.
소수 $p$와 $\gcd(p-1,r)\neq1$인 $r$에 대해서 $m^r\text{mod}\ p$가 있을 때 $m$을 구할 수 있는가?
일반적으로 $\gcd(p-1,r)=1$이라면 $p-1$에 대한 $r$의 역수 $r^{-1}$을 구한 뒤 $(m^r)^{r^{-1}}$을 계산하면 $m$을 구할 수 있습니다. 하지만 그렇지 않은 경우에 대해서는 본 적이 없었기 때문에 검색하는데 시간을 꽤 들이게 되었습니다.
저는 한 논문을 보고 구현했지만, 일반적으로 Adleman-Manders-Miller Root Extraction이라는 Method를 사용한다는 것을 CTF가 끝난 뒤 알게 되었습니다. 이번 글에서는 Adleman-Manders-Miller Root Extraction를 중점적으로 설명하고, 다음 논문에서는 어떤 식으로 구했는지만 간략하게 소개하고자 합니다.
본론
Adleman-Manders-Miller Root Extraction
Adlemann-Manders-Miller Root Extraction은 위와 같은 문제에서 일반적으로 쓰이는 알고리즘입니다.
우선 이차 잉여(quadratic residue)처럼 $r$th residue를 정의할 수가 있습니다.
만약 $p-1$이 $r^t \cdot s$와 같은 꼴로 작성이 가능하다고 합시다. ($t>1, \gcd(r, s) = 1$) 그러면 어떤 수 $x$에 대해서 $x^{r^{t-1}s}$ 가 1이 되는지를 확인하면 됩니다.
이제 어떤 수 $y$가 있고 $y$가 위의 방법을 통해 $r$th residue인 것을 안다고 합시다. 그리고 이 $y$에 대해서 $x^r = y$인 $r$th root $x$를 찾고 싶다고 합시다.
우리는 $(y^s)^{r^{t-1}} = 1$임을 알고 있기 때문에, 만약 $s \vert r\alpha - 1$인 $\alpha$를 구하면 $(y^{r\alpha - 1})^{r^{t-1}} = 1$ 또한 성립함을 알 수 있습니다. $\alpha$는 Euclidean algorithm을 통해 쉽게 구할 수 있습니다.
만약 $t = 1$이라면 자동으로 $y^\alpha$가 $y$의 $r$th root임을 알 수 있습니다. 지금부터는 $t \geq 2$라고 합시다.
어떤 $r$th non-residue $z$를 알고 있다고 합시다. 이러한 $z$는 무작위 시도를 통해 쉽게 구할 수 있습니다. 그러면 어떤 $i, j (i\neq j, i,j\in{0, 1, \cdots, r - 1})$에 대해서 $(z^s)^{ir^{t-1}} \neq (z^s)^{jr^{t-1}}$ 가 성립함을 알 수 있습니다. (만약 이해가 안 간다면 귀류법을 사용해봅시다.)
이로부터 $K_i = (z^s)^{ir^{t-1}}, K = {K_0, K_1, \cdots, K_{r-1}}$이라고 정의해봅시다. 이 $K$라는 집합은 $a^r = 1$을 만족하는 $a$를 모아놓은 집합과 동일합니다. 그러므로 $(y^{r\alpha-1})^{r^{t-1}} = ((y^{r\alpha-1})^{r^{t-2}})^t = 1$로부터 어떤 $j_1$에 대해 $(y^{r\alpha-1})^{r^{t-2}} = K_{r - j_1}$ ($K_0 = K_r$)이 성립함을 알 수 있고, $(y^{r\alpha-1})^{r^{t-2}} K_{j_1} = 1$임을 알 수 있습니다. 이 때 $j_1$을 구하는 것은 이산 로그를 구하는 알고리즘을 사용해서 쉽게 구할 수 있습니다.
$K_{j_1}$을 풀어서 쓰면 $(y^{r\alpha-1})^{r^{t-2}} (z^s)^{j_1 r^{t-1}} = 1$라는 식을 얻게 됩니다. 만약 $t$가 3 이상이라면 위의 과정을 반복해서 $(y^{r\alpha-1})^{r^{t-3}} (z^s)^{j_1 r^{t-2}} K_{j_2}= 1$인 $j_2$를 구할 수 있고, 이를 계속 반복해서 $t-1$번에 도달하게 되면 $(y^{r\alpha-1}) (z^s)^{j_1 r} (z^s)^{j_2 r^2} \cdots (z^s)^{j_{t-1} r^{t-1}}= 1$을 얻게 됩니다. 이를 정리하면 $(y^\alpha)^r ((z^s)^{j_1+j_2 r + \cdots + j_{t-1} r^{t-2}})^r = y$를 얻게 됩니다. 곧, $y^\alpha (z^s)^{j_1+j_2 r + \cdots + j_{t-1} r^{t-2}}$가 $y$의 $r$th root가 됩니다.
테스트용으로 코드를 작성해보면 다음과 같습니다.
import random
print("START")
while True:
q = random.randint(2^1023, 2^1024)
r = random_prime(100000, False, 10000)
t = random.randint(2, 100)
p = q * r^t + 1
if is_prime(p):
break
m = 123456789
y = pow(m, r, p)
print("p:", p)
print("q:", q)
print("r:", r)
print("y:", y)
def rth_root(y, r, p):
assert pow(y, (p - 1) // r, p) == 1
while True:
z = random.randint(2, p - 1)
if pow(z, (p - 1) // r, p) != 1:
break
t, s = 0, p - 1
while s % r == 0:
t += 1
s //= r
_, _, alpha = xgcd(s, r)
alpha = alpha % s
assert (r * alpha - 1) % s == 0
F = GF(p)
y, z = F(y), F(z)
a = z^(r^(t - 1) * s)
b = y^(r * alpha - 1)
c = z^s
h = F(1)
for i in range(1, t):
d = b^(r^(t - 1 - i))
if d == F(1):
j = 0
else:
j = -discrete_log(d, a, r)
b = b * (c^r)^j
h = h * c^j
c = c^r
return Integer(y^alpha * h)
m = rth_root(y, r, p)
print("rth_root:", m)
assert pow(m, r, p) == y
t = GF(p).zeta(r) # Finding t^r == 1
for i in range(0, r):
if (m * pow(t, i, p)) % p == 123456789:
print("YES")
실행 결과는 다음과 같습니다.
START
p: 19845869324196932235409027281453237511434025783339558849495583074177336489263619484081351480299158875363901884038529922270951971742691903247477767765786598100784004885618076125069821944126679592384952248500498735969619129537473277019889546982844294769783094852625682530907522145655908913960414003360923121238022646178320019703539731039785624809849
q: 127344816046005269180334687651471228514658965420652245698906570149747555809209220329500784794231658638357396721144033888708517969524208360023701168054677342633788298237158168251112498454806640341253022696445653859713428647852602639353685739977163035617890581378896233143839457903755954965791714844513884429688
r: 59441
y: 8054535770919722080404583182108390450265057931906853517144924854772068727626370584508261755788475398692986120155099710858963822564068287749479392420091184037399559110122884625475846810853148628974365291773997987357754404130570934390302800356028471361498042743906102948651034240856679272883757340850200884510763800362787823448867567674198254346090
rth_root: 19125731625834586797396468559434933034567444803978795950368199805730794533441707548079298539852224407474576775661503881035695117341077200789210868038529573118867529946523884811478026924812044015155406936957493954278885808301549471833926433450315114085613992388479146717212980160134169005764576516730124573341659693926971510642412713012052598464851
Namhun Koo, Gook Hwa Cho, and Soonhak Kwon의 Method
이 논문의 경우 깊이 이해를 하지 않은 상태에서 $t = 1$인 경우에 대해서만 사용했습니다.
이 논문에서는 $t$가 작은 경우에 대해서 효율적인 방법을 제시하고 있는데, 구체적인 증명은 이해하지 못했습니다. 대신, Examples and Algorithms 란에서 소개하고 있는 알고리즘을 간략히 소개하고자 합니다.
$t = 1$일 경우, $1 + \alpha \frac{p - 1}{r} \equiv 0$인 $\alpha$를 구한 뒤, $c^{\frac{1 + \alpha \frac{p - 1}{r}}{r}}$을 구하면 됩니다. $t=1$일 확률은 일반적으로 $\frac{r-1}{r}$로 근사가 가능하기 때문에, 대부분의 경우 $r$에 대해서 별도의 복잡한 계산 없이 구하는 것이 가능합니다. 이는 앞서 소개한 Adleman-Manders-Miller Root Extraction에서도 동일합니다.
$t$가 2 이상일 경우, 수학적으로는 많이 복잡해져서 이해하는 것이 어려웠습니다. 간략한 알고리즘은 페이퍼에서 찾아볼 수 있으나, specific한 unity value $\xi$를 찾는 것이 난관입니다. 논문에서 소개하는 unity value $\xi$를 구할 수 있게 된다면, 나머지 알고리즘은 multiplication으로만 구성되어있어 기존 method보다 효율적일 것으로 보입니다.
결론
이번 기회에 $r$th root를 구하는 알고리즘에 대해서 제대로 이해하고 정리해보고 싶었습니다. Adleman-Manders-Miller Root Extraction에 대해서는 정리하고 코드를 작성해보니 좀 더 제대로 이해할 수 있는 기분이 들었지만, 그 다음 method는 어느 정도 시간을 들여가며 읽어보았지만 아직 역부족이었습니다. :(
만약 제 설명이 부족했다면 하단의 참고 문헌란을 참고해주세요. 읽어주셔서 감사합니다.