Bitcoin and Cryptocurrency Technologies와 수업 내용을 참고하여 포스팅.

---

Collision‐resistance

충돌은 다른 input이 같은 output을 가질 때 발생한다.

예를 들어, One-way 해시 함수에서

x = “Viva”, y = “Vegas”일 때 H(x) = H(y) = 2로 충돌이 일어난다.

해시 함수 H가 x!=y이고 H(x)=H(y)인 두 값 x,y를 찾는 것이 실현 불가능할때,

H를 Collision‐resistance라고 한다.

비록 H가 Collision-resistance라고 해도, input이 output보다 크기 때문에 충돌은 피할 수 없다.

|M| » |T|인 해시 함수 H: M →T 가 있다.

H 의 충돌 예시로 다음을 만족하는 m0,m1 ∈ M의 쌍이 있다 가정한다.

H(m0) = H(m1) and m 0 ≠ m 1

H는 같은 해시 출략값을 가질 eff(efficient)가 neg(negligible)하다면 collision resistant이다.

일방향함수(One-way function)

일방향함수는 계산하기는 쉽지만 역을 구하는 것은 어려운 함수이다.

M이 주어진다면 해시 함수를 계산하는 것은 쉽다.

하지만 결과값인 h가 주어졌을 때, H(M) = h인 M의 값을 찾는 것은 어렵다.

마찬가지로, 주어진 M1으로 H(M1) = H(M2)인 M2의 값을 찾는 것 또한 어렵다.

만약 H가 일방향함수가 아니라면 Collision-resistance가 아니다.

H가 Collision-resistance라면 H는 일방향함수이다.

---

Secure Hash Algorithm

SHA

1993년부터 미국 NSA가 제작하고 미국 국립표준기술연구소(NIST)에서 표준으로 제작한 해시 암호 알고리즘이다. 1993년 SHA-0을 시작으로, 현재 최신 버전은 2001년 방식이 나온 SHA-2을 사용 중이고, 2012년 10월에 SHA-3이 정식 발표되었다.

Generic attack on C.R. functions

**

M

» 2^n인 해시 함수 **H: M → {0,1}^n의 경우를 생각해보자.

이 함수의 충돌을 찾기 위해선 Generic alg의 시간 복잡도는 O(2^(n/2))다.

SHA-256은 output이 256bit이므로 O(2^128)으로 eff가 neg하므로 collision-resistance이다.

The birthday paradox

생일 문제

사람이 임의로 모였을 때 그 중에 생일이 같은 두 명이 존재할 확률을 구하는 문제이다. 생일의 가능한 가짓수는 365개(2월 29일을 고려할 경우 366개)이므로 366명 이상의 사람이 모인다면 비둘기집 원리에 따라 생일이 같은 두 명이 반드시 존재하며, 23명 이상이 모인다면 그 중 두 명이 생일이 같은 확률은 1/2를 넘는다.

2^160에서 2^80개를 뽑으면 같은 확률이 1/2를 넘는다.

이것이 Bitcoin에서 SHA-256을 채택한 이유이다.