Section.05 해시함수와 응용

1.일방향 해시함수

(1)일방향 해시함수의 개요

1)기본개념

• 일방향 해시함수(one-way hash function)에는 입력과 출력이 각각 1개씩 있다. 입력은 메시지라 하고 출력은 해시값(hash value)이라 한다.
• 일방향 해시함수는 어떤 메시지든지 단지 비트열로 취급하며, 그 비트열을 기초로 해시값을 계산한다.

2)일방향 해시함수의 성질

• 임의의 길이 메시지로부터 고정길이의 해시값을 계산한다.
• 어떤 길이의 메시지를 입력으로 주더라도 일방향 해시함수는 짧은 해시값을 생성하지 않으면 의미가 없다.
• 해시값을 고속으로 계산할 수 있다.
• 해시값을 구하기위해 시간이 너무 오래 걸리면 안 된다.
• 일방향성을 갖는다.
• 일방향 해시함수는 일방향성을 가질 필요가 있다. 이것은 해시값으로부터 메시지를 역산링 수 없다는 성질이다.
• 그림...
• 메시지가 다르면 해시값도 다르다.
• 무결성을 확인하기위해 사용한다. 메시지가 1비트라도 변화하면 해시값은 매우 높은 확률로 다른 해시값이 되어야 하기 때문이다.
• 2개의 다른 메시지가 같은 해시값을 갖는 것을 충돌(collision)이라고 한다. 일방향 해시함수를 무결성 확인에 사용하기 위해서는 충돌이 있어서는 안된다.
• 충돌을 발견하기 어려운 성질을 가리켜 충돌내성(collision resistance)이라함. 암호기술에서 새용되는 일방향 해시함수는 충돌내성을 가질 필요가 있다.

(2)메시지 무결성

1)무결성 점검

• 메시지 혹은 문서의 무결성을 점검하기위해 암호학적 해시함수를 사용해야 하고 이렇게 생성된 새로운 메시지 다이제스트와 이전의 메시지 다이제스트를 비교해 보아야 한다.
• 만약 이 두 개가 동일하다면 원래의 메시지가 변경되지 않았다는 것을 확신할 수 있다.

2)암호학적 해시함수 기준

①개요

• 암호학적 해시함수는 프리이미지 저항성(preimage resistance), 제2프리이미지 저항성(second preimage resistance), 충돌저항성(collision resistence)의 3가지 기준을 충족해야 한다.

②프리 이미지 저항성(역상저항성)

• 암호학적 해시함수는 프리이미지 저항성이 있어야한다. 
• 프리이미지
• f(x)=y에서 x는 y의 이전 이미지라고 한다.f가 일대일 대응이 아니면 하나의 y에 여러 이전 이미지가 있을 수 있다.
• 프리이미지 저항성이란 주어진 해시함수 h와 y=h(M)에 대해 Eve가 y=h(M')를 만족하는 다른 메시지 M'를 찾아낸다는 것이 매우 힘들어야 한다는 성질이다.

③제2프리이미지 저항성(두번째 역상 저항성, 약한 충돌 내성)

• 메시지를 쉽게 위조할 수 없도록 해야함.
• Eve는 메시지 M과 다이제스트 h(M)을 가로챈다. Eve는 h(M)=h(M')을 만족하는 다른 메시지를 생성한다.

④충돌 저항성(강한 충돌 저항성)

• Eve가 동일한 다이제스트를 가지는 2개의 메시지를 구하지 못하도록 하는 것이다. 여기서 공격자는 어떤 정보도 없는 상태에서 동일한 다이제스트를 갖는 2개의 메시지를 생성할 수 있다.

3)전자 서명에 이용되는 해시함수의 특성

• 해시값을 고속으로 계산할 수 있다.
• 약 일방향성(weak onewayness)
• 해시값 H로부터 h(M)=H 되는 서명문 M을 찾는것은 계산상 불가능해야 한다.
• 강 일방향성(strong onewayness)
• 어떤 서명문 M과 그 해시값 H=h(M)가 주어졌을 때 h(M')=H되는 서명문 M'!=M을 찾는것이 계산상 불가능 해야 한다.
• 충돌 회피성
• h(M)=h(M')되는 서명문 쌍 (M,M')(M!=M') 을 찾는것이 계산상 불가능해야 한다.

(3)일방향 해시함수의 응용

1)소프트웨어 변경 검출

• 자신이 입수한 소프트웨어가 변경되었는지를 확인하기 위해 사용.
• 사용자는 소프트웨어를 입수한 후 , 자신의 손으로 해시값을 가시 계산해서 그 것을 오리지널 사이트에서 제공하는 해시값과 비교함.

2)패스워드를 기초로 한 암호화 

• 패스워드를 기초로 한 암호화(password based encryption;PBE)에서 사용된다.
• PBE에서는 password와 솔트(의사난수 생성기로 생성한 랜덤값)를 섞는 결과의 해시값을 구해 그것을 암호화키로 사용한다. 이 방법으로 패스워드에 대한 사전공격을 막을 수 있다.
• 사전공격: 사전에 있는 단어를 입력해 암호를 알아내거나 해독하는 컨퓨터 공격법

3)메시지 인증 코드 

