LSH（ハッシュ関数）

LSHは、 PCやスマートデバイスなどの汎用ソフトウェア環境における整合性を確保するために、 2014年に韓国で設計された暗号ハッシュ関数です。^{[ 1 ]} LSHは、韓国暗号モジュール検証プログラム（KCMVP）によって承認された暗号アルゴリズムの1つです。また、韓国の国家標準（KS X 3262）でもあります

仕様

ハッシュ関数LSHの全体構造を次の図に示します

LSHの全体構造

ハッシュ関数LSHは、1つのゼロをパディングするワイドパイプMerkle-Damgård構造を持ちます。LSHのメッセージハッシュ処理は、以下の3つの段階から構成されます。

1. 初期化：
   • 与えられたビット列メッセージにゼロを1つ埋め込む
   • パディングされたビット文字列メッセージから 32 ワード配列メッセージ ブロックに変換します。
   • 初期化ベクトルを使用した連鎖変数の初期化。
2. 圧縮：
   • メッセージブロックを含む圧縮関数の反復処理による連鎖変数の更新
3. ファイナライズ：
   • 最終連鎖変数から16ビットのハッシュ値を生成します${\displaystyle n}$

関数ハッシュ関数 LSH 入力:ビット文字列メッセージ${\displaystyle m}$ 出力:ハッシュ値${\displaystyle h\in \{0,1\}^{n}}$ 手順 ${\displaystyle \qquad }$ ゼロ1つでパディング${\displaystyle m}$ ${\displaystyle \qquad }$ パディングされたビット文字列から メッセージブロックを生成する${\displaystyle t}$ ${\displaystyle \{{\textsf {M}}^{(i)}\}_{i=0}^{t-1}}$ ${\displaystyle t={\Big \lceil}{\frac {|m|+1}{32w}}{\Big \rceil}}$ ${\displaystyle \qquad }$ ${\displaystyle {\textsf {CV}}^{(0)}\leftarrow {\textsf {IV}}}$ ${\displaystyle \qquad }$ 〜するために${\displaystyle i=0}$ ${\displaystyle (t-1)}$ ${\displaystyle \qquad }$ ${\displaystyle \qquad }$ ${\displaystyle {\textsf {CV}}^{(i+1)}\leftarrow {\textrm {CF}}({\textsf {CV}}^{(i)},{\textsf {M}}^{(i)})}$ ${\displaystyle \qquad }$ 〜のために終了 ${\displaystyle \qquad }$ ${\displaystyle h\leftarrow {\textrm {FIN}}_{n}({\textsf {CV}}^{(t)})}$ ${\displaystyle \qquad }$ 戻る${\displaystyle h}$

ハッシュ関数LSHの仕様は次のとおりです

ハッシュ関数LSH仕様

