[암호학] 3장 공개키암호 정리

*공개키 암호 시스템

공개키 알고리즘

• 두 개의 다른 키 사용

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

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

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

공개키 알고리즘의 특징

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

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에서는 정수내에 곱셈에 대한 역원이 존재한다.)

*공개키 암호 시스템의 응용

공개키 암호의 기밀성

A라는 사람이 B에게 평문(P)을 보내고 싶은데 딴사람이 보면 안된다.

B가 받는것이기에 B의 공개키를 레파지토리에서 찾아본다.

암호해독자는 암호문과 B의 공개키를 탈취한다.

공개키를 이용한 인증

개인키와 공개키는 쌍으로 존재한다.

A가 문서를 보낼때 자신만 가지고 있는 개인키로 서명문을 암호화하여 보낸다.

서명문은 A의 공개키로 풀린다.

A는 부인방지 효과를 얻을 수 있다.

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

A의 개인키로 암호화를 하고

받는 사람의 공개키로 암호화를 한번 더 한다.

B는 자신의 개인키로 암호화를 한고

B의 공개키로 암호화한다.

# 완벽하지만 실제로 성능이 너무 안좋아 사용하지 않는다.

# 보안상 문제는? 가용성?

*공개키 암호 시스템의 종류

공개키 암호 시스템의 사용

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

알고리즘	암호/복호	디지털서명	키교환
RSA	가능	가능	가능
ELGamal	가능	가능	가능
Diffie-Hellman	불가	불가	가능
EC(타원곡선)	가능	가능	가능

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

소인수 분해의 어려움

• RSA

이산대수문제

•  엘가말(El Gamal)
• 디퍼헬만(Diffie-Hellman)
• 타원 곡선 (Elliptic Curve)

*공개키 암호를 위한 요구 사항

공개키 알고리즘의 조건 (Diffie와 Hellman)

• 키 쌍(공개키 KU, 개인키 KR)의 생성이 쉽다.
• 다음 식과 같은 암호문의 생성이 쉽다.

C = EKUb(M)

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

M = DKRb(C) = DKRb[EKUb(M)]

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

M = EKUb[DKRb(M)]

*공개키 암호 분석

공격 유형

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

*RSA

RSA의 개발

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

알고리즘

• 평문은 블록으로 암호화
• 암호화

C = Me mod n

• 복호화

M = Cd mod n

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

e,d,n 값 생성

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

e와 d는 mod ф(n)에서 곱셈에 대한 역원 e와 n을 알더라도 ф(n)을 계산하기 힘들기 때문에 d를 알 수 없다. ф(n)은 n을 소인수분해해야 하는데 이것은 수학적인 난제이다.

복호화 과정의 증명

RSA 알고리즘 정리

* RSA - 예제

RSA 알고리즘 사용 예

공개키와 개인키 생성

암호화와 복호화 : 평문 메시지 M = 19 일 경우