Multiplication

먼저 이 코드를 분석하기 위해서는 자바 디컴파일러가 필요합니다. 첫 번째로 JD-GUI 를 사용해 디컴파일링을 시도했지만, 이 문제는 의도적으로 JD-GUI 를 깨뜨리는 안티 디컴파일이 들어가 있습니다. 그래서 CFR 로 소스를 보기로 했다.

java -jar cfr.jar target.jar --outputdir out

밑에는 내가 얻어낸 소스다.

코드를 보면 이 문제는 long 오버플로우를 이용하는 문제라는 걸 알 수 있습니다. 그걸 뒷받침하는 증거 몇 개를 찾아낼 수 있습니다.

1. long 타입

long var1 — Java long 은 signed 64-bit 이고, 범위는 -2^63 ~ 2^63 - 1 입니다.

2. 정상적인 산술 역산이 실패한다

만약 오버플로우가 아니라면, 문제는 이렇게 단순해야 합니다.

l = (-1536092243306511225) / 26729

하지만 실제로는:

• 나눗셈 결과가 정수가 아님 (유리수임)
• Java long 은 소수를 허용하지 않음
• 즉 정상적인 수학 문제로 성립하지 않음

CrackMe 에서 “정수 입력”을 요구하는데 정수 해가 없다는 건 의도적인 함정입니다.

long l = Long.decode(stringArray[0]);
if ((l *= 26729L) == -1536092243306511225L) {
    System.out.println("Correct!");
}

이 수식으로부터, Java long 은 64-bit 2의 보수이므로 모든 연산은 mod 2⁶⁴ 입니다.

l × 26729 ≡ −1536092243306511225   (mod 2^64)
l         ≡ −1536092243306511225 × 26729^-1   (mod 2^64)

이제 계산은 코드를 만들어 하면 됩니다. 저는 AI 에게 이 로직을 가지고 코드 생성을 부탁했습니다.

import java.math.BigInteger;

public class SolveMultiplicative {
    public static void main(String[] args) {
        // 2^64 (long overflow의 모듈러)
        BigInteger MOD = BigInteger.ONE.shiftLeft(64);

        // 문제에서 비교하는 결과값 (long literal)
        BigInteger target = BigInteger.valueOf(-1536092243306511225L);

        // 곱해지는 상수
        BigInteger multiplier = BigInteger.valueOf(26729);

        /*
         * 핵심 수학:
         *   x * 26729 ≡ target        (mod 2^64)
         *   x         ≡ target * inverse(26729)  (mod 2^64)
         */
        BigInteger inverse = multiplier.modInverse(MOD);
        BigInteger x = target.multiply(inverse).mod(MOD);

        /*
         * JVM long은 signed 64bit이므로
         * MSB(63bit)가 1이면 음수로 변환
         */
        if (x.testBit(63)) {
            x = x.subtract(MOD);
        }
        System.out.println("Answer = " + x);
    }
}

답, 플래그는: -8978084842198767761