문제

중국인의 나머지 정리는 모듈러가 서로 소인 일련의 선형 합동에서 고유한 해를 제공합니다.

즉, 일련의 임의의 정수 $a_i$와 서로소인 $n_i$가 주어진다고 할 때, 다음의 선형 합동이 유지되는 경우:

참고로 “서로소인 정수 쌍”이라는 말은 ${n_1, n_2, …, n_i}$의 정수 집합이 주어졌을 때, 집합에서 선택한 모든 정수 쌍이 서로 서로소임을 의미합니다: $gcd(n_i, n_j) = 1$.

x ≡ a1 mod n1
x ≡ a2 mod n2
...
x ≡ an mod nn

$N = n_1 * n_2 * … * n_n$ 인 경우, x ≡ a mod N으로 고유한 해가 존재합니다.

암호학에서는 중국인의 나머지 정리를 사용하여 매우 큰 정수 문제를 여러 더 쉬운 문제들로 줄이는 데 도움을 받습니다.

다음 선형 합동이 주어진 경우:

x ≡ 2 mod 5
x ≡ 3 mod 11
x ≡ 5 mod 17

x ≡ a mod 935에서 정수 a를 찾아보세요.

가장 큰 모듈러를 갖는 합동부터 시작하여, x ≡ a mod p에서 임의의 정수 k에 대해 x = a + k*p로 쓸 수 있음을 이용하세요.

풀이

5, 11, 17이 쌍마다 서로소이므로 연립 합동식은 $5 * 11 * 17 = 935$ 에 대하여 유일한 해를 가집니다. $m = 935, n_1 = 187, n_2=85, n_3=55$라고 하겠습니다

$n_1s_1 ≡ 187s_1 ≡ 2s_1 ≡ 1\,(mod\,5)$

$n_2s_2 ≡ 85s_2 ≡ 8s_2 ≡ 1\,(mod\,11)$

$n_3s_3 ≡ 55s_3 ≡ 4s_3 ≡ 1\,(mod\,17)$

위 식들을 풀면 $s_1 = 3, s_2 = 7, s_3 = 13$ 입니다.

그러므로 $x ≡ a_1n_1s_1 + a_2n_2s_2 + a_3n_3s_3 ≡ 21873 + 3857 + 55513 ≡ 6482 ≡ 872\,(mod\,935)$ 입니다

Python code

if __name__=="__main__":
    from pwn import *
    import math

    m = 5  * 11 * 17
    n1 = 11 * 17
    n2 = 5 * 17
    n3 = 5 * 11

    s1 = pow(n1, -1, 5)
    s2 = pow(n2, -1, 11)
    s3 = pow(n3, -1, 17)

    result = 2*n1*s1 + 3*n2*s2 + 5*n3*s3

    log.success(f'Flag = {result}')