[Cryptohack] Diffie-Hellman Starter 1 write up

정수 모듈로 n으로 이루어진 집합은 덧셈과 곱셈의 연산을 포함하여 링(Ring)이 됩니다.
이는 집합 내의 두 요소를 더하거나 곱하는 경우에도 집합 내의 다른 요소가 반환된다는 것을 의미합니다.
모듈러스가 소수일 때: n = p인 경우, 우리는 집합 내의 모든 요소에 대한 역원을 보장받으며, 이로 인해 링은 필드(Field)로 승격됩니다. 이 필드를 유한체 Fp라고 합니다.Diffie-Hellman 프로토콜은 일반적으로 큰 소수인 유한체 Fp의 요소들로 작동합니다.
소수 p = 991과 요소 g = 209가 주어진 경우, g * d mod 991 = 1을 만족하는 역원 d를 찾아보겠습니다.

 

역원으로 d를 구하면 되는 문제이다 역원은 RSA에서도 했듯이 pycrypto 안에있는 inverse함수로 구할 수 있다.

from Crypto.Util.number import inverse
print(inverse(209, 991))

g(209) inverse 991 을 하면 당연히 d 가 나온다 

569 가 flag