HSOC 암호학 멘토링 (rsa 기본원리)

동아리 멘토링 할 때도 본인이 멘토면 자료는 직접 만들어서 합시다
이거 혹은 다른 멘토 자료 그대로 본인 블로그에 올리거나 자료로 만들어서 쓰지 말고.. 안 그럴거라 믿을게요

RSA

최초의 공개 키 암호화 방안 (Rivest-Shamir-Adleman)
암호화, 복호화에 다른 키를 사용 (Public key로 암호화, Private key로 복호화)
→ 비대칭키 암호
→ 공개키 암호
RSA 등장 후 1년 후 디피, 헬먼이 공개키 암복호화 개념 소개 → 공개키 서명 수행 x
소인수분해 이용
디지털 서명 구축에 사용됨
개인키 소유자 → 서명 가능
공개키 이용 → 서명의 유효성 확인
트랩도어 치환 개념을 활용

트랩도어 치환

수 $x$를 같은 범위의 수 $y$로 변환하는 함수
공개키를 이용해서 $x$로부터 $y$를 계산하기 쉬움
하지만 개인키를 모르면 $y$로부터 $x$를 계산하는게 사실상 불가능한 방식으로 변환한다는 특징
→ RSA의 경우 $x$가 평문, $y$가 암호문
 

개념1

유클리드 알고리즘

$$ GCD(A,B)\;=\;GCD(B,r) $$
: 주어진 두 수 사이에 존재하는 최대공약수(GCD)를 구하는 알고리즘
두 수 : $a, b \;\;(a>b)$
몫 : $q$
나머지 : $r$
위를 정리해보면 $a = b*q+r$
유클리드 알고리즘은 위 식에서
$a = b*q+r$
$b = b1*r+r1$
$b1 = b2*r1+r2$
…
위와 같은 과정을 거쳐 나머지인 $r_n$이 0이 되었을 때 $b_n$의 값이 두 수의 최대공약수라는 것
위 식을 이용해서 두 수의 최대공약수를 구한다면 다음과 같음
두 수 : 100, 16
100 = 16*6+4
16 = 4*4+0
원래 우리가 일반적으로 하는 방식인 소인수분해한 다음 최대공약수를 구하는것과 비교해보면 훨씬 간단함
100 = 225*5
16 = 222*2
최대공약수 = 2*2 = 4
 

베주 항등식

확장 유클리드 알고리즘 → 베주 항등식의 명제를 가정
두 정수와 그 최대공약수 사이 관계 보여주는 항등식
3가지 참인 명제
$GCD(a, b) = d$ 라고 할 때

1. $ax + by = d$ 를 만족하는 정수 $x, y$가 존재
2. $d$는 정수 $x, y$에 대하여 $ax + by$ 로 표현할 수 있는 가장 작은 정수
3. $ax + by$ 로 표현될 수 있는 모든 정수는 $d$의 배수

증명

$$ S\;=\;ax\;+\;by>0\;|\;x,y\in ℤ $$
집합 $S$는 자연수의 부분집합, $S$가 공집합이 아닐 경우
자연수 정렬성 → “공집합이 아닌 양의 정수의 모든 집합은 최소 원소를 갖는다.”
 

확장 유클리드 알고리즘

유클리드 알고리즘을 확장하여 $a, b$의 최대공약수 뿐만 아니라 $ax + by = gcd(a, b)$를 만족하는 정수해 $x, y$를 찾는 알고리즘
ex) $gcd(240, 46) = c$ 라고 할 때 $240x + 16y = c$의 해와 $c$ 구하기

최대공약수는 $2,\;$$2$$240x + 46y = 2$를 만족하는 정수해 $x = -9, y = 47$
 
 

용어 설명

$gcd(a,b)$ : 정수 $a, b$의 최대공약수
$a\equiv b\;(mod\;m)$ : $a$와 $b$는 $m$에 의해 나누어졌을 때의 나머지가 동일
이 수식이 성립하면 $a-b$는 $m$의 정수배라 볼 수 있음
이때 $a=b\;mod\;m$ 과 $a \equiv b\; (mod\;m)$은 다름
$=$ 이 들어가는거는 계산 결과를 나타냄
ex) 2 = 17 mod 5
$\equiv$ 가 들어가는건 표현한다는거, 같다는 의미를 나타냄 (합동)
ex) 17 = 2 mod 5
 

