RSA 암호 시스템
🔒

RSA 암호 시스템

Created
2021/01/26 03:43
Last edited
2021/06/16 06:17
Tags
Crypto
Research

Intro

What is RSA?

RSA 암호 시스템은 공개 키 암호 방식 (Public-Key Cryptography, PKC) 의 일종이다.
1978년에 세 수학자 Rivest, Shamir, Adleman에 의해 개발되었으며, 이들의 이름의 앞글자를 따서 RSA라고 부르게 되었다.
RSA 암호 시스템은 수학적으로 큰 숫자의 소인수분해가 어렵다는 사실을 기반으로 안전성을 보장하여 동작하는 암호 시스템이다.
자세한 동작 원리는 후술하겠지만 일단 이해하기 쉽게 간단히 예를 들어서 설명해보자.
A가 B에게 메시지를 전달하려고 한다. 1. A는 B의 열린 자물쇠를 들고 와서 전달하고자 하는 메시지를 봉인한다. 2. A는 B에게 봉인한 메시지를 전달한다. 3. B는 해당 자물쇠의 열쇠로 A에게 받은 봉인된 메시지를 열어 확인한다.
CSS
복사

What is PKC?

PKC(Public-Key Cryptography, 공개 키 암호 방식)이란, 사전에 공개된 공개 키(Public Key)로 암호화하고, 비밀 키(Private Key)로 복호화를 하는 암호화 방식을 말하며, 암호화키와 복호화키가 달라 비대칭키 암호 방식(Asymmetric Cryptography)이라고도 부른다.

Mathematics

RSA 암호 시스템을 이해하기 위해서는, 해당 암호 시스템이 수학을 기반으로 동작하기 때문에 몇 가지 수학적 이론들을 알고 있어야 한다.
기본적인 수학 기호 및 용어 설명은 다음과 같다.
ZZ : 정수의 집합
gcd(a,b)gcd(a,b) : 정수 aa와 bb의 최대공약수
a ∣ ba\ |\ b : 정수 bb는 정수 aa로 나누어 떨어진다.
a∤ba∤b : 정수 bb는 정수 aa로 나누어 떨어지지 않는다.
a≡b (mod m)a ≡ b\ (mod\ m) : 정수 aa를 mm으로 나눈 나머지와 정수 bb를 mm으로 나눈 나머지는 같다.
기약잉여계 : 자연수 nn에 대하여 nn 이하의 nn과 서로소인 수들의 집합을 기약잉여계라 한다.

