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 (mod2^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