개념2

비대칭키 암호화 : 비밀키로 공개키 알아내기 o, 공개키로 비밀키 알아내기 x
→ 이산대수 어려움 통해 구현
RSA는 소인수분해의 난해함을 기초로 보안 유지
두 소수: $p, q$
$p*q$ = 쉬움 ($k$)
$k$ = 소인수분해 어려움 ($p$=?, $q$=?)
$p, q$ : 페르마 소수 중 선택 (1024bit, 2048bit …)

F0 = 21 + 1 = 3
F1 = 22 + 1 = 5
F2 = 24 + 1 = 17
F3 = 28 + 1 = 257
F4 = 216 + 1 = 65537
F5 = 232 + 1 = 4294967297 = 641 × 6700417 (오일러, 1732)
F6 = 264 + 1 = 18446744073709551617 = 274177 × 67280421310721
F7 = 2128 + 1 = 340282366920938463463374607431768211457 = 59649589127497217 × 5704689200685129054721

큰 수는 컴퓨터로도 소인수분해 어려움
 

페르마의 소정리

$$ p가 \;소수이면,\;모든\;정수\;a에\;대해\;a^p\equiv a\;(mod\;p)\\ p가\;소수이고\;a가\;p의\;배수가\;아니면,\;a^{p-1}\equiv1\,(mod\;p) $$
위의 두번째 경우라면 $p$는 소수가 아님
모든 합성수 $p$에 대해 성립 안됨, 확률적으로 $p$가 합성수인데 소수로 판별 가능
페르마 소정리는 많은 합성수들이 상대적으로 시간이 오래 걸리는 완전한 소수 판별 x, 합성수인지 알려줌
페르마 소정리 → 소수(소수일 가능성 정수) → 다른 완전한 방법으로 소수인지 확인 → $p, q$로 사용
 

오일러 정리

페르마의 소정리를 일반화한 것 → 소수 p를 정수 n으로 확장한 형태
$$ a와\;n이\;서로\;서로소인\;양의\;정수일\;때,\\a^{\phi(n)}\equiv1\;(mod\;n) $$
 

개념3

나머지 연산 매우 자주 활용

m = a%b

$a^b\equiv m\;(mod\;N)$에서 $m$을 계산하는 일을 매우 자주 수행
→ 큰 수의 나머지를 빠르고 간단하게 계산하는 방법

 

나머지의 성질

정리 1

$$ ab\;mod\;N=(a\;mod\;N)(b\;mod\;N)\,mod\;N $$
→ 두 수의 곱의 나머지는 각각의 수의 나머지를 먼저 구하고 그 나머지를 곱한 수의 나머지를 구해도됨
 

지수법칙

$b=p+q$일 때 $a^b=a^{p+q}=a^p*a^q$
——>
$$ a^b\;mod\;N=a^pa^q\;mod\;N=(a^p\;mod\;N)(a^q\;mod\;N)\,mod\;N $$
 

정리 2

$$ a^b\;mod\;N=(a\;mod\;N)^b\;mod\;N $$
나머지를 먼저 계산해서 밑을 작게 만들고 거듭제곱해서 연산 용량 줄이기
 

동작

기호

$N$ : 암복호화 과정에 이용되는 modulus로 사용, $N=p*q$ 인 합성수
$p, q$ : 공개되지 않은 두 소수
$e$ : 공개된 지수
$d$ : $d*e\equiv 1\;mod\;(p-1)(q-1)$을 만족하는 공개되지 않은 자연수
$m$ : 암호화 전 평문 (메세지), 이때 m < N
$c$ : 암호문
$E$ : 암호변환함수 (Encrypt)
$D$ : 복호변환함수 (Decrypt)

키 생성

1. 큰 소수 $p, q$를 생성
2. $N=pq$를 계산
3. $(p-1)(q-1)$과 서로소인 정수 $e$를 정함
   1. $\phi(N)$는 오일러 피 함수 : $N$과 서로소인 $N$ 이하의 자연수 개수
      1. ex) 8 이하의 양의 정수 중 8과 서로소인 수는 1, 3, 5, 7로 4개임. $\phi(6)=2$
   2. $N$이 소수인 경우 $\phi(N)=N-1$ (1부터 $p-1$까지 모두 $p$와 서로소이기 때문에)
   3. 곱셈적 함수
   4. $\phi(N) = \phi(pq)=\phi(p)\phi(q)=(p-1)(q-1)$