• 일방향 해시함수를 사용해서 메시지 인증코드를 구성할 수 있다.
• 메시지 인증코드: 송신자와 수신자만이 공유하고 있는 키 와 메시지를 혼합해서 그 해시값을 계산한 값

4)전자서명

• 현실 사회의 서명(사인)이나 날인에 해당하는 행위를 디지털 세계로 가져온 것이다.

5)전자입찰 시스템

• 입찰 공고를 한 다수의 공급자가 응찰하여 오면 이중에서 가장 싼 가격을 제시, 계약을 맺는 입찰 방식을 인터넷을 이용해 구현한 것.
• 요구사항
• 독립성: 전자입찰 시스템의 각 구성요소들은 자신들의 독자적인 자율성을 보장받아야 한다.
• 비밀성: 네트워크상에서 각 구성요소 간에 개별정보는 누구에게도 노출되어서는 안된다.
• 무결성: 입찰시 입찰자 자신의 정보를 확인 가능하게 함으로써 누락 및 변조 여부를 확인할 수 있어야 한다.
• 공평성: 입찰이 수행될 때 모든 정보는 공개되어야 한다. 
• 안전성: 각 입찰 참여자간의 공모는 방지되어야 하고 입찰 공고자와 서버의 독단이 발생해서는 안된다.

(4) 랜덤 오라클 모델과 해시함수에 대한 공격 

1)랜덤 오라클 모델

①개요

• 해시함수에 대한 이상적인 수학적 모델

②비둘기집 원리

• 만약 n+1마리의 비둘기가 n개의 비둘기집에 들어가 있다면 적어도 한 비둘기 집에는 두 마리의 비둘기가 들어가 있다는 뜻.
• 일반화된 버전은, 만약 kn+1마리의 비둘기가 n개의 비둘기집에 들어가 있다면 적어도 한 개의 비둘기집에는 k+1마리의 비둘기가 들어가 있어야 한다는 원리이다.

③생일문제(생일공격)

• 특정의 해시값을 생성하는 메시지를 구하는 것이 아니라, 해시값은 뭐든지 괜찮고, 어쨌든 같은 해시값을 생성하는 2개의 메시지를 구하는 것이다.
• 생일공격(birthday attack)은 일방향 해시함수의 강한 충돌내성을 깨고자 하는 공격
• 생일 패러독스
• 생일퀴즈: 랜덤으로 N명의 그룹을 생각한다. N명중 적어도 2명의 생일이 일치랑 확률이 1/2이상이 되도록 하기위해서는 N의 최소 숫자는?
• 답: N=23이다. 이떄 확률이 0.507297로 1/2이상임.

2)일방향 해시함수에 대한 공격 

①무차별 공격

• 암호에 대해 무차별 공격이 가능했던 것처럼 일방향 해시함수에 대해서도 가능함.
• 일방향 해시함수의 약한 충돌내성을 깨기위한 공격이다. SHA-1의 경우 해시값이 160비트이므로 2^160회의 시행횟수를 행하면 목적하는 메시지가 발견될 것이라고 기대할 수 있다.

②기타 해시함수 공격의 종류 및 특성

• 일치 블록 연쇄공격
• 새로운 메시지 M'를 사전에 다양하게 만들어 놓았다가 공격하고자 하는 메시지 M의 해시함수값 h(M)과 같은 해시함수값을 갖는 것을 골라 사용하는 공격.
• 중간자 연쇄공격 
• 전체 해시값이 아니라 해시 중간의 결과에 대한 충돌쌍을 찾는다. 특정 포인트를 공격대상으로 삼는다.
• 고정점 연쇄공격
• 압축함수에서 고정점이란  압축 함수에서 고정점이란 을 만족하는 쌍 를 말한다. 
• 그러한 메시지 블록과 연쇄변수 쌍을 얻게 되면 연쇄변수가 발생하는 특정한 점에서 임의의 수의 동등한 블록들  를 메시지의 중간에 삽입해도 전체 해시값이 변하지 않는다.
• 차분 연쇄공격 
• 다중 라운드 블록암호의 공격: 다중 라운드 블록암호를 사용하는 해시함수에서 입력값과 그에 대응하는 출력값 차이의 통계적 특성을 조사하는 기법사용.
• 해시함수의 공격: 압축함수의 입출력 차이를 조사해 0의 충돌쌍을 주로 찾아내는 방법사용.

