암호학 5 - 공개키 암호

공개키 알고리즘
• 두 개의 다른 키 사용

공개키 : 모든 사람이 접근 가능한 키 (공개)

개인키 : 각 사용자 자신만이 소유 (비밀)

관용 암호에 사용되는 키는 비밀키라고 함

공개키 알고리즘의 특징
• 암호 알고리즘과 암호키를 알아도 복호키 계산 불가능
• 두 개의 키 중 하나는 암호에 다른 하나는 복호에 사용

 

1. 공개키와 개인키 생성
2. 공개키는 공개하고 개인키는 개인이 소유
3. A는 B의 공개키로 메시지를 암호화
4. B는 자신의 개인키로 메시지 복호화
(B의 개인키를 모르는 제 3자는 메시지 복호 불가능)

 

- 암호 사양
  암호알고리즘 : mod 7에서 곱셈
  공개키 : 3, 개인키 : 5
  원문 : 4

- 암호화
 4 * (3 mod 7) = 5 (암호문)

- 복호화
 5 * (5 mod 7) = 4 (원문)

>> mod 7 에서 3, 5는 서로 역원 (mod에서는 정수 내에 곱셈에 대한 역원이 존재한다.)

 

mod 소수에서는 잉여계가 다 나온다.

 

원문 : WE WISH YOU A MERRY CHRISTMAS AND A HAPPY NEW YEAR
 W E  W  I  S  H  Y  O  U  A  M  E  R  R  Y  C  H  R  I  S  T  M  A  S  A  N  D  A  H  A  P  P  Y  N  E  W  Y  E  A  R
23 5  23 9  19 8  25 15 21 1  13 5  18 18 25 3  8  18 9  19 20 13 1  19 1  14 4  1  8  1  16 16 25 14 5  23 25 5  1  18
4  25 4  8  21 3  14 1  31 5  28 25 16 16 14 15 3  16 8  21 26 28 5  21 5  33 20 5  3  5  6  6  14 33 25 4  14 25 5  16
D  Y  D  H  U  C  N  A  %  E  @  Y  P  P  N  O  C  P  H  U  Z  @  E  U  E  &  T  E  C  E  F  F  N  &  Y  D  N  Y  E  P
^암호

개인키 : 5
공개키 : 15

암호화 : (개인키*원문 키맵매칭 값) mod 37 = 암호문 값

암호 알고리즘 : mod37 에서 곱셈
공개키 : 15
키맵
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
0 A B C D E F G H I J  K  L  M  N  O  P  Q  R  S  T  U  V  W  X  Y  Z  !  @  #  $  %  ^  &  *  (  )

서명문 : DYDHUCNA%E@YPPNOCPHUZ@EUE&TECEFFN&YDNYEP

복호화 : (공개키*암호문 키맵매칭 값) mod 37 = 원문 값

 

▶ 공개키 암호의 기밀성

▶ 공개키를 이용한 인증 (부인 방지)

- 기밀 통신시 공개키로 암호화한다.

- 사용자 인증시 개인키로 암호화한다.

 

▶ 공개키를 이용한 기밀통신과 서명

▶ 공개키 암호 시스템의 사용
• 암호/복호 (수신자의 공개키로 메시지 암호)
• 디지털 서명 (송신자의 개인키로 메시지 서명)
• 키 교환 (세션키를 교환하기 위해 사용)

▶ 공개키 암호는 수학적인 난제를 이용 암호화를 수행한다.

▶ 소인수 분해의 어려움
• RSA

▶ 이산대수문제
• 엘가말(El Gamal)
• 디퍼헬만(Diffie-Hellman)
• 타원 곡선 (Elliptic Curve)

 

▶ 공개키 알고리즘의 조건 (Diffie와 Hellman)
• 키 쌍(공개키 KU, 개인키 KR)의 생성이 쉽다.
• 다음 식과 같은 암호문의 생성이 쉽다.

• 다음식과 같은 암호문의 복구화가 쉽다.

• 공개키 KUb로부터 개인키 KRb를 결정하는 것은 어렵다.
• 공개키 KUb와 암호문 C로부터 메시지 M의 복구가 어렵다.
• 암호와 복호 기능이 다음과 같이 적용 가능하다. (추가 사항)

 

▶ 공격 유형
• 전사적 공격에 취약
  → 키의 크기를 크게 함으로써 방지
(상대적으로 속도가 느려짐)
• 공개키로부터 개인키를 계산하는 방법
  → 수학적으로 계산이 불가능함을 증명하지 못함
• 가능한 메시지 공격
: 모든 가능한 메시지를 공개키로 암호화하여 암호문과 비교
  → 메시지에 임의의 비트를 추가함으로써 방지

 

▶ RSA의 개발
: 1977년에 개발되어 1978년에 공포 (Rivest, Shamir, Adleman)

▶ 알고리즘
• 평문은 블록으로 암호화
• 암호화

• 복호화

공개키 : KU = {e, n}, 개인키 : KR = { d, n }

 

▶ e,d,n 값 생성
• p, q 선택 : p와 q는 10¹⁰⁰ 정도의 소수
• n = p * q
• e : GCD(e, ф(n)) = 1인 값을 선택
• d : e * d = 1 mod ф(n) 인 값을 계산

 

▶ 복호화 과정의 증명