[CryptoHack] Modular Square Root

 

개념 설명

---

모듈러 제곱근

 

르장드르 기호(Legendre Symbol)에서 우리는 숫자가 소수(prime) 모듈러의 제곱근인지를 결정할 수 있는 빠른 방법을 소개했다. 우리는 더 나아갈 수 있다: 그러한 제곱근을 효율적으로 계산하기 위한 알고리즘이 있다. Tonelli-Shanks라고 불리는 것이 있는데, 이것은 19세기에 이탈리아 인에ㅕ의해 처음 묘사되었고 1970년대에 Daniel Shanke에 의해 독립적으로 재발견 되었다는 사실에서 재미있는 이름을 얻었다. 

 

2가 아닌 모든 소수는 모든 홀수가 다음과 같은 합동성을 띄기 때문에 $p \equiv 1 \mod 4$ 또는 $p \equiv 3 \mod 4$ 형식이다.

앞선 문제의 힌트처럼 $p \equiv 3 \mod 4$의 경우, 제곱근을 계산하기 위한 매우 간단한 공식은 페르마의 소정리에서 바로 도출된다.

 

https://crypto.stackexchange.com/questions/20993/significance-of-3mod4-in-squares-and-square-roots-mod-n/20994#20994

Significance of 3mod4 in squares and square roots mod n?

그것은 여전히 $p \equiv 1 \mod 4$라는 경우를 남기므로 더 일반적인 알고리즘이 필요하다.

공식? 식? $r^ \equiv a \mod p$에서 Tonelli-Shanks는 $r$을 계산한다.

 

! Tonelli-Shanks는 composite(소수가 아닌) 모듈러에 대해 작동하지 않는다. composites (소수가 아닌) 제곱근 모듈러를 찾는 것은 게

산적으로 정수의 인수분해와 동등하다. 즉, 어려운 문제이다.

 

이 알고리즘의 주요 사례는 타원 곡선의 좌표를 찾는 것이다. 작동 원리가 다소 복잡하기 때문에 자세한 내용은 논의하지 않을 것이지만 구현은 쉽게 찾을 수 있고 Sage는 하나의 빌트인 함수를 가지고 있다.

2048비트 소수 p에 대한 a의 모듈러 제곱근을 구하라. 둘 중 작은 제곱근을 flag으로 제출하라.

 

풀이

---

https://rkm0959.tistory.com/20

Tonelli-Shanks Algorithm

https://sean9892.tistory.com/27

Introduction and Proof of Tonelli-Shanks Algorithm

아니 왜 sage가 안되는지 모르겠다..

 

결국 문제는 이차 잉여 a와 홀수인 소수 p가 주어졌을 때 제곱근 x를 찾는 것인데

위 링크에서 배우는 것만으로 코드를 작성하기가 어려웠다. (나는)

 

 

chat gpt에게 알고리즘 코드를 작성해달라고 해서 나온 코드