(5)일방향 해시함수를 이용해 해결할 수 없는 문제

• 일방향 해시함수는 조작과 변경을 검출할 수 있지만 거짓행세를 검출하지는 못함.
• 파일의 무결성을 조사하는 것뿐만 아니라 이 파일이 정말 Alice의 것인가를 확인하고 싶은 경우에는 무결성 외에 인증이라는 절차가 필요하다.
• 인증을 수행하기 위한 기술이 메시지 인증코드와 전자서명이다.

2.암호학적 해시함수의 예

(1)개요

1)압축함수의 두 가지 유형

• 기본개념
• 아무런 기초없이 처음보터 새로 만드는 것, 목적에 맞게 특별하게 설계
• 압축함수 자리에 대칭키 블록암호를 사용
• 새로 만드는 해시함수
• 메시지 다이제스트(Message Digest)(MD2-MD4-MD5)
• 최종버전인 MD5는 MD4의 강화버전으로 메시지를 512비트로 된 블록들로 나누고 128비트로 다이제스트 출력.
• 현재 128비트 메시지 다이제스트는 충돌 공격에 내성을 갖기에는 길이가 너무 짧다고 알려짐.
• SHA(Secure Hash Algorithm)
• 최근에 가장 널리 사용되는 해시함수는 안전 해시알고리즘(SHA)임.
• SHA는 MD4 해시함수에 기초애서 만들어졌고 설계도 MD4를 모델로함. SHA-1은 해시값으로 160비트를 출력한다.
• 이외 설명이 있는데 사실 귀찮음 ...........필요시 추가.

• 구분	SHA-1	SHA-224	SHA-256	SHA-384	SHA-512
  MD길이	160	224	256	384	512
  최대 메시지 길이	2⁶⁴-1	2⁶⁴-1	2⁶⁴-1	2¹²⁸-1	2¹²⁸-1
  블록길이	512	512	512	1024	1024
  워드길이	32	32	32	64	64
  단계 수	80	64	64	80	80

• 기타 알고리즘
• RIPEMD(Race Integrity Primitives Evaluation Message Digest)
• HAVAL
• 주요 해시 알고리즘 비교

• 항목	MD5	SHA-1	RIPEMD-160
  다이제스트 길이	128비트	160비트	160비트
  처리단위	512비트	512비트	512비트
  단계수	64(16번의4라운드)	80(20번의4라운드)	160(16번의10라운드)
  최대 메시지 크기	무한	2⁶⁴-1	2⁶⁴-1
  앤디언	Little-endian	Big-endian	Little-endian

• 블록암호기반 해시함수
• 반복 암호학적 해시함수 안에 사용되는 압축함수 자리에 대칭키 블록암호를 써서 사용할 수 있다.
• DES,AES처럼 검증된 여러개의 대칭키 알고리즘이 있어 새로 압축함수를 만들 필요 없이 이 것들을 일방향 함수로 사용할 수 있기 때문이다. 이 경우 블록암호의 암호화 기능만 사용하는 것이다.

(2)SHA-512

1)개요

• 기본개념
• SHA-512는 다중블록메시지로부터 512비트 다이제스트를 생성한다. 각 블록은 1024비트 길이를 가진다. 
• 
• 길이 필드와 패딩
• 메시지 다이제스트를 생성하기 전에 SHA-512에서는 메시지에 추가적으로 덧붙이는 128비트의 부호 없는 정수길이 필드가 필요하다.
• 이 필드에서는 메시지의 길이가 비트수로 표현된 값이 저장된다. 이 길이는 패딩을 하기 전에 원해 메시지의 길이를 나타낸다.
• 

3.메시지 인증 코드(MAC)

(1)MAC의 개요

1)개본개념 

• 메시지 인증을 위해 필요한 것은 메시지 인증코드(MAC: Message Authentication Code)이다. 
• 무결성을 확인하고 메시지에 대한 인증을 하는 기술이다. 거짓변경과 거짓행세 검출 가능. 
• 메시지 인증코드는 임의 길이의 메시지와 송신자 및 수신자가 공유하는 키라는 2개의 입력을 기초로 해서 고정비트길이의 출력을 계산하는 함수이다. 이 출력을 MAC값이라한다.
• 

2)변경 감지 코드 (MDC: Modification Detection Code)

