LSH 는 대한민국이 PC, 스마트 디바이스 등 범용 CPU에서 무결성을 제공하기 위해 2014년에 개발한 해시 함수이다.[ 1] 대한민국 암호모듈 검증제도 검증대상 암호 알고리즘이며, 대한민국 국가 표준(KS X 3262)이다.
해시 함수 LSH의 전체 구조는 아래와 같다.
해시 함수 LSH 전체 구조 LSH는 입력 메시지에 대해 다음과 같은 세 단계를 거쳐 해시값을 출력한다.
초기화(Initialization): 입력 메시지를 메시지 블록 비트 길이의 배수가 되도록 패딩을 한 후, 이를 메시지 블록 단위로 분할한다. 그리고 연결 변수를 IV {\displaystyle {\textsf {IV}}} 압축(Compression): 32워드 배열 메시지 블록을 압축 함수의 입력으로 하여 얻은 출력값으로 연결 변수를 갱신하며, 이를 마지막 메시지 블록을 처리할 때까지 반복하여 메시지를 압축한다. 완료(Finalization): 압축 과정을 통해 연결 변수에 최종 저장된 값으로부터 n비트 길이의 해시 함수 출력값을 생성한다. function 해시 함수 LSHinput: 메시지 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} m {\displaystyle m} 32 w t {\displaystyle 32wt} 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)}} 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} 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)}} ( N s + 1 ) {\displaystyle (N_{s}+1)} M j ( i ) {\displaystyle {\textsf {M}}_{j}^{(i)}} ( 0 ≤ j ≤ N s ) {\displaystyle (0\leq j\leq N_{s})} T = ( T [ 0 ] , … , T [ 15 ] ) {\displaystyle {\textsf {T}}=(T[0],\ldots ,T[15])} CV ( i ) {\displaystyle {\textsf {CV}}^{(i)}} Step j {\displaystyle {\textrm {Step}}_{j}} M j ( i ) {\displaystyle {\textsf {M}}_{j}^{(i)}} T {\displaystyle {\textsf {T}}} T {\displaystyle {\textsf {T}}} ( 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])} ( N s + 1 ) {\displaystyle (N_{s}+1)} 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])} 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}} 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}} X = ( X [ 0 ] , … , X [ 15 ] ) {\displaystyle {\textsf {X}}=(X[0],\ldots ,X[15])}
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])} 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}}
LSH는 현재까지 알려진 모든 해시 함수 공격에 대해 안전하다. LSH는 ideal cipher model 하에서 쿼리의 수가 q < 2 n / 2 {\displaystyle q<2^{n/2}} q < 2 n {\displaystyle q<2^{n}} [ 1] [ 1]
LSH는 다양한 소프트웨어 플랫폼에서 SHA-2/3 대비 빠른 속도를 보유하고 있다. 아래 표는 다양한 플랫폼 상에서 LSH의 1MB 메시지에 대한 해시값 계산 속도를 보여준다.
LSH의 1MB 메시지에 대한 해시값 계산 속도 (cycles/byte)[ 1] Platform P1[ a] P2[ b] P3[ c] P4[ d] P5[ e] P6[ f] P7[ g] P8[ h] LSH-256- n {\displaystyle n} 3.60 3.86 5.26 3.89 11.17 15.03 15.28 14.84 LSH-512- n {\displaystyle n} 2.39 5.04 7.76 5.52 8.94 18.76 19.00 18.10
↑ Intel Core i7-4770K @ 3.5GHz (Haswell), Ubuntu 12.04 64-bit, GCC 4.8.1 with “-m64 -mavx2 -O3” ↑ Intel Core i7-2600K @ 3.40GHz (Sandy Bridge), Ubuntu 12.04 64-bit, GCC 4.8.1 with “-m64 -msse4 -O3” ↑ Intel Core 2 Quad Q9550 @ 2.83GHz (Yorkfield), Windows 7 32-bit, Visual studio 2012 ↑ AMD FX-8350 @ 4GHz (Piledriver), Ubuntu 12.04 64-bit, GCC 4.8.1 with “-m64 -mxop -O3” ↑ Samsung Exynos 5250 ARM Cortex-A15 @ 1.7GHz dual core (Huins ACHRO 5250), Android 4.1.1 ↑ Qualcomm Snapdragon 800 Krait 400 @ 2.26GHz quad core (LG G2), Android 4.4.2 ↑ Qualcomm Snapdragon 800 Krait 400 @ 2.3GHz quad core (Samsung Galaxy S4), Android 4.2.2 ↑ Qualcomm Snapdragon 400 Krait 300 @ 1.7GHz dual core (Samsung Galaxy S4 mini), Android 4.2.2 아래 표는 Haswell 기반 플랫폼에서 LSH와 몇 종류의 해시 함수 성능을 비교한 것이다. LSH는 Intel Core i7-4770k @ 3.5 GHz quad core 플랫폼에서, 다른 해시 함수는 Intel Core i5-4570S @ 2.9 GHz quad core 플랫폼에서 성능을 측정한 결과이다.
Speed benchmark of LSH, SHA-2 and the SHA-3 finalists at the platform based on Haswell CPU (cycles/byte)[ 1] Algorithm Message size in bytes long 4,096 1,536 576 64 8 LSH-256-256 3.60 3.71 3.90 4.08 8.19 65.37 Skein-512-256 5.01 5.58 5.86 6.49 13.12 104.50 Blake-256 6.61 7.63 7.87 9.05 16.58 72.50 Grøstl-256 9.48 10.68 12.18 13.71 37.94 227.50 Keccak-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 Skein-512-512 4.67 5.51 5.80 6.44 13.59 108.25 Blake-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 Grøstl-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 Keccak-512 16.36 17.86 18.46 20.35 21.56 171.88
아래 표는 Samsung Exynos 5250 ARM Cortex-A15 @ 1.7 GHz dual core 플랫폼에서 LSH와 몇 종류의 해시 함수 성능을 비교한 것이다.
Speed benchmark of LSH, SHA-2 and the SHA-3 finalists at the platform based on Exynos 5250 ARM Cortex-A15 CPU (cycles/byte)[ 1] Algorithm Message size in bytes long 4,096 1,536 576 64 8 LSH-256-256 11.17 11.53 12.16 12.63 22.42 192.68 Skein-512-256 15.64 16.72 18.33 22.68 75.75 609.25 Blake-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 Keccak-256 36.03 38.01 40.54 48.13 125.00 1000.62 Grøstl-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 Blake-512 13.46 14.82 16.88 20.98 77.53 623.62 Skein-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 Keccak-512 63.31 64.59 67.85 77.21 121.28 968.00 Grøstl-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
C, Java, Python으로 구현된 LSH의 배포용 소스코드는 KISA 암호이용활성화 웹페이지에서 다운받을 수 있다.[ 2]
LSH는 2019년 대한민국 암호모듈 검증제도 검증대상 암호알고리즘 목록에 포함되었다.[ 3]
LSH는 아래 표준으로 제정되어 있다.
↑ 가 나 다 라 마 바 Kim, Dong-Chan; Hong, Deukjo; Lee, Jung-Keun; Kim, Woo-Hwan; Kwon, Daesung (2014). 〈LSH: A New Fast Secure Hash Function Family〉. 《International Conference on Information Security and Cryptology - ICISC 2014》. Lecture Notes in Computer Science 8949 . Springer/Heidelberg. 286–313쪽. ↑ “LSH 소스코드” . ↑ “암호모듈검증” . ↑ “e-나라 표준인증” .
![{\displaystyle m_{a}=(m[0],\ldots ,m[4wt-1])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cbc48d8752f23db915bd9326469042c7c23626d2)
![{\displaystyle m[k]=m_{8k}\|m_{(8k+1)}\|\ldots \|m_{(8k+7)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/00194b743f9909d356a205887738da5349b7249d)
![{\displaystyle {\textsf {M}}=(M[0],\ldots ,M[32t-1])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bdbfb053f15842258c6a818f02fee38e61136130)
![{\displaystyle M[s]\leftarrow m[ws/8+(w/8-1)]\|\ldots \|m[ws/8+1]\|m[ws/8]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ff942009f93b5f2bf938904afa8d1c87c1df093e)
![{\displaystyle {\textsf {M}}^{(i)}\leftarrow (M[32i],M[32i+1],\ldots ,M[32i+31])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9c89cafb0da4dc3e59e17a999d72b66aa8fb15b9)
![{\displaystyle {\textsf {CV}}^{(0)}[l]\leftarrow {\textsf {IV}}[l]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d00f73c945226f234883521f4244aec7d19585b3)
![{\displaystyle {\textsf {IV}}[0]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e999e9f3741fbdf52af9cc4a4d9be0b6ccf6945f)
![{\displaystyle {\textsf {IV}}[1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/19ef984c6c0763a1541d89acf2fa95341b570fa7)
![{\displaystyle {\textsf {IV}}[2]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/03c25b70ee80852f78587b5154f3ddad3a9e007a)
![{\displaystyle {\textsf {IV}}[3]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5d723c75229cca886dc8219503ca59f941b57e34)
![{\displaystyle {\textsf {IV}}[4]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c027deaf01f0c4b67a9749d6ff1def884912c858)
![{\displaystyle {\textsf {IV}}[5]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0cd23ddaf854ce9b457cd9c5d0da3efa6aae8274)
![{\displaystyle {\textsf {IV}}[6]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4ed177acf98ade6005bbc3598aa9ad09a21f3be6)
![{\displaystyle {\textsf {IV}}[7]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6bd8b8e7594b13b83421f693bc44bc9a4ef862bf)
![{\displaystyle {\textsf {IV}}[8]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f291543f56da1d3c98a207c145214248d5417d0c)
![{\displaystyle {\textsf {IV}}[9]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ddebb4dacc2f97b7603f883187c8d2bcbc43c860)
![{\displaystyle {\textsf {IV}}[10]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bb7dbd6006744b44ffd77084d528da5588bdda63)
![{\displaystyle {\textsf {IV}}[11]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ae7f16181346c9d69ee705ea0858c9102ab54e2d)
![{\displaystyle {\textsf {IV}}[12]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2a2bd2ddfbeace72719eed88c2eea81ff3904c80)
![{\displaystyle {\textsf {IV}}[13]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2361328bc13a1f6fe820a015a2ee0b2220d28d57)
![{\displaystyle {\textsf {IV}}[14]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4897271813f7c994d55ddd614305fc32cac0cbee)
![{\displaystyle {\textsf {IV}}[15]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/99235ba6fce415b369c060c2381097b6978b52a5)
![{\displaystyle {\textsf {T}}=(T[0],\ldots ,T[15])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e4e09d90a1fc91872834fcd3db926cdf0232846f)
![{\displaystyle {\textsf {M}}^{(i)}=(M^{(i)}[0],\ldots ,M^{(i)}[31])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/35b851ae62b4ce876b5a95aae53bf7832d9ceba5)
![{\displaystyle {\textsf {M}}_{0}^{(i)}\leftarrow (M^{(i)}[0],M^{(i)}[1],\ldots ,M^{(i)}[15])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8bc56dd40f2cf9561c310e1cb9266c02c0d6a5ab)
![{\displaystyle {\textsf {M}}_{1}^{(i)}\leftarrow (M^{(i)}[16],M^{(i)}[17],\ldots ,M^{(i)}[31])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/79c190f11728ea49c9f324944be1d4c878c53227)
![{\displaystyle {\textsf {M}}_{j}^{(i)}[l]\leftarrow {\textsf {M}}_{j-1}^{(i)}[l]\boxplus {\textsf {M}}_{j-2}^{(i)}[\tau (l)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f9b4426630f63a02dd6235065ece3cc5a0833663)
![{\displaystyle {\textsf {X}}=(X[0],\ldots ,X[15])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9013d421817a8cf5117819d4484066cc9adef1b5)
![{\displaystyle {\textsf {Y}}=(Y[0],\ldots ,Y[15])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2525d8d1074a2047bd22fc53aad1f74c93e3700e)
![{\displaystyle {\textrm {MsgAdd}}({\textsf {X}},{\textsf {Y}}):=(X[0]\oplus Y[0],\ldots ,X[15]\oplus Y[15])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/116a4f232b0e499dec64cad7c873fd5feb163043)
![{\displaystyle T[l]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b1aa20a1c0598137a811b490168efae37eb82058)
![{\displaystyle T[l+8]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a217b6395baa6d31045da231e60e09deb3ac56aa)
![{\displaystyle (T[l],T[l+8])\leftarrow {\textrm {Mix}}_{j,l}(T[l],T[l+8])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bcbfbb4b4c4dae0c9b3562bd5a5632c078e536c3)
![{\displaystyle X\leftarrow X\oplus SC_{j}[l]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/81303461fe349f41536a9de3b97568351a29bdee)
![{\displaystyle {\textsf {SC}}_{j}=(SC_{j}[0],\ldots ,SC_{j}[7])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/efecbf19a2f53ca2817f56703e737cfd9886f68b)
![{\displaystyle SC_{j}[l]\leftarrow SC_{j-1}[l]\boxplus SC_{j-1}[l]^{\lll 8}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/26a0a4dc7a14e437f7ab4c709adc9a98fbc4b63e)
![{\displaystyle SC_{0}[0]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/68d1bf7cd02ea4ce227fad05bee1ef10edf21c0d)
![{\displaystyle SC_{0}[1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/53155ed01cf05325fc1859cf17d1cedf334cf95c)
![{\displaystyle SC_{0}[2]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5bab5db617e31e28457e43edfcbb76dbcf623df3)
![{\displaystyle SC_{0}[3]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/73cd303774e917e32fb6b20b1282a69c69ad47da)
![{\displaystyle SC_{0}[4]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6518b1bf1a8a2d3539ad10dcde5ad1762d1c8d30)
![{\displaystyle SC_{0}[5]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3f29498127cd8b547101780ac7d6faebc5e40a86)
![{\displaystyle SC_{0}[6]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/63b1c7d4c29c8ce552a4c9c8c051ff647c86f425)
![{\displaystyle SC_{0}[7]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d8390e42cb325cfd246dc5fbbad160fcd6503e1d)
![{\displaystyle {\textrm {WordPerm}}({\textsf {X}}):=(X[\sigma (0)],\ldots ,X[\sigma (15)])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/435885d328f4ac7724b8eb19003047b746d71ac6)
![{\displaystyle {\textsf {CV}}^{(t)}=(CV^{(t)}[0],\ldots ,CV^{(t)}[15])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8bf75c3ec18bf9366032be2c289a4e1b7ba01b35)
![{\displaystyle {\textsf {H}}=(H[0],\ldots ,H[7])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d9ff06158214fe226ae3568f0177c850ac93485c)
![{\displaystyle {\textsf {h}}_{\textsf {b}}=(h_{b}[0],\ldots ,h_{b}[w-1])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3871dbee4168d6e037d2556abf84519327990cca)
![{\displaystyle H[l]\leftarrow CV^{(t)}[l]\oplus CV^{(t)}[l+8]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/524ccce489c981495f6deb5314c3b041552b560c)
![{\displaystyle h_{b}[s]\leftarrow H[\lfloor 8s/w\rfloor ]_{[7:0]}^{\ggg (8s\mod w)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5eddf9108c60a66ddbb911c2ac494f9d5f3be00a)
![{\displaystyle h\leftarrow (h_{b}[0]\|\ldots \|h_{b}[w-1])_{[0:n-1]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/79cb13674ed90511ce660a290d19af365883be48)
![{\displaystyle X_{[r:s]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a5528ba03773c5ae88d735b1dd9d3687f4979151)
![{\displaystyle x_{[r:s]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4cfb9f6af51f92ca78f9041a73b269025311d409)
