diffie-hellman

+/CRYPTO

diffie-hellman

육키티 2025. 1. 10. 04:23

cryptohack starter 스테이지 하나씩 풀어보자

정수 modulo N으로 이루어진 set은 덧셈과 곱셈을 포함하여 R이 된다.

n=p(소수)일 때, set 내 모든 요소의 역원은 존재한다. 때문에 R은 F가 가능하다. 이 F를 finite field(?) Fp라고 한다. Diffie-Hellman은 큰 소수인 유한체 Fp의 element들로 이루어진다.

문제) p=991과 F(991)의 element g=209가 주어졌을 때, find the inverse element d such that g*d(mod991)=1

파이썬 코드를 짜서 해결하자

for i in range(0,990):
    res=(i*209)%991
    if res==1:
        print("inverse: %d" %i)

Fp의 모든 element는 제곱을 통하여 subgroup H를 만들 수 있다. element g의 subgrup H=<g>

primitive element(?) Fp는 H가 Fp*이다. 0을 제외한 Fp의 element는 어떠한 정수 n에 의해 g^n(mod p)로 정의할 수 있다.

이때 primitive element는 generators of the finite field로 불린다.

문제) F(28151)에서 primitive element가 될 수 있는 가장 작은 element g 구하기

브루트포스보다 더 괜찮은 방법을 찾아보라고 한다..

일단 기초정수론에 대해 가물가물하므로, 몇가지 복습했다.

Zn* 기약 잉여계: Zn의 원소 중에서 곱셈에 대한 역원이 있는 숫자들의 집합

이때 n이 소수 p이면, Zp*={1, .., p-1}

문제를 수식으로 정리하면,

F(28151)*=<g>={1,...,28150}={g^n,g^(n+1),...}일 때 g 구하는 방법

1. 소인수분해 28150=2*5^2*563

2. 2부터 p-1중에서 다음 조건 만족

#소인수 n일 때 
g^(28150/n) =/= 1 (mod 28151)

파이썬 코드를 짜보자

p=28151
arr1=[2,5,563]
arr2=[(p-1)//arr1[0],(p-1)//arr1[1],(p-1)//arr1[2]]

for g in range(2,p):
    flag=True
    for i in arr2:
        if pow(g,i,p)==1:
            flag=False
            break
    if flag==True:
        print(f"The smallest g={g}")
        break