• 변경 감지 코드는 메시지의 무결성을 보장하는 메시지 다이제스트이다. 즉, 해당 메시지가 변경되지 않았다는것을 보장함. 
• Bob는 수신한 메시지로부터 새로운 MDC를 생성하여 Alice로부터 수신된 MDC와 비교한다. 만약 이 두 값이 동일하다면 해당 메시지는 변경되지 않았다는 뜻이 된다.
• 

3)메시지 인증 코드

• 미세지의 무결성은 물론 Alice가 메시지의 원래 전송자이며 다른 사람이 Alice인척 하는 것이 아니라는 것을 말해주는 데이터 출원지 인증을 보장하기 위해 변경 감지 코드를 메시지 인증코드(MAC: Message Authentication Code)로 바꿀 필요가 있다.
• MDC와 MAC의 차이를 살펴보면 MAC에는 Alice 와 Bob사이에 비밀값이 포함된다는 것이다. 예를들어 Eve는 가지고 있지 않은 비밀키가 두 사람 사이의 비밀 값이 될 수 있다. 
• 

4) MAC키의 배송 문제 

• MAC에서는 송신자와 수신자가 키를 공유할 필요가 있다.
• 송신자와 수신자가 키를 공유할 필요가 있다는 것은 대칭키 암호 때의 '키 배송 문제'와 같은 문제가 메시지 인증코드에서도 일어남을 의미한다.

(2)MAC의 구현 사례

1)축소 MAC

• MAC의 안전성을 높이기 위해 축소 MAC(nested MAC)이 설계되었는데 이 안에서는 해싱이 두 단계로 이루어져 있다.
• 첫 번쨰 단계에서 키는 메시지와 이어 붙이고 해시하여 중간 단계의 다이제스트를 생성한다. 2번째 단계에서 키는 중간단계 다이제스트에 이어 붙이고 최종적인 다이제스트를 생성한다.
• 

2)HMAC

• HMAC의 구현절차는 단순화된 축소 MAC보다 훨씬 복잡하다. HMAC에는 패딩같은 추가적인 조치가 더 들어가 있다.
• 
• HMAC은 일방향 해시함수를 이용하여 메시지 인증코드를 구성하는 방법이다. HMAC의 H는 Hashed를 의미한다.

3)CMAC(Cipher-based Message Authentication Code)

• 대칭키 암호 시스템에 대한 암호 블록체인(CBC)모드와 유사한 방법이다. 하지만 여기에서 사용한 아이디어는 N개의 평문블록으로부터 N개의 암호문 블록을 만드는 것이 아니다.
• 

(3)MAC의 이용 예 

1)IPsec

• IP(Internet Protocol)에 보안 기능을 추가한 것임.
• IPsec에서는 통신 인증과 무결성을 확인하기 위해 MAC를 이용 가능.

2)SSL/TLS

• SSL/TLS는 웹에서 온라인 쇼핑을 할 때 사용되는 통신 프로토콜 이다.
• SSL/TLS는 통신 내용의 인증과 무결성 확인을 위해 메시지 인증코드를 이용한다.

(4)MAC에 대한 공격

1)재전송공격 

• 개요 
• 적극적 공격자 멜로리는 자신이 보존해 두었던 MAC값을 반복해서 송신하는 공격을 감행한다. 이와 같은 공격을 재전송 공격(replay attack), 혹은 리플레이 공격이라고 한다.
• 재전송 공격을 막을 수 있는 방법에는 몇 가지가 있다.
• 
• 순서번호
• 송신 메시지에 매회 1회씩 증가하는 번호 (순서번호, sequence number)를 붙이기로 약속하고 , MAC값의 계산에서는 순서번호도 메시지에 포함시키도록 한다.
• 이렇게 해두면 멜로리는 순서본호를 늘렸을 떄의 MAC값을 계산할 수 없기 때문에 재전송 공격을 막을 수 있다. 이 방법은 유효하지만 통신 상대마다 마지막 순서 번호를 기록해 두어야 하는 번거로움이 있다.
• 타임스템프
• 송신 메시지에 현재 시각을 넣기로 약속해두고 그 이전의 메시지가 왔을 경우에는 MAC값이 바르더라도 오류라고 판단한다.
• 송/수신자 사이에 시계를 일치시켜 두는 동기화를 하지 않으면 안된다. 
• 비표(nonce)
• 메시지를 수신하기에 앞서 수신자를 송신자에게 일회용의 랜덤한 값을 전달한다. 이 값을 일반적으로 nonce(비표)라고 한다.
• 송신자는 메시지 안에 비표를 포함해서 MAC값을 계산한다. 비표의 값은 통신때마다 바뀌기 때문에 재전송 공격을 할 수 없다. 이 방법은 유효하지만 통신 데이터의 양은 약간 증가하게 된다. 

