H4CKING GAME - cryptography, Season1 : CanYouSolveDLP?

Season1 : CanYouSolveDLP?

 

output_.txt

0.01MB

prob.py

0.00MB

먼저 flag를 bytes_to_long()을 이용해서 정수로 변환한다.

 

 

코드를 분석해보자. 우선

m = b2l(f)

 

그리고 1024-bit 소수 p를 생성한다.

p = getPrime(1024)

 

이후 hint는 

hint = pow(p+1, 2*m+1, p**s)

여기서 중요한 건 p+1을 매우 큰 지수 2*m+1로 거듭제곱한 뒤 p**s로 나눈다는 것이다.

 

 

(p + 1)^(2m + 1)

이 값을 p에 대해 생각해 보면 중요한 특징이 있음.

 

이항정리를 이용하면 다음과 같이 전개할 수 있다.

(p + 1)^k

= 1 + k*p + k(k-1)/2*p^2 + ...

여기서 k = 2m + 1이다.

따라서 p^2를 기준으로 나머지를 생각하면 p^2 이상의 항들은 모두 사라진다.

결국 다음과 같은 형태만 남는다.

1 + k*p

즉,

hint mod p^2

를 계산하면 k = 2m+1에 대한 정보를 얻을 수 있다.

 

 

이제 hint를 이용해서 2m+1 을 찾아보자.

먼저 hint를 p^2로 나눈다.

x = hint % (p ** 2)

앞에서 확인한 것처럼 이 값은 다음 형태가 된다.

1 + (2m + 1) * p

따라서 1을 빼고 p로 나누면 2m + 1을 얻을 수 있다.

k = (x - 1) // p

그리고 마지막으로 2로 나누고 1을 빼면 원래 m을 얻을 수 있다.

m = (k - 1) // 2

 

 

이제 정수를 다시 flag 로 변환해야 함.

문제에서는 처음에 flag를 다음과 같이 정수로 변환했다.

m = b2l(f)

따라서 복구한 m을 다시 bytes로 변환하면 원래 flag가 나온다.

 

 

이때 s를 신경쓰지 않아도 되는 이유 ! 

우리에게 필요한 건 p 제곱보다 작은 범위의 정보다. p**s로 계산된 hint를 다시 p**2로 나머지 연산하면 필요한 부분을 그대로 얻을 수 있기 때문

 

그래서 hint % (p ** 2) 만 계산하면 됨