베주 항등식 (Bézout's Identity)

적어도 둘 중 하나는 0이 아닌 두 정수 aa, bb가 있을 때, 두 정수 x x, yy에 대하여 다음 명제가 성립한다.
ax+by=gcd(a,b)ax+by=gcd(a,b) 를 만족하는 정수 xx, yy가 반드시 존재한다.

증명

우선, 다음과 같은 집합 SS를 정의한다.
S={ax+by∣ax+by>0, x∈Z, y∈Z}S= \{ax+by∣ax+by>0,\ x∈Z,\ y∈Z\}
또한, 아래에서 집합 SS는 ∣a∣|a|와 ∣b∣|b| 중 적어도 하나를 원소로 가짐, 즉, S≠∅S≠∅ 임을 알 수 있다.
{a×1+b×0∈Sif a>0a×(−1)+b×0∈Sif a<0b≠0,∣b∣∈Sif a=0\begin{cases} a×1+b×0∈S &\text{if } a>0 \\ a×(-1)+b×0∈S &\text{if } a<0 \\ b≠0, |b|∈S &\text{if } a=0 \\ \end{cases}
집합 SS는 정의에 따라서 자연수의 부분집합이므로 자연수의 정렬성에 의해 집합 SS의 최소항이 존재함을 알 수 있다.
이제 집합 SS의 최소항을 dd라고 하자.
이때, dd는 집합 SS의 원소이므로 ak+bl=dak+bl=d 를 만족시키는 두 정수 kk, ll이 존재한다고 할 수 있다.
그리고 나머지 정리에 의해 aa를 dd로 나눈 몫 qq와 나머지 rr에 대해 다음과 같이 나타낼 수 있다.
a=dq+r (q는 정수, r은 0≤r<d인 정수)a=dq+r\ (q는\ 정수,\ r은\ 0≤r<d인\ 정수)
위 식을 rr에 대하여 정리하면 다음과 같다.
r=a−dq=a−(ak+bl)q=(1−kq)a+(−lq)br=a-dq=a-(ak+bl)q=(1-kq)a+(-lq)b
여기서 r>0r>0이라면 집합 SS의 정의에 의하여 r∈Sr∈S 이고, r<dr<d 이기 때문에 dd가 집합 SS의 최소항이라는 가정에 모순이 된다.
따라서 r=0r=0이며, 이를 대입해보면 a=dqa=dq, 즉, d ∣ ad\ |\ a 임을 알 수 있다.
똑같은 방식으로 d ∣ bd\ |\ b 임을 알 수 있다.
따라서, d ∣ ad\ |\ a 이고 d ∣ bd\ |\ b 이므로 dd는 aa와 bb의 공약수, 즉, d ∣ gcd(a,b)d\ |\ gcd(a,b) 라고 할 수 있다.
그리고 aa와 bb의 공약수 ee가 있다고 하자.
그러면 a=ea′a=ea', b=eb′b=eb' 이라고 할 수 있다.
이를 d=ak+bld=ak+bl 에 대입해보면 d=ea′k+eb′l=e(a′k+b′l)d=ea'k+eb'l=e(a'k+b'l)이므로 e ∣ de\ |\ d 라고 할 수 있다.
결론적으로, e ∣ de\ |\ d 이고 d ∣ gcd(a,b)d\ |\ gcd(a,b) 이므로 d = gcd(a,b)d\ =\ gcd(a,b) 이고,
d=gcd(a,b)=ax+byd = gcd(a,b) = ax + by 를 만족하는 두 정수 xx, yy가 존재함을 알 수 있다.

유클리드 호제법 (Euclidian Algorithm)

두 정수 aa, bb가 있고, aa를 bb로 나눈 나머지 rr(0≤r<b)(0≤r<b)에 대하여 다음 식이 성립한다.
gcd(a,b)=gcd(b,r)gcd(a,b) = gcd(b,r)

증명

aa, b b의 최대공약수, 즉, gcd(a,b)gcd(a,b)를 GG라고 하자.
그렇다면 서로소인 두 정수 a′a', b′b'에 대해 a=Ga′a=Ga', b=Gb′b = Gb' 와 같이 나타낼 수 있다.
그리고 나머지 정리에 의해 aa를 bb로 나눈 몫 qq, 나머지 rr에 대해 다음과 같이 나타낼 수 있다.
a=bq+r(0≤r<b)a = bq + r (0≤r<b)
위 식을 rr에 대하여 정리하면 다음과 같다.
r=a−bq=Ga′−Gb′q=G(a′−b′q)r = a - bq = Ga' - Gb'q = G(a' - b' q)
따라서, r=G(a′−b′q)r = G(a'-b'q), G ∣ rG\ |\ r 임을 알 수 있다.
이제 gcd(b′,a′−b′q)=G′gcd(b', a'-b'q) = G' 이라고 하자.
그렇다면 서로소인 두 정수 kk, ll에 대해 b′=G′kb'=G'k, a′−b′q=G′la'-b'q=G'l 과 같이 나타낼 수 있다.
그리고 a'을 아래와 같이 나타낼 수 있다.
a′=a′−b′q+b′q=G′l−G′kq=G′(l−kq)a' = a'-b'q+b'q = G'l-G'kq=G'(l-kq)
따라서, a′=G(l−kq)a'=G(l-kq), G′ ∣ a′G'\ |\ a' 임을 알 수 있고,
G′ ∣ b′G'\ |\ b' 이므로 G′G'은 a′a'와 b′b'의 공약수이고, a′a'와 b′b'은 서로소이므로 G′=1G'=1, 즉, b′b'와 a′−b′qa'-b'q는 서로소라는 것을 알 수 있다.
결론적으로, b=Gb′b=Gb', r=G(a′−b′q)r=G(a'-b'q) 이고, b′b'와 a′−b′qa'-b'q는 서로소이므로, gcd(b,r)=G=gcd(a,b)gcd(b,r) = G = gcd(a,b) 임을 알 수 있다.

확장된 유클리드 알고리즘 (Extended Euclidian Algorithm)

두 정수 aa, bb에 대하여 베주의 항등식인 ax+by=gcd(a,b)ax+by=gcd(a,b) 를 만족시키는 정수 xx, yy의 값은 다음과 같이 구할 수 있다.
eea.py
def eea(a, b): r0, r1, x0, x1, y0, y1 = a, b, 1, 0, 0, 1 while r1: q = r0 // r1 t = r0 r0 = r1 r1 = t - r0 * q t = x0 x0 = x1 x1 = t - x0 * q t = y0 y0 = y1 y1 = t - y0 * q return x0, y0
Python
복사

증명

유클리드 호제법에 의해, 두 정수 aa, bb의 최대공약수 gcd(a,b)gcd(a,b)에 대해서 다음과 같이 나타낼 수 있다.
gcd(a,b)=gcd(b,r1)=gcd(r1,r2)= ⋅ ⋅ ⋅=gcd(ri−1,ri)= ⋅ ⋅ ⋅gcd(a,b) = gcd(b,r_1) = gcd(r_1,r_2) =\ ·\ ·\ · = gcd(r_{i-1}, r_i) = \ ·\ ·\ ·
또한, 이를 풀어서 정리하면 아래와 같다.
a=bq0+r1 (0<r1<b)b=r1q1+r2 (0<r2<r1)r1=r2q2+r3 (0<r3<r2)...ri−1=riqi+ri+1 (0<ri+1<ri)..a = bq_0 + r_1\ (0<r_1<b)\\b = r_1q_1 + r_2\ (0<r_2<r_1)\\r_1 = r_2q_2+r_3\ (0<r_3<r_2)\\.\\.\\.\\r_{i-1} = r_iq_i+r_{i+1}\ (0<r_{i+1}<r_i)\\.\\.
따라서 ri+1=ri−1−riqir_{i+1}=r_{i-1}-r_iq_i 라는 점화식을 도출할 수 있고,
ri=axi+byir_i=ax_i+by_i (xix_i, yiy_i는 정수) 라 하고 위 점화식에 대입하여 정리하면 다음과 같다.
ri+1=axi+1+byi+1=axi−1+byi−1−(axi+byi)qi=a(xi−1−xiqi)+b(yi−1−yiqi)r_{i+1} = ax_{i+1}+by_{i+1}\\\quad\quad= ax_{i-1}+by_{i-1}-(ax_i+by_i)q_i \\\quad\quad= a(x_{i-1}-x_iq_i)+b(y_{i-1}-y_iq_i)
따라서 xi+1=xi−1−xiqix_{i+1}=x_{i-1}-x_iq_i, yi+1=yi−1−yiqiy_{i+1}=y_{i-1}-y_iq_i 라는 점화식을 도출할 수 있다.
그러면 r0=a=ax0+by0 (x0=1, y0=0), r1=b=ax1+by1 (x1=0, y1=1)r_0=a=ax_0+by_0\ (x_0=1,\ y_0=0),\ r_1=b=ax_1+by_1\ (x_1=0,\ y_1=1) 라 하고
위에서 구한 점화식으로 rir_i이 0이 될 때까지 반복하면, 그때의 xix_i, yiy_i의 값이 각각 ax+by=gcd(a,b)ax+by=gcd(a,b) 를 만족하는 x,yx, y 값이 되는 것이다.

오일러의 정리 (Euler's Theorem)

서로소인 두 정수 aa와 nn에 대하여 다음 식이 성립한다.
aφ(n)≡1 (mod n)a^{φ(n)}≡1\ (mod\ n)

증명

정수 nn의 기약잉여계 MM은 다음과 같다.
M={p1, p2, p3, ⋅⋅⋅, pφ(n)}M = \{p_1,\ p_2,\ p_3,\ ···,\ p_{φ(n)}\}
또한, MM의 모든 원소에 각각 nn과 서로소인 정수 aa를 곱한 집합 aMaM은 다음과 같다.
aM={ap1, ap2, ap3, ⋅⋅⋅, apφ(n)}aM = \{ap_1,\ ap_2,\ ap_3,\ ···,\ ap_{φ(n)}\}
이때, 집합 aMaM의 각 원소들은 nn과 서로소인 수들의 곱으로 이루어져 있으므로 모두 nn과 서로소이다.
또한, 서로 다른 MM의 원소인 pi,pjp_i, p_j에 대해 api≡apj (mod n)ap_i≡ap_j\ (mod\ n)를 만족한다고 가정하면
api≡apj (mod n)ap_i≡ap_j\ (mod\ n)
\quad\quad⇒ api−apj≡0 (mod n)ap_i-ap_j≡0\ (mod\ n)
\quad\quad⇒ a(pi−pj)≡0 (mod n)a(p_i-p_j)≡0\ (mod\ n)
인데, aa는 nn과 서로소이므로 pi−pjp_i-p_j가 nn의 배수라는 것인데, pi,pj p_i, p_j가 둘 다 nn 이하의 서로 다른 자연수이므로 −n<pi−pj<n, pi−pj≠0-n<p_i-p_j<n,\ p_i-p_j≠0이어서 모순이 발생한다.
즉, 집합 aMaM의 각 원소들을 nn으로 나눈 나머지들의 집합은 모두 nn과 서로소이며, 서로 다른 자연수이므로 nn의 기약잉여계인 MM과 같다고 볼 수 있다.
따라서, MM의 모든 원소를 곱한 값은 집합 aMaM의 각 원소들을 nn으로 나눈 나머지들의 곱과 같다는 것을 알 수 있고, 이를 식으로 나타내면 다음과 같다.
aφ(n)(p1p2⋅⋅⋅pφ(n))≡p1p2⋅⋅⋅pφ(n) (mod n)a^{φ(n)}(p_1p_2···p_{φ(n)}) ≡ p_1p_2···p_{φ(n)}\ (mod\ n)
여기서 p1p2⋅⋅⋅pφ(n)p_1p_2···p_{φ(n)}은 nn과 서로소인 수들의 곱이므로 nn과 서로소이므로 양변을 p1p2⋅⋅⋅pφ(n)p_1p_2···p_{φ(n)}으로 나눌 수 있는데, 그렇게 하면 다음과 같다.
∴ aφ(n)≡1 (mod n)∴\ a^{φ(n)}≡1\ (mod\ n)

페르마의 소정리 (Fermat's little Theorem)

소수 pp와 pp와 서로소인 정수 aa에 대하여 다음 식이 성립한다.
ap−1≡1 (mod p)a^{p-1}≡1\ (mod\ p)
따름정리 : 소수 pp에 대하여 다음 식이 성립한다.
ap≡a (mod p)a^p≡a\ (mod\ p)

증명

(i)(i) p∤ap∤a일 때
φ(p)=p−1φ(p) = p-1이고,
pp가 소수이고 p∤ap∤a이므로 pp와 aa는 서로소이다.
따라서 오일러의 정리에 의하여 ap−1≡1 (mod p)a^{p-1}≡1\ (mod\ p)이다.
또, 양변에 aa를 곱하면 ap≡a (mod p)a^p≡a\ (mod\ p)이다.
(ii)(ii) p ∣ ap\ |\ a일 때
p가 소수이고 p ∣ ap\ |\ a이므로 aa가 pp의 배수이다.
그래서 a≡0 (mod p)a≡0\ (mod\ p)이다.
또한 ap≡0 (mod p)a^p≡0\ (mod\ p)이다.
따라서 ap≡a (mod p)a^p≡a\ (mod\ p)이다.

Mechanism

Key Generation

1.
두 소수 p,qp, q를 준비한다.
2.
N=pqN = pq를 계산한다.
3.
φ(N)φ(N), 즉, (p−1)(q−1)(p-1)(q-1)과 각각 서로소인 정수 ee를 준비한다.
4.
ed≡1 (mod φ(N))ed≡1\ (mod\ φ(N))를 만족하는 정수 dd를 찾는다. (확장 유클리드 알고리즘 사용)
5.
p,qp, q는 더 이상 필요 없으며, 보안상의 문제가 될 수 있으니, 파기한다.
여기서 NN과 ee는 공개키이며, 키 생성 후 공개된다.
또한, dd는 비밀키이며, 공개되지 않는다.

Encryption

공개키 NN과 ee, 전달하고자 하는 메시지 m (m<N)m\ (m<N)에 대하여 다음을 계산한다.
c=me mod N\quad\quad c = m^e\ mod\ N
여기서 cc가 암호화된 메시지이다.

Decryption

공개키 N, 비밀키 d, 암호화된 메시지 c에 대하여 다음을 계산한다.
m=cd mod N\quad\quad m=c^d\ mod\ N
여기서 mm이 복호화된 메시지이다.

Proof

우선 복호화 식을 정리해보면 다음과 같다.
m=cd mod Nm=c^d\ mod\ N
=(me mod N)d mod N=(m^e\ mod\ N)^d\ mod\ N
=med mod N=m^{ed}\ mod\ N
⇒ med≡m (mod N)m^{ed}≡m\ (mod\ N)
따라서 위 합동식 RSA 암호 시스템을 검증하기 위해서는 med≡m (mod N)m^{ed}≡m\ (mod\ N)를 증명하면 된다.
우선 N=p×qN = p × q이므로 위 합동식이 mod pmod\ p일때와 mod qmod\ q일때 모두 성립하면, mod Nmod\ N일때도 성립하기 때문에, mod Nmod\ N 대신 mod pmod\ p를 사용해보자.
또한, ed≡1 (mod φ(N))ed≡1\ (mod\ φ(N))이므로, 적당한 정수 kk에 대하여 ed=k×φ(N)+1=k(p−1)(q−1)+1ed = k×φ(N)+1=k(p-1)(q-1)+1 이라 할 수 있다.
이제 이들을 위 합동식에 대입하여 정리해보면 다음과 같다.
med≡m (mod N)m^{ed}≡m\ (mod\ N)
⇒ med≡m (mod p)m^{ed}≡m\ (mod\ p)
⇒ mk(p−1)(q−1)+1≡m (mod p)m^{k(p-1)(q-1)+1}≡m\ (mod\ p)
⇒ mk(p−1)(q−1)×m≡m (mod p)m^{k(p-1)(q-1)}×m≡m\ (mod\ p)
⇒ (mp−1)k(q−1)×m≡m (mod p)(m^{p-1})^{k(q-1)}×m≡m\ (mod\ p)
여기서 두 가지 경우로 나눌 수 있는데,
첫 번째 경우는 m이 p의 배수가 아닐때이다.
mm이 pp의 배수가 아니면 pp가 소수이기 때문에 페르마의 소정리에 의해 mp−1≡1 (mod p)m^{p-1}≡1\ (mod\ p)이고, 이 식을 위에 대입해보면
(mp−1)k(q−1)×m≡m (mod p)(m^{p-1})^{k(q-1)}×m≡m\ (mod\ p)
⇒ 1k(q−1)×m≡m (mod p)1^{k(q-1)}×m≡m\ (mod\ p)
⇒ m≡m (mod p)m≡m\ (mod\ p)
이므로 합동식이 성립하게 된다.
두 번째 경우는 mm이 pp의 배수일 때이다.
mm이 pp의 배수이면 위 합동식의 양변은 모두 p p로 나누어 떨어져서 0이 되므로, 합동식이 성립하게 된다.
Made with