(5)MAC로 해결할 수 없는 문제 

1) 제 3자에 대한 증명 

• MAC은 공유키를 사용하기에 MAC값을 계산할 수 있는 것은 엘리스 또는 밥이다.두 사람이 서로 통신하고 있는 동안은 '그 MAC값을 계산한 것은 상대' 라고 말할 수 있다. 공유키를 알고 있는 두 사람 중 한 사람은 자신이기 때문이다. 
• 그러나 제 3자 빅터에게 '이 MAC값을 계산한 것은 자신이 아니라 상대'라고 증명할 방법은 없다. 전자서명을 사용하면 제 3자에 대한 증명이 가능해진다. 

2)부인방지

• 송신자 엘리스는 '나는 밥에게 메시지를 보내지 않았다.' 라고 빅터에게 주장 할 수 있다.
• MAC에서를 엘리스와 밥 중 어느 쪽 주장이 맞는지를 판단할 수 없기 때문에 부인방지를 할 방법이 없다. 
• 전자서명을 사용하면 부인방지가 가능해진다.

Section.04 비대칭키 암호

1.비대칭키 암호

(1)키 배송 문제

1)개요

• 대칭키 암호를 사용하려고 하면 키 배송 문제가 발생한다.
• 키를 보내지 않으면 수신자는 복호화할 수 없다. 키를 보내면 도청자도 복호화할 수 있다. 키를 보내지 않으면 되는데 키를 보내서도 안된다. -> 대칭키 암호의 키 배송 문제 
• 
• 키 배송 문제를 해셜하기 위한 방법에는 몇 가지가 있다.
• 키의 사전공유
• 키 배포 센터
• Diffie-Hellman 교환
• 공개키 암호

2)키의 사전 공유에 의한 해결

• 키 배송 문제를 해결하기 위한 가장 간단한 방법은 안전한 방법으로 키를 사전에 건내주는 것.
• 이 방법의 한계는 인원이 많아지면 통신을 위한 키의 수가 방대해지는 것.
• n명의 사원이 자신 외의 사람과 통신하고 싶을 경우 키의 수는 n(n-1)/2

3)키 배포 센터에 의한 해결

①개요

• 암호 통신이 필요해 질 때마다 통신용 키를 키 배포 센터(Key Distribution Center)라는 신뢰받는 제 3자에 의뢰해서 개인과 키 배포 센터 사이에서만 키를 사전에 공유하는것.
• 회사 안에 키 배포 센터의 역할을 하는 컴퓨터를 지정해 둔다. 이 컴퓨터에는 데이터 베이스가 있고, n명의 사원이 있다면 n개의 키가 그 안에 있다.

②단계별 순서 

• 

③세션키

• KDC는 각 구성원을 위해 비밀키를 생성한다. 이 비밀키는 구성원과 KDC사이에서만 사용될 수 있고 구성원끼리의 통신에서는 사용할 수 없다.
• alice가 bob과 기밀성을 유지하면서 통신을 하고자 한다면 alice는 bob과 자신 사이에 비밀키가 한 개 필요하다. KDC는 이들 두 사람과 센터 사이의 비밀키들을 이용해 alice와 bob사이에 필요한 세션키를 생성할 수 있다.
• 두 통신자 사이의 세션 대칭키는 오직 한 번만 사용한다.

4)Diffie-Hellman키 교환에 의한 해결

①개요

• 공개키 암호방식의 개념을 이용해 두 사용자 간에 공통의 암호화 키를 안전하게 공유할 수 있는 방법을 제시하였으며, 많은 키 분배 방식에 관한 연구의 기본이 되었다.(최초의 비밀키 교환 프로토콜)
• Diffie-Hellman 프로토콜 방법에서는 양쪽 통신주체가 KDC없이 대칭 세션키를 생성한다. 대칭키를 만들기 전에양쪽은 두 개의 수 p와g를 선택해야 한다. 여기서 p는 매우 큰 소수로서 300자리가 넘는 십진수(1024비트).
• 유한체상의 이산대수문제를 풀기 어렵다는 사실이 Diffie-Hellman키 교환을 뒷받침하고있다.(이산대수문제: G^A mod P로부터 수 A를 구하는 문제)

②절차

