RSA [2]

RSA 개념과 이론은 http://richong.tistory.com/67 해당 위치에 존재

실습

RSA 인증서 형태

.pem : base64 형태로 존재함

.der :  바이너리 형태로 존재함

RSA 키 생성 과정 및 코드

Φ(n) : 1부터 n까지의 자연수 중, n과 서로 소인 것의 개수

1 .랜덤한 두개의 큰소수 p, q 를 고릅니다. 

2.  n = p*q 와 Φ(n) = (p-1)(q-1) 를 계산 합니다.

3.  랜덤한 정수 e 를 선택 합니다. 1 < e < Φ(n), gcd(e, Φ(n))=1

4.  확장된 유클리드 알고리즘을 사용해서 정수 d를 계산 합니다. 

1 < d < Φ(n), ed ≡ 1 (mod Φ(n))

5,  public Key 는 (n, e)가 되고, private Key 는 d가 된다.

#!/usr/bin/python
 
import gmpy
import sys
 
# p는 큰 소수 1
p = 169524110085046954319747170465105648233168702937955683889447853815898670069828343980818367807171215202643149176857117014826791242142210124521380573480143683660195568906553119683192470329413953411905742074448392816913467035316596822218317488903257069007949137629543010054246885909276872349326142152285347048927
 
# q는 큰소수 2
q = 170780128973387404254550233211898468299200117082734909936129463191969072080198908267381169837578188594808676174446856901962451707859231958269401958672950141944679827844646158659922175597068183903642473161665782065958249304202759597168259072368123700040163659262941978786363797334903233540121308223989457248267
 
 
#1 < e < Φ(n) 숫자
e = 65537
 
#암호문
c = 4531850464036745618300770366164614386495084945985129111541252641569745463086472656370005978297267807299415858324820149933137259813719550825795569865301790252501254180057121806754411506817019631341846094836070057184169015820234429382145019281935017707994070217705460907511942438972962653164287761695982230728969508370400854478181107445003385579261993625770566932506870421547033934140554009090766102575218045185956824020910463996496543098753308927618692783836021742365910050093343747616861660744940014683025321538719970946739880943167282065095406465354971096477229669290277771547093476011147370441338501427786766482964
 
 
n = p * q # 두개의 소수의 곱
 
phi = (p-1)*(q-1) #Φ(n) = (p-1)(q-1) 를 계산
 
d = gmpy.invert(e, phi)  #1 < d < Φ(n), ed ≡ 1 (mod Φ(n))
                         #d를 구한다. e와 Φ(n)가 있어서 d를 구할수 있음
 
#d는 개인키
#(n,e) 는 공개키
 
#   pow(암호문, 개인키, n)
m = pow(c, d, p*q)
 
print(hex(m)[2:].replace('L','').decode('hex'))