[CryptoHack] Successive Powers

문제

풀이

x의 거듭제곱을 mod p 연산해준 결과값이 차례대로 문제에 주어져 있다.
이를 수식으로 표현해보면 다음과 같다.

첫 번째 식의 양변에 x를 곱해주면 두 식은 다음의 하나의 식으로 정리된다.

같은 방식으로 여러 개의 식을 세울 수 있다.
계산의 편의를 위해 비교적 간단한 두 개의 식을 만들어주고, x항을 소거하여
mod p 연산값이 0이 되는 세 자리 수 p를 파이썬을 통해 구해줄 수 있다.

두 번째 식에 3을 곱해준 후 첫 번째 식을 빼주면 비교적 간단한 식을 만들 수 있다.

주어진 수 중 가장 간단한 수인 4를 포함한 식을 세우고 x를 소거해준다.

첫 번째 식의 양변에 2를 곱하고 두 번째 식의 양변에 3을 곱한 후
두 식을 빼면 x항을 소거할 수 있다.

$836*3 - 335*2\equiv0(mod\;p)$

다음 식을 만족하는 세 자리 소수 p를 찾아주면 되는데,
주어진 수들이 mod p 연산된 수들이므로 p는 가장 큰 수인 851보다 커야 한다.
따라서 p를 다음과 같이 찾아줄 수 있다.

a = 836*3-335*2
for _ in range(851, 1000):
    if(a%_ == 0):
        print(_)

p = 919라는 결과가 나왔다.
이제 $4x\equiv836(mod\;919)$를 만족하는 x값만 찾아주면 된다.
gcd(4 , 919) = 1이므로 위 식을 만족하는 x값은 단 한 개 존재한다.

x = 0
while True:
    x += 1
    if (4*x-836) % 919 == 0:
        print(x)
        break

FLAG = crypto{919,209}