해시 함수 LSH의 전체 구조는 아래와 같다.
해시 함수 LSH 전체 구조
LSH는 입력 메시지에 대해 다음과 같은 세 단계를 거쳐 해시값을 출력한다.
초기화(Initialization): 입력 메시지를 메시지 블록 비트 길이의 배수가 되도록 패딩을 한 후, 이를 메시지 블록 단위로 분할한다. 그리고 연결 변수를
IV
{\displaystyle {\textsf {IV}}}
로 초기화한다.
압축(Compression): 32워드 배열 메시지 블록을 압축 함수의 입력으로 하여 얻은 출력값으로 연결 변수를 갱신하며, 이를 마지막 메시지 블록을 처리할 때까지 반복하여 메시지를 압축한다.
완료(Finalization): 압축 과정을 통해 연결 변수에 최종 저장된 값으로부터 n비트 길이의 해시 함수 출력값을 생성한다.
function 해시 함수 LSH
input: 메시지
m
{\displaystyle m}
output: 해시값
h
∈
{
0
,
1
}
n
{\displaystyle h\in \{0,1\}^{n}}
procedure
{\displaystyle \qquad }
m
p
←
pad
(
m
)
{\displaystyle m_{p}\leftarrow {\textrm {pad}}(m)}
;
{\displaystyle \qquad }
m
p
{\displaystyle m_{p}}
로부터 메시지 블록
(
M
(
0
)
,
M
(
1
)
,
⋯
,
M
(
t
−
1
)
)
{\displaystyle (M^{(0)},M^{(1)},\cdots ,M^{(t-1)})}
생성;
{\displaystyle \qquad }
CV
(
0
)
←
IV
{\displaystyle {\textsf {CV}}^{(0)}\leftarrow {\textsf {IV}}}
;
{\displaystyle \qquad }
for
i
=
0
{\displaystyle i=0}
to
(
t
−
1
)
{\displaystyle (t-1)}
do
{\displaystyle \qquad }
{\displaystyle \qquad }
CV
(
i
+
1
)
←
CF
(
CV
(
i
)
,
M
(
i
)
)
{\displaystyle {\textsf {CV}}^{(i+1)}\leftarrow {\textrm {CF}}({\textsf {CV}}^{(i)},M^{(i)})}
;
{\displaystyle \qquad }
end for
{\displaystyle \qquad }
h
←
FIN
n
(
CV
(
t
)
)
{\displaystyle h\leftarrow {\textrm {FIN}}_{n}({\textsf {CV}}^{(t)})}
;
{\displaystyle \qquad }
return
h
{\displaystyle h}
;
해시 함수 LSH의 규격은 다음 표와 같다.
해시 함수 LSH 규격
구분
출력 비트 길이 (
n
{\displaystyle n}
)
압축 함수의 단계 수 (
N
s
{\displaystyle N_{s}}
)
연결 변수 비트 길이
메시지 블록 비트 길이
워드 비트 길이 (
w
{\displaystyle w}
)
LSH-256-224
224
26
512
1024
32
LSH-256-256
256
LSH-512-224
224
28
1024
2048
64
LSH-512-256
256
LSH-512-384
384
LSH-512-512
512
해시 함수의 입력 메시지를
m
{\displaystyle m}
이라 하자. 먼저
m
{\displaystyle m}
은 덧붙이기(padding) 과정을 거친다. 덧붙이기 과정은
m
{\displaystyle m}
의 끝에 비트 ‘1’을 덧붙인 후, 전체 길이가
32
w
t
{\displaystyle 32wt}
비트가 될 때까지 비트 ‘0’을 덧붙인다. 여기에서
t
=
⌈
(
|
m
|
+
1
)
/
32
w
⌉
{\displaystyle t=\lceil (|m|+1)/32w\rceil }
이다.
덧붙이기를 마친 메시지를
m
p
=
m
0
‖
m
1
‖
…
‖
m
(
32
w
t
−
1
)
{\displaystyle m_{p}=m_{0}\|m_{1}\|\ldots \|m_{(32wt-1)}}
이라고 하자. 이때
m
p
{\displaystyle m_{p}}
는
4
w
t
{\displaystyle 4wt}
바이트 배열
m
a
=
(
m
[
0
]
,
…
,
m
[
4
w
t
−
1
]
)
{\displaystyle m_{a}=(m[0],\ldots ,m[4wt-1])}
로 볼 수 있다. 여기에서
m
[
k
]
=
m
8
k
‖
m
(
8
k
+
1
)
‖
…
‖
m
(
8
k
+
7
)
{\displaystyle m[k]=m_{8k}\|m_{(8k+1)}\|\ldots \|m_{(8k+7)}}
(
0
≤
k
≤
(
4
w
t
−
1
)
)
{\displaystyle (0\leq k\leq (4wt-1))}
이다. 바이트 배열
m
a
{\displaystyle m_{a}}
는 다음과 같이
32
t
{\displaystyle 32t}
워드 배열
M
=
(
M
[
0
]
,
…
,
M
[
32
t
−
1
]
)
{\displaystyle {\textsf {M}}=(M[0],\ldots ,M[32t-1])}
으로 변환할 수 있다.
M
[
s
]
←
m
[
w
s
/
8
+
(
w
/
8
−
1
)
]
‖
…
‖
m
[
w
s
/
8
+
1
]
‖
m
[
w
s
/
8
]
{\displaystyle M[s]\leftarrow m[ws/8+(w/8-1)]\|\ldots \|m[ws/8+1]\|m[ws/8]}
(
0
≤
s
≤
(
32
t
−
1
)
)
{\displaystyle (0\leq s\leq (32t-1))}
이어서 워드 배열
M
{\displaystyle {\textsf {M}}}
으로부터 다음과 같은 규칙에 따라
t
{\displaystyle t}
개 메시지 블록
M
(
0
)
{\displaystyle {\textsf {M}}^{(0)}}
,
M
(
1
)
{\displaystyle {\textsf {M}}^{(1)}}
, \ldots ,
M
(
t
−
1
)
{\displaystyle {\textsf {M}}^{(t-1)}}
을 구성할 수 있다.
M
(
i
)
←
(
M
[
32
i
]
,
M
[
32
i
+
1
]
,
…
,
M
[
32
i
+
31
]
)
{\displaystyle {\textsf {M}}^{(i)}\leftarrow (M[32i],M[32i+1],\ldots ,M[32i+31])}
(
0
≤
i
≤
(
t
−
1
)
)
{\displaystyle (0\leq i\leq (t-1))}
연결 변수
CV
(
0
)
{\displaystyle {\textsf {CV}}^{(0)}}
(
∈
W
16
)
{\displaystyle (\in {\mathcal {W}}^{16})}
는 초기값을 이용하여 다음과 같이 배열 색인별로 값을 할당하는 방식으로 초기화한다.
이때,
W
t
{\displaystyle {\mathcal {W}}^{t}}
는
t
≥
1
{\displaystyle t\geq 1}
일 때
t
{\displaystyle t}
개 워드 배열의 전체 집합을 나타낸다.
CV
(
0
)
[
l
]
←
IV
[
l
]
{\displaystyle {\textsf {CV}}^{(0)}[l]\leftarrow {\textsf {IV}}[l]}
(
0
≤
l
≤
15
)
{\displaystyle (0\leq l\leq 15)}
초기값은 다음과 같다.
모든 값은 16진수로 표현되어 있다.
LSH-256-224 초기값
IV
[
0
]
{\displaystyle {\textsf {IV}}[0]}
IV
[
1
]
{\displaystyle {\textsf {IV}}[1]}
IV
[
2
]
{\displaystyle {\textsf {IV}}[2]}
IV
[
3
]
{\displaystyle {\textsf {IV}}[3]}
IV
[
4
]
{\displaystyle {\textsf {IV}}[4]}
IV
[
5
]
{\displaystyle {\textsf {IV}}[5]}
IV
[
6
]
{\displaystyle {\textsf {IV}}[6]}
IV
[
7
]
{\displaystyle {\textsf {IV}}[7]}
068608D3
62D8F7A7
D76652AB
4C600A43
BDC40AA8
1ECA0B68
DA1A89BE
3147D354
IV
[
8
]
{\displaystyle {\textsf {IV}}[8]}
IV
[
9
]
{\displaystyle {\textsf {IV}}[9]}
IV
[
10
]
{\displaystyle {\textsf {IV}}[10]}
IV
[
11
]
{\displaystyle {\textsf {IV}}[11]}
IV
[
12
]
{\displaystyle {\textsf {IV}}[12]}
IV
[
13
]
{\displaystyle {\textsf {IV}}[13]}
IV
[
14
]
{\displaystyle {\textsf {IV}}[14]}
IV
[
15
]
{\displaystyle {\textsf {IV}}[15]}
707EB4F9
F65B3862
6B0B2ABE
56B8EC0A
CF237286
EE0D1727
33636595
8BB8D05F
LSH-256-256 초기값
IV
[
0
]
{\displaystyle {\textsf {IV}}[0]}
IV
[
1
]
{\displaystyle {\textsf {IV}}[1]}
IV
[
2
]
{\displaystyle {\textsf {IV}}[2]}
IV
[
3
]
{\displaystyle {\textsf {IV}}[3]}
IV
[
4
]
{\displaystyle {\textsf {IV}}[4]}
IV
[
5
]
{\displaystyle {\textsf {IV}}[5]}
IV
[
6
]
{\displaystyle {\textsf {IV}}[6]}
IV
[
7
]
{\displaystyle {\textsf {IV}}[7]}
46A10F1F
FDDCE486
B41443A8
198E6B9D
3304388D
B0F5A3C7
B36061C4
7ADBD553
IV
[
8
]
{\displaystyle {\textsf {IV}}[8]}
IV
[
9
]
{\displaystyle {\textsf {IV}}[9]}
IV
[
10
]
{\displaystyle {\textsf {IV}}[10]}
IV
[
11
]
{\displaystyle {\textsf {IV}}[11]}
IV
[
12
]
{\displaystyle {\textsf {IV}}[12]}
IV
[
13
]
{\displaystyle {\textsf {IV}}[13]}
IV
[
14
]
{\displaystyle {\textsf {IV}}[14]}
IV
[
15
]
{\displaystyle {\textsf {IV}}[15]}
105D5378
2F74DE54
5C2F2D95
F2553FBE
8051357A
138668C8
47AA4484
E01AFB41
LSH-512-224 초기값
IV
[
0
]
{\displaystyle {\textsf {IV}}[0]}
IV
[
1
]
{\displaystyle {\textsf {IV}}[1]}
IV
[
2
]
{\displaystyle {\textsf {IV}}[2]}
IV
[
3
]
{\displaystyle {\textsf {IV}}[3]}
0C401E9FE8813A55
4A5F446268FD3D35
FF13E452334F612A
F8227661037E354A
IV
[
4
]
{\displaystyle {\textsf {IV}}[4]}
IV
[
5
]
{\displaystyle {\textsf {IV}}[5]}
IV
[
6
]
{\displaystyle {\textsf {IV}}[6]}
IV
[
7
]
{\displaystyle {\textsf {IV}}[7]}
A5F223723C9CA29D
95D965A11AED3979
01E23835B9AB02CC
52D49CBAD5B30616
IV
[
8
]
{\displaystyle {\textsf {IV}}[8]}
IV
[
9
]
{\displaystyle {\textsf {IV}}[9]}
IV
[
10
]
{\displaystyle {\textsf {IV}}[10]}
IV
[
11
]
{\displaystyle {\textsf {IV}}[11]}
9E5C2027773F4ED3
66A5C8801925B701
22BBC85B4C6779D9
C13171A42C559C23
IV
[
12
]
{\displaystyle {\textsf {IV}}[12]}
IV
[
13
]
{\displaystyle {\textsf {IV}}[13]}
IV
[
14
]
{\displaystyle {\textsf {IV}}[14]}
IV
[
15
]
{\displaystyle {\textsf {IV}}[15]}
31E2B67D25BE3813
D522C4DEED8E4D83
A79F5509B43FBAFE
E00D2CD88B4B6C6A
LSH-512-256 초기값
IV
[
0
]
{\displaystyle {\textsf {IV}}[0]}
IV
[
1
]
{\displaystyle {\textsf {IV}}[1]}
IV
[
2
]
{\displaystyle {\textsf {IV}}[2]}
IV
[
3
]
{\displaystyle {\textsf {IV}}[3]}
6DC57C33DF989423
D8EA7F6E8342C199
76DF8356F8603AC4
40F1B44DE838223A
IV
[
4
]
{\displaystyle {\textsf {IV}}[4]}
IV
[
5
]
{\displaystyle {\textsf {IV}}[5]}
IV
[
6
]
{\displaystyle {\textsf {IV}}[6]}
IV
[
7
]
{\displaystyle {\textsf {IV}}[7]}
39FFE7CFC31484CD
39C4326CC5281548
8A2FF85A346045D8
FF202AA46DBDD61E
IV
[
8
]
{\displaystyle {\textsf {IV}}[8]}
IV
[
9
]
{\displaystyle {\textsf {IV}}[9]}
IV
[
10
]
{\displaystyle {\textsf {IV}}[10]}
IV
[
11
]
{\displaystyle {\textsf {IV}}[11]}
CF785B3CD5FCDB8B
1F0323B64A8150BF
FF75D972F29EA355
2E567F30BF1CA9E1
IV
[
12
]
{\displaystyle {\textsf {IV}}[12]}
IV
[
13
]
{\displaystyle {\textsf {IV}}[13]}
IV
[
14
]
{\displaystyle {\textsf {IV}}[14]}
IV
[
15
]
{\displaystyle {\textsf {IV}}[15]}
B596875BF8FF6DBA
FCCA39B089EF4615
ECFF4017D020B4B6
7E77384C772ED802
LSH-512-384 초기값
IV
[
0
]
{\displaystyle {\textsf {IV}}[0]}
IV
[
1
]
{\displaystyle {\textsf {IV}}[1]}
IV
[
2
]
{\displaystyle {\textsf {IV}}[2]}
IV
[
3
]
{\displaystyle {\textsf {IV}}[3]}
53156A66292808F6
B2C4F362B204C2BC
B84B7213BFA05C4E
976CEB7C1B299F73
IV
[
4
]
{\displaystyle {\textsf {IV}}[4]}
IV
[
5
]
{\displaystyle {\textsf {IV}}[5]}
IV
[
6
]
{\displaystyle {\textsf {IV}}[6]}
IV
[
7
]
{\displaystyle {\textsf {IV}}[7]}
DF0CC63C0570AE97
DA4441BAA486CE3F
6559F5D9B5F2ACC2
22DACF19B4B52A16
IV
[
8
]
{\displaystyle {\textsf {IV}}[8]}
IV
[
9
]
{\displaystyle {\textsf {IV}}[9]}
IV
[
10
]
{\displaystyle {\textsf {IV}}[10]}
IV
[
11
]
{\displaystyle {\textsf {IV}}[11]}
BBCDACEFDE80953A
C9891A2879725B3E
7C9FE6330237E440
A30BA550553F7431
IV
[
12
]
{\displaystyle {\textsf {IV}}[12]}
IV
[
13
]
{\displaystyle {\textsf {IV}}[13]}
IV
[
14
]
{\displaystyle {\textsf {IV}}[14]}
IV
[
15
]
{\displaystyle {\textsf {IV}}[15]}
BB08043FB34E3E30
A0DEC48D54618EAD
150317267464BC57
32D1501FDE63DC93
LSH-512-512 초기값
IV
[
0
]
{\displaystyle {\textsf {IV}}[0]}
IV
[
1
]
{\displaystyle {\textsf {IV}}[1]}
IV
[
2
]
{\displaystyle {\textsf {IV}}[2]}
IV
[
3
]
{\displaystyle {\textsf {IV}}[3]}
ADD50F3C7F07094E
E3F3CEE8F9418A4F
B527ECDE5B3D0AE9
2EF6DEC68076F501
IV
[
4
]
{\displaystyle {\textsf {IV}}[4]}
IV
[
5
]
{\displaystyle {\textsf {IV}}[5]}
IV
[
6
]
{\displaystyle {\textsf {IV}}[6]}
IV
[
7
]
{\displaystyle {\textsf {IV}}[7]}
8CB994CAE5ACA216
FBB9EAE4BBA48CC7
650A526174725FEA
1F9A61A73F8D8085
IV
[
8
]
{\displaystyle {\textsf {IV}}[8]}
IV
[
9
]
{\displaystyle {\textsf {IV}}[9]}
IV
[
10
]
{\displaystyle {\textsf {IV}}[10]}
IV
[
11
]
{\displaystyle {\textsf {IV}}[11]}
B6607378173B539B
1BC99853B0C0B9ED
DF727FC19B182D47
DBEF360CF893A457
IV
[
12
]
{\displaystyle {\textsf {IV}}[12]}
IV
[
13
]
{\displaystyle {\textsf {IV}}[13]}
IV
[
14
]
{\displaystyle {\textsf {IV}}[14]}
IV
[
15
]
{\displaystyle {\textsf {IV}}[15]}
4981F5E570147E80
D00C4490CA7D3E30
5D73940C0E4AE1EC
894085E2EDB2D819
초기화 단계에서 생성된
t
{\displaystyle t}
개의 메시지 블록은 압축 단계에서 순차적으로 압축 함수(compression function)
CF
:
W
16
×
W
32
→
W
16
{\displaystyle {\textrm {CF}}:{\mathcal {W}}^{16}\times {\mathcal {W}}^{32}\rightarrow {\mathcal {W}}^{16}}
의 입력값으로 사용된다.
압축 함수
CF
{\displaystyle {\textrm {CF}}}
는 연결 변수
CV
(
i
)
(
∈
W
16
)
{\displaystyle {\textsf {CV}}^{(i)}(\in {\mathcal {W}}^{16})}
와 메시지 블록
M
(
i
)
(
∈
W
32
)
{\displaystyle {\textsf {M}}^{(i)}(\in {\mathcal {W}}^{32})}
를 입력으로 받아 연결 변수
CV
(
i
+
1
)
(
∈
W
16
)
{\displaystyle {\textsf {CV}}^{(i+1)}(\in {\mathcal {W}}^{16})}
을 반환한다.
압축 함수는 다음 네 가지 함수로 구성된다.
메시지 확장 함수
MsgExp
:
W
32
→
W
16
(
N
s
+
1
)
{\displaystyle {\textrm {MsgExp}}:{\mathcal {W}}^{32}\rightarrow {\mathcal {W}}^{16(Ns+1)}}
메시지 덧셈 함수
MsgAdd
:
W
16
×
W
16
→
W
16
{\displaystyle {\textrm {MsgAdd}}:{\mathcal {W}}^{16}\times {\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}}
섞음 함수
Mix
j
:
W
16
→
W
16
{\displaystyle {\textrm {Mix}}_{j}:{\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}}
워드 단위 치환
WordPerm
:
W
16
→
W
16
{\displaystyle {\textrm {WordPerm}}:{\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}}
압축 함수의 전체 구조를 도시하면 다음 그림과 같다.
해시 함수 LSH 압축 함수
압축 함수 입력값 중 메시지 블록
M
(
i
)
{\displaystyle {\textsf {M}}^{(i)}}
는 메시지 확장 함수 MsgExp를 거쳐
(
N
s
+
1
)
{\displaystyle (N_{s}+1)}
개의 16워드 크기 데이터
M
j
(
i
)
{\displaystyle {\textsf {M}}_{j}^{(i)}}
(
0
≤
j
≤
N
s
)
{\displaystyle (0\leq j\leq N_{s})}
로 확장된다.
이어서 16워드 크기의 임시 변수
T
=
(
T
[
0
]
,
…
,
T
[
15
]
)
{\displaystyle {\textsf {T}}=(T[0],\ldots ,T[15])}
에
CV
(
i
)
{\displaystyle {\textsf {CV}}^{(i)}}
를 할당한 후, 순차적으로 단계 함수(step function)
Step
j
{\displaystyle {\textrm {Step}}_{j}}
를 통해 데이터
M
j
(
i
)
{\displaystyle {\textsf {M}}_{j}^{(i)}}
를 처리하면서
T
{\displaystyle {\textsf {T}}}
를 갱신한다.
단계 함수를 거쳐
T
{\displaystyle {\textsf {T}}}
에 저장된 값은 MsgAdd 함수를 통해 처리된 후
(
i
+
1
)
{\displaystyle (i+1)}
번 째 연결 변수
CV
(
i
+
1
)
{\displaystyle {\textsf {CV}}^{(i+1)}}
에 입력된다.
이러한 압축 함수 처리 절차는 다음과 같다.
압축 함수에서 순차적으로
M
j
(
i
)
{\displaystyle {\textsf {M}}_{j}^{(i)}}
를 처리하는 단계 함수
Step
j
:
W
16
×
W
16
→
W
16
{\displaystyle {\textrm {Step}}_{j}:{\mathcal {W}}^{16}\times {\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}}
는 다음과 같다.
Step
j
:=
WordPerm
∘
Mix
j
∘
MsgAdd
{\displaystyle {\textrm {Step}}_{j}:={\textrm {WordPerm}}\circ {\textrm {Mix}}_{j}\circ {\textrm {MsgAdd}}}
(
0
≤
j
≤
(
N
s
−
1
)
)
{\displaystyle (0\leq j\leq (N_{s}-1))}
단계 함수의 전체 구조는 다음 그림과 같다.
해시 함수 LSH의
j
{\displaystyle j}
번째 단계 함수
Step
j
{\displaystyle {\textrm {Step}}_{j}}
압축 함수에 입력된 메시지 블록
M
(
i
)
=
(
M
(
i
)
[
0
]
,
…
,
M
(
i
)
[
31
]
)
{\displaystyle {\textsf {M}}^{(i)}=(M^{(i)}[0],\ldots ,M^{(i)}[31])}
에 대해, 메시지 확장 함수 MsgExp는
(
N
s
+
1
)
{\displaystyle (N_{s}+1)}
개의 16워드 길이의 데이터
M
j
(
i
)
{\displaystyle {\textsf {M}}_{j}^{(i)}}
(
0
≤
j
≤
N
s
)
{\displaystyle (0\leq j\leq N_{s})}
를 생성한다.
생성 방법은 다음과 같다.
M
0
(
i
)
←
(
M
(
i
)
[
0
]
,
M
(
i
)
[
1
]
,
…
,
M
(
i
)
[
15
]
)
{\displaystyle {\textsf {M}}_{0}^{(i)}\leftarrow (M^{(i)}[0],M^{(i)}[1],\ldots ,M^{(i)}[15])}
M
1
(
i
)
←
(
M
(
i
)
[
16
]
,
M
(
i
)
[
17
]
,
…
,
M
(
i
)
[
31
]
)
{\displaystyle {\textsf {M}}_{1}^{(i)}\leftarrow (M^{(i)}[16],M^{(i)}[17],\ldots ,M^{(i)}[31])}
M
j
(
i
)
[
l
]
←
M
j
−
1
(
i
)
[
l
]
⊞
M
j
−
2
(
i
)
[
τ
(
l
)
]
{\displaystyle {\textsf {M}}_{j}^{(i)}[l]\leftarrow {\textsf {M}}_{j-1}^{(i)}[l]\boxplus {\textsf {M}}_{j-2}^{(i)}[\tau (l)]}
(
0
≤
l
≤
15
,
2
≤
j
≤
N
s
)
{\displaystyle (0\leq l\leq 15,\ 2\leq j\leq N_{s})}
함수
τ
{\displaystyle \tau }
는 다음과 같이 정의된
Z
16
{\displaystyle \mathbb {Z} _{16}}
상의 치환이다.
Z
16
{\displaystyle \mathbb {Z} _{16}}
상의 치환
τ
{\displaystyle \tau }
l
{\displaystyle l}
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
τ
(
l
)
{\displaystyle \tau (l)}
3
2
0
1
7
4
5
6
11
10
8
9
15
12
13
14
두 개의 16워드 길이의 변수
X
=
(
X
[
0
]
,
…
,
X
[
15
]
)
{\displaystyle {\textsf {X}}=(X[0],\ldots ,X[15])}
와
Y
=
(
Y
[
0
]
,
…
,
Y
[
15
]
)
{\displaystyle {\textsf {Y}}=(Y[0],\ldots ,Y[15])}
를 입력으로 받아 16워드 길이의 결과값을 출력하는 메시지 덧셈 함수
MsgAdd
:
W
16
×
W
16
→
W
16
{\displaystyle {\textrm {MsgAdd}}:{\mathcal {W}}^{16}\times {\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}}
는 다음과 같이 정의한다.
MsgAdd
(
X
,
Y
)
:=
(
X
[
0
]
⊕
Y
[
0
]
,
…
,
X
[
15
]
⊕
Y
[
15
]
)
{\displaystyle {\textrm {MsgAdd}}({\textsf {X}},{\textsf {Y}}):=(X[0]\oplus Y[0],\ldots ,X[15]\oplus Y[15])}
섞음 함수
Mix
j
:
W
16
→
W
16
{\displaystyle {\textrm {Mix}}_{j}:{\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}}
는 16워드 길이의 변수
T
=
(
T
[
0
]
,
…
,
T
[
15
]
)
{\displaystyle {\textsf {T}}=(T[0],\ldots ,T[15])}
를 입력으로 받아 두 개의 워드
T
[
l
]
{\displaystyle T[l]}
,
T
[
l
+
8
]
{\displaystyle T[l+8]}
(
0
≤
l
≤
7
)
{\displaystyle (0\leq l\leq 7)}
을 쌍으로 구성한 후 아래와 같이 각각을 섞어
T
{\displaystyle {\textsf {T}}}
를 갱신한다.
(
T
[
l
]
,
T
[
l
+
8
]
)
←
Mix
j
,
l
(
T
[
l
]
,
T
[
l
+
8
]
)
{\displaystyle (T[l],T[l+8])\leftarrow {\textrm {Mix}}_{j,l}(T[l],T[l+8])}
(
0
≤
l
≤
7
)
{\displaystyle (0\leq l\leq 7)}
여기에서
Mix
j
,
l
:
W
2
→
W
2
{\displaystyle {\textrm {Mix}}_{j,l}:{\mathcal {W}}^{2}\rightarrow {\mathcal {W}}^{2}}
은 두 개 워드
X
{\displaystyle X}
,
Y
{\displaystyle Y}
를 처리하는 부분 섞음 함수로 다음과 같다.
부분 섞음 함수
Mix
j
,
l
{\displaystyle {\textrm {Mix}}_{j,l}}
를 도식화하면 다음 그림과 같다.
해시 함수 LSH의 부분 섞음 함수
섞음 함수
Mix
j
,
l
{\displaystyle {\textrm {Mix}}_{j,l}}
에 사용되는 비트 순환량
α
j
{\displaystyle \alpha _{j}}
,
β
j
{\displaystyle \beta _{j}}
,
γ
l
{\displaystyle \gamma _{l}}
은 다음 표와 같다.
비트 순환량
α
j
{\displaystyle \alpha _{j}}
,
β
j
{\displaystyle \beta _{j}}
는 짝수 단계와 홀수 단계에서 다른 값이 적용된다.
비트 순환량
α
j
{\displaystyle \alpha _{j}}
,
β
j
{\displaystyle \beta _{j}}
,
γ
l
{\displaystyle \gamma _{l}}
w
{\displaystyle w}
j
{\displaystyle j}
α
j
{\displaystyle \alpha _{j}}
β
j
{\displaystyle \beta _{j}}
γ
0
{\displaystyle \gamma _{0}}
γ
1
{\displaystyle \gamma _{1}}
γ
2
{\displaystyle \gamma _{2}}
γ
3
{\displaystyle \gamma _{3}}
γ
4
{\displaystyle \gamma _{4}}
γ
5
{\displaystyle \gamma _{5}}
γ
6
{\displaystyle \gamma _{6}}
γ
7
{\displaystyle \gamma _{7}}
32
짝수
29
1
0
8
16
24
24
16
8
0
홀수
5
17
64
짝수
23
59
0
16
32
48
8
24
40
56
홀수
7
3
그리고 8워드 길이의 단계 상수
SC
j
=
(
S
C
j
[
0
]
,
…
,
S
C
j
[
7
]
)
{\displaystyle {\textsf {SC}}_{j}=(SC_{j}[0],\ldots ,SC_{j}[7])}
는 먼저
SC
0
{\displaystyle {\textsf {SC}}_{0}}
를 아래 표와 같이 정의한 후, 나머지
(
N
s
−
1
)
{\displaystyle (N_{s}-1)}
개의 상수
SC
j
{\displaystyle {\textsf {SC}}_{j}}
를
S
C
j
[
l
]
←
S
C
j
−
1
[
l
]
⊞
S
C
j
−
1
[
l
]
⋘
8
{\displaystyle SC_{j}[l]\leftarrow SC_{j-1}[l]\boxplus SC_{j-1}[l]^{\lll 8}}
(
0
≤
l
≤
7
,
1
≤
j
≤
(
N
s
−
1
)
)
{\displaystyle (0\leq l\leq 7,1\leq j\leq (N_{s}-1))}
와 같이 유도한다.
초기 단계 상수
w
=
32
{\displaystyle w=32}
w
=
64
{\displaystyle w=64}
S
C
0
[
0
]
{\displaystyle SC_{0}[0]}
917caf90
97884283c938982a
S
C
0
[
1
]
{\displaystyle SC_{0}[1]}
6c1b10a2
ba1fca93533e2355
S
C
0
[
2
]
{\displaystyle SC_{0}[2]}
6f352943
c519a2e87aeb1c03
S
C
0
[
3
]
{\displaystyle SC_{0}[3]}
cf778243
9a0fc95462af17b1
S
C
0
[
4
]
{\displaystyle SC_{0}[4]}
2ceb7472
fc3dda8ab019a82b
S
C
0
[
5
]
{\displaystyle SC_{0}[5]}
29e96ff2
02825d079a895407
S
C
0
[
6
]
{\displaystyle SC_{0}[6]}
8a9ba428
79f2d0a7ee06a6f7
S
C
0
[
7
]
{\displaystyle SC_{0}[7]}
2eeb2642
d76d15eed9fdf5fe
워드 단위 치환
WordPerm
:
W
16
→
W
16
{\displaystyle {\textrm {WordPerm}}:{\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}}
은 16워드 길이의 변수
X
=
(
X
[
0
]
,
…
,
X
[
15
]
)
{\displaystyle {\textsf {X}}=(X[0],\ldots ,X[15])}
를 입력으로 받아 16워드 길이의 결과값을 출력한다.
WordPerm
(
X
)
:=
(
X
[
σ
(
0
)
]
,
…
,
X
[
σ
(
15
)
]
)
{\displaystyle {\textrm {WordPerm}}({\textsf {X}}):=(X[\sigma (0)],\ldots ,X[\sigma (15)])}
이때, 사용되는 함수
σ
{\displaystyle \sigma }
는 다음 표와 같이 정의된
Z
16
{\displaystyle \mathbb {Z} _{16}}
상의 치환이다.
Z
16
{\displaystyle \mathbb {Z} _{16}}
상의 치환
σ
{\displaystyle \sigma }
l
{\displaystyle l}
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
σ
(
l
)
{\displaystyle \sigma (l)}
6
4
5
7
12
15
14
13
2
0
1
3
8
11
10
9
완료 함수
FIN
n
:
W
16
→
{
0
,
1
}
n
{\displaystyle {\textrm {FIN}}_{n}:{\mathcal {W}}^{16}\rightarrow \{0,1\}^{n}}
은 압축 과정의 결과로 생성된 마지막 연결 변수
CV
(
t
)
=
(
C
V
(
t
)
[
0
]
,
…
,
C
V
(
t
)
[
15
]
)
{\displaystyle {\textsf {CV}}^{(t)}=(CV^{(t)}[0],\ldots ,CV^{(t)}[15])}
에 적용되어
n
{\displaystyle n}
비트 길이의 해시값
h
{\displaystyle h}
를 생성한다.
H
=
(
H
[
0
]
,
…
,
H
[
7
]
)
{\displaystyle {\textsf {H}}=(H[0],\ldots ,H[7])}
를 8워드 길이의 변수,
h
b
=
(
h
b
[
0
]
,
…
,
h
b
[
w
−
1
]
)
{\displaystyle {\textsf {h}}_{\textsf {b}}=(h_{b}[0],\ldots ,h_{b}[w-1])}
는
w
{\displaystyle w}
바이트 길이의 변수라고 하면, 출력 함수
FIN
n
{\displaystyle {\textrm {FIN}}_{n}}
은 다음 절차를 수행한다.
H
[
l
]
←
C
V
(
t
)
[
l
]
⊕
C
V
(
t
)
[
l
+
8
]
{\displaystyle H[l]\leftarrow CV^{(t)}[l]\oplus CV^{(t)}[l+8]}
(
0
≤
l
≤
7
)
{\displaystyle (0\leq l\leq 7)}
h
b
[
s
]
←
H
[
⌊
8
s
/
w
⌋
]
[
7
:
0
]
⋙
(
8
s
mod
w
)
{\displaystyle h_{b}[s]\leftarrow H[\lfloor 8s/w\rfloor ]_{[7:0]}^{\ggg (8s\mod w)}}
(
0
≤
s
≤
(
w
−
1
)
)
{\displaystyle (0\leq s\leq (w-1))}
h
←
(
h
b
[
0
]
‖
…
‖
h
b
[
w
−
1
]
)
[
0
:
n
−
1
]
{\displaystyle h\leftarrow (h_{b}[0]\|\ldots \|h_{b}[w-1])_{[0:n-1]}}
이때, 임의의 워드
X
{\displaystyle X}
에 대해
r
≥
s
{\displaystyle r\geq s}
일 때,
X
[
r
:
s
]
{\displaystyle X_{[r:s]}}
는
X
{\displaystyle X}
의 비트열 표현에서 부분 비트열
x
r
‖
x
r
−
1
‖
…
‖
x
s
{\displaystyle x_{r}\|x_{r-1}\|\ldots \|x_{s}}
를 나타낸다.
그리고 임의의 비트열
x
{\displaystyle x}
에 대해
r
≤
s
{\displaystyle r\leq s}
일 때,
x
[
r
:
s
]
{\displaystyle x_{[r:s]}}
는
x
{\displaystyle x}
의 부분 비트열
x
r
‖
x
r
+
1
‖
…
‖
x
s
{\displaystyle x_{r}\|x_{r+1}\|\ldots \|x_{s}}
를 나타낸다.