SHA-512 계산(Computation) [이론 2편]

처음 접속하신 분들은 1~2부를 먼저 읽고 오셔야 이해가 되세요!! 

해시 함수란? 1부 이해편 (http://blog.naver.com/tpinlab/10121477582)

해시 함수란? 2부 심화편 (http://blog.naver.com/tpinlab/10121517078)

해시 함수란? 3부 이론1편 (http://blog.naver.com/tpinlab/10121774937)

 

 

 

 

 

[SHA-2의 전체 흐름도]

 

 

위의 그림에는 1024bit 짜리 패딩된 메시지가 N개 있다.

각각의 패딩 메시지를 블록(Block)라고 표현할 수 있다.

첫번째 압축 함수(Compression Function)에는 맨 처음 블록 1024bit와

이론 1편에서 상수로 정의한 초기 해시 값(H0(0)~H7(0))을 입력 값으로 들어간다.

이 압축 함수를 통과하면 무조건 512bit가 출력된다.

 

이 출력은 다음 패딩 메시지가 존재할 경우 초기 해시 값 대신 사용된다.

꼬리에 꼬리를 무는 식이다.

 

 

 

 

 

 

[압축 함수의 내부]

 

 

이 압축 함수의 내부는 이렇게 생겼다.

위의 그림중 상단에 있는 A~H 블록은 초기 해시 값을 나타낸다.

512bit 초기 해시 값을 8개로 쪼개어 토막을 내었으니, A ~ H까지 각각 64bit 이다.

이렇게 나누어진 초기 해시 값들을 패딩 메시지의 64bit 만큼과 함께 각각의 라운드들을 통과 시킨다.

W0 ~ W79는 1024bit인 패딩 메시지를 다음 그림과 같이 80개로 나눈 것이다.

 

 

[패딩 메시지를 64bit 로 분할하는 함수]

 

 

SHA-512는 64bit 단위로 연산을 수행하도록 최적화된 해시 함수이다.

그림에는 0라운드 부터 79라운드 까지 표기되어 있지만, 편의상 80라운드를 통과한다고 말한다.

(0~79는 80개)

이 라운드는 또다시 내부 구조가 아래 그림과 같이 펼쳐진다.

 

 

 

 

[라운드의 내부 구조]

 

 

라운드의 내부구조는 좀 더 복잡하게 구성되어 있는데,

입력으로 들어온 A, B, C 블록을 출력 블록의 B, C, D 로 각각 넘겨주고,

마찬가지로 입력으로 들어온 E, F, G 블록을 출력 블록의 F, G, H 로 각각 넘겨준다.

출력 블록의 A와 E는 각각 연산 과정이 조금씩 다른 과정을 통과하는데

입력으로 들어온 D, H 블록을 이용하여 계산 된다.

 

위의 그림에서 중간 부분이 출력 블록 A, E의 연산을 나타내고 있다.

Majority 연산은 위의 그림 하단에 정의되어 있듯이 입력으로 받는 인자(Parameter)가 총 3개이고,

각각의 인자가 A, B, C라면 (A&B xor B&C xor C&A)를 연산하게 된다.

XOR은 틀리면 1, 같으면 0의 값이 반환되는 독특한 연산으로 연산 비용이 적어 자주 사용된다.

쉽게 말해서 1 xor 99를 계산한다면 1과 99는 서로 다르므로 결과는 1이 된다.

왼쪽 피연산자와 오른쪽 피연산자가 서로 같으면 0이 되겠지?

(XOR; Exclusive OR, 배타적 OR)

 

Rotate 연산은 입력으로 받는 인자가 1개 뿐이고 라운드의 입력으로 들어온 A 블록을 넘겨주는데,

내부에는 오른쪽 회전(Right-Rotation; 오른쪽 로테이션) 연산이 존재한다.

A 블록을 (28칸 오른쪽 회전 xor 34칸 오른쪽 회전 xor 39칸 오른쪽 회전) 을 연산한 후

그 결과가 반환된다.

 

이렇게 계산된 Majority와 Rotate 연산 결과를 각각 모듈로 덧셈(Modulo Plus) 연산을 한다.

모듈로 덧셈 연산의 결과는 무조건 2^64, 즉 64bit가 나와야 하므로 상위 자리 올림 등의 bit 는

잘려 나갈 수도 있다.

 

이렇게 나온 결과 값을 Mixer2의 Conditional과 Rotate 연산을 거친 결과 값과 또다시

모듈로 덧셈을 하여 출력 블록의 A로 내보낸다.

 

Mixer2의 Conditional 연산은 입력으로 받는 인자가 총 3개이고,

각각의 인자가 E, F, G라면 (E&F xor notE&G)를 연산하게 된다.

not 연산은 1이면 0, 0이면 1을 출력하는 입력과 정 반대의 출력을 내보내는 연산이다.

 

Rotate 연산은 Mixer1의 Rotate 연산과 동일하다.

이렇게 나온 Mixer1과 Mixer2의 결과를 서로 모듈로 덧셈하여 나온 값을 출력 블록의 A로 내보내고,

Mixer2의 결과와 입력 블록의 D를 서로 모듈로 덧셈하여 나온 값을 출력 블록의 E로 내보낸다.

 

여기까지가 한 개의 라운드가 실행하게 되는 과정의 설명이다.

이 과정을 총 80번 반복한 다음, 그 출력 블록을 라운드가 시작되기 전의 입력 블록과 각각

모듈로 덧셈을 진행하고 512bit의 출력을 내보낸다. 패딩 메시지 1개의 압축 함수의 연산이 끝났다.

 

이 512bit의 출력은 다음 패딩 메시지가 존재한다면 똑같은 과정을 또 반복해야 할 때

초기 해시 값 대신 사용되는 중요한 값이 된다.

 

 

다음 [부록편] 시간에는 해시 함수의 취약점에 대하여 알아본다.

 

 

 

 

[연재 목록]

해시 함수란? 1부 이해편 (http://blog.naver.com/tpinlab/10121477582)

해시 함수란? 2부 심화편 (http://blog.naver.com/tpinlab/10121517078)

해시 함수란? 3부 이론1편 (http://blog.naver.com/tpinlab/10121774937)

해시 함수란? 4부 이론2편 (http://blog.naver.com/tpinlab/10121820313)

해시 함수란? 5부 부록편 () 작성중..

 

 

 

 

 

[참고자료]

http://securitylab.ssu.ac.kr/

http://en.wikipedia.org/wiki/SHA-2

http://word.tta.or.kr/terms/termsView.jsp?gubun=1&terms_num=10477

 

 

 

 

 

 

 

 

 

출처 : http://blog.naver.com/tpinlab/10121774937