Published on

[ Algorithm ] 해시 알고리즘

Authors
  • avatar
    Name
    유사공대생
    Twitter

pope 아저씨의 해시에 대한 견해

실력있는 프로그래머를 가르는 가장 큰 요인은 컴퓨터에 대해서 잘 이해하고 있는 사람이다.

그런데 이해를 잘하게 된다면 컴퓨터는 결국에 숫자로 돈다는 것을 알게 된다. 따라서 숫자로 이루어진 해시가 컴퓨터에 가장 최적화된 개념이다.

해시란?

해시는 데이터를 고정된 길이의 문자열로 변환하는 알고리즘 또는 함수를 의미한다. 이 고정된 길이의 문자열은 일반적으로 고유한 입력 데이터에 대해 고유한 출력 값을 생성한다. 해시 함수는 다양한 용도로 사용되며, 주로 데이터의 무결성을 검증하거나 데이터를 안전하게 저장하거나 빠르게 검색하기 위해 사용된다.

보통 데이터 무결성 검증, 비밀번호저장, 데이터베이스 검색, 블록체인과 암호화폐에 사용된다.

image

Java에서 SHA-256 해시함수를 사용하여 문자열을 해싱하는 예제

import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;

public class HashExample {
    public static void main(String[] args) {
        String input = "Hello, World!";

        try {
            // MessageDigest 객체 생성
            MessageDigest md = MessageDigest.getInstance("SHA-256");

            // 입력 데이터 바이트로 변환
            byte[] inputBytes = input.getBytes();

            // 해시 계산
            byte[] hashBytes = md.digest(inputBytes);

            // 해시 값을 16진수 문자열로 변환하여 출력
            StringBuilder hexString = new StringBuilder();
            for (byte b : hashBytes) {
                String hex = Integer.toHexString(0xff & b);
                if (hex.length() == 1) {
                    hexString.append('0');
                }
                hexString.append(hex);
            }
            System.out.println("SHA-256 Hash: " + hexString.toString());

        } catch (NoSuchAlgorithmException e) {
            e.printStackTrace();
        }
    }
}

해시 알고리즘의 정의와 속성

다양한 해시 알고리즘의 용도

  • 해시는 컴공에서 매우 근본이 되는 알고리즘중 하나
  • 이미 여러 번 본 해시 알고리즘의 용도
    • 해시 테이블에서 데이터를 저장할 위치를 찾기 위해
    • 길이가 긴 데이터 둘을 빨리 비교하기 위해
      • 단 다른 경우만 빨리 비교 가능
    • 누출되면 곤란한 데이터의 원본을 저장하기 않기 위해
  • 용도에 따라 해시 알고리즘의 요구사항이 조금씩 달라질 수 있음

해시 함수의 정의

  • 임의의 크기를 가진 값을 고정 크기의 값에 대응시키는 함수
  • 여전히 함수이므로 수학에서의 함수의 정의도 만족해야 함
  • 입력값이 같으면 언제나 출력값도 같아야 함(결정론적 작동)

해시 알고리듬 분류과 속성

해시 알고리듬 분류

  • (비암호학적) 해시 함수

  • 암호학적 해시 함수

  • 체크 섬(검사합, checksum)

  • 순환 중복 검사(cyclic redundancy check, CRC)

이 모두 해시 함수의 필요요건을 충족하지만(임의크기가 고정 크기가 된다, 결정론적으로 작동한다.) 해시 알고리즘의 다른 속성은 조금씩 달라짐

모든 해시 알고리즘의 속성

  • 효율성(efficiency)
  • 균일성(uniformity)
  • 등

균일성

  • 해시 함수의 출력값이 고르게 분포될수록 균일성이 높음
    • 입력값으로 기대하는 값에 대해(예: 모든 정수값, 사전에 있는 단어)
  • 흔히 훌륭한 해시 함수는 균일성이 높아야 한다고 함
    • 즉, 출력 범위 안의 모든 값들이 동일한 확류롤 나와야 함(균등 분포)
    • 이러면 해시 충돌이 적어 O(1) 해시 테이블을 기대할 수 있음
  • 완벽한(perfect) 해시 함수: 해시 충돌이 전혀 없는 함수
    • 입력값이 매우 제한적일 경우에만 가능
    • 이유: 나중에 생일 문제(birthday problem)에서 설명

균일성의 측정

  • 카이제곱 검정(chi-squared test)을 이용

image

  • 결과가 0.95 ~ 1.05 사이면 균일한 분포를 가진 해시 함수라 봄

균일성을 높일 수 있는 실용적인 방법

  • 해시 값을 덜 중복되게 버킷 수를 정할 것(소수를 사용)
  • 완벽한 '눈사태'가 일어나도록 해시 함수를 설계하는 것

눈사태 효과(avalanche effect)

  • 입력값이 약간만 바뀌어도 출력값이 굉장히 많이 바뀌는 것
    • 보통 암호학적 알고리즘이 매우 선호하는 효과
    • 알고리즘의 규칙을 쉽게 유추할 수 없음
  • 엄격한 눈사태 기준(strict avalanche criterion, SAC)
    • 입력값에서 1비트를 뒤집으면 출력값의 각 비트가 뒤집힐 확률 50%
    • 이 기준을 충족하는 해시 함수는 분포가 균일할 가능성이 매우 높음

효율성

  • 보통 빠른 해시 함수를 선호함

  • 공간을 더 낭비해도 빠른 접근 속도를 선호

    • 저장된 데이터를 빨리 찾는 용도로 사용하는 해시 함수

  • 충돌이 좀 더 나더라도 더 빠른 함수를 선호

    • 어차피 해시 충돌은 드문 일
    • 몇 개 난다고 O(1)에서 크게 느려지지 않음

  • 하지만 하드웨어 가속이 어려운 해시를 선호하는 경우도 있음

    • 여전히 소프트웨어에서는 빨리 실행되는걸 선호

비암호학적 해시함수

  • 암호학적으로 사용하기에 안정하지 않은 해시 함수들

  • 보안적으로 문제 없는 용도에 주로 사용

    • 데이터 저장 및 찾기(해시 테이블)
    • 저장/전송 중에 생긴 데이터 오류 탐지
    • 고유한 ID 생성

  • 출처 해시함수

Discuss on Twitter • View on GitHub