[Hash] 해시 알고리즘

1. 해시 함수, 해시 알고리즘

• 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수.
• 이런 해시 함수에 의해 얻어지는 갑은 해시 값, 해시 코드, 해시 라고 한다.
• 해시 테이블 자료구조에 사용되며, 매우 빠른 데이터 검색을 위한 곳에 널리 사용된다.

 

2. 안전한 해시 함수

• 역상 저항성 : 해시 값을 생성하는 입력값을 찾는 것이 계산상 어려워야한다.
• 제 2역상 저항성 : 동일한 해시값(y)이 나오는 다른 입력값(x`)을 찾는 것은 계산적으로 불가능 해야한다.
• 충돌 저항성 : 동일한 해시 값이 나와서는 안된다.

3. SHA 종류

• SHA-1
  • SHA-0을 변형한 함수
  • 264비트의 메시지로부터 160비트의 해시값을 만들어 내고, 입력 메시지는 512bit 패딩을 적용하는 방식 사용
  • 충돌쌍 문제 
    • 두 데이터에 대한 해시를 계산하였더니 같은 결과값이 도출되는 것
    • SHA 1사용이 지양되는 이유
• SHA-2
  • SHA-224, SHA-256, SHA-384, SHA-512 ...
  • 수학적으로 충돌 가능성은 존재하지만, 공학적으로는 그 가능성이 없다고 무방하다.
  • 해시값에 대해 계산된 해시를 비교함으로써 사람이 데이터의 무결성을 파악할 수 있다.

• SHA-3
  • SHA-2가 출력할 수 있는 메시지 해시값의 크기를 모두 출력
  • 충돌 저항성, 역상 저항성, 제2 역상 저항성을 모두 갖춤
  • SHA-2가 사용되는 곳에 SHA-3를 바로 적용 가능
  • 높은 수준의 병렬 구조를 가지고 메모리 접근해서 효율성이 아주 좋음
  • 단점으로 아직 SHA-22가 보편적으로 쓰인다.
    • SHA-3을 지원하는 소프트웨어나 하드웨어가 사실상 없음
    • SHA-1,2보다 느린 속도
    •  

4. 해시 문자 해싱 단계적 과정

 

1) 먼저 변환하고자 하는 문자열을 바이너리 형태로 변환

• 예를 들어 'a'는 '01000001'라는 기계어로 변환
• 그래서 'hello world'는 다음 과같이 88비트 바이너리 코드로 변환된다.

01101000 01100101 01101100 01101100 01101111 00100000 01110111 01101111
01110010 01101100 01100100

 

2) 바이너리 데이터는 512비트의 블락으로 나누고, 만약 512보다 작다면 패딩을 통해 사이즈를 늘려준다.

• 먼저 1을 붙여서 89비트를 만들어준다.
• 마지막 64비트를 제외하고 총 448비트까지 0으로 채워준다.

01101000 01100101 01101100 01101100 01101111 00100000 01110111 01101111
01110010 01101100 01100100 10000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000

 

3) 마지막 64비트는 원래 문자열 길이의 정수를 나타낸다.

• hello world는 88비트였으므로 정수 88을 비트화해서 1011000으로 바꿔서 넣어준다.

01101000 01100101 01101100 01101100 01101111 00100000 01110111 01101111
01110010 01101100 01100100 10000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 01011000

 

4) 앞서 512비트로 나눈 블락을 다시 32비트로 자른다.

5) 압축 함수 64회를 반복 수행한다.

6) 그리고 나서 블락 별로 해시값을 구하는데 첫번째 블락의 해시 결과가 두번째 블락의 입력값으로 사용되는 연결 로직을 가진다.

7)최종적으로 256비트의 해시값이 생성된다.

• 256비트는 32바이트 이다. 
• 이를 16진수로 표현하면 64자리의 16진수 문자열이 된다.

4. 참조

1. SHA : https://egg-stone.tistory.com/19

[DATABASE] SHA 해시 함수(단방향 알고리즘)

 

2. SHA-256 알고리즘 : https://losskatsu.github.io/blockchain/sha256/#4-sha-256-%EA%B3%BC%EC%A0%95

[블록체인] SHA-256 해시 알고리즘에 대해 알아보자