[CryptoHack] DIFFIE-HELLMAN (Diffie-Hellman Starter 1, 2)

Diffie-Hellman Starter 1

문제 및 설명

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

풀이

g * d mod 991 = 1에 대한 역원 d는 inverse 함수로 구할수 있다.

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

답은 569이다.

Diffie-Hellman Starter 2

문제

유한체 Fp의 모든 요소는 곱셈의 반복적인 작용으로 생성된 부분집합 H를 만들기 위해 사용될 수 있습니다. 다른 말로, 요소 g: H = {g, g^2, g^3, ...}입니다. Fp의 원시 원소(Primitive Element)는 부분집합 H = Fp를 만족하는 요소입니다. 즉, Fp의 모든 요소는 어떤 정수 n에 대해 g^n mod p로 표현될 수 있습니다. 이러한 이유로 원시 원소는 종종 유한체의 생성자(Generator)로도 불립니다. p = 28151인 유한체에 대해, Fp의 원시 원소 중 가장 작은 요소 g를 찾아보겠습니다. ✍이 문제는 브루트 포스를 통해 풀수 있지만, 다른 계산에 대하여 괜찮은 방법으로 풀수 있습니다.

풀이

해당 문제는 sage math를 통해 primitive_element함수를 사용하여 가장 작은 요소인 g값을 찾을 수 있다.

print(GF(28151).primitive_element())

https://cocalc.com/features/sage?utm_source=sagemath.org&utm_medium=icon

답은 7이다.