• 
• Alice는 임의의 큰 수 x를 0<= x <=p-1안에서 택하고 R1 = g^x mod p를 계산한다.
• bob는 다른 임의의 큰 수 y를 0<= y <=p-1안에서 택하고 R2 = g^y mod p를 계산한다.
• alice는 R1을 bob에게 보낸다. 여기서 alice는 오직 R1만을 보낸다.
• bob은 마찬가지로 R2만 보냄.
• alice는 K = (R2)^x mod p 를 계산한다.
• bob은 K = (R2)^y mod p 를 계산함.
• 이렇게 구한 값 K는 아래와 같고 세션에 사용될 대칭키이다.
• K = (g^x mod p)^y mod p = (g^y mod p)^x mod p = g^xy mod p

③Diffie-Hellman의 안전성

• Diffie-Hellman키 교환은 두 가지 공격에 약점을 보인다.  이산대수공격, 중간자공격.
• 이산대수공격
• 키 교환의 안전성은 이산대수문제를 퓰기 어렵가는데 기반을 두고 있다.
• eve가 R1과 R2를 가로챌 수 있을 것이다. 만약 eve가 R1 = g^x mod 로부터 x를 구하고 R2 = g^y mod 로부터 y를 구할 수 있다면, eve는 대칭키 K를 계산할 수 있게된다. 
• 중간자공격
• 키 교환 프로토콜은 이런 공격에 취약한데 그 이유는 인증단계가 없기 때문이다. 이런 공격을 막기 위해서는 디지털서명과 공개키 인증서 등을 이용한다.

5)공개키 암호에 의한 해결 

• 대칭키 암호에서 암호화키와 복호화키는 같지만 공개키암호는 서로 다름.
• 수신자는 미리 암호화키를 송신자에게 알려준다. 이는 도청자에게 알려져도 좋다. 송신자는 암호화키를 써서 암호화하여 수신자에게 보낸다.
• 복호화할 수 있는 것은 복호화키를 가지고 있는 사람(수신자)뿐이다. 이렇게하면 복호화키를 수신자에게 배송할 필요가 없어진다.
• 

(2)공개키 암호 (public-key cryptography)

1)개요

• 대칭키 암호는 평문을 복잡한 형태로 변환해서 기밀성을 유지한다. 공개키 암호는 수학적으로 해결하기 곤란한 문제를 토대로 해서 기밀성을 유지한다.
• 공개키 암호방식의 중요한 장점은 전자 문서의 무결성과 부인방지 기능을 갖고 있는 전자서명을 구현하는데 활용될 수 있으며 다양한 암호 프로토콜에 사용될 수 있다는 점이다. 
• 공개키 암호에서는 암호/복호화키가 분리되어있다. 송신자는 암호화키를 써서 메시지를 암호화하고 수신자는 복호화키를 써서 암호문을 복호화한다.

2)공개키 암호의 역사

• ㅇㅅaㅇ

3)일반적인 아이디어 

①개요 

• 일반적으로 대칭키 암호 시스템의 비밀키는 기호열(비트열 등)이지만, 비대칭키 암호시스템의 개인키는 하나의 숫자이거나 그 이상의 숫자들로이루어진다.
• 
• 이 그림에서 중요한점
• 암호 시스템의 비대칭성 강조.
• 보안성을 제공하는 책임이 대부분 수신자에게있음.(여기는 bob)
• bob는 개인키와 공개키로 된 두 개의 키를 만들어야 한다.

4)공개키 암호의 취약점 

• 이 방법에 의해 키 배송문제는 해결함. 그러나 입수한 공개키가 정말 바른 공개키인지 판단할 필요가 생김(공개키 신뢰성 문제)
• 공개키 인증에 관한 문제로 인증과정이 없을 시 중간가 공격에 취약하다.
• 수학이론적으로 풀기 어려운 문제를 이용하기 때문에 관용 암호시스템과 비교할 때 암호화 시간이 훨씬 오래 걸린다는 단점을 갖는다.

(3)RSA암호 시스템

1)개요

①기본개념

• RSA는 공개키 암호 알고리즘 중 하나이며 사실상 표준임.
• 인수분해 문제해결의 높은 난이도를 이용한 가장 대표적인 공개키 암호 알고리즘으로 암호화뿐 아니라 디지털서명의 용도로도 많이 사용된다.
• SSL프로토콜을 가진 많은 웹브라우저, PGP그리고 공개키 암호시스템을 사용하는 정부시스템 등이 RSA를 사용.

②암호화의 복호화

• RSA에서는 두 개의 지수 e와d를 사용함. e는 공개하지 않는값, d는 비밀로 유지하는 값. 
• Alice는 C=P^e mod n을 이용해 평문 P에서 암호문 C를 생성한다. bob은 암호문 C에서 P=C^d mod n을 구해 alice가 보낸 평문을 얻는다. 모듈러 n은 매우 큰 수이고 키 생성 프로세스를 통해 얻는다.
• 

