해시 함수의 특성과 이용(2015, 9월모평A)

온라인을 통한 통신, 금융, 상거래 등은 우리에게 편리함을 주지만 보안상의 문제도 안고 있는데, 이런 문제를 해결하기 위하여 암호 기술이 동원된다. 예를 들어 전자 화폐의 일종인 비트코인은 해시 함수를 이용하여 화폐 거래의 안전성을 유지한다. 해시 함수란 입력 데이터 x에 대응하는 하나의 결과 값을 일정한 길이의 문자열로 표시하는 수학적 함수이다. 그리고 입력 데이터 x에 대하여 해시 함수 H를 적용한 수식을 H(x)=k라 할 때, k를 해시 값이라 한다. 이때 해시 값은 입력 데이터의 내용에 미세한 변화만 있어도 크게 달라진다. 현재 여러 해시 함수가 이용되고 있는데, 해시 값을 표시하는 문자열의 길이는 각 해시 함수마다 다를 수 있지만 특정 해시 함수에서의 그 길이는 고정되어 있다.

이러한 특성을 갖고 있기 때문에 해시 함수는 데이터의 내용이 변경되었는지 여부를 확인하는데 이용된다. 가령, 상호 간에 동일한 해시 함수를 사용한다고 할 때, 전자 문서와 그 문 서의 해시 값을 함께 전송하면 상대방은 수신한 전자 문서에 동일한 해시 함수를 적용하여 결과 값을 얻은 뒤 전송받은 해시 값과 비교함으로써 문서가 변경되었는지 확인할 수 있다.

그런데 해시 함수가 일방향성과 충돌회피성을 만족시키면 암호 기술로도 활용된다. 일방향성이란 주어진 해시 값에 대응하는 입력 데이터의 복원이 불가능하다는 것을 말한다. 특정 해시 값 k가 주어졌을 때 H(x)=k를 만족시키는 x를 계산하는 것이 매우 어렵다는 것이다. 그리고 충돌회피성이란 특정 해시 값을 갖는 서로 다른 데이터를 찾아내는 것이 현실적으로 불가능하다는 것을 의미한다. 서로 다른 데이터 x, y에 대해서 H(x)와 H(y)가 각각 도출한 값이 동일하면 이것을 충돌이라 하고, 이때의 x와 y를 충돌쌍이라 한다. 충돌회피성은 이러한 충돌쌍을 찾는 것이 현재 사용할 수 있는 모든 컴퓨터의 계산 능력을 동원하더라도 그것을 완료하기가 사실상 불가능하다는 것이다.

해시 함수는 온라인 경매에도 이용될 수 있다. 예를 들어 ○○ 온라인 경매 사이트에서 일방향성과 충돌회피성을 만족시키는 해시 함수 G가 모든 경매 참여자와 운영자에게 공개되어 있다고 하자. 이때 각 입찰 참여자는 자신의 입찰가를 감추기 위해 논스*의 해시 값과, 입찰가에 논스를 더한 것의 해시 값을 함께 게시판에 게시한다. 해시 값 게시 기한이 지난 후 각 참여자는 본인의 입찰가와 논스를 운영자에게 전송하고 운영자는 최고 입찰가를 제출한 사람을 낙찰자로 선정한다. 이로써 온라인 경매 진행 시 발생할 수 있는 다양한 보안상의 문제를 해결할 수 있다.

* 논스: 입찰가를 추측할 수 없게 하기 위해 입찰가에 더해지는 임의의 숫자.