[암호학] 1. RSA

Soowon Jeong·2021년 12월 28일
1

암호학

목록 보기
2/9
post-thumbnail

이전 글에서는 보안의 기본 개념과 대표적인 암호 시스템에 대해 간략하게 설명했습니다.
비대칭 암호에서 어려운 문제란 무엇이고 그것이 어떻게 사용되는지 알아보겠습니다. 자세한 내용보다는 개념 위주로 서술하겠습니다.

RSA 암호

RSA 암호는 IFP (Integer Factorization Problem) 문제를 사용합니다. IFP 문제는 간단히 소인수분해라고 생각하면 됩니다.

pq=npq = n일 때, ppqq를 이용해 nn을 구하는 것은 쉽지만 nn으로 ppqq를 구하는 것은 어렵습니다.

Number Theory

소수

먼저 소수(prime number)가 무엇인지에 대해 알아보겠습니다.

소수 pp11보다 크며, ±1,±p\pm1, \pm p만을 약수로 가집니다.

또한 이 소수들의 곱을 이용하면 모든 수를 표현할 수 있습니다.

1보다 큰 모든 정수 aa에 대하여, a=p1α1p2α2ptαt(p1<p2<pt, pi is prime number)a = p_{1}^{\alpha_{1}} \cdot p_{2}^{\alpha_{2}} \cdots p_{t}^{\alpha_{t}} (p_{1} < p_{2} \cdots < p_{t},\ p_{i}\ \text{is prime number}) 로 표현할 수 있는 단 하나의 방법이 존재합니다.

서로소

최대공약수에 대한 설명은 생략하겠습니다. 두 수 aa, bb에 대해서 c=gcd(a,b)c = \gcd(a, b)aa, bb의 최대공약수라고 합니다.
만약 gcd(a,b)=1\gcd(a, b) = 1이라면 aabb는 서로소입니다.

모듈러 연산

어떤 정수 aa와 양의 정수 nn이 있을 때, aann으로 나누면 다음과 같은 관계가 성립합니다.

a=qn+r, 0rn and q=a/na = q \cdot n + r,\ 0 \leq r \leq n\ \text{and}\ q = \lfloor a / n\rfloor. qq는 몫, rr은 나머지입니다.
여기서 amod na\mod\ nrr, 즉 나머지가 됩니다.

만약 amodn=bmodna\mod n = b\mod n이라면 abmodna \equiv b\mod n이라고 쓰며, mod n\text{mod}\ n에 대해 합동이라고 합니다.

Euler's Totient Function

오일러의 토션트 함수 또는 오일러의 파이 함수라고 부르는 함수가 있습니다.
이 함수는 양의 정수 nn에 대해 nn보다 작은 정수 중 1을 포함한 서로소의 개수를 나타냅니다.
표기는 다음과 같습니다.

ϕ(n)\phi (n)

오일러 토션트 함수는 다음과 같은 성질이 있습니다.

어떤 양의 정수에 nn에서 다른 소수 pp, qq에 대해, n=p×qn = p \times q일 때, ϕ(n)\phi (n)은 다음과 같이 정해집니다.
ϕ(n)=ϕ(pq)=ϕ(p)ϕ(q)=(p1)(q1)\phi (n) = \phi (pq) = \phi (p)\phi (q) = (p-1)(q-1)

페르마의 소정리

페르마의 소정리는 다음과 같습니다.

pp가 소수이고 aapp로 나눠지지 않을 때 ap11modpa^{p-1} \equiv 1\mod p가 성립합니다.

증명은 생략하겠습니다.

오일러의 정리

오일러의 정리는 페르마의 소정리의 일반화를 통해 얻어집니다.

모든 서로소인 aann에 대해 aϕ(n)1modna^{\phi (n)} \equiv 1\mod n이 성립합니다.

오일러 토션트 함수의 성질을 이용해 다음과 같은 따름정리가 나오게 됩니다.

두 개의 소수 ppqq에 대해 정수 mmnnn=pqn = pq이고 0<m<n0<m<n일 때,
mϕ(n)+1=m(p1)(q1)+1mmodnm^{\phi (n) + 1} = m^{(p-1)(q-1) + 1}\equiv m\mod n

RSA 암호의 구현

이제 위와 같은 정리들을 이용해 만들어진 RSA 암호를 살펴보겠습니다.

키 생성

  1. 두 개의 소수 ppqq를 정합니다.
  2. pq=npq = n(p1)(q1)=ϕ(n)(p-1)(q-1) = \phi (n)을 구합니다.
  3. ϕ(n)\phi (n)과 서로소인 정수 ee를 고릅니다.
  4. 1modϕ(n)=ed1\mod \phi (n) = ed가 되도록 dd를 찾습니다.

여기서 nnee가 공개키, dd가 개인키가 됩니다. 왜 그럴까요?
그 이유를 설명하기 위해서 암호화 과정과 복호화 과정을 설명하겠습니다.

암호화와 복호화

  • 암호화
    C=Memodn for 0<M<NC = M^e \mod n\ for\ 0 < M < N (여기서 MM은 평문, CC는 암호문입니다.)
  • 복호화
    M=CdmodnM = C^d \mod n

복호화가 왜 성립하는지 증명하겠습니다.

Cd=(Me)d=Med=Mkϕ(n)+1=M(Mϕ(n))k=M\begin{aligned} C^d &= (M^e)^d\\ &= M^{ed}\\ &= M^{k\phi (n) + 1}\\ &= M\cdot (M^{\phi (n)})^k\\ &= M \end{aligned}

Cd=MedC^d = M^{ed}까지는 암호화의 과정을 적용시키면 쉽게 계산할 수 있습니다.
키 생성 과정의 4번에서 모듈러의 정의를 적용시키면 ed=kϕ(n)+1ed = k\phi (n) + 1이 나오고,
Mϕ(n)M^{\phi (n)}오일러 정리를 적용하면 1이 됩니다.

암호화 과정과 복호화 과정을 함수로 나타내면 다음과 같습니다.

C=f(M)=MemodnM=f1(C)=CdmodnC = f(M) = M^{\textcolor{green} {e}} \mod \textcolor{green}{n}\\ M = f^{-1}(C) = C^\textcolor{red}{d} \mod n

이전 글에서 비밀통로 일방향 함수는 특정한 정보를 알고 있다면 역함수를 구하기 쉽다고 설명했습니다.
여기서 dd를 알고 있다면 역함수를 구하기 쉬울 것입니다.
암호문을 보내는 사람이 공개키로만 암호를 만들면 개인키를 가지고 있는 수신자는 다시 암호를 평문으로 변환할 수 있게 됩니다.

다음 글에서는 또 다른 어려운 문제인 DLP와 그 어려움을 이용한 ElGamal에 대해서 설명하겠습니다.

0개의 댓글