③키 생성

• 알고리즘
• 안전을 위해 권장되는 각 소수 p와 q의 크기틑 512비트이다. 이 크기는 10진수로 약 154자리수이다. 이런 소수를 사용하면 모듈러로 사용할 n은 1024비트로 십진수 309자리가 된다.

2)RSA알고리즘 예

3)RSA에 대한 공격

①소인수분해 공격

• RSA는 모듈러 값이 매우 커서 이 값을 적절한 시간 내에 소인수분해 하는 것이 불가능하다는 아이디어에 근거해 안전성을 보장한다.
• bob는 p와 q를 선택하고 n = pq를 계산한다. 비록 n이 공개되는 값이지만 p와 q는 비밀로 유지한다. 만일 eve가 n을 소인수분해하여 p와q를 구할 수 있다면 eve는 ...을 계산할 수 있게 된다. 
• 현실적인 시간 내에 소인수분해를 마칠 수 있는 효율적인 소인수분해 알고리즘이 개발되지 않는 이상 RSA는 안전함.

②중간자공격

• 중간자공격은 기밀성에 대해 매우 유효한 공격 방법이다.
• 이 공격은 적극적 공격자 멜로리가 송신자와 수신자 사이에 들어가서 송신자에 대해서는 수신자처럼, 수신자에대해서는 송신자처럼 행세하는 공격이다. 
• 이 공격은 어떤 공개키 암호에도 사용가능.
• 이 공격을 막기 위해서는 입수한 공개키가 진짜인지 인증이 필요해진다. 이때 사용되는 것이 공개키 인증이다. 

4)권장사항 

5)최적 비대칭키 암호 패딩(OAEP)

①개요

• RSA에서 짧은 메시지 공격에 의해 암호문을 위험에 빠뜨리게 된다.
• 단순히 의미없는 데이터(패딩)를 메시지에 붙여서 eve의 공격 작업을 어렵게 만들 수 있다. 하지만 eve가 추가적인 노력을 하면 암호문을 충분히 공격할 수 있다.
• RSA그룹과 생산판매를 하는 몇명의 업자들이 제안한 해결책은 최적 비대칭키 암호화패딩(OAEP:Optional Asymmetric Encryption Padding)이라는 절차를 적용하는것.

(4)Rabin 암호 시스템 

1)개요 

• RSA암호 시스템의 변형. RSA는 지수합동에 근거하고, Rabin은 2차 합동에 근거한다.

2)암호화와 복호화

• Rabin암호시스템에서 암호화는 한번의 곱셈으로 매우 빠르고 간단함.
• 성능 낮은 플렛폼에서 잘 활용. 

3)Rabin 시스템 보안

• Rabin 의 p,q가 충분히 크다면 안전.
• Rabin의 복잡도는 큰 수 n을 두 개의 소수 곱으로 소인수분해하는 수준의 복잡도와 동일함. 따라서 Rabin 은 RSA만큼 안전함.

(5)ELGamal

1)개요

• 이산대수 문제에 근거해 만든 시스템
• 오픈소스를 기초로 키 분배 방식 및 공개키 암호 방식 실현.

2)암호화와 복호화

• bob의 공개키를 이용해 누구든지 bob에게 메시지를 보낼 수 있다. 만약 고속 지수 알고리즘을 사용한다면, ELGamal암호 시스템의 암호화는 다항식정도의 복잡도를 갖는 시간 내에 수행할 수 있다.
• ELGamal 방식에 의한 암호화애서는 암호문의 길이가 평문의 2배가 된다는 단점.

3)응용

• ELGamal은 RSA를 활용할 수 있는 곳에는 어디에나 사용할수 있다. 키 교환, 인증, 짧은 메시지의 암호화와 복호화에 사용할 수 있다.
• 암호 SW인 GnuPG에 구현되어있음 

(6)타원곡선 암호(elliptic curve cryptosystem;ECC)

• ECC는 유한체 위에서 정의된 타원곡선 군에서의 이산대수의 문제에 기초한 공개키 암호 알고리즘. RSA암호방식에 이어 전자상거래의 핵심 기술.
• RSA보다 키의 비트수를 적게 하면서도 동일한 성능을 제공하는 것이 가장 큰 특징.(160비트 ECC는 1024비트 RSA와 성능 동일.)
• 다양한 암호방식설계 가능. HW,SW로 구현 쉬움. 스마트카드, 무선통신 단말기등 메모리, 처리능력이 제한된 응용분야에 효율적.
• ECC는 RSA보다 상대적으로 지명도가 부족하며 배경이론이 복잡하고 해당 분야에서의 전문가가 적다는 단점이 있지만 , 최근 높은 속도로 구현이 가능하여 발전가능성이 큰 암호화 방식.