アルゴリズム	ダイジェストサイズ（ビット） ${\displaystyle n}$	ステップ関数の数（） ${\displaystyle N_{s}}$	ビット単位で可変サイズを連鎖する	メッセージブロックサイズ（ビット）	ワードサイズ（ビット）（） ${\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

初期化

与えられたビット文字列メッセージをとする。与えられたメッセージは0 で埋められる。つまり、ビット 1 は の末尾に追加され、ビット 0 は埋められたメッセージのビット長が になるまで追加される。ここ で、と は以上の最小の整数である${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle 32wt}$ ${\displaystyle t=\lceil (|m|+1)/32w\rceil }$ ${\displaystyle \lceil x\rceil}$ ${\displaystyle x}$

を の1 ビットのゼロ詰め文字列とします。すると、 はバイト配列とみなされます。ここで、すべての に対して となります。バイト配列は次のようにワード配列に変換されます。 ${\displaystyle m_{p}=m_{0}\|m_{1}\|\ldots \|m_{(32wt-1)}}$ ${\displaystyle 32wt}$ ${\displaystyle m}$ ${\displaystyle m_{p}}$ ${\displaystyle 4wt}$ ${\displaystyle m_{a}=(m[0],\ldots,m[4wt-1])}$ ${\displaystyle m[k]=m_{8k}\|m_{(8k+1)}\|\ldots \|m_{(8k+7)}}$ ${\displaystyle 0\leq k\leq (4wt-1)}$ ${\displaystyle 4wt}$ ${\displaystyle m_{a}}$ ${\displaystyle 32t}$ ${\displaystyle {\textsf {M}}=(M[0],\ldots,M[32t-1])}$

${\displaystyle M[s]\leftarrow m[ws/8+(w/8-1)]\|\ldots \|m[ws/8+1]\|m[ws/8]}$ ${\displaystyle (0\leq s\leq (32t-1))}$

ワード配列から、32 ワード配列のメッセージ ブロックを次のように定義します。 ${\displaystyle {\textsf {M}}}$ ${\displaystyle t}$ ${\displaystyle \{{\textsf {M}}^{(i)}\}_{i=0}^{t-1}}$

${\displaystyle {\textsf {M}}^{(i)}\leftarrow (M[32i],M[32i+1],\ldots ,M[32i+31])}$ ${\displaystyle (0\leq i\leq (t-1))}$

16 ワードの配列連鎖変数は初期化ベクトルに初期化されます。 ${\displaystyle {\textsf {CV}}^{(0)}}$ ${\displaystyle {\textsf {IV}}}$

${\displaystyle {\textsf {CV}}^{(0)}[l]\leftarrow {\textsf {IV}}[l]}$ ${\displaystyle (0\leq l\leq 15)}$

初期化ベクトルは以下のとおりです。以下の表では、すべての値は16進数で表されています。 ${\displaystyle {\textsf {IV}}}$

LSH-256-224 初期化ベクトル

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

LSH-256-256 初期化ベクトル

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

LSH-512-224 初期化ベクトル

${\displaystyle {\textsf {IV}}[0]}$	${\displaystyle {\textsf {IV}}[1]}$	${\displaystyle {\textsf {IV}}[2]}$	${\displaystyle {\textsf {IV}}[3]}$
0C401E9FE8813A55	4A5F446268FD3D35	FF13E452334F612A	F8227661037E354A
${\displaystyle {\textsf {IV}}[4]}$	${\displaystyle {\textsf {IV}}[5]}$	${\displaystyle {\textsf {IV}}[6]}$	${\displaystyle {\textsf {IV}}[7]}$
A5F223723C9CA29D	95D965A11AED3979	01E23835B9AB02CC	52D49CBAD5B30616
${\displaystyle {\textsf {IV}}[8]}$	${\displaystyle {\textsf {IV}}[9]}$	${\displaystyle {\textsf {IV}}[10]}$	${\displaystyle {\textsf {IV}}[11]}$
9E5C2027773F4ED3	66A5C8801925B701	22BBC85B4C6779D9	C13171A42C559C23
${\displaystyle {\textsf {IV}}[12]}$	${\displaystyle {\textsf {IV}}[13]}$	${\displaystyle {\textsf {IV}}[14]}$	${\displaystyle {\textsf {IV}}[15]}$
31E2B67D25BE3813	D522C4DEED8E4D83	A79F5509B43FBAFE	E00D2CD88B4B6C6A

LSH-512-256初期化ベクトル

${\displaystyle {\textsf {IV}}[0]}$	${\displaystyle {\textsf {IV}}[1]}$	${\displaystyle {\textsf {IV}}[2]}$	${\displaystyle {\textsf {IV}}[3]}$
6DC57C33DF989423	D8EA7F6E8342C199	76DF8356F8603AC4	40F1B44DE838223A
${\displaystyle {\textsf {IV}}[4]}$	${\displaystyle {\textsf {IV}}[5]}$	${\displaystyle {\textsf {IV}}[6]}$	${\displaystyle {\textsf {IV}}[7]}$
39FFE7CFC31484CD	39C4326CC5281548	8A2FF85A346045D8	FF202AA46DBDD61E
${\displaystyle {\textsf {IV}}[8]}$	${\displaystyle {\textsf {IV}}[9]}$	${\displaystyle {\textsf {IV}}[10]}$	${\displaystyle {\textsf {IV}}[11]}$
CF785B3CD5FCDB8B	1F0323B64A8150BF	FF75D972F29EA355	2E567F30BF1CA9E1
${\displaystyle {\textsf {IV}}[12]}$	${\displaystyle {\textsf {IV}}[13]}$	${\displaystyle {\textsf {IV}}[14]}$	${\displaystyle {\textsf {IV}}[15]}$
B596875BF8FF6DBA	FCCA39B089EF4615	ECFF4017D020B4B6	7E77384C772ED802

LSH-512-384 初期化ベクトル

${\displaystyle {\textsf {IV}}[0]}$	${\displaystyle {\textsf {IV}}[1]}$	${\displaystyle {\textsf {IV}}[2]}$	${\displaystyle {\textsf {IV}}[3]}$
53156A66292808F6	B2C4F362B204C2BC	B84B7213BFA05C4E	976CEB7C1B299F73
${\displaystyle {\textsf {IV}}[4]}$	${\displaystyle {\textsf {IV}}[5]}$	${\displaystyle {\textsf {IV}}[6]}$	${\displaystyle {\textsf {IV}}[7]}$
DF0CC63C0570AE97	DA4441BAA486CE3F	6559F5D9B5F2ACC2	22DACF19B4B52A16
${\displaystyle {\textsf {IV}}[8]}$	${\displaystyle {\textsf {IV}}[9]}$	${\displaystyle {\textsf {IV}}[10]}$	${\displaystyle {\textsf {IV}}[11]}$
BBCDACEFDE80953A	C9891A2879725B3E	7C9FE6330237E440	A30BA550553F7431
${\displaystyle {\textsf {IV}}[12]}$	${\displaystyle {\textsf {IV}}[13]}$	${\displaystyle {\textsf {IV}}[14]}$	${\displaystyle {\textsf {IV}}[15]}$
BB08043FB34E3E30	A0DEC48D54618EAD	150317267464BC57	32D1501FDE63DC93

LSH-512-512 初期化ベクトル

${\displaystyle {\textsf {IV}}[0]}$	${\displaystyle {\textsf {IV}}[1]}$	${\displaystyle {\textsf {IV}}[2]}$	${\displaystyle {\textsf {IV}}[3]}$
ADD50F3C7F07094E	E3F3CEE8F9418A4F	B527ECDE5B3D0AE9	2EF6DEC68076F501
${\displaystyle {\textsf {IV}}[4]}$	${\displaystyle {\textsf {IV}}[5]}$	${\displaystyle {\textsf {IV}}[6]}$	${\displaystyle {\textsf {IV}}[7]}$
8CB994CAE5ACA216	FBB9EAE4BBA48CC7	650A526174725FEA	1F9A61A73F8D8085
${\displaystyle {\textsf {IV}}[8]}$	${\displaystyle {\textsf {IV}}[9]}$	${\displaystyle {\textsf {IV}}[10]}$	${\displaystyle {\textsf {IV}}[11]}$
B6607378173B539B	1BC99853B0C0B9ED	DF727FC19B182D47	DBEF360CF893A457
${\displaystyle {\textsf {IV}}[12]}$	${\displaystyle {\textsf {IV}}[13]}$	${\displaystyle {\textsf {IV}}[14]}$	${\displaystyle {\textsf {IV}}[15]}$
4981F5E570147E80	D00C4490CA7D3E30	5D73940C0E4AE1EC	894085E2EDB2D819

圧縮

この段階では、初期化段階でメッセージから生成された32ワード配列のメッセージブロックが、圧縮関数の反復によって圧縮されます。圧縮関数には、 16ワードの連鎖変数と32ワードのメッセージブロックの2つの入力があります。そして、 16ワードの連鎖変数を返します。ここで、そして以降、は すべてのワード配列の集合を表します${\displaystyle t}$ ${\displaystyle \{{\textsf {M}}^{(i)}\}_{i=0}^{t-1}}$ ${\displaystyle m}$ ${\displaystyle {\textrm {CF}}:{\mathcal {W}}^{16}\times {\mathcal {W}}^{32}\rightarrow {\mathcal {W}}^{16}}$ ${\displaystyle i}$ ${\displaystyle {\textsf {CV}}^{(i)}}$ ${\displaystyle i}$ ${\displaystyle {\textsf {M}}^{(i)}}$ ${\displaystyle (i+1)}$ ${\displaystyle {\textsf {CV}}^{(i+1)}}$ ${\displaystyle {\mathcal {W}}^{t}}$ ${\displaystyle t}$ ${\displaystyle t\geq 1}$

圧縮関数では次の 4 つの関数が使用されます。

• メッセージ拡張機能${\displaystyle {\textrm {MsgExp}}:{\mathcal {W}}^{32}\rightarrow {\mathcal {W}}^{16(Ns+1)}}$
• メッセージ追加機能${\displaystyle {\textrm {MsgAdd}}:{\mathcal {W}}^{16}\times {\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}}$
• ミックス機能${\displaystyle {\textrm {Mix}}_{j}:{\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}}$
• 単語順列機能${\displaystyle {\textrm {WordPerm}}:{\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}}$

圧縮機能の全体構造は次の図に示されています

LSHの圧縮機能

圧縮関数において、メッセージ展開関数は与えられた から16ワード配列のサブメッセージを生成します。を 番目連鎖変数に設定された一時的な16ワード配列とします。番目ステップ関数は2つの入力を持ち、を更新します。つまり、 です。すべてのステップ関数は の順に実行されます。その後、 によるもう1つの操作が実行され、番目連鎖変数が に設定されます。圧縮関数の詳細なプロセスは以下のとおりです。 ${\displaystyle {\textrm {MsgExp}}}$ ${\displaystyle (N_{s}+1)}$ ${\displaystyle \{{\textsf {M}}_{j}^{(i)}\}_{j=0}^{N_{s}}}$ ${\displaystyle {\textsf {M}}^{(i)}}$ ${\displaystyle {\textsf {T}}=(T[0],\ldots ,T[15])}$ ${\displaystyle i}$ ${\displaystyle {\textsf {CV}}^{(i)}}$ ${\displaystyle j}$ ${\displaystyle {\textrm {Step}}_{j}}$ ${\displaystyle {\textsf {T}}}$ ${\displaystyle {\textsf {M}}_{j}^{(i)}}$ ${\displaystyle {\textsf {T}}}$ ${\displaystyle {\textsf {T}}\leftarrow {\textrm {Step}}_{j}\left({\textsf {T}},{\textsf {M}}_{j}^{(i)}\right)}$ ${\displaystyle j=0,\ldots ,N_{s}-1}$ ${\displaystyle {\textrm {MsgAdd}}}$ ${\displaystyle {\textsf {M}}_{N_{s}}^{(i)}}$ ${\displaystyle (i+1)}$ ${\displaystyle {\textsf {CV}}^{(i+1)}}$ ${\displaystyle {\textsf {T}}}$

機能圧縮機能${\displaystyle {\textrm {CF}}}$ 入力: -番目の連鎖変数と-番目のメッセージブロック${\displaystyle i}$ ${\displaystyle {\textsf {CV}}^{(i)}\in {\mathcal {W}}^{16}}$ ${\displaystyle i}$ ${\displaystyle {\textsf {M}}^{(i)}\in {\mathcal {W}}^{32}}$ 出力:番目の連鎖変数${\displaystyle (i+1)}$ ${\displaystyle {\textsf {CV}}^{(i+1)}\in {\mathcal {W}}^{16}}$ 手順 ${\displaystyle \qquad }$ ${\displaystyle \{{\textsf {M}}_{j}^{(i)}\}_{j=0}^{N_{s}}\leftarrow {\textrm {MsgExp}}\left({\textsf {M}}^{(i)}\right)}$ ${\displaystyle \qquad }$ ${\displaystyle {\textsf {T}}\leftarrow {\textsf {CV}}^{(i)}}$ ${\displaystyle \qquad }$ 〜するために${\displaystyle j=0}$ ${\displaystyle (N_{s}-1)}$ ${\displaystyle \qquad }$ ${\displaystyle \qquad }$ ${\displaystyle {\textsf {T}}\leftarrow {\textrm {Step}}_{j}\left({\textsf {T}},{\textsf {M}}_{j}^{(i)}\right)}$ ${\displaystyle \qquad }$ 〜のために終了 ${\displaystyle \qquad }$ ${\displaystyle {\textsf {CV}}^{(i+1)}\leftarrow {\textrm {MsgAdd}}\left({\textsf {T}},{\textsf {M}}_{N_{s}}^{(i)}\right)}$ ${\displaystyle \qquad }$ 戻る${\displaystyle {\textsf {CV}}^{(i+1)}}$

ここで- 番目のステップ関数は次のようになります。 ${\displaystyle j}$ ${\displaystyle {\textrm {Step}}_{j}:{\mathcal {W}}^{16}\times {\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}}$

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

次の図は、圧縮関数の - 番目のステップ関数を示しています。${\displaystyle j}$ ${\displaystyle {\textrm {Step}}_{j}}$

番目のステップ関数${\displaystyle j}$ ${\displaystyle {\textrm {Step}}_{j}}$

メッセージ展開関数 MsgExp

を - 番目の32ワード配列メッセージブロックとします。メッセージ展開関数は、メッセージブロックから16ワード配列のサブメッセージを生成します。最初の2つのサブメッセージと は次のように定義されます。 ${\displaystyle {\textsf {M}}^{(i)}=(M^{(i)}[0],\ldots ,M^{(i)}[31])}$ ${\displaystyle i}$ ${\displaystyle {\textrm {MsgExp}}}$ ${\displaystyle (N_{s}+1)}$ ${\displaystyle \{{\textsf {M}}_{j}^{(i)}\}_{j=0}^{N_{s}}}$ ${\displaystyle {\textsf {M}}^{(i)}}$ ${\displaystyle {\textsf {M}}_{0}^{(i)}=(M_{0}^{(i)}[0],\ldots ,M_{0}^{(i)}[15])}$ ${\displaystyle {\textsf {M}}_{1}^{(i)}=(M_{1}^{(i)}[0],\ldots ,M_{1}^{(i)}[15])}$

• ${\displaystyle {\textsf {M}}_{0}^{(i)}\leftarrow (M^{(i)}[0],M^{(i)}[1],\ldots ,M^{(i)}[15])}$
• ${\displaystyle {\textsf {M}}_{1}^{(i)}\leftarrow (M^{(i)}[16],M^{(i)}[17],\ldots ,M^{(i)}[31])}$

次のサブメッセージは次のように生成されます。 ${\displaystyle \{{\textsf {M}}_{j}^{(i)}=(M_{j}^{(i)}[0],\ldots ,M_{j}^{(i)}[15])\}_{j=2}^{N_{s}}}$

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

ここで、 上の順列は次のように定義されます。 ${\displaystyle \tau }$ ${\displaystyle \mathbb {Z} _{16}}$

順列${\displaystyle \tau :\mathbb {Z} _{16}\rightarrow \mathbb {Z} _{16}}$

${\displaystyle 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

2 つの 16 ワード配列との場合、メッセージ追加関数は次のように定義されます。 ${\displaystyle {\textsf {X}}=(X[0],\ldots ,X[15])}$ ${\displaystyle {\textsf {Y}}=(Y[0],\ldots ,Y[15])}$ ${\displaystyle {\textrm {MsgAdd}}:{\mathcal {W}}^{16}\times {\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}}$

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

ミックス関数 ミックス

番目のミックス関数は、2語のペアごとにミックスすることで16語の配列を更新します。 の場合、ミックス関数は次のように進行します ${\displaystyle j}$ ${\displaystyle {\textrm {Mix}}_{j}:{\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}}$ ${\displaystyle {\textsf {T}}=(T[0],\ldots ,T[15])}$ ${\displaystyle T[l]}$ ${\displaystyle T[l+8]}$ ${\displaystyle (0\leq l<8)}$ ${\displaystyle 0\leq j<N_{s}}$ ${\displaystyle {\textrm {Mix}}_{j}}$

${\displaystyle (T[l],T[l+8])\leftarrow {\textrm {Mix}}_{j,l}(T[l],T[l+8])}$ ${\displaystyle (0\leq l<8)}$

2単語混合関数を示します。 とを単語とします。2単語混合関数は次のように定義されます。 ${\displaystyle {\textrm {Mix}}_{j,l}}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle {\textrm {Mix}}_{j,l}:{\mathcal {W}}^{2}\rightarrow {\mathcal {W}}^{2}}$

機能2語混合機能${\displaystyle {\textrm {Mix}}_{j,l}}$ 入力: 単語と${\displaystyle X}$ ${\displaystyle Y}$ 出力:単語と${\displaystyle X}$ ${\displaystyle Y}$ 手順 ${\displaystyle \qquad }$ ${\displaystyle X\leftarrow X\boxplus Y}$ ; ; ${\displaystyle \qquad X\leftarrow X^{\lll \alpha _{j}}}$ ${\displaystyle \qquad }$ ${\displaystyle X\leftarrow X\oplus SC_{j}[l]}$ ; ${\displaystyle \qquad }$ ${\displaystyle Y\leftarrow X\boxplus Y}$ ; ; ${\displaystyle \qquad Y\leftarrow Y^{\lll \beta _{j}}}$ ${\displaystyle \qquad }$ ${\displaystyle X\leftarrow X\boxplus Y}$ ; ; ${\displaystyle \qquad Y\leftarrow Y^{\lll \gamma _{l}}}$ ${\displaystyle \qquad }$ 戻る 、; ${\displaystyle X}$ ${\displaystyle Y}$

2 語ミックス関数は次の図に示されています。 ${\displaystyle {\textrm {Mix}}_{j,l}}$

2語混合機能${\displaystyle {\textrm {Mix}}_{j,l}(X,Y)}$

で使用されるビット回転量、を次の表に示します。 ${\displaystyle \alpha _{j}}$ ${\displaystyle \beta _{j}}$ ${\displaystyle \gamma _{l}}$ ${\displaystyle {\textrm {Mix}}_{j,l}}$

ビット回転量、、および${\displaystyle \alpha _{j}}$ ${\displaystyle \beta _{j}}$ ${\displaystyle \gamma _{l}}$

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

forで使用される- 番目の 8 ワード配列定数は以下のように定義されます。初期の 8 ワード配列定数は次の表で定義されています。 の場合、- 番目の定数はforによって生成されます。 ${\displaystyle j}$ ${\displaystyle {\textsf {SC}}_{j}=(SC_{j}[0],\ldots ,SC_{j}[7])}$ ${\displaystyle {\textrm {Mix}}_{j,l}}$ ${\displaystyle 0\leq l<8}$ ${\displaystyle {\textsf {SC}}_{0}=(SC_{0}[0],\ldots ,SC_{0}[7])}$ ${\displaystyle 1\leq j<N_{s}}$ ${\displaystyle j}$ ${\displaystyle {\textsf {SC}}_{j}=(SC_{j}[0],\ldots ,SC_{j}[7])}$ ${\displaystyle SC_{j}[l]\leftarrow SC_{j-1}[l]\boxplus SC_{j-1}[l]^{\lll 8}}$ ${\displaystyle 0\leq l<8}$

初期8ワード配列定数${\displaystyle {\textsf {SC}}_{0}}$

	${\displaystyle w=32}$	${\displaystyle w=64}$
${\displaystyle SC_{0}[0]}$	917caf90	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

単語順列関数 WordPerm

16単語の配列をとします。単語順列関数は次のように定義されます ${\displaystyle {\textsf {X}}=(X[0],\ldots ,X[15])}$ ${\displaystyle {\textrm {WordPerm}}:{\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}}$

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

これは次の表で定義された 上の順列です。${\displaystyle \sigma }$ ${\displaystyle \mathbb {Z} _{16}}$

順列${\displaystyle \sigma :\mathbb {Z} _{16}\rightarrow \mathbb {Z} _{16}}$

${\displaystyle 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

ファイナライズ

ファイナライズ関数は、最終連鎖変数から-ビットのハッシュ値を返します。が8ワード変数で、が -バイト変数の場合、ファイナライズ関数は以下の手順を実行します ${\displaystyle {\textrm {FIN}}_{n}:{\mathcal {W}}^{16}\rightarrow \{0,1\}^{n}}$ ${\displaystyle n}$ ${\displaystyle h}$ ${\displaystyle {\textsf {CV}}^{(t)}=(CV^{(t)}[0],\ldots ,CV^{(t)}[15])}$ ${\displaystyle {\textsf {H}}=(H[0],\ldots ,H[7])}$ ${\displaystyle {\textsf {h}}_{\textsf {b}}=(h_{b}[0],\ldots ,h_{b}[w-1])}$ ${\displaystyle w}$ ${\displaystyle {\textrm {FIN}}_{n}}$

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

ここで、は のワードのサブビット文字列を表します。また、は の-ビット文字列のサブビット文字列を表します。 ${\displaystyle X_{[i:j]}}$ ${\displaystyle x_{i}\|x_{i-1}\|\ldots \|x_{j}}$ ${\displaystyle X}$ ${\displaystyle i\geq j}$ ${\displaystyle x_{[i:j]}}$ ${\displaystyle x_{i}\|x_{i+1}\|\ldots \|x_{j}}$ ${\displaystyle l}$ ${\displaystyle x=x_{0}\|x_{1}\|\ldots \|x_{l-1}}$ ${\displaystyle i\leq j}$

セキュリティ

LSHは、ハッシュ関数に対するこれまでの既知の攻撃に対して安全です。理想的な暗号モデルにおいて、 LSHは衝突耐性、原像攻撃耐性、第二原像攻撃耐性を備えています。ここで、LSH構造のクエリ数です。^{[ 1 ]} LSH-256は、ステップ数が13以上の場合、既存のすべてのハッシュ関数攻撃に対して安全です。一方、LSH-512は、ステップ数が14以上の場合、安全です。セキュリティマージンとして機能するステップ数は、圧縮関数の50%であることに注意してください。^{[ 1 ]}${\displaystyle q<2^{n/2}}$ ${\displaystyle q<2^{n}}$ ${\displaystyle q}$

パフォーマンス

LSHは、様々なソフトウェアプラットフォームにおいてSHA-2/3よりも優れたパフォーマンスを発揮します。次の表は、複数のプラットフォームにおけるLSHの1MBメッセージハッシュの速度パフォーマンスを示しています

LSHの1MBメッセージハッシュ速度（サイクル/バイト）^{[ 1 ]}

プラットフォーム	P1 [ a ]	P2 [ b ]	P3 [ c ]	P4 [ d ]	P5 [ e ]	P6 [女性]	P7 [グラム]	P8 [ h ]
LSH-256-${\displaystyle n}$	3.60	3.86	5.26	3.89	11.17	15.03	15.28	14.84
LSH-512-${\displaystyle n}$	2.39	5.04	7.76	5.52	8.94	18.76	19.00	18.10

1. Intel Core i7-4770K @ 3.5GHz (Haswell)、Ubuntu 12.04 64ビット、GCC 4.8.1（「-m64 -mavx2 -O3」オプション付き）
2. Intel Core i7-2600K @ 3.40GHz (Sandy Bridge)、Ubuntu 12.04 64ビット、GCC 4.8.1（「-m64 -msse4 -O3」オプション付き）
3. Intel Core 2 Quad Q9550 @ 2.83GHz (Yorkfield)、Windows 7 32ビット、Visual Studio 2012
4. AMD FX-8350 @ 4GHz (Piledriver)、Ubuntu 12.04 64ビット、GCC 4.8.1（「-m64 -mxop -O3」オプション付き）
5. Samsung Exynos 5250 ARM Cortex-A15 @ 1.7GHz デュアルコア (Huins ACHRO 5250)、Android 4.1.1
6. Qualcomm Snapdragon 800 Krait 400 @ 2.26GHz クアッドコア (LG G2)、Android 4.4.2
7. Qualcomm Snapdragon 800 Krait 400 @ 2.3GHz クアッドコア (Samsung Galaxy S4)、Android 4.2.2
8. Qualcomm Snapdragon 400 Krait 300 @ 1.7GHz デュアルコア (Samsung Galaxy S4 mini)、Android 4.2.2

次の表は Haswell ベースのプラットフォームでの比較です。LSH は Intel Core i7-4770k @ 3.5 GHz クアッド コア プラットフォームで測定され、その他は Intel Core i5-4570S @ 2.9 GHz クアッド コア プラットフォームで測定されています。

Haswell CPUベースのプラットフォームにおけるLSH、SHA-2、SHA-3ファイナリストの速度ベンチマーク（サイクル/バイト）^{[ 1 ]}

アルゴリズム	メッセージサイズ（バイト）
	長さ	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 ベースのプラットフォームにおける LSH、SHA-2、SHA-3 ファイナリストの速度ベンチマーク (サイクル/バイト) ^{[ 1 ]}

アルゴリズム	メッセージサイズ（バイト）
	長さ	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 C1 96 3A 08 98 BA 1B 71 47 41

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

LSH-512-256("abc") = CD 89 23 10 53 26 02 33 2B 61 3F 1E C1 1A 69 62 FC A6 1E A0 9E CF FC D4 BC F7 58 58 D8 02 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）によって承認された暗号アルゴリズムの1つです。^{[ 3 ]}

標準化

LSHは以下の標準に含まれています。

• KS X 3262、ハッシュ関数LSH（韓国語）^{[ 4 ]}

参考文献

1. Kim, Dong-Chan; Hong, Deukjo; Lee, Jung-Keun; Kim, Woo-Hwan; Kwon, Daesung (2015). 「LSH：新しい高速セキュアハッシュ関数ファミリー」 .情報セキュリティと暗号学 - ICISC 2014.コンピュータサイエンス講義ノート. 第8949巻. Springer International Publishing. pp.  286– 313. doi : 10.1007/978-3-319-15943-0_18 . ISBN 978-3-319-15943-0.
2. "KISA 암호이용활성화 - 암호알고리즘 소스코드 " . seed.kisa.or.kr
3. “KISA 암호이용활성화 - 개요” .シード.kisa.or.kr。
4. 「韓国の規格と認証（韓国語）」。