RSA 맨날 까먹는 거 같다.

RSA?

공개키 암호화 알고리즘 중 하나이다. 공개 키, 비밀 키를 사용하기 때문에 비대칭 암호라고도 한다. Asymmetric.

Key

Trap door one way function의 방식이다. 이게 정말 신기하지 않나? 수학 전공은 아니고, 현암응도 안 들었지만 이런 방식이 있다는 게 넘 신기하다.

암튼, 키를 생성하는 방법은 두 가지가 있다.

1. 소인수분해

   N=pq이다.

2. 이산대수

   g^x mod p

이중에서 RSA의 키생성은 1번째를 이용한다. 서술하자면, 매우 큰 소수 p,q를 고르고, n=pq와 k=O(n)를 구한다(오일러 함수 약자 찾기가 귀찮아서 대문자 O로 대체) 여기서 ed=1 (mod O(n))이다. 이때 e가 public, d가 private key이다.

오일러 함수

어디서는 오일러의 피 함수?라고 하네. 난 걍 오일러 함수(totient func)으로 하겠다. 위에서 설명한 것에 대한 보충인데 오일러 함수는 1부터 n까지의 양의 정수 중에 n과 서로소인 수의 개수를 근으로 내는 함수이다. gcd(n,k)=1인 근의 개수를 세면 된다.

+) 아 파이를 피라고 쓴 거구나.

소수 p,q(mod n)에 대해서 오일러 파이 함수 공식은 O(n)=(p-1)(p-1) (mod n)이다.

메시지 암호화

c=m^e (mod n)
m=c^d (mod n)

간단하죠? m=m^(ed)가 되는데 ed=1이니까 복호화가 된다.

def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a

def dec(pk,c):
  key, n =pk
  m=[chr((char**key)%n) for char in c]
  return ''.join(m)

def enc(pk,m):
  key, n=pk
  c=[(ord(char)**key)%n for char in m]
  return c

def get_private_key(e, tot):
    k=1
    while (e*k)%tot != 1:
        k+=1
    return k

def get_public_key(tot):
  e=2
  while e<tot and gcd(e, tot)!=1:
      e += 1
  return e

n = p*q
totient = (p-1)*(q-1)
e = get_public_key(totient)
d = get_private_key(e, totient)
c = enc((e,n), m)
m = dec((d,n),c)