[Crypto] RSA 파이썬 코드 및 개념

RSA 공개키 개인키 구하는법

 

1. p 값, q값 생성 ( 무작위로 큰 두 소수를 선택 )

# 파이썬에서 p, q 값을 생성하는 방법
from Crypto.Util.number import getPrime

p = getPrime(1024) #1024 = 1024bit를 의미
q = getPrime(1024)

pycryptodome이 설치되어 있지 않을 경우

# pycryptodome 설치되어있지 않을 시 설치법
$ pip install pycryptodome

2. n 계산

p와 q를 곱하면 n이 된다.

n = p * q

 

 

3. phi 계산

(p-1)과 (q-1)을 곱하면 phi가 된다.

*phi = n이하의 n과 서로소인 수들의 개수

phi = (p-1) * (q-1)

 

4. e 선택

주로 65537

다른 값이 되더라도 1<e<phi이고 phi와 서로소인 수로 선택

 

 

5. d 계산

mod phi에 대한 e의 곱셈의 역원을 구한다.

de=1(mod phi)를 만족하는 d를 계산한다.

즉, 임의의 정수 k에 대해서 다음을 만족할 것

de=1+k(phi)

# gmpy2의 invert나 divm으로 계산할 수 있다.
d = invert(e, phi)
d = divm(1, e, phi)
# invert = 바로 곱셈의 역원을 구해준다
# divm = 첫번째 인자를 1로 지정해주면 역원을 구해준다.

gmpy2 설치법 *추후 내가 작성한 글로 변경할 예정

https://domdom.tistory.com/169

[Python3] 리눅스/Windows에서 python gmpy, gmpy2 설치 방법

 

6. 결과

공개키: (e, n)

개인키: (d, n)

---

RSA 암호화 및 복호화

암호화

암호문 = 평문^e mod n

 

복호화

복호문 = 암호문^d mod n