PARI / GP 를 사용한 빅데이터 연산 : diffie hellman key exchange

PARI/GP 를 사용해 디피 헬만 키 교환 방식을 실제 연산으로 확인해 본다.

여기서 소수(prime)라는 수가 정말 중요하다.

이 소수의 규칙을 찾은 사람은 아직까지 없다. 

위키피디아에는 소수라는 값은 파이라는 값과 연관 있다고 나와있다. 

이 파이는 원이라는 수와 연관이 있으므로 자연현상과 관련있다는 점을 알 수 있다. 

1. 소수 구하기

1) isprime(양수) : 이 값이 소수인지 알 수 있다. (참 : 1 거짓 : 0 반환)

2) nextprime(양수) : 어떤 수보다 크거나 같은 수 중에 가장 가까운 소수 반환

2. 랜덤한 수 구하기

1) random(양수) : 0 ~ 어떠한 수 내의 랜덤한 값 반환

이 수를 사용하여 로또 번호를 랜덤으로 뽑을 수도 있다.

for(n=1, 6, print(random(45)+1))

다음과 같이 입력하면 로또번호 6개를 받을 수 있을 것이다.

2. 함수 작성하기

함수를 입력했을 때 프로그램을 종료하면 함수가 날라가게 된다.

따라서 함수는 텍스트 파일에 작성하고 불러오는 방식으로 사용하는 것이 좋다.

예제로 함수를 사용해 nextprime()를 실제 구현해 본다.

마지막에 print(n) 대신 return n이나 그냥 n을 사용해도 무관하다.

참고로 우리가 작업한 기록은 모두 gp_history.txt에 저장된다.

3. 모듈로 연산

a - c = b * k 와 같은 연산이 있을 때 

모듈로 연산하기 위해선 c = Mod(a, b)를 사용한다.

출력이 Mod(c,b)로 출력되는데 c만 구하기 위해선 lift(Mod(a,b))를 사용한다.

4. 제너레이터 생성기

Z5 = {0,1,2,3,4} 라 할 때

이는 즉 0보단 크거나 같고 5보단 작은 수를 의미한다.

이때 이 때 Z5에서 0을 제외한 어떤 수 x를 선택한 뒤 x^n mod 5 연산을 한 값이 Z5에 있는 모든 값이 나오게 되면 이는 제너레이터라고 한다.

또는 x^n mod 5에서 값이 1이 나 올 때 이 때 n이 phi(x)과 같으면 이를 제너레이터이라 한다.

이를 표현하기 위해 order을 사용한다.

phi(x) = 4

order(2) = 4

order(3) = 4

order(4) = 2

이다. 따라서 2와, 3는 제너레이터이지만 4는 제너레이터가 아니다.    

이 때 가장 근접한 제너레이터를 찾기 위해선 Znprimroot를 사용하면 된다.

제너레이터의 개수를 알기 위해선 eulerphi(eulerphi(x)) 를사용하면 된다.

5.  디피 헬만 키 교환

위의 수행을 통해 제너레이터가 2라는 것은알수있다.

이때 여기서 0보다 크고 5보단 작은 어떤 수를 주었을 때

그 수가 나오기 위해선 제너레이터를 몇 승을 해야 선택한 수가 나오는 가?

이 문제가 난제이다.

 4 == 2 ^ n mod(5)

여기서는 n이 2라는 것을 쉽게 알 수 있다. 

하지만 mod 값이 크고, 선택한 값이 클 경우 문제가 굉장히 어려워진다.

1) 엄청 큰 소수 구하기 : 10^ 50 + 151

2) 제너레이터 선택 : 11

tip) 제너레이터로 만들 수 있는 개수

3) 제너레이터가 맞는지 확인

4) 개인키 선택 및 확인

znlog를 사용해 찾기 어려운 값인지 확인한다. 찾지못할경우 어려운 수

이 10^50은 바닷물에 콧물을 빠뜨린 뒤 찾는 것과 비슷하다고 한다.

5) 비밀키는 g^nm mod p 이다.

이것을 깨기 위해 위키피디아를 보면 index calculus 와 같은 방법을 사용하지만 아직도 깨기 힘들다고 한다.