4. $ed$를 $(p-1)(q-1)$로 나눈 나머지가 1인 정수 $d$를 계산 (확장 유클리드 알고리즘 사용)
   1. $ed\equiv 1\;(mod\;\phi(N))$를 만족하는 정수 $d$
   2. $ed\;\% \;(p-1)(q-1)= 1$
   3. $d \equiv e^{-1}(mod\; \phi(n))$

• 키로 사용되지 않는 두 소수 $p, q$는 공개되면 안됨
  • 공개열쇠 $e$로부터 개인열쇠 $d$를 찾을 수 있음
• 상황에 따라 3단계와 4단계의 순서를 바꿔서 개인열쇠를 먼저 정하고 공개열쇠를 생성함

참고

3단계에서 $e, (p-1)(q-1)$이 서로소여야 하는 이유 - 4단계 (서로소가 아니면 위 조건을 만족하는 $d$는 존재하지 않음)
4단계는 어떤 정수 $x$가 있을 때 다음과 같이 요약 가능
$$ ed=(p-1)(q-1)x\,+\,1 $$
 

암호화

$$ c=m^e\;mod\;N $$
평문을 나타내는 자연수를 e제곱한 결과를 N으로 나눠준것
→ $e, N$을 알면 누구든 암호화 가능
암호화키쌍 : $(e, N)$
 

복호화

$$ m=c^d\;mod\;N $$
$d, N$을 알면 누구든 복호화 가능
복호화키쌍 : $(d, N)$
 

복호화 증명

$m=c^d\;mod\;N$
$=(m^e\;mod\;N)^d\;mod\;N$
$=m^{ed}\;mod\;N$
$\to m^{ed} \equiv m\;(mod\;N)$
$m^{ed} \equiv m\;(mod\;N)$를 증명하면됨
$N=p*q$ 이므로 위 합동식이 $mod\;p$일 때 또는 $mod\;q$일 때 성립하면 $mod\;N$일 때도 성립함
$ed\equiv1\;(mod\;\phi(N))$이므로 적당한 정수 $k$가 존재하여 $ed=k*\phi(N)+1=k(p-1)(q-1)+1$이라 쓸 수 있음
 

1. 페르마의 소정리 이용

위 합동식에 대입하면
$m^{ed}\equiv m\;(mod\;N)$
$\to m^{ed}\equiv m \;(mod\;p)$
$\to m^{k(p-1)(q-1)+1} \equiv m\;(mod\;p)$
$\to m^{k(p-1)(q-1)} \,*\,m\equiv m\;(mod\;p)$
$\to (m^{p-1})^{k(q-1)}\,*\,m \equiv m\;(mod\;p)$
 

경우 1 - m이 p의 배수가 아닐 때

$m$이 $p$의 배수가 아니면 $p$가 소수이기 때문에 페르마의 소정리에 의해
$m^{p-1}\equiv 1\;(mod\;p)$이고 이 식을 위에 대입하면
$(m^{p-1})^{k(q-1)}\,*\,m \equiv m\;(mod\;p)$
$\to 1^{k(q-1)}\,*\, m \equiv m\;(mod\;p)$
$\to m \equiv m\;(mod\;p)$
이므로 합동식이 성립함
 

경우 2 - m이 p의 배수일 때

$m$이 $p$의 배수면 합동식 양변이 모두 $p$로 나누어 떨어짐 → 0이됨
따라서 합동식이 성립함
 

2. 오일러 정리 이용

$m \equiv c^d \;(mod\;n) \\ c^d \equiv (m^e)^d \equiv m^{ed}\; (mod \; n)$
오일러 정리를 이용하면 $ed = x\phi(n)\;+\;1$을 만족하는 자연수 $x$가 존재함. 따라서 다음 합동식이 성립함
$m^{ed} \equiv (m^{\phi(n)})^km\;(mod\;n)$
$(m^{\phi(n)})^km \equiv\;m\;(mod\;n)$

---