def legendre_symbol(a, p):
    """Compute the Legendre symbol (a/p)"""
    ls = pow(a, (p - 1) // 2, p)
    return -1 if ls == p - 1 else ls

def tonelli_shanks(n, p):
    """Find a square root of n modulo p using the Tonelli-Shanks algorithm"""
    if legendre_symbol(n, p) != 1:
        return None
    q = p - 1
    s = 0
    while q % 2 == 0:
        q //= 2
        s += 1
    if s == 1:
        return pow(n, (p + 1) // 4, p)
    z = 2
    while legendre_symbol(z, p) != -1:
        z += 1
    c = pow(z, q, p)
    r = pow(n, (q + 1) // 2, p)
    t = pow(n, q, p)
    m = s
    while t != 1:
        i = 0
        x = t
        while x != 1:
            x = pow(x, 2, p)
            i += 1
        b = pow(c, pow(2, m - i - 1, p - 1), p)
        r = (r * b) % p
        t = (t * pow(b, 2, p)) % p
        c = pow(b, 2, p)
        m = i
    return r

 

이걸로 문제를 풀어도 되고.. 근데 이거 좀 다른데..?

 

from sympy.ntheory.residue_ntheory import _sqrt_mod_tonelli_shanks as mod_sqrt

sympy에도 mod_sqrt 함수가 있어서 문제를 풀 수 있다.

 

근데 그냥 풀고 넘어갈 수는 없으니 알고리즘이 어떻게 작동하는지 보도록 하자. 원리는 다음에 알아보고..

 

tonelli-shanks 함수는 아래와 같이 동작한다.

 

1. 오일러 판별 $ a^{(p-1)/2} \equiv 1 \mod p$가 동작하는지 확인한다. 1이 아니라면 이차 잉여가 아니므로 $x^2 \equiv a \mod p$를 만족하는 $x$가 존재하지 않는다. 

 

2. $p-1 = Q\cdot2^S$를 만족하는 홀수 Q와 음이 아닌 정수 S를 찾는다.

3. mod p에서 이차 잉여가 아닌 자연수 z를 찾는다. ($i=2$부터 $i^{(p-1)/2} \equiv 1 \mod p$가 아닐 때까지 i를 증가시키고 종료 시 i를 z라고 하면 최소의 이차 비잉여를 찾을 수 있다.)

 

4. 아래 변수를 초기화한다.

$M = S$ 

$c = z^Q \mod p$

$t = n^Q \mod p$

$R = n^{(Q+1)/2} \mod p$

 

5. 아래 과정을 반복한다. (while True)

$t = 0$이면 0을 출력한다. (종료)

$t = 1$이면 R을 출력한다. (종료)

$0 < i < M$이면서 $t^{2^i} \equiv 1 \mod p$를 만족하는 최소의 자연수 i를 찾는다. for문 돌리면 될듯.

$b = c^{2^{M-i-1}} \mod p$ 대입

$M = i$

$c = b^2 \mod p$

$t = tb^2 \mod p$

$R = Rb \mod p$

 

이러다가 출력되는 숫자 +-R이 $x^2 \equiv a \mod p$의 근이 된다.

이걸 바탕으로 코드를 다시 짜보자.

 

# from sympy.ntheory.residue_ntheory import _sqrt_mod_tonelli_shanks as mod_sqrt

def is_quadratic_residue(a, p) : #legendre_symbol
    if pow(a, (p-1)//2, p) == 1 :
        return True
    else :
        return False

def tonelli_shanks(a, p) :
    #1
    if is_quadratic_residue(a, p) == False :
        return None
    #2
    Q = p-1
    S = 0
    while Q % 2 == 0 :
        Q //= 2
        S += 1
    #3
    z = None
    for i in range(2, p) :
        if not is_quadratic_residue(i, p) :
            z = i
            break
    #4
    M = S
    c = pow(z, Q, p)
    t = pow(a, Q, p)
    R = pow(a, (Q+1)//2, p) 

    #5
    while True :
        if t == 0 :
            return 0
        elif t == 1:
            return R
        for i in range(M) :
            if pow(t, 2**i, p) == 1 :
                break
        b = pow(c, 2**(M - i - 1), p)
        M = i
        c = (b**2) % p 
        t = (t * b**2) % p
        R = (R * b) % p

a = 8479994658316772151941616510097127087554541274812435112009425778595495359700244470400642403747058566807127814165396640215844192327900454116257979487432016769329970767046735091249898678088061634796559556704959846424131820416048436501387617211770124292793308079214153179977624440438616958575058361193975686620046439877308339989295604537867493683872778843921771307305602776398786978353866231661453376056771972069776398999013769588936194859344941268223184197231368887060609212875507518936172060702209557124430477137421847130682601666968691651447236917018634902407704797328509461854842432015009878011354022108661461024768
p = 30531851861994333252675935111487950694414332763909083514133769861350960895076504687261369815735742549428789138300843082086550059082835141454526618160634109969195486322015775943030060449557090064811940139431735209185996454739163555910726493597222646855506445602953689527405362207926990442391705014604777038685880527537489845359101552442292804398472642356609304810680731556542002301547846635101455995732584071355903010856718680732337369128498655255277003643669031694516851390505923416710601212618443109844041514942401969629158975457079026906304328749039997262960301209158175920051890620947063936347307238412281568760161

print(tonelli_shanks(a, p))
# print(type(mod_sqrt(a, p)))

작성한 코드에서..

mod_sqrt는 답이 나올 때도 있고 아닐 때도 있다.. 아마 두 개의 제곱근 중 큰 수가 나오거나 작은 수가 나오거나..

그래서 tonelli_shanks 알고리즘을 사용하는 것으로.. 이게 나을 듯? 다만 작동 방법을 유클리드 호제법처럼 외우고 있어야겠다.