(7)대칭키 방식과 비대칭키 방식의 비교

2.하이브리드 암호시스템

1)대칭키 암호와 공개키 암호 

• 대칭키 암호를 사용하면 기밀성을 유지한 통신이 가능하다. 그러나 대칭키 암호를 실제로 운영하기 위해서는 키 배송 문제를 해결할 필요가 있다.
• 공개키 암호를 사용하면 복호화에 사용할 키를 배송할 필요가 없어지기 때문에 대칭키 암호가 근본적으로 가지고 있는 키 배송문제를 해결할 수 있다.
• 공개키 암호의 문제점
• 대칭키 암호에 비해 처리가 느림
• 중간자 공격에 취약
• 하이브리드 암호 시스템은 이 중 첫째를 해결하는 방법임. 두번째 문제는 공개키에 대한 인증으로 해결.

2)하이브리드 암호 시스템(Hybrid Cryotosystem)

• 하이브리드암호 시스템은 대칭키 암호화 공개키 암호의 장점을 살릴 수 있도록 조합한 방법. 
• 메시지를 일단 고속의 대칭키 암호로 암호화한다. 그러면 메시지가 암호문으로 변환되기 때문에 메시지의 기밀성을 지킬 수 있게된다. 
• 다음에 대칭키 암호의 키 키밀성을 지키기 위해 이 부분에 공개키 암호를 사용한다. 즉, 메시지를 암호화할 때 사용한 대칭키 암호키를 공개키 암호로 암호화 한다.

3)하이브리드 암호시스템의 암호화

①메시지의 암호화

• PRNG(pseudo random number generator):의사난수 생성기
• 오른쪽 반은매시지의 암호화를 행하는 부분(대칭키암호), 왼쪽반은 세션키의 암호화를 행하는 부분(공개키암호).
• 메시지를 암호화(C1=E(K,P))하는 것은 대칭키암호를 이용해 암호화하는것과 동일하다.

②세션키의 암호화

• 왼쪽 부분에서는 세션키의 작성과 세션키의 암호화를 수행한다.
• 세션키는 한번의 통신을 위해 일시적으로 만들어지는 키로, 의사난수 생성기로 생성하는것이 보통이다.
• 세션키는 오른쪽 반의 대칭키 암호로 건네져서 대칭키 암호의 비밀키로 사용된다.
• 세션키는 수신자의 공개키로 암호화한다. 공개키 암호의 암호화에 사용하는 키는 수신자의 공개키 이다. 
• 세션키는 대칭키 암호에 있어서는 키이지만, 공개키 암호의 입장에서는 하나의 평문이다. 라는 개념이 핵심. 
• 세션키가 대칭키 암호와 공개키 암호라는 2개의 암호를 서로 이어주는 중요한 역할을 하고있다.

③결합

• 오른쪽 반에서 대칭키로 암호화된 암호문을 얻고, 왼쪽 반에서 수신자의 공개키로 암호화된 세션키를 얻는다. 그리고 이 2개를 결합한다. 
• 결합이라는것은 단지 순서대로 붙여 놓은것. 
• 이렇게 결합한 것이 하이브리드 암호 시스템 전체에 있어 암호문이 된다.

4)하이브리드 암호시스템의 복호화

①분할

• 하이브리드 암호시스템의 암호문은 수신자의 공개키 암호로 암호화된 세션키와 대칭키로 암호화된 암호문을 결합한 것이다. 먼저 이 양자를 분할한다.
• 암호문이 어떠한 구조를 하고 있는지 송신자와 수신자사이에 정해두면 분할하는것은 쉽다.

②세션키의 복호화 

• 세션키는 공개키 암호를 사용해서 복호화한다. 그러기위해서는 복호화하기, 즉 수신자의 개인키가 필요하다.
• 수신자의 개인키로 복호화된 세션키는 메시지 복호화키로 이용된다.

③메시지 복호화

• 메시지는 대칭키 암호를 써서 복호화한다.
• 복호화키로 조금 전에 공개키 복호 알고리즘으로 복호화한 세션키를 사용한다.

5)하이브리드 암호 시스템의 구체적인 예

• 공개키 암호의 처리속도가 느린점을 대칭키 암호로 해결하고 대칭키 암호의 키 배송문제를 공개키 암호로 해결. 
• PGP, SSL/TSL에서도 사용
• PGP의 처리에서는 하이브리드 암호 시스템에 디지털서명, 디지털서명의 검증, 개인키의 관리도 추가해 연관되게 된다.