[현대 암호학] 08-1.일방향 해시 함수

1. 일방향 해시 함수

 

파일의 진위

 

어제 저장한 파일과 오늘의 파일 비교

• 밤새 맬로리가 파일을 변경했는지 어떤지를 조사하고 싶다.

 

무결성(Integrity)

파일이 변경되지 않았음

파일의 무결성을 조사하고 싶다.

 

 

파일 전체를 안전한 장소에 보존해두고 나중에 비교하는 방법 

 

 

파일의 지문(fingerprint)

• 범죄 수사에서 지문을 채취하는 것과 마찬가지로 앨리스가 만든 파일의 "지문"을 채취할 수 없을까?
• 파일 전체를 비교하는 대신에 작은 지문만을 비교하는 것만으로도 무결성을 확인할 수 있다면 매우 편리

 

파일을 비교하는 대신에 해시 값을 비교하는 방법 

 

 

일방향 해시 함수(One-way hash function)란?

• 일방향 해시 함수는 바로 파일의 지문을 재취하는 기술
• 일방향 해시 함수가 만들어내는 "해시 값"(다이제스트)은 메시지의 지문에 해당

 

 

일방향 해시 함수(One-way hash function)

• 입력과 출력이 각각 1개씩 있다.
• 입력은 메시지(message)
• 출력은 해시값(hash value)
• 일방향 해시 함수는 메시지를 기초로 해서 해시 값을 계산

 

 

일방향 함수의 예(단순 설명을 위한 예이다.)

• 입력: 임의의 숫자
• 처리: 입력되는 숫자를 23으로 나누는 메커니즘
• 출력: 그 몫을 소수로 표시했을 때 소수점 이하 7자리부터 10자리까지 4자리 숫자

입력: 345689 처리: 345689 ÷ 23 출력: 7391

• 몫: 15029.95652173913043... 이므로 7자리부터 10자리의 수는 7391

 

일방향 해시 함수는 메시지를 기초로 해서 해시 값을 계산

일방향 해시 함수는 메시지를 기초로 해서 값을 계산한다 .

 

일정한 크기의 출력

• 해시 값의 길이는 메시지의 길이와는 관계가 없다.
• 메시지가 1비트라도, 1메가바이트라도, 100기가바이트라도 일방향 해시 함수는 고정된 길이의 해시 값을 출력
• 예: SHA-1의 출력은 항상 160비트(20바이트)

  해시 값은 항상 고정 길이

 

 

 

일방향 해시 함수의 성질

 

• 임의의 길이 메시지로부터 고정 길이의 해시 값을 계산한다.
• 해시 값을 고속으로 계산 할 수 있다.
• 메시지가 다르면 해시 값도 다른다.
• 일방향성을 갖는다.

 

1) 고정 길이의 출력

• 어떠한 크기의 메시지라도 크기에 관계없이 입력으로 사용할 수 있어야 한다.
• 어떤 길이의 메시지를 입력으로 주더라도 일방향 해시 함수는 짧은 해시 값을 생성

 

2) 빠른 계산 속도

• 해시 값 계산은 고속이어야 한다.
• 메시지가 길어지면 해시값을 구하는 시간이 길어지는 것은 어쩔수 없다.
• 현실적인 시간 내에 계산할 수 없다면 소용이 없다.

 

3) 메시지가 다르면 해시 값도 다르다.

• 메시지가 1비트라도 변화하면 해시 값은 매운 높은 확률로 다른 값이 되어야 한다.

 

4) 일방향성을 갖는다.

• 해시 값으로부터 메시지를 역산할 수 없다는 성질
• 메시지로 부터 해시 값을 계산하는 것은 간단히 할 수 있다.
• 해시 값으로부터 메시지를 계산하는 것은 불가능해야 한다.

 

5) 기타

 

해시 함수의 충돌

 

충돌(Collision)

• 2개의 다른 메시지가 같은 해시 값을 갖는 것

 

충돌 내성(Collision Resistance)

• 충돌을 발견하는 것이 어려운 성질

 

일방향 함수의 충돌 내성

 

 

 

 

 

[참고] 해시 함수의 성질

 

• 일방향성
• 강한 충돌 내성: 2개의 해시 값이 같은, 2개의 메세지를 찾을 없게 하는 성질
• 약한 출돌 내성: 2개의 해시 값이 같을 때, 2개의 메세지가 같다는 것을 찾을수 없게 하는 성질

 

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

• y = h(M)에 대해 메시지 M을 찾는 것이 계산적으로 불가능
• 어떤 해시 값에 대해서, 원래 입력 값을 찾는 어려워야 하며, 이를 일방향성(One-wayness)이라고 한다.

 

제2 역상 저항성(약한 충돌 내성)

• h(M) = h(M'), M≠M'을 만족하는 다른 입력 값 M'을 찾는 것이 어려움
• 어떤 입력 값에 대하여, 그 입력값의 해시값과 같은 해시값이 갖는 또다른 입력값을 찾는 것이 어려워야 한다.

 

 

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

• h(M) = h(M')과 같이 동일한 다이제스트를 가지는 2개의 메시지(M, M')를 구하는 것이 계산적으로 불가능
• 다른 표현 : 걍 일방향성 -> 서명문 M과 그 해시값 H=h(M) 이 주어졌을 때 H=h(M')가 되는 M'을 찾는 것이 계산상 불가능
• 같은 해시값을 갖는 두 입력값을 찾는 것이 어려워야 한다.

 

충돌 저항성

 

 

 

해시 함수 관련 용어

 

(해시 함수) 일방향 해시 함수

• 메시지 다이제스트 함수(Message Digest Function)
• 메시지 요약 함수
• 암호적 해시 함수

 

(입력) 일방향 해시 함수이 입력이 되는 메시지

• 프리-이미지(Pre-Image)

 

(출력) 해시 값은

• 메시지 다이제스트(Message Digest)
• 핑거프린트(Fingerprint)
• 해시 값(Hash Value)

 

무결성

• 완전성
• 보전성