Home > Algorithm > 2024 > πŸ“¦[DS,Algorithm] ν•΄μ‹œ(Hash)

πŸ“¦[DS,Algorithm] ν•΄μ‹œ(Hash)
DataStructure Algorithm

1️⃣ ν•΄μ‹œ(Hash).

ν•΄μ‹œ(Hash)λž€ 컴퓨터 κ³Όν•™μ—μ„œ 주어진 μž…λ ₯ 데이터λ₯Ό κ³ μ •λœ 크기의 κ³ μœ ν•œ κ°’(일반적으둜 숫자)으둜 λ³€ν™˜ν•˜λŠ” κ³Όμ • λ˜λŠ” κ·Έ κ²°κ³Ό 값을 λ§ν•©λ‹ˆλ‹€.

ν•΄μ‹œλŠ” 주둜 데이터 검색, 데이터 무결성 검증, μ•”ν˜Έν™” 등에 μ‚¬μš©λ©λ‹ˆλ‹€.

1️⃣ ν•΄μ‹œμ˜ κ°œλ….

  1. ν•΄μ‹œ ν•¨μˆ˜(Hash Function)
    • μž„μ˜μ˜ 길이λ₯Ό 가진 데이터λ₯Ό κ³ μ •λœ 길이의 ν•΄μ‹œ κ°’μœΌλ‘œ λ³€ν™˜ν•˜λŠ” ν•¨μˆ˜μž…λ‹ˆλ‹€.
    • ν•΄μ‹œ ν•¨μˆ˜λŠ” λ™μΌν•œ μž…λ ₯에 λŒ€ν•΄ 항상 λ™μΌν•œ ν•΄μ‹œ 값을 생성해야 ν•˜λ©°, μ„œλ‘œ λ‹€λ₯Έ μž…λ ₯에 λŒ€ν•΄μ„œλŠ” κ°€λŠ₯ν•œ ν•œ λ‹€λ₯Έ ν•΄μ‹œ 값을 생성해야 ν•©λ‹ˆλ‹€.
  2. ν•΄μ‹œ κ°’(Hash Value)
    • ν•΄μ‹œ ν•¨μˆ˜λ₯Ό 톡해 μƒμ„±λœ κ³ μ •λœ 크기의 좜λ ₯ κ°’μž…λ‹ˆλ‹€.
      • 이λ₯Ό ν•΄μ‹œ μ½”λ“œ(Hash Code) λ˜λŠ” λ‹€μ΄μ œμŠ€νŠΈ(Digest)라고도 ν•©λ‹ˆλ‹€.

2️⃣ ν•΄μ‹œ ν•¨μˆ˜μ˜ νŠΉμ§•.

  1. κ²°μ •μ„±(Deterministic) : λ™μΌν•œ μž…λ ₯에 λŒ€ν•΄ 항상 λ™μΌν•œ ν•΄μ‹œ 값을 λ°˜ν™˜ν•©λ‹ˆλ‹€.

  2. νš¨μœ¨μ„±(Efficiency) : ν•΄μ‹œ ν•¨μˆ˜λŠ” μž…λ ₯ 데이터λ₯Ό λΉ λ₯΄κ²Œ μ²˜λ¦¬ν•˜μ—¬ ν•΄μ‹œ 값을 생성해야 ν•©λ‹ˆλ‹€.

  3. 좩돌 μ €ν•­μ„±(Collision Resistance) : μ„œλ‘œ λ‹€λ₯Έ 두 μž…λ ₯이 λ™μΌν•œ ν•΄μ‹œ 값을 갖지 μ•Šλ„λ‘ ν•΄μ•Ό ν•©λ‹ˆλ‹€. ν˜„μ‹€μ μœΌλ‘œ μ™„λ²½ν•œ 좩돌 저항성은 λΆˆκ°€λŠ₯ν•˜λ―€λ‘œ, κ°€λŠ₯ν•œ μΆ©λŒμ„ μ΅œμ†Œν™”ν•˜λŠ” 것이 μ€‘μš”ν•©λ‹ˆλ‹€.

  4. 역상 μ €ν•­μ„±(Pre-image Resistance) : ν•΄μ‹œ 값을 톡해 μ›ν•΄μ˜ μž…λ ₯ 데이터λ₯Ό μœ μΆ”ν•˜λŠ” 것이 μ–΄λ ΅κ±°λ‚˜ λΆˆκ°€λŠ₯ν•΄μ•Ό ν•©λ‹ˆλ‹€.

  5. 두 번째 역상 μ €ν•­μ„±(Second Pre-image Resitance) : νŠΉμ • μž…λ ₯κ³Ό λ™μΌν•œ ν•΄μ‹œ 값을 κ°–λŠ” 또 λ‹€λ₯Έ μž…λ ₯을 μ°ΎλŠ” 또 λ‹€λ₯Έ μž…λ ₯을 μ°ΎλŠ” 것이 μ–΄λ €μ›Œμ•Ό ν•©λ‹ˆλ‹€.

