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

컴퓨터와 수학, 몽상 조금

페이지 맨 위로 올라가기

컴퓨터와 수학, 몽상 조금

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

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

  • 2020.10.17 19:32
  • 학부 수업/이산수학
반응형

튜링 코드Turing Code는 앨런 튜링이 개발한, 정수론을 이용한 암호화 방법이다.

"victory"라는 메세지를 암호화하는 예시를 통해 튜링 코드를 배워보자.
우리가 암호화할 메시지를 $m$, 암호화된 메시지를 $m'$, 암호화에 사용할 키 값을 $k$로 나타낼 것이다.

"victory"는 정수로 22090320151825로 나타낼 수 있다. (v는 알파벳 22번째, i는 09번째... 와 같은 방식이다.)

튜링 코드 버전 1

소수 만들기

먼저 암호화할 숫자에 적절한 수를 붙여 소수로 만들어준다. 22090320151825에 13을 붙이면 소수가 된다.

$$m=2209032015182513$$

키 값 정하고 암호화하기

다음으로 암호화에 사용될 키key 값을 하나 정한다. 이 키값이 있어야만 암호화와 복호화가 가능하다.
키값 역시 큰 소수를 사용한다.

이제 단순히 암호화할 메세지와 키 값을 곱해주면 암호화가 완료된다.

수학적으로, 두 소수의 곱은 복호화하기가 상당히 복잡하다. 약분이 $E\cdot k$로만 가능한데, 이를 약분하려면 무수한 수의 숫자를 하나하나 대입해가며 약분이 되는 $k$나 $E$를 찾는 수밖에 없다.

$E' = E\cdot k$

튜링 코드 버전 1의 복호화, 취약점

암호화 방법을 보면 알겠지만 튜링 코드 버전 1의 복호화는 아주 간단하다.

$$ E = \frac{E'}{k}$$

단순하면서도 해킹하려면 엄청난 노가다를 해야하니 좋아보이지만, 튜링코드엔 큰 단점이 있다. 만약 같은 키로 암호화된 문장 두개가 있다면, 최대공약수를 이용해 $k$를 알아낼 수 있다.

$$E_1' = E_1\cdot k\\
E_2' = E_2\cdot k\\
k = \text{gcd}(E1', E2')$$

튜링 코드 버전 2

튜링 코드 버전 2는 두 개의 키 값을 요구한다. 공개 키Public Key인 $p$와 비공개 키Secret Key인 $k$이다. 두 키는 모두 소수이다.

암호화할 메세지 $m$은 0부터 $p-1$사이의 값이다. ($m \in \{0, 1, \cdots , p-1\}$)

암호화와 복호화는 다음과 같다.

$$ m' = \text{rem} (m\cdot k, p)\\
m = \text{rem}(m'\cdot k^{-1} , p)$$

증명

$m' = \text{rem}(m\cdot k,p)$이므로, $m' \equiv m\cdot k(\mod p)$이다.

이때, $k^{-1} (\mod p)$가 있다면, $m'\cdot k^{-1} \equiv m\cdot k\cdot k^{-1} (\mod p)$ 이므로, $m'\cdot k^{-1} \equiv m $이다.

그러므로 $m=\text{rem} (m'\cdot k^{-1}, p)$

튜링 코드 버전 2의 취약점

만약 우리가 암호화된 데이터 중 하나라도 원문을 알고있다면, 튜링 코드 버전 2를 해킹할 수 있다. (즉, 우리가 적어도 한 쌍의 $m$, $m'$를 안다면)

$m\equiv m' \cdot k (\mod p)$이므로, $\text{gcd}(m, p)$는 1이다. ($m$과 $p$는 서로소이다.)

그러므로, $m' \cdot m^{-1} \equiv m\cdot k \cdot m^{-1} \equiv k (\mod p)$이다.

$k$가 뭔지는 모르지만, 이를 통해 $k^{-1]$을 계산할 수 있다.

튜링 코드 v2 실습

$m = 2, k = 13, p = 7$을 써서 암호화 실습을 해보자.

$$\begin{align*}m' &= \text{rem}(m\cdot k, p)\\
&=\text{rem}(2\cdot 13, 7)\\
&= 5\end{align*}$$

우리가 $k$를 안다면, 복호화는 다음과 같다.

$$m = \text{rem}(m'\cdot k^{-1}, p)$$

$k^{-1} (\mod p)$는 $k\cdot k^{-1} \equiv 1 (\mod p)$이므로,

$$ 13 \cdot k^{-1} \equiv 1 (\mod 7) $$

$$k^{-1} = 6 $$

그러므로,

$$\begin{align*}m &= \text{rem}(5 \cdot 6, 7)\\ &= 30 \mod 7 = 2 \end{align*}$$

해킹 실습

만약 우리가 $k$는 모르고 $m=2, m'=5$만 알았다고 생각해보자. $p$는 공개키로, 7임이 알려져있다.

$m'\cdot m^{-1} \equiv k (\mod p)$이다.

$m\cdot m^{-1} = 1 (\mod p)$이므로, $m^{-1} = 4$이다.

$$ 5\cdot 4 \equiv k (\mod 7)$$

이제, $k^{-1}$을 계산 가능하다.

20의 $(\mod 7)$에 대한 곱셈의 역원을 구하면 된다.

$$k^{-1} = 6$$

$$\begin{align*} m &= \text{rem}(m' \cdot k^{-1}, p)\\
&= \text{rem}(5 \cdot 6, 7) = 2 \end{align*}$$

반응형

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

8. RSA 암호화 (RSA Encryption Algorithm)  (1) 2020.10.17
7. 정수론: 오일러의 피 함수과 페르마의 소정리 (Number Theory: Euler's Phi Function and Fermat's Little Theorem)  (2) 2020.10.17
5. 정수론: 서로소와 합동식 (Number Theory: Congruent and Relatively Prime)  (2) 2020.10.17
4. 정수론: 최대공약수 (Number Theory: Great Common Divisor)  (1) 2020.10.14
3.5 Unstacking Game 강한 귀납법으로 증명하기  (0) 2020.10.14

댓글

이 글 공유하기

  • 구독하기

    구독하기

  • 카카오톡

    카카오톡

  • 라인

    라인

  • 트위터

    트위터

  • Facebook

    Facebook

  • 카카오스토리

    카카오스토리

  • 밴드

    밴드

  • 네이버 블로그

    네이버 블로그

  • Pocket

    Pocket

  • Evernote

    Evernote

다른 글

  • 8. RSA 암호화 (RSA Encryption Algorithm)

    8. RSA 암호화 (RSA Encryption Algorithm)

    2020.10.17
  • 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
  • 5. 정수론: 서로소와 합동식 (Number Theory: Congruent and Relatively Prime)

    5. 정수론: 서로소와 합동식 (Number Theory: Congruent and Relatively Prime)

    2020.10.17
  • 4. 정수론: 최대공약수 (Number Theory: Great Common Divisor)

    4. 정수론: 최대공약수 (Number Theory: Great Common Divisor)

    2020.10.14
다른 글 더 둘러보기

정보

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

컴퓨터와 수학, 몽상 조금

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

검색

메뉴

  • 홈
  • 태그
  • 방명록

카테고리

  • 분류 전체보기 (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.

티스토리툴바