이 영역을 누르면 첫 페이지로 이동
컴퓨터와 수학, 몽상 조금 블로그의 첫 페이지로 이동

컴퓨터와 수학, 몽상 조금

페이지 맨 위로 올라가기

컴퓨터와 수학, 몽상 조금

컴퓨터공학, 딥러닝, 수학 등을 다룹니다.

8. RSA 암호화 (RSA Encryption Algorithm)

  • 2020.10.17 23:03
  • 학부 수업/이산수학
반응형

RSA 암호화는 대표적인 공개키 방식 암호화 알고리즘으로, 개발자 세 명의 이름을 따서 만들어졌다. (즉, Really Secure Algorithm 따위의 멋있는 약자가 아니라, 김이박 암호화 같은 이름이다.)

RSA 암호화는 공개 키 $e, n$과, 비공개 키 $d$을 사용한다.

$e$는 암호화Encryption, $d$는 복호화Decryption의 약자이다. 복호화하고자 하는 이만 비공개 키를 알고 있어도 되는 특성 때문에, $d$는 개인 키라고도 불린다.

키 만들기

  1. 먼저, 두 개의 큰 소수 $p, q$를 준비한다. 이때, 암호화할 메시지 $m$보다 $p$가 커야 한다.
    (보통 큰 홀수를 하나 만들어서, 2씩 더해가면서 소수를 찾는다.)
  2. $(p-1), (q-1)$과 각각 서로소인 정수 $e$를 얻는다. (보통 소수인 3(0x11)이나 65537(0x10001)을 사용한다.)
  3. $ed \mod (p-1)(q-1) = 1$인 $d$를 찾는다. 즉, $d$는 $e (\mod (p-1)(q-1))$의 곱의 역원이다.
  4. $n=p\cdot q$를 구한다. 보통 RSA 암호화에서 키의 크기를 논하면 $n$의 크기를 말한다.
  5. 이제 $e,n$은 공개하고, $p,q$는 파기한다.

$e$는 암호화 $d$는 복호화에 사용되며, 두 과정 모두 $n$역시 필요로 한다. $p,q$는 키 생성 과정에서만 사용되고 이후에는 쓸모가 없으므로 키 생성 후 파기한다.

암호화/복호화

$$m' = \text{rem}(m^e, n) $$

$$m = \text{rem}((m')^d, n)$$

증명

암호화한 메세지 $m'$과 원래 메세지 $m$이 어떻게 똑같은지 증명해보자.

페르마의 소정리에 의해, 어떤 소수 $p$의 오일러 피 함수 $\phi(p)$는 $p-1$이다. 즉, $n = pq$이므로, $\phi(n) = (p-1)(q-1)$이다.

$ed=r(p-1)(q-1)+1 = r\phi(n)+1$이다. ($r$은 어떤 정수)

$mr \mod n = (m\mod n)(r\mod n) \mod n$, $m^r \mod n = (m \mod n)^r mod n$이다.

그러므로,

$$ \begin{align*}m' &= m^d \mod n = (m^e \mod n)^d \mod n \\
&= (m^e)^d \mod n = m^{ed} \mod n\\
&= m^{r\phi(n)+1} \mod n = (m^{\phi(n)} \mod n)^r \cdot m \mod n\\
&= 1^r\cdot m \mod n = m\end{align*}$$

예제

$m = 11$을 RSA 암호화 해보자.

$p = 7, q = 13, e = 5$으로 정하자. $n = pq = 91$이 된다.

$5\cdot d \mod (6\cdot 12) = 1$인 $d$를 확장된 유클리드 호제법으로 구해보자.

$5, 72$의 최대공약수를 구하면 된다.

$i$ $x$ $y$ $r$ $q$
0 1 0 72  
1 0 1 5 14
2 1 -14 2 2
3 -2 29 1 2
      0  

$5,72$의 최대 공약수는 $-2\cdot 72 + 29\cdot 5 = 1$이다.

즉, $d=29$이다.

이제 $e, n$을 활용한 암호화다.

$$ \begin{align*}m' &= m^e \mod n\\
&=11^5 \mod 91\\
&=161051 \mod 91 = 72 \end{align*}$$

이제 $p,q$는 파기하고, $e=5, n=91$을 공개한다. 그리고 복호화를 할 사람에게만 개인키인 $d=29$를 제공한다.

복호화를 해보자.

$$ \begin{align*} m &= (m')^d \mod n\\
&= 72^29 \mod 91\end{align*}$$

$72^29$는 컴퓨터로 계산하기엔 엄청나게 큰 수다. 이를 간단히 계산하는 방법이 있으나 본 글에서는 다루지 않겠다.

알아보고 싶다면, 이 글의 2문단 아래쪽을 참고하면 된다.

계산 결과는 11이 된다.

반응형

'학부 수업 > 이산수학' 카테고리의 다른 글

10. 매칭 알고리즘 (Matching Algorithm)  (1) 2020.10.18
9. 그래프 이론과 P-NP 문제 (Graph Theory and P-NP Problem)  (2) 2020.10.18
7. 정수론: 오일러의 피 함수과 페르마의 소정리 (Number Theory: Euler's Phi Function and Fermat's Little Theorem)  (2) 2020.10.17
6. 정수론: 암호화, 복호화 (Number Theory: Encryption and Decryption)  (2) 2020.10.17
5. 정수론: 서로소와 합동식 (Number Theory: Congruent and Relatively Prime)  (2) 2020.10.17

댓글

이 글 공유하기

  • 구독하기

    구독하기

  • 카카오톡

    카카오톡

  • 라인

    라인

  • 트위터

    트위터

  • Facebook

    Facebook

  • 카카오스토리

    카카오스토리

  • 밴드

    밴드

  • 네이버 블로그

    네이버 블로그

  • Pocket

    Pocket

  • Evernote

    Evernote

다른 글

  • 10. 매칭 알고리즘 (Matching Algorithm)

    10. 매칭 알고리즘 (Matching Algorithm)

    2020.10.18
  • 9. 그래프 이론과 P-NP 문제 (Graph Theory and P-NP Problem)

    9. 그래프 이론과 P-NP 문제 (Graph Theory and P-NP Problem)

    2020.10.18
  • 7. 정수론: 오일러의 피 함수과 페르마의 소정리 (Number Theory: Euler's Phi Function and Fermat's Little Theorem)

    7. 정수론: 오일러의 피 함수과 페르마의 소정리 (Number Theory: Euler's Phi Function and Fermat's Little Theorem)

    2020.10.17
  • 6. 정수론: 암호화, 복호화 (Number Theory: Encryption and Decryption)

    6. 정수론: 암호화, 복호화 (Number Theory: Encryption and Decryption)

    2020.10.17
다른 글 더 둘러보기

정보

컴퓨터와 수학, 몽상 조금 블로그의 첫 페이지로 이동

컴퓨터와 수학, 몽상 조금

  • 컴퓨터와 수학, 몽상 조금의 첫 페이지로 이동

검색

메뉴

  • 홈
  • 태그
  • 방명록

카테고리

  • 분류 전체보기 (276)
    • Tech Trend (3)
    • Deep Learning (77)
      • 공부 노트 (21)
      • 논문 리뷰 (44)
      • 논문 스키밍 (1)
      • 영상처리 (11)
    • Engineering (3)
      • Tips (2)
      • Experiences (1)
    • Blog (42)
      • 회고 & 계획 (16)
      • 내 이야기 (8)
      • 리뷰 (3)
      • 군대에 간 공돌이 (9)
      • ML엔지니어 취업 도전기 (1)
      • 여행 (4)
    • 학부 수업 (141)
      • 머신러닝 (16)
      • C프로그래밍 (8)
      • 자료구조 (11)
      • 알고리즘 (17)
      • 디지털시스템 (25)
      • 컴퓨터구조 (11)
      • 확률과 통계 (21)
      • 선형대수학 (14)
      • 이산수학 (18)
      • 데이터시각화 (0)
    • 강의 (9)
      • 딥러닝 기초 (7)
      • Python (2)

공지사항

인기 글

정보

백지오의 컴퓨터와 수학, 몽상 조금

컴퓨터와 수학, 몽상 조금

백지오

블로그 구독하기

  • 구독하기
  • RSS 피드

티스토리

  • 티스토리 홈
  • 이 블로그 관리하기
  • 글쓰기
반응형

나의 외부 링크

  • profile
  • github
  • linkedin

방문자

  • 전체 방문자
  • 오늘
  • 어제
Powered by Tistory / Kakao. © 백지오. Designed by Fraccino.

티스토리툴바