3️⃣ ν•΄μ‹œ ν•¨μˆ˜μ˜ μš©λ„.

  1. 데이터 검색 : ν•΄μ‹œ ν…Œμ΄λΈ”(Hash Table)κ³Ό 같은 μžλ£Œκ΅¬μ‘°μ—μ„œ λΉ λ₯Έ 데이터 검색을 μœ„ν•΄ μ‚¬μš©λ©λ‹ˆλ‹€.

  2. 데이터 무결성 검증 : 데이터가 λ³€κ²½λ˜μ§€ μ•Šμ•˜μŒμ„ ν™•μΈν•˜κΈ° μœ„ν•΄ ν•΄μ‹œ 값을 μ‚¬μš©ν•©λ‹ˆλ‹€. 예λ₯Ό λ“€μ–΄, 파일의 ν•΄μ‹œ 값을 λΉ„κ΅ν•˜μ—¬ 파일이 μ†μƒλ˜μ§€ μ•Šμ•˜μŒμ„ 확인할 수 μžˆμŠ΅λ‹ˆλ‹€.

  3. μ•”ν˜Έν™” 및 λ³΄μ•ˆ : νŒ¨μŠ€μ›Œλ“œ μ €μž₯, 디지털 μ„œλͺ…, λ©”μ‹œμ§€ 인증 μ½”λ“œ(MAC) λ“±μ—μ„œ λ°μ΄ν„°μ˜ 무결성과 기밀성을 보μž₯ν•˜κΈ° μœ„ν•΄μ„œ μ‚¬μš©λ©λ‹ˆλ‹€.

4️⃣ ν•΄μ‹œ ν•¨μˆ˜μ˜ 예

  • SHA-256(Secure Hash Algorithm 256-bit) : 256λΉ„νŠΈμ˜ ν•΄μ‹œ 값을 μƒμ„±ν•˜λŠ” μ•”ν˜Έν™” ν•΄μ‹œ ν•¨μˆ˜μž…λ‹ˆλ‹€.

  • MD5(Message Digest Algorithm 5) : 128λΉ„νŠΈμ˜ ν•΄μ‹œ 값을 μƒμ„±ν•˜λŠ” ν•΄μ‹œ ν•¨μˆ˜λ‘œ, ν˜„μž¬λŠ” 좩돌 μ €ν•­μ„±μ˜ μ·¨μ•½μ„± λ•Œλ¬Έμ— λ³΄μ•ˆ μš©λ„λ‘œλŠ” ꢌμž₯λ˜μ§€ μ•ŠμŠ΅λ‹ˆλ‹€.

  • CRC32(Cyclic Redundancy Check 32-bit) : 데이터 전솑 였λ₯˜ κ²€μΆœμ„ μœ„ν•΄ μ‚¬μš©λ˜λŠ” 32λΉ„νŠΈ ν•΄μ‹œ ν•¨μˆ˜μž…λ‹ˆλ‹€.

πŸ™‹β€β™‚οΈ μ£Όμš” 포인트 μš”μ•½

  • ν•΄μ‹œ(Hash) λŠ” 데이터λ₯Ό κ³ μ •λœ 크기의 κ³ μœ ν•œ κ°’μœΌλ‘œ λ³€ν™˜ν•˜λŠ” κ³Όμ •μž…λ‹ˆλ‹€.

  • ν•΄μ‹œ ν•¨μˆ˜λŠ” λΉ λ₯΄κ³  효율적으둜 ν•΄μ‹œ 값을 μƒμ„±ν•˜λ©°, μΆ©λŒμ„ μ΅œμ†Œν™”ν•˜κ³  역상을 μ˜ˆμΈ‘ν•  수 없도둝 μ„€κ³„λ˜μ–΄μ•Ό ν•©λ‹ˆλ‹€.

  • ν•΄μ‹œ ν•¨μˆ˜λŠ” 데이터 검색, 무결성 검증, μ•”ν˜Έν™” λ“± λ‹€μ–‘ν•œ μš©λ„λ‘œ μ‚¬μš©λ©λ‹ˆλ‹€.

πŸ’» ν•΄μ‹œ ν•¨μˆ˜μ˜ 예제 μ½”λ“œ

μ•„λž˜λŠ” Javaμ—μ„œ SHA-256 ν•΄μ‹œ ν•¨μˆ˜λ₯Ό μ‚¬μš©ν•˜μ—¬ λ¬Έμžμ—΄μ˜ ν•΄μ‹œ 값을 μƒμ„±ν•˜λŠ” μ˜ˆμ œμž…λ‹ˆλ‹€.

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

public class Main {

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

    try {
      // SHA-256 ν•΄μ‹œ ν•¨μˆ˜ μΈμŠ€ν„΄μŠ€ 생성
      MessageDigest digest = MessageDigest.getInstance("SHA-256");

      // μž…λ ₯ λ¬Έμžμ—΄μ˜ ν•΄μ‹œ κ°’ 계산
      byte[] hash = digest.digest(input.getBytes());

      // ν•΄μ‹œ 값을 16μ§„μˆ˜ λ¬Έμžμ—΄λ‘œ λ³€ν™˜ν•˜μ—¬ 좜λ ₯
      System.out.println("Hash value: " + bytesToHex(hash));
    } catch (NoSuchAlgorithmException e) {
      e.printStackTrace();
    }
  }

  // λ°”μ΄νŠΈ 배열을 16μ§„μˆ˜ λ¬Έμžμ—΄λ‘œ λ³€ν™˜ν•˜λŠ” ν•¨μˆ˜
  private static String bytesToHex(byte[] bytes) {
    StringBuilder hexString = new StringBuilder();

    for (byte b : bytes) {
      String hex = Integer.toHexString(0xff & b);

      if (hex.length() == 1) hexString.append('0');
      hexString.append(hex);
    }
    return hexString.toString();
  }
}