안녕하세요ㅎㅎ
이번에 서울여대 정보보호영재교육원에서 교육받은 1차 1부 수업 내용인 해시함수에 대해 포스팅을 하려고 합니다.
이번 계기로, 앞으로 crypto 공부를 이어나가지 않을까 싶습니다 ^^
해시함수란?
해시함수는 임의의 데이터를 고정된 길이로 매핑하는 함수를 말합니다.
예를 들자면 이런것입니다.
MD5를 예시로 들어보겠습니다.
이렇게 다른 길이의 평문들을 넣게되어도, 같은 길이의 해시값을 가지는 것을 알 수 있습니다.
또한 동일한 입력값을 넣으면, 동일한 결과를 도출합니다.
그리고, 하나 더 알 수 있는것은 입력값이 한글자만 차이가 나더라도, 결과값이 완전히 변하기 때문에 예측하기 어렵습니다 ㅎㅎ
ex)
md5("a") : 0cc175b9c0f1b6a831c399e269772661
md5("a!") : a46da3640231e41e1782925a91e46103이렇게 해시함수의 특징 세가지는
- 임의의 평문을 고정된 데이터로 매핑.
- 동일한 입력값은 동일한 결과값, 다른 입력값은 다른 결과값.
- 눈사태효과 : 입력값이 조금만 달라져도, 결과값이 완전히 달라짐.
이러한 해시함수는 다양한 분야에서 이용됩니다.
- 해시테이블 자료구조에서 이용함
- 매우 빠른 데이터 검색에 사용됨
- 큰 파일에서 중복되는 레코드를 찾을 수 있음
- 블록체인에서 chain을 구성하는 요소
- 암호의 목적으로도 사용됨
여기서 중요하게 보아야할 부분은 '암호의 목적'으로 사용되는 해시 함수입니다.
암호용 해시함수
위에서 본 해시함수의 특성은 보안의 분야에서 암호용으로 사용하기 적합한 함수입니다.
예를들면 이런 것들이 있지요.
MD5, SHA-1, SHA-512 등등..
이러한 암호용 해시함수가 가져야할 특징이 2가지가 있습니다.
- 해시값은 항상 유일해야 한다. (중복되는 것이 존재하면 안된다)
- 역함수가 존재해서는 안된다. (해시값을 토대로, INPUT값을 유추할 수 있으면 안된다)
이렇게 암호용 해시함수는 이러한 2가지 특성을 만족하게 됩니다.
이 2가지 조건을 만족하지 않는다면, 암호용으로서 많이 취약합니다.
만약, 역함수가 존재하여 해시값으로 암호 평문을 알수 있다면 큰일나겠죠?
그렇다면, 왜 이러한 조건을 만족하게 되느냐?
그 이유는 바로 해시값의 길이는 항상 고정되어 있기 때문입니다!
엥? 그게 무슨상관이죠?
엄청난 상관이 있습니다 ㅎㅎ
해시함수는 기본적으로 INPUT 평문의 길이는 제한이 없고, 결과 값은 항상 길이가 같습니다.
수학적으로 바라보게 되면 정의역은 무한한데, 치역은 제한되어 있는 것이죠.
즉, 이런 셈입니다.
이러한 상태일때 만족하는 것이 있습니다.
바로 역함수가 존재하지 않는것이죠.
역함수가 존재할 조건은 일대일 함수 일때, 즉 정의역과 치역의 원소개수가 같아야 합니다.
그런데, 위의 그림에서는 치역이 제한되어 있기 때문에 역으로 값을 구할수 없는것이죠.
어??? 근데 이거 왜이래요? 이렇게 되면, 해시값이 유일한 값이 도출되고, 중복되는 값이 없어야 하는데,
저러면 중복되는것이 생기지 않나요..?
네 맞습니다. 해시함수는 사실 1.번 특성을 만족할 수 없습니다.
해시값으로 만들 수 있는 경우의 수가 정의역의 수보다 적기 때문이죠.
만약 저기에서 치역이 A, B, C, D밖에 없고, 정의역이 1 ~ 6로 치면 이렇게 됩니다
함수라는 조건을 만족하기 위해 정의역의 원소가 치역에 모두 대응한걸 볼 수 있습니다.
하지만, 빨간색 화살표를 한번 보세요
이렇게, 치역이 정의역보다 적으면 어쩔수 없이 충돌이 일어나는 것을 확인할 수 있습니다.
그래서 항상 새로운 암호방식이 만들어집니다!
SHA-1도 예전에는 많이 사용되었다가, 중복되는 값이 발견이 되고 취약해지면서 새로운 암호방식이 계속해서 나오는중이죠.
오늘 해시함수에 대해 알아보는건 여기까지 해보겠습니다 ㅎㅎ
다음에 기회가 된다면, 해시함수의 알고리즘이나 암호화 방식에대한 주제를 다루어볼 예정입니다^^
감사합니다