LSH(해시 함수)

LSH는 PC, 스마트기기 등 범용 소프트웨어 환경에서 무결성을 제공하기 위해 2014년 우리나라가 설계한 암호해시함수다.^[1] LSH는 한국암호화모듈검증프로그램(KCMVP)이 승인한 암호 알고리즘 중 하나이다. 그리고 대한민국의 국가표준(KS X 3262)이다.

사양

해시함수 LSH의 전체적인 구조는 다음 그림과 같다.

해시함수 LSH는 0이 1인 패딩으로 광파이프 머클담그리드 구조를 갖췄다. LSH의 메시지 해싱 프로세스는 다음의 3단계로 구성된다.

1. 초기화:
   • 지정된 비트 문자열 메시지의 01 패딩.
   • 패딩된 비트 문자열 메시지에서 32단어 배열 메시지 블록으로 변환.
   • 초기화 벡터를 사용한 체인 변수 초기화.
2. 압축:
   • 메시지 블록을 사용한 압축 함수를 반복하여 체인 변수 업데이트.
3. 최종화:
   • 최종 체인 변수에서 $n{\displaystyle }$ ${\displaystyle n$} -bit$$ 해시 값 생성.

함수 해시 함수 LSH 입력: 비트 문자열 $메시지{\displaystyle }$ m ${\displaystyle m}$ 출력: 해시 값 $h{\displaystyle \in \{0}$, ${\displaystyle 1}$ ${\displaystyle {}^{}}$ ${\displaystyle n^{}}$ ${\$ 절차 ${\displaystyle }$$m{\displaystyle }$$${\$displaystyle \qquad$} 원제로$$ 패딩(m ${\displaystyle m}$ ${\displaystyle \qquad }$Generation of ${\displaystyle t}$ message blocks ${\displaystyle \{{\textsf {M}}^{(i)}\}_{i=0}^{t-1}}$, where ${\displaystyle t={\Big \lceil }{\frac { m +1}{32w}}{\Big \rceil }}$ from the padded bit string $\displaystyle \qquad }$${\displaystyle {\textsf {CV}^{(0)\왼쪽 화살표 {\textsf {}IV}}$ $\displaystyle \qquad }$을 위해 ${\displaystyle i=0}$ 로 ${\displaystyle (t-1)}$ 하다 $\displaystyle \qquad }$$\displaystyle \qquad }$${\displaystyle {\textsf {CV}^{(i+1)}\좌측 화살표 {\textrum {CF}{\textsf {CV}^{(i)},{\textsf {M}^{{{{}}}}}}}$ $\displaystyle \qquad }$을 위해 끝나다. $\displaystyle \qquad }$${\displaystyle h\leftarrow {\textrm {FIN}_{n}({\textsf {CV}^{(t)}}}$ $\displaystyle \qquad }$돌아오다 $(\displaystyle h}$

해시함수 LSH의 사양은 다음과 같다.

해시함수 LSH 사양

알고리즘.	다이제스트 크기(비트)(${\displaystyle }$ ${\displaystyle$ n$\})$	스텝 함수 수(${\displaystyle N_{}}$ s ${\$	체인 변수 크기(비트)	메시지 블록 크기(비트)	단어 크기(비트)(${\displaystyle }$ ${\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 }$ ${\displaystyle m}$을(를) 지정된 비트 문자열 메시지로 설정하십시오$$. The given ${\displaystyle m}$ is padded by one-zeros, i.e., the bit ‘1’ is appended to the end of ${\displaystyle m}$, and the bit ‘0’s are appended until a bit length of a padded message is ${\displaystyle 32wt}$, where ${\displaystyle t=\lceil ( m +1)/32w\rceil }$ and ${\displaystyle \lceil x}$${\displaystyle ▼}$ ${\displaystyle \lceil$ x$\rceil }$은(는) $x{\displaystyle }$ ${\displaystyle$ x$}$ 이상 최소 정수임$.$

let $m{\displaystyle {}_{}}$ ${\displaystyle p_{}}$= ${\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\displaystyle {}_{}}$… ${\displaystyle \Vert }$ ${\displaystyle {}_{}}$( ${\displaystyle {32}_{}}$ w ${\displaystyle t_{}}$- $){\$ ${\displaystyle \mathrm{m\_}}$${p}=m_{0}\m_{1}\ldots$\$\$$m_{{{{$$n1}}}}}}}}}}}}{\$$displaystystylem m$$$-bit$$ string$$. Then ${\displaystyle m_{p}}$ is considered as a ${\displaystyle 4wt}$-byte array ${\displaystyle m_{a}=(m[0],\ldots ,m[4wt-1])}$, where ${\displaystyle m[k]=m_{8k}\ m_{(8k+1)}\ \ldots \ m_{(8k+7)}}$ for 모두 $0{\displaystyle \mathrm{}}$ ${\displaystyle \le }$ ${\displaystyle k}$ ${\displaystyle \le }$( 4 ${\displaystyle w}$ ${\displaystyle t}$- ${\displaystyle 1}$) ${\displaystyle$ 0$\leq k\leq (4wt-1$ $4{\displaystyle \mathrm{}}$ ${\displaystyle w}$ ${\displaystyle t}$ ${\displaystyle 4wt}$ -byt$$ 어레이 $m{\displaystyle {}_{}}$ ${\displaystyle a_{}}$ ${\$는 다음과 같이$$ ${\displaystyle \mathrm{32<img\; alt="m\_\{a\}"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/aefb2f5b0650af85e06c339f57a7f506978824a1"\; style="vertical-align:\; -0.671ex;\; width:3.142ex;\; height:2.009ex;"\; papago-attr-id="73">}}$ ${\displaystyle t}$ ${\displaystyle$32t$$$}$ $-word{\displaystyle }$ $어레이$M ${\displaystyle =}$ (${\displaystyle M}$ [ ${\displaystyle 0}$ ,${\displaystyle }$,$M$ [$32$ ${\displaystyle \mathrm{t}}$ - 1$$로$변환$된다.

${\displaystyle M[s]\왼쪽 화살표 m[ws/8+(w/8-1)]\ \ldots \m[ws/8+1]\m[ws/8]}}$ ${\displaystyle(0\leq s\leq(32t-1)}$

word array $M{\displaystyle }$ ${\$에서 다음과 같이$$ $t{\displaystyle }$ ${\displaystyle$ t$}$ 32단어$$ 어레이 메시지 블록${\displaystyle }${${\displaystyle {}^{}}$(${\displaystyle i^{}}$ ${\displaystyle {)}^{}}$ ${\displaystyle {\}}_{}^{}}$ = ${\displaystyle 0_{}^{}}$- ${\displaystyle 1_{}^{}}$ ${\$을 정의한다$.$

${\displaystyle {\textsf{M}^{(i)}\왼쪽 화살표(M[32i],M[32i+1],\ldots,M[32i+31])}$ ${\displaystyle(0\leq i\leq (t-1)}$

16단어 어레이 체인 변수 ${\displaystyle {\mathrm{CV}}^{}}$( 0${\displaystyle {}^{}}$) ${\${CV$}^{(0)}}$ 초기화 벡터 ${\displaystyle \mathsf{\text{IV}}}$ ${\$ {\textsf ${}}$에 초기화됨$$$IV}}$.

${\displaystyle {\textsf {CV}^{(0)}[l]\왼쪽 화살표 {\textsf {}IV}[l]}$ ${\displaystyle(0\leq l\leq 15)}$

초기화 벡터 ${\displaystyle \mathsf{\text{IV}}}$ ${\${$IV}}$은(는) 다음과 같다. 다음 표에서 모든 값은 16진수 형식으로 표현된다.

LSH-256-224 초기화 벡터

$디스플레이 스타일(displaystyle {\putf {IV}[0]}$	$디스플레이 스타일(displaystyle {\putf {IV}[1]}$	$디스플레이 스타일(displaystyle {\putf {IV}[2]}$	$디스플레이 스타일(displaystyle {\putf {IV}[3]}$	$디스플레이 스타일(displaystyle {\putf {IV}[4]}$	$디스플레이 스타일(displaystyle {\putf {IV}[5]}$	$디스플레이 스타일(displaystyle {\putf {IV}[6]}$	$디스플레이 스타일(displaystyle {\putf {IV}[7]}$
068608D3	62D8F7A7	D76652AB	4C600A43	BDC40AA8	1ECA0B68	DA1A89BE	3147D354
$디스플레이 스타일(displaystyle {\putf {IV}[8]}$	$디스플레이 스타일(displaystyle {\putf {IV}[9]}$	$디스플레이 스타일(displaystyle {\putf {IV}[10]}$	$디스플레이 스타일(displaystyle {\putf {IV}[11]}$	$디스플레이 스타일(displaystyle {\putf {IV}[12]}$	$디스플레이 스타일(displaystyle {\putf {IV}[13]}$	$디스플레이 스타일(displaystyle {\putf {IV}[14]}$	$디스플레이 스타일(displaystyle {\putf {IV}[15]}$
707EB4F9	F65B3862	6B0B2ABE	56B8EC0A	CF237286	EE0D1727	33636595	8BB8D05F

LSH-256-256 초기화 벡터

$디스플레이 스타일(displaystyle {\putf {IV}[0]}$	$디스플레이 스타일(displaystyle {\putf {IV}[1]}$	$디스플레이 스타일(displaystyle {\putf {IV}[2]}$	$디스플레이 스타일(displaystyle {\putf {IV}[3]}$	$디스플레이 스타일(displaystyle {\putf {IV}[4]}$	$디스플레이 스타일(displaystyle {\putf {IV}[5]}$	$디스플레이 스타일(displaystyle {\putf {IV}[6]}$	$디스플레이 스타일(displaystyle {\putf {IV}[7]}$
46A10F1F	FDDCE486	B41443A8	198E6B9D	3304388D	B0F5A3C7	B36061C4	7ADBD553
$디스플레이 스타일(displaystyle {\putf {IV}[8]}$	$디스플레이 스타일(displaystyle {\putf {IV}[9]}$	$디스플레이 스타일(displaystyle {\putf {IV}[10]}$	$디스플레이 스타일(displaystyle {\putf {IV}[11]}$	$디스플레이 스타일(displaystyle {\putf {IV}[12]}$	$디스플레이 스타일(displaystyle {\putf {IV}[13]}$	$디스플레이 스타일(displaystyle {\putf {IV}[14]}$	$디스플레이 스타일(displaystyle {\putf {IV}[15]}$
105D5378	2F74DE54	5C2F2D95	F2553FBE	8051357A	138668C8	47AA4484	E01AFB41

LSH-512-224 초기화 벡터

$디스플레이 스타일(displaystyle {\putf {IV}[0]}$	$디스플레이 스타일(displaystyle {\putf {IV}[1]}$	$디스플레이 스타일(displaystyle {\putf {IV}[2]}$	$디스플레이 스타일(displaystyle {\putf {IV}[3]}$
0C401E9FE8813A55	4A5F446268FD3D35	FF13E452334F612A	F8227661037E354a
$디스플레이 스타일(displaystyle {\putf {IV}[4]}$	$디스플레이 스타일(displaystyle {\putf {IV}[5]}$	$디스플레이 스타일(displaystyle {\putf {IV}[6]}$	$디스플레이 스타일(displaystyle {\putf {IV}[7]}$
A5F223723C9CA29D	95D965A11AED3979	01E23835B9AB02CC	52D49CBAD5B30616
$디스플레이 스타일(displaystyle {\putf {IV}[8]}$	$디스플레이 스타일(displaystyle {\putf {IV}[9]}$	$디스플레이 스타일(displaystyle {\putf {IV}[10]}$	$디스플레이 스타일(displaystyle {\putf {IV}[11]}$
9E5C2027773F4ED3	66A5C8801925B701	22BBC85B4C6779D9	C13171A42C559C23
$디스플레이 스타일(displaystyle {\putf {IV}[12]}$	$디스플레이 스타일(displaystyle {\putf {IV}[13]}$	$디스플레이 스타일(displaystyle {\putf {IV}[14]}$	$디스플레이 스타일(displaystyle {\putf {IV}[15]}$
31E2B67D25BE3813	D522C4DEED8E4D83	A79F5509B43FBAFE	E00D2CD88B4B6C6a

LSH-512-256 초기화 벡터

$디스플레이 스타일(displaystyle {\putf {IV}[0]}$	$디스플레이 스타일(displaystyle {\putf {IV}[1]}$	$디스플레이 스타일(displaystyle {\putf {IV}[2]}$	$디스플레이 스타일(displaystyle {\putf {IV}[3]}$
6DC57C33DF989423	D8EA7F6E8342C199	76DF8356F8603AC4	40F1B44DE838223a
$디스플레이 스타일(displaystyle {\putf {IV}[4]}$	$디스플레이 스타일(displaystyle {\putf {IV}[5]}$	$디스플레이 스타일(displaystyle {\putf {IV}[6]}$	$디스플레이 스타일(displaystyle {\putf {IV}[7]}$
39FE7CFC31484CD	39C4326CC5281548	8A2FF85A346045D8	FF202AA46DBDD61E
$디스플레이 스타일(displaystyle {\putf {IV}[8]}$	$디스플레이 스타일(displaystyle {\putf {IV}[9]}$	$디스플레이 스타일(displaystyle {\putf {IV}[10]}$	$디스플레이 스타일(displaystyle {\putf {IV}[11]}$
CF785B3CD5FCDB8B	1F0323B64A8150BF	FF75D972F29EA355	2E567F30BF1CA9E1
$디스플레이 스타일(displaystyle {\putf {IV}[12]}$	$디스플레이 스타일(displaystyle {\putf {IV}[13]}$	$디스플레이 스타일(displaystyle {\putf {IV}[14]}$	$디스플레이 스타일(displaystyle {\putf {IV}[15]}$
B596875BF8FF6DBA	FCA39B089EF4615	ECFF4017D020B4B6	7E77384C772ED802

LSH-512-384 초기화 벡터

$디스플레이 스타일(displaystyle {\putf {IV}[0]}$	$디스플레이 스타일(displaystyle {\putf {IV}[1]}$	$디스플레이 스타일(displaystyle {\putf {IV}[2]}$	$디스플레이 스타일(displaystyle {\putf {IV}[3]}$
53156A66292808F6	B2C4F362B204C2기원전	B84B7213BFA05C4E	976CEB7C1B299F73
$디스플레이 스타일(displaystyle {\putf {IV}[4]}$	$디스플레이 스타일(displaystyle {\putf {IV}[5]}$	$디스플레이 스타일(displaystyle {\putf {IV}[6]}$	$디스플레이 스타일(displaystyle {\putf {IV}[7]}$
DF0CC63C0570AE97	DA4441BAA486CE3f	6559F5D9B5F2ACC2	22DACF19B4B52A16
$디스플레이 스타일(displaystyle {\putf {IV}[8]}$	$디스플레이 스타일(displaystyle {\putf {IV}[9]}$	$디스플레이 스타일(displaystyle {\putf {IV}[10]}$	$디스플레이 스타일(displaystyle {\putf {IV}[11]}$
BBCDACEFDE80953a	C9891A2879725B3e	7C9FE6330237E440	A30BA550553F7431
$디스플레이 스타일(displaystyle {\putf {IV}[12]}$	$디스플레이 스타일(displaystyle {\putf {IV}[13]}$	$디스플레이 스타일(displaystyle {\putf {IV}[14]}$	$디스플레이 스타일(displaystyle {\putf {IV}[15]}$
BB08043FB34E3E30	A0DEC48D54618EAD	150317267464BC57	32D1501FDE63DC93

LSH-512-512 초기화 벡터

$디스플레이 스타일(displaystyle {\putf {IV}[0]}$	$디스플레이 스타일(displaystyle {\putf {IV}[1]}$	$디스플레이 스타일(displaystyle {\putf {IV}[2]}$	$디스플레이 스타일(displaystyle {\putf {IV}[3]}$
ADD50F3C7F07094E	E3F3CEE8F9418A4f	B527ECDE5B3D0AE9	2EF6DEC68076F501
$디스플레이 스타일(displaystyle {\putf {IV}[4]}$	$디스플레이 스타일(displaystyle {\putf {IV}[5]}$	$디스플레이 스타일(displaystyle {\putf {IV}[6]}$	$디스플레이 스타일(displaystyle {\putf {IV}[7]}$
8CB994CAE5ACA216	FBB9EAE4BBA48CC7	650A526174725FEA	1F9A61A73F8D8085
$디스플레이 스타일(displaystyle {\putf {IV}[8]}$	$디스플레이 스타일(displaystyle {\putf {IV}[9]}$	$디스플레이 스타일(displaystyle {\putf {IV}[10]}$	$디스플레이 스타일(displaystyle {\putf {IV}[11]}$
B6607378173B539b	1BC99853B0C0B9ED	DF727FC19B182D47	DBEF360CF893A457
$디스플레이 스타일(displaystyle {\putf {IV}[12]}$	$디스플레이 스타일(displaystyle {\putf {IV}[13]}$	$디스플레이 스타일(displaystyle {\putf {IV}[14]}$	$디스플레이 스타일(displaystyle {\putf {IV}[15]}$
4981F5E570147E80	D00C4490CA7D3E30	5D73940C0E4AE1EC	894085E2EDB2D819

압축

$이{\displaystyle }$ 단계에서는 초기화 단계의 $메시지$ m ${\displaystyle m}$에서 생성되는 ${\displaystyle {\mathrm{t}}_{}^{}}$ ${\displaystyle {}^{}{}_{}^{}}$displaystyle$\{\textsf$ {{$M}^{{\textsf{M}}\}}_{i=0}^{t-1}$의 32단어$$ 어레이 메시지 블록을 압축함수의 반복으로 압축한다$.$ The compression function ${\displaystyle {\textrm {CF}}:{\mathcal {W}}^{16}\times {\mathcal {W}}^{32}\rightarrow {\mathcal {W}}^{16}}$ has two inputs; the ${\displaystyle i}$-th 16-word chaining variable ${\displaystyle {\textsf {CV}}^{(i)}}$ and the ${$$\displaystyle i}$-th 32-word message block ${\displaystyle {\textsf {M}}^{(i)}}$. And it returns the ${\displaystyle (i+1)}$-th 16-word chaining variable ${\displaystyle {\textsf {CV}}^{(i+1)}}$. Here and subsequently, ${\displaystyle {\mathcal {W}}^{t}}$ denotes th$e{\displaystyle }$ t ${\displaystyle \ge }$ 1 ${\displaystyle t\geq 1}$에 대한 모든 t ${\displaystyle$ t$}$ -word$$ 배열 집합$.$

압축함수에 사용되는 기능은 다음과 같다.

• 메시지 확장 함수 ${\displaystyle \text{MsgExp}}$ :${\displaystyle }$W ${\displaystyle {32}^{}}$→ W ${\displaystyle {16}^{}}$ ${\displaystyle {(\mathrm{Ns}}^{}}$+ 1${\displaystyle {}^{}}$) ${\$ {$W}^{32}\오른쪽$ 화살표 ${\mathcal {{W}^{16(Ns+1)}}}}}}}}}}}$
• 메시지 추가 함수 ${\displaystyle \text{MsgAdd}}$: W ${\displaystyle {16}^{}}$ ${\displaystyle {}^{}}$ W ${\displaystyle {16}^{}}$→ W ${\displaystyle {16}^{}}$ ${\${\$MsgAdd}},$ {\$mathcal{W}^{16}\time {\mathcal{W}}\mathcal {W}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}$
• ${\displaystyle {\text{혼합}}_{}}$ 함수 ${\displaystyle {믹스}_{}}$ j${\displaystyle {}_{}}$: W ${\displaystyle {16}^{}}$→ W ${\displaystyle {16}^{}}$ ${\$ {$Mix}_{j}:$${\mathcal{W}^{16}\오른쪽 화살표 {\mathcal{W}^{16}}}}$
• Word-permution 함수 ${\displaystyle \text{WordPerm}}$: W ${\displaystyle {16}^{}}$→ ${\displaystyle {\mathcal{}}^{}}$ ${\displaystyle {16}^{}}$ ${\$${\mathcal{W}^{16}\오른쪽 화살표 {\mathcal{W}^{16}}}}$

압축함수의 전체적인 구조는 다음 그림과 같다.

In a compression function, the message expansion function ${\displaystyle {\textrm {MsgExp}}}$ generates ${\displaystyle (N_{s}+1)}$ 16-word array sub-messages ${\displaystyle \{{\textsf {M}}_{j}^{(i)}\}_{j=0}^{N_{s}}}$ from given ${\displa$$ystyle {\textsf {M}}^{(i)}}$. Let ${\displaystyle {\textsf {T}}=(T[0],\ldots ,T[15])}$ be a temporary 16-word array set to the ${\displaystyle i}$-th chaining variable ${\displaystyle {\textsf {CV}}^{(i)}}$. The ${\displaystyle j}$-th step function ${\displaystyle {\textrm {Step}}_{j}}$ having two inputs ${\displaystyle {\textsf {T}}}$ and ${\displaystyle {\textsf {M}}_{j}^{(i)}}$ updates ${\displaystyle {\textsf {T}}}$, i.e., ${\displaystyle \mathsf{\text{T}}\leftarrow {\text{Step}}_j(\mathsf{\text{T}},{\mathsf{\text{M}}}_{}^{}}$${\displaystyle {\textsf {T}}\leftarrow {\textrm {Step}}_{j}\left({\textsf {T}},{\textsf {M}}_{j}^{(i)}\right)}$. All step functions are proceeded in order ${\displaystyle j=0,\ldots ,N_{s}-1}$. Then one more ${\displaystyle {\textrm {MsgAdd}}}$ operation by ${\displaystyle {\mathsf{\text{M}}}_{N_s}^{(i}}$${\displaystyle {\textsf {M}}_{N_{s}}^{(i)}}$ is proceeded, and the ${\displaystyle (i+1)}$-th chaining variable ${\displaystyle {\textsf {CV}}^{(i+1)}}$ is set to ${\displaystyle {\textsf {T}}}$. The process of a compression function in detail is as follows.

함수 압축 함수 ${\displaystyle \text{CF}}$ ${\$ input: The ${\displaystyle i}$-th chaining variable ${\displaystyle {\textsf {CV}}^{(i)}\in {\mathcal {W}}^{16}}$ and the ${\displaystyle i}$-th message block ${\displaystyle {\textsf {M}}^{(i)}\in {\mathcal {W}}^{32}}$ 출력:${\displaystyle }$(${\displaystyle i}$+ ${\displaystyle 1}$) ${\displaystyle (i+1)}$ -th$$ chaining 변수 ${\displaystyle {\mathsf{\text{CV}}}^{}}$ ${\displaystyle {(}^{\mathrm{i}}}$+ 1${\displaystyle {}^{}}$) ${\displaystyle {}^{}}$ ${\displaystyle {\mathcal{}}^{}}$ ${\displaystyle {16}^{}}$ ${\$CV}^{($i+1)\in {\mathcal$ {$W}^{16}}$ 절차 $\displaystyle \qquad }$${\displaystyle \{\textsf {M}_{j}^{{{j}^{{n_}\{j=0}^{{n_}}}}\좌측 화살표 {\textrm {MsgExp}}\좌측({\textsf {M}}}^{{m}}\오른쪽)}$ $\displaystyle \qquad }$${\displaystyle {\textsf {T}\왼쪽 화살표 {\textsf {CV}^{(i)}}}$ $\displaystyle \qquad }$을 위해 ${\displaystyle j=0}$ 로 ${\displaystyle(N_{s}-1)}$ 하다 $\displaystyle \qquad }$$\displaystyle \qquad }$${\displaystyle {\textsf {T}\왼쪽 화살표 {Step}_{j}\왼쪽({\textsf {T},{\textsf {M}_{j}^{j}^{i}\오른쪽)}}$ $\displaystyle \qquad }$을 위해 끝나다. $\displaystyle \qquad }$${\displaystyle {\textsf {CV}^{(i+1)}\좌측 화살표 {\textrm {MsgAdd}}\좌측({\textsf {T},{\textsf {M}_{N_{s}^{{i)}\우측)}$ $\displaystyle \qquad }$돌아오다 ${\displaystyle {\textsf {CV}^{(i+1)}}}}$

여기에 $j{\displaystyle }$ ${\displaystyle j}$ -th$$ 번째 단계 함수 ${\displaystyle {\text{Step}}_{}}$ ${\displaystyle j_{}}$: ${\displaystyle {\mathcal{}}^{}}$ ${\displaystyle {16}^{}}$ ${\displaystyle {}^{}}$ W ${\displaystyle {16}^{}}$→ ${\displaystyle {\mathcal{}}^{}}$ ${\displaystyle {16}^{}}$ ${\$${\mathcal{W}^{16}\time {\mathcal{W}^{16}\오른쪽$ 화살표 ${\mathcal{W}^{16}}}$는 다음과 같다.

${\displaystyle {\textrm {Step}_{j}:={\textrm {WordPerm}\circle {\textrm {Mix}_{j}\circle {\textrm {MsgAdd}}}}}$ ${\displaystyle (0\leq j\leq (N_{s}-1)}$

다음 그림은 압축함수의$$ $j{\displaystyle }$ ${\displaystyle j}$ -step$$ 함수 ${\displaystyle {Step}_{}}$ j ${\$을(를) 보여준다.

메시지 확장 함수 MsgExp

$M{\displaystyle {}^{}}$( ${\displaystyle i^{}}$)${\displaystyle {}^{}}$=${\displaystyle }$( ${\displaystyle \mathrm{M}{}^{}}$( )${\displaystyle {}^{}}$=${\displaystyle {}^{}}$( ) [ 0 ${\displaystyle ]}$, ${\displaystyle \dots ,}$ M${\displaystyle {}^{}}$(${\displaystyle {}^{}}$)${\displaystyle {}^{}}$[ ${\displaystyle 31}$ ${\displaystyle {\textsf {M}^{{i}}=(M^{)}[0],\$$ldots$$, M^{i}[31]}}}}}$을(를)로 두십시오$.$ The message expansion function ${\displaystyle {\textrm {MsgExp}}}$ generates ${\displaystyle (N_{s}+1)}$ 16-word array sub-messages ${\displaystyle \{{\textsf {M}}_{j}^{(i)}\}_{j=0}^{N_{s}}}$ from a message block ${\displaystyle {\textsf$${M}^{(i$ The first two sub-messages ${\displaystyle {\textsf {M}}_{0}^{(i)}=(M_{0}^{(i)}[0],\ldots ,M_{0}^{(i)}[15])}$ and ${\displaystyle {\textsf {M}}_{1}^{(i)}=(M_{1}^{(i)}[0],\ldots ,M_{1}^$${(i)}[15]}$은(는) 다음과 같이 정의된다$$.

• ${\displaystyle {\textsf {{M}_{0}^{(i)}\왼쪽 화살표(M^{{0}[0],M^{{i)}[1],\ldots,M^{(i)}[15]}}}}}}}$
• ${\displaystyle {\textsf{M}_{1}^{(i)}\왼쪽 화살표(M^{(i)}[16],M^{{(i)}[17],\ldots ,M^{(i)}[31])}$

The next sub-messages ${\displaystyle \{{\textsf {M}}_{j}^{(i)}=(M_{j}^{(i)}[0],\ldots ,M_{j}^{(i)}[15])$$\}_{j=2}}^{N_{s}}}}$은(는) 다음과 같이 생성된다$$.

• ${\displaystyle {\textsf {{M}_{j}^{{{j}^{{{}}}[l]{{m}_{j-1}^{\textsf {\textsf{M}}}}}{j-2}^{\textsf[\tau(l)]}}$ ${\displaystyle(0\leq l\leq 15,\ 2\leq j\leq N_{s}}}}$

여기서 $\tau {\displaystyle }$ ${\displaystyle \tau$}은$($는) 다음과 같이 정의된$$ $Z{\displaystyle {\mathbb{}}_{}}$ ${\displaystyle {16}_{}}$ ${\$ {Z$} _{16}$에 대한 순열이다$$.

순열${\displaystyle }\tau {\displaystyle }$ : Z ${\displaystyle {16}_{}}$→ Z ${\displaystyle {16}_{}}$ ${\$ 화살표 $\mathb {Z} _{16}}}$

$l}$	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
$\displaystyle \tau(l)}$	3	2	0	1	7	4	5	6	11	10	8	9	15	12	13	14

메시지 추가 기능 MsgAdd

For two 16-word arrays ${\displaystyle {\textsf {X}}=(X[0],\ldots ,X[15])}$ and ${\displaystyle {\textsf {Y}}=(Y[0],\ldots ,Y[15])}$, the message addition function ${\displaystyle {\textrm {MsgAdd}}:{\mathca$$l{W}^{16}\time {\mathcal{W}^{16}\오른쪽$ 화살표 ${\mathcal{W}^{16}}}$는 다음과 같이 정의된다$$.

${\displaystyle {\textrm {MsgAdd}({\textsf {X},{\textsf {Y}):=(X[0]\oplus Y[0],\ldots, X[15]\oplus Y[15])}}}}}}$

믹스 함수 믹스

$j{\displaystyle }$ ${\displaystyle j}$ -th$$ 혼합 함수 ${\displaystyle {\text{Mix}}_{}}$ ${\displaystyle j_{}}$: W ${\displaystyle {16}^{}}$→ ${\displaystyle {\mathcal{}}^{}}$ ${\displaystyle {16}^{}}$ ${\$ {$Mix}_{j}:${{W\mathcal}}^{16}\rightarrow{{W\mathcal}}^{16}}모든two-word 한켤레를 혼합하여;(0≤ 나는<>8){\displaystyle(0\leq l< 8)}을 위한 T[나는]{T[나는]\displaystyle}과 T[는 a=l+8]{T[l+8]\displaystyle}은16-word 배열 T=({\displaystyle{\textsf{T}}=(T[0],\ldots ,T[15])}을 업데이트한다. 들어 < ${\$ 혼합 함수 ${\displaystyle {\text{Mix}}_{}}$ ${\displaystyle j_{}}$ ${\$는 다음과$$ 같이 진행한다.

$(T[l],)T[l+8]\왼쪽 화살표 {\textrm {Mix}_{j,l}(T[l]),T[l+8]}$ ${\displaystyle(0\leq l<8)}$

여기서 ${\displaystyle {\text{믹스}}_{}}$ ${\displaystyle j_{}}$, ${\displaystyle l_{}}$ ${\$는 두 단어의 믹스함수다. $X{\displaystyle }$ ${\displaystyle X}$과 $Y{\displaystyle }$ ${\displaystyle Y}$을(를) 단어로$$ 한다. 2단어 혼합함수 ${\displaystyle {Mix}_{}}$ j${\displaystyle {}_{}}$, ${\displaystyle l_{}}$: ${\displaystyle W^{\mathrm{}}}$ 2${\displaystyle {}^{}}$→ W ${\displaystyle 2^{\mathrm{}}}$ ${\$ 화살표 ${\mathcal{W}^{{W}}}}}}}{$2}}: 다음과 같이 정의된다$$.

함수 2단어 혼합 함수 ${\displaystyle {믹스}_{}}$ j${\displaystyle {}_{}}$, ${\displaystyle l_{}}$ ${\$ {$Mix}_{j,l}}$ 입력: 워드 $X{\displaystyle }$ ${\displaystyle X}$ $및$ Y ${\displaystyle Y}$ 출력: 워드 $X{\displaystyle }$ ${\displaystyle X}$ $및$ Y ${\displaystyle Y}$ 절차 ${\displaystyle \qquad }$ $X$${\displaystyle }$ ${\displaystyle \leftarrow }$ ${\displaystyle X}$ ${\displaystyle ⊞}$ ${\displaystyle Y}$ ${\displaystyle X\leftarrow$ X$\boxplus$ Y$\};$ ${\displaystyle X}$ ${\displaystyle \leftarrow }$ ${\displaystyle {}^{{}_{}}}$ ${\displaystyle {j_{}}^{}}$ ${\$ ${\displaystyle \qquad }$ X ${\displaystyle \leftarrow }$ $X$${\displaystyle }$ ${\displaystyle \oplus }$ ${\displaystyle S}$ ${\displaystyle C_{}}$ ${\displaystyle {}_{}}$[ ${\displaystyle l}$ ${\displaystyle ]}$ ${\displaystyle X\leftarrow$ X$\oplus SC_{j}[l]}$; ${\displaystyle }$$\{\backslash$$displaystyle \qquad }$${\displaystyle Y}$$$ ${\displaystyle X}$ ${\displaystyle ⊞}$ Y ${\displaystyle$ Y {\$displaystyle Y$${\displaystyle {}^{}}$$\$β j {\$displaystyle \qquad Y^{\lll \lll$ \$beta _{j$ ; ${\displaystyle \qquad }$ $X$${\displaystyle }$ ${\displaystyle \leftarrow }$ ${\displaystyle X}$ ${\displaystyle ⊞}$ ${\displaystyle Y}$ ${\displaystyle X\leftarrow$ X$\boxplus$ Y$\};$ ${\displaystyle Y}$ ${\displaystyle \leftarrow }$ $\$ ${\displaystyle {l_{}}^{}}$ {\$displaystyle$ \$qquad$Y^{\$lll \lll$ \$gamma$_$\{$$l}}$ ${\displaystyle \qquad }$$반환$ $X{\displaystyle }$ ${\displaystyle$ X$\},$ Y ${\displaystyle Y$

2단어 ${\displaystyle {\text{혼합함수}}_{\mathrm{Mix}}}$ j , l ${\$는 다음 그림과 같다$$.

${\displaystyle {\text{다음}}_{}}$ ${\displaystyle {표}_{}}$에는${\displaystyle {}_{}}$${\displaystyle {믹스}_{}}$ j ,$$ {\displaystyle {\$displaystyle \alpha_{$j},$$${\displaystyle {\beta j}_{}}$ ${\$$displaystyle \beta_{$$j},$$$γ l ${\$$displaystystyle {\textrm {Mix}_{j,l}$에 사용되는 비트$$ 회전량이 나와$$ 있다.

비트 회전량 ${\displaystyle {\alpha j}_{}}$ ${\$ $\beta {\displaystyle {}_{}}$ ${\displaystyle j_{}}$ ${\$$\gamma {\displaystyle {}_{}}$ ${\displaystyle l_{}}$ ${\$

${\displaystyle w}$	$(\displaystyle j}$	${\displaystyle \alpha _{j}}$	${\displaystyle \beta _{j}}$	${\displaystyle \cHB_{0}}$	${\displaystyle \cHB _{1}}$	${\displaystyle \cHB _{2}}$	${\displaystyle \cHB_{3}}$	${\displaystyle \cHB_{4}}$	${\displaystyle \cHB_{5}}$	${\displaystyle \cHB_{6}}$	${\displaystyle \cHB_{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

The ${\displaystyle j}$-th 8-word array constant ${\displaystyle {\textsf {SC}}_{j}=(SC_{j}[0],\ldots ,SC_{j}[7])}$ used in ${\displaystyle {\textrm {Mix}}_{j,l}}$ for ${\displaystyle 0\leq l<8}$ is defined as follows. 초기 8단어 어레이 상수 ${\displaystyle {\mathsf{\text{SC}}}_{}}$ ${\displaystyle 0_{\mathrm{}}}$=${\displaystyle }$( ${\displaystyle S}$ ${\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$[ ${\displaystyle 0}$ ${\displaystyle ]}$, ${\displaystyle \dots ,}$ S ${\displaystyle {C\mathrm{}}_{}}$ ${\displaystyle {}_{}}$[ ${\displaystyle 7}$ ${\displaystyle ]}$) ${\displaystyle {\textsf{SC}_{0}=(SC_{0}[0],\ldots ,SC_{0}[7])}$은 다음 표에 정의되어$$ 있다. 1≤ j<>;Ns{\displaystyle 1\leq j&lt을 말한다.⊞ SCj1[나는]8{\displaystyle SC_{j}[나는]\l ⋘ − ← SCj1[나는]− N_{s}}, j{j\displaystyle}-th 상수 SCj)(SCj[0],…, SCj[7]){\displaystyle{\textsf{SC}}_ᆵ=(SC_{j}[0],\ldots,SC_{j}[7])}SCj[나는]에 의해 만들어진다.$eftarrow SC_{j-1}[l]\boxplus SC_{j-1}[l]^{\lll$ 8$},$ < ${\displaystyle 0\leq l<8}$.

초기 8단어 어레이 상수 ${\displaystyle {\mathsf{\text{SC}}}_{}}$ ${\displaystyle 0_{\mathrm{}}}$ ${\$

	${\displaystyle w=32})$	$w=64}$
${\displaystyle SC_{0}[0]}$	9171990년	97884283c938982a
${\displaystyle SC_{0}[1]}$	6c1b10a2	ba1fca93533e2355
${\displaystyle SC_{0}[2]}$	6f352943	c519a2e87aeb1c03
${\displaystyle SC_{0}[3]}$	cf778243	9a0fc95462af17b1
${\displaystyle SC_{0}[4]}$	2ceb7472	fc3dda8ab019a82b
${\displaystyle SC_{0}[5]}$	29e96ff2	02825d079a895407
${\displaystyle SC_{0}[6]}$	8a9ba428	79f2d0a7ee06a6f7
${\displaystyle SC_{0}[7]}$	2eeb2642	d76d15eed9fdf5fe

Word-Permutation 함수 WordPerm

$X{\displaystyle }$=${\displaystyle }$( ${\displaystyle X}$[ ${\displaystyle 0}$ ${\displaystyle ]}$,${\displaystyle }$… ,${\displaystyle X}$[ ${\displaystyle 15}$ ${\displaystyle ]}$) ${\displaystyle {\textsf{X}=(X[0],\ldots ,X[15])}$을(를) 16자 배열로 한다$$. Word-permution 함수 ${\displaystyle \text{WordPerm}}$: W ${\displaystyle {16}^{}}$→ ${\displaystyle {\mathcal{}}^{}}$ ${\displaystyle {16}^{}}$ ${\$${\mathcal{W}^{16}\오른쪽$ 화살표 ${\mathcal{W}^{16}}}$는 다음과$$ 같이 정의된다.

${\displaystyle {\textPerm}({\textsf {X})=(X[\sigma (0)],\ldots,X[\sigma (15))]}}}$

여기서 ${\displaystyle \sigma }$은(는) 다음 표로 정의된$$ $Z{\displaystyle {\mathbb{}}_{}}$ ${\displaystyle {16}_{}}$ ${\$16$}$에 대한 순열이다.

순열${\displaystyle }\sigma {\displaystyle }$ : Z ${\displaystyle {16}_{}}$→ ${\displaystyle {\mathbb{}}_{}}$ ${\displaystyle {16}_{}}$ ${\$ 화살표 $\mathb {Z} _{16}}}$

$l}$	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
$\displaystyle \sigma (l)}$	6	4	5	7	12	15	14	13	2	0	1	3	8	11	10	9

최종화

${\displaystyle {\text{최종화}}_{}}$ 함수 ${\displaystyle {\mathrm{FINn}}^{}{}_{}}$: W ${\displaystyle 16{}^{}}$→${\displaystyle }${ 0${\displaystyle ,}$ ${\displaystyle 1}$ $}$ {\$displaystyle$ {\$textrm${\fIN$}_{n}:$${\mathcal {W}}^{16}\rightarrow \{0,1\}^{n}}$ returns ${\displaystyle n}$-bit hash value ${\displaystyle h}$ from the final chaining variable ${\displaystyle {\textsf {CV}}^{(t)}=(CV^{(t)}[0],\ldots ,CV^{(t)}[15])}$. When ${\displaystyle \mathsf{\text{H}}=(H[0],\dots ,H[7]}$${\displaystyle {\textsf {H}}=(H[0],\ldots ,H[7])}$ is an 8-word variable and ${\displaystyle {\textsf {h}}_{\textsf {b}}=(h_{b}[0],\ldots ,h_{b}[w-1])}$ is a ${\displaystyle w}$-byte variable, the finalization function ${\displaystyle {\textrm {FIN}}_{n}$${}$은(는) 다음 절차를 수행한다$$.

• ${\displaystyle H[l]\왼쪽 화살표 CV^{(t)}[l]\oplus CV^{(t)}[l+8]}$ ${\displaystyle(0\leq l\leq 7)}$
• ${\displaystyle h_{b}[s]\왼쪽 화살표 H[\lfloor 8s/w\rfloor ]_{[7:0]}^{\gg(8s\mod w)}}}}}}}$ ${\displaystyle(0\leq s\leq (w-1)}$
• ${\displaystyle h\leftarrow (h_{b}[0]\ldots \ h_{b}[w-1])_{[0:n-1]}}}$

Here, ${\displaystyle X_{[i:j]}}$ denotes ${\displaystyle x_{i}\ x_{i-1}\ \ldots \ x_{j}}$, the sub-bit string of a word ${\displaystyle X}$ for ${\displaystyle i\geq j}$. And ${\displaystyle x_{[i:j]}}$ denotes ${\displaystyle x_i\Vert x_{i+1}\Vert \dots \Vert }$${\displaystyle x_{i}\ x_{i+1}\ \ldots \ x_{j}}$, the sub-bit string of a ${\displaystyle l}$-bit string ${\displaystyle x=x_{0}\ x_{1}\ \ldots \ x_{l-1}}$ for ${\displaystyle i\leq j}$.

보안

LSH는 현재까지 알려진 해시함수 공격으로부터 안전하다. LSH는 이상적인 암호 모델에서 < / 2 ${\$ 충돌 방지 및 pre-image $내성$을 가지고 있으며$, 여기서$$q{\displaystyle }$ ${\displaystyle q}$은 LSH 구조에 대한 여러 질의 사항이다.^[1] 스텝 수가 13개 이상일 때 기존의 모든 해시함수 공격에 대해 LSH-256이, 스텝 수가 14개 이상일 경우 LSH-512가 보안된다. 보안 마진으로 작동하는 단계는 압축 함수의 50%에 해당한다는 점에 유의하십시오.^[1]

퍼포먼스

LSH는 다양한 소프트웨어 플랫폼에서 SHA-2/3을 능가한다. 다음 표는 여러 플랫폼에서 LSH의 1MB 메시지 해싱의 속도 성능을 보여준다.

1MB 메시지 해싱 속도 LSH(주기/바이트)^[1]

플랫폼	P1[a]	P2[b]	P3[c]	P4[d]	P5[e]	P6[f]	P7[g]	P8[h]
${\displaystyle }$ ${\displaystyle n}$	3.60	3.86	5.26	3.89	11.17	15.03	15.28	14.84
${\displaystyle }$ ${\displaystyle n}$	2.39	5.04	7.76	5.52	8.94	18.76	19.00	18.10

다음 표는 Haswell을 기반으로 한 플랫폼에서 비교한 것이며, LSH는 Intel Core i7-4770k @ 3.5GHz 쿼드 코어 플랫폼에서, 다른 표는 Intel Core i5-4570S @ 2.9GHz 쿼드 코어 플랫폼에서 측정한다.

Haswell CPU(사이클/바이트)^[1] 기반 플랫폼에서 LSH, SHA-2 및 SHA-3 최종 결승전의 속도 벤치마크

알고리즘.	메시지 크기(바이트)
	장기의	4,096	1,536	576	64	8
LSH-256-256	3.60	3.71	3.90	4.08	8.19	65.37
스키인-512-256	5.01	5.58	5.86	6.49	13.12	104.50
블레이크-256	6.61	7.63	7.87	9.05	16.58	72.50
그뢰스틀-256	9.48	10.68	12.18	13.71	37.94	227.50
케차크-256	10.56	10.52	9.90	11.99	23.38	187.50
SHA-256	10.82	11.91	12.26	13.51	24.88	106.62
JH-256	14.70	15.50	15.94	17.06	31.94	257.00
LSH-512-512	2.39	2.54	2.79	3.31	10.81	85.62
스키인-512-512	4.67	5.51	5.80	6.44	13.59	108.25
블레이크-512	4.96	6.17	6.82	7.38	14.81	116.50
SHA-512	7.65	8.24	8.69	9.03	17.22	138.25
그뢰스틀-512	12.78	15.44	17.30	17.99	51.72	417.38
JH-512	14.25	15.66	16.14	17.34	32.69	261.00
케차크-512	16.36	17.86	18.46	20.35	21.56	171.88

다음 표는 Samsung Exynos 5250 ARM Cortex-A15 @ 1.7GHz 듀얼 코어 플랫폼에서 측정한다.

Exynos 5250 ARM Cortex-A15 CPU(사이클/바이트)^[1] 기반 플랫폼에서 LSH, SHA-2 및 SHA-3 최종 결승전의 속도 벤치마크

알고리즘.	메시지 크기(바이트)
	장기의	4,096	1,536	576	64	8
LSH-256-256	11.17	11.53	12.16	12.63	22.42	192.68
스키인-512-256	15.64	16.72	18.33	22.68	75.75	609.25
블레이크-256	17.94	19.11	20.88	25.44	83.94	542.38
SHA-256	19.91	21.14	23.03	28.13	90.89	578.50
JH-256	34.66	36.06	38.10	43.51	113.92	924.12
케차크-256	36.03	38.01	40.54	48.13	125.00	1000.62
그뢰스틀-256	40.70	42.76	46.03	54.94	167.52	1020.62
LSH-512-512	8.94	9.56	10.55	12.28	38.82	307.98
블레이크-512	13.46	14.82	16.88	20.98	77.53	623.62
스키인-512-512	15.61	16.73	18.35	22.56	75.59	612.88
JH-512	34.88	36.26	38.36	44.01	116.41	939.38
SHA-512	44.13	46.41	49.97	54.55	135.59	1088.38
케차크-512	63.31	64.59	67.85	77.21	121.28	968.00
그뢰스틀-512	131.35	138.49	150.15	166.54	446.53	3518.00

테스트 벡터

각 다이제스트 길이에 대한 LSH에 대한 테스트 벡터는 다음과 같다. 모든 값은 16진법 형태로 표현된다.

LSH-256-224("abc") = F7 C5 3B A4 03 4E 70 8E 74 FB A4 2E 55 99 7C A5 12 6B B7 62 36 88 F8 53 42 F7 37 32

LSH-256-256("abc") = 5F BF 36 5D AE A5 44 6A 70 53 C5 2B 57 40 4D 77 A0 7A 5F 48 A1 F7 96 3A 08 98 BA 1B 71 4741

LSH-512-224("abc") = D1 68 32 34 51 3E C5 69 83 94 57 1E AD 12 8A 8C 37 3E 97 1B 97 1B A2 0D CF 89 E4 89

LSH-512-256("abc") = CD 89 23 10 53 26 02 33 2B 61 3F C1 1A 69 62 FC A6 1E 9E CF FC D4 BC F7 58 58 D8 ED EC

LSH-512-384("abc") = 5F 34 4E FA A0 E4 3C CD 2E 5E 19 4D 60 39 79 4B 4F B4 31 F1 0F B4 B6 5F D4 5E 9D A4 EC DE 0F 27 B6 6E 8D BD FA 47 25 2E 0D 0B 74 1B FD 91 F9 FE

LSH-512-512("abc") = A3 D9 3C FE 60 DC 1A AC DD 3B D4 BE F0 A6 98 53 81 A3 96 C7 D4 9D 9F D1 77 79 56 97 C3 53 52 08 B5 C5 72 24 BE F2 10 84 D4 20 83 E9 5A 4B D8 EB 33 E8 69 81 2B 65 03 1C 42 88 19 A1 E7 CE 59 6D

구현

LSH는 공공 또는 민간, 상업 또는 비상업적 용도로 무료로 사용할 수 있다. C, Java, Python에서 구현된 LSH 배포 소스 코드는 KISA의 암호화 사용 활성화 웹페이지에서 다운로드할 수 있다.^[2]

KCMVP

LSH는 한국암호화모듈검증프로그램(KCMVP)이 승인한 암호 알고리즘 중 하나이다.^[3]

표준화

LSH는 다음 표준에 포함되어 있다.

• KS X 3262, 해시함수 LSH(한국어)^[4]

참조