이제 이전에 만든 RSA 프로그램을 기반으로 만들어보겠다. 간단하게 RSA와 같이 소수를 생성하고 어쩌고저쩌고 하면 되겠구나! 싶었다. 그런데, 예상못한 어려움에 부딪혔다. 랜덤한 소수값은 구할 수 있는데, 그 소수값의 원시근은 어떻게 구할까...? 일단 소수값은 RSA 프로그램에서 했던 것 처럼, 밀러-라빈 소수 판정법을 이용해서 구하면 된다. $$a^{p-1} \equiv 1 \pmod{p}$$ 위의 조건을 갖는 원시근을 찾아야한다. (연산량이 너무 많다...) 그런데.. 열심히 코드를 짜다 보니.... 알게된 것이 있다. 디피헬만의 q(소수) , a(원시근)는 공개된 값이라서 상수로 Fix 해둔 값으로 해도 된다는 것이였다.... 3시간 정도 찾아보고 공부했었는데,,,

오우! RSA 암호화 프로그램을 개발하던 중, 디피 헬만 암호화 프로그램을 구현해 보라는 학교 과제가 생겼다. 먼저, 디피헬만 알고리즘은 이산대수의 복잡성을 보안 기법으로 사용한다. 소수 q와 q의 원시근 a을 사용해서 복잡도가 증가하는데, 키를 만드는 방법은 아래와 같다. (엘리스와 밥으로 예시를 들어서 설명하겠다.) 1. 엘리스는 개인키($X_A$)와 공개키($Y_A$)를 생성한다. $X_A < q$ $Y_A \equiv a^{X_A} \pmod{q}$ 2. 밥은 개인키($X_B$)와 공개키($Y_B$)를 생성한다. $X_B < q$ $Y_B \equiv a^{X_B} \pmod{q}$ 3. 엘리스와 밥은 공개키를 서로 교환한다. 4. 엘리스는 밥의 공개키($Y_B$)로 비밀키($K_A$)를 생성한다..

학교 과제로 개발한 RSA 프로그램이 있으므로, 이것을 개선하는 쪽으로 개발을 진행할 것이다. 코드는 깃허브에 모두 올려져있다. 개발에 참고한 코드는 여기있다. 많은 부분을 카피했다. 파일명은 encript.py이고 내용은 아래와 같다. from argparse import ArgumentParser from util import get_random_prime, get_random_coprime, mod_exp parser = ArgumentParser(description='RSA암호화') parser.add_argument('-f', '--file_path', action="store", dest="file_path", type=str, help="file path", default=None) par..

이번 포스팅은 RSA 암호화 프로그램을 개발하고자 한다. RSA 암호화 알고리즘은 공개키 암호화 알고리즘으로 개인키와 공개키를 만들어서, 개인키로 암호화를 하면 공개키로만 복호화를 할 수 있고 공개키로 암호화를 하면 개인키로만 복호화를 할 수 있다. 먼저 개인키와 공개키를 만들어보자 (간단하다!) 개인키와 공개키 만들기 1. 소수인 $ p, q $를 무작위로 뽑는다. 2. n을 구한다. $n = p \times q$ 3. 오일러 수를 구한다. $\Phi = (p - 1)(q - 1)$ 4. $\Phi$와 서로소인 정수 $e$를 구한다. 5. $e \times d \pmod{\Phi} = 1$ 인 $d$를 구한다. 여기서 개인키는 $(d, n)$, 공개키는 $(e, n)$이다. 암호화 복호화 개인키를 이용..