Misplaced Pages

#244755

29-481: LSH may refer to: Computing [ edit ] LSH (hash function) , in cryptography lsh , a UNIX secure shell Locality-sensitive hashing , in algorithms Ship types [ edit ] Landing Ship Headquarters , UK Royal Navy Landing Ship, Heavy , a hull classification symbol , Australian and US Navy Other uses [ edit ] Lashio Airport , Myanmar (IATA: LSH) Legion of Super-Heroes ,

58-845: A {\displaystyle m_{a}} converts into a 32 t {\displaystyle 32t} -word array M = ( M [ 0 ] , … , M [ 32 t − 1 ] ) {\displaystyle {\textsf {M}}=(M[0],\ldots ,M[32t-1])} as follows. 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))} From

87-483: A fictional team in DC Comics Lysergic acid hydroxyethylamide , an alkaloid See also [ edit ] Lash (disambiguation) Lish (disambiguation) LSHS (disambiguation) Lush (disambiguation) Topics referred to by the same term [REDACTED] This disambiguation page lists articles associated with the title LSH . If an internal link led you here, you may wish to change

116-1222: A message block M ( i ) {\displaystyle {\textsf {M}}^{(i)}} . The first two sub-messages M 0 ( i ) = ( M 0 ( i ) [ 0 ] , … , M 0 ( i ) [ 15 ] ) {\displaystyle {\textsf {M}}_{0}^{(i)}=(M_{0}^{(i)}[0],\ldots ,M_{0}^{(i)}[15])} and M 1 ( i ) = ( M 1 ( i ) [ 0 ] , … , M 1 ( i ) [ 15 ] ) {\displaystyle {\textsf {M}}_{1}^{(i)}=(M_{1}^{(i)}[0],\ldots ,M_{1}^{(i)}[15])} are defined as follows. The next sub-messages { M j ( i ) = ( M j ( i ) [ 0 ] , … , M j ( i ) [ 15 ] ) } j = 2 N s {\displaystyle \{{\textsf {M}}_{j}^{(i)}=(M_{j}^{(i)}[0],\ldots ,M_{j}^{(i)}[15])\}_{j=2}^{N_{s}}} are generated as follows. Here τ {\displaystyle \tau }

145-1301: A temporary 16-word array set to the i {\displaystyle i} -th chaining variable CV ( i ) {\displaystyle {\textsf {CV}}^{(i)}} . The j {\displaystyle j} -th step function Step j {\displaystyle {\textrm {Step}}_{j}} having two inputs T {\displaystyle {\textsf {T}}} and M j ( i ) {\displaystyle {\textsf {M}}_{j}^{(i)}} updates T {\displaystyle {\textsf {T}}} , i.e., T ← Step j ( T , M j ( i ) ) {\displaystyle {\textsf {T}}\leftarrow {\textrm {Step}}_{j}\left({\textsf {T}},{\textsf {M}}_{j}^{(i)}\right)} . All step functions are proceeded in order j = 0 , … , N s − 1 {\displaystyle j=0,\ldots ,N_{s}-1} . Then one more MsgAdd {\displaystyle {\textrm {MsgAdd}}} operation by M N s ( i ) {\displaystyle {\textsf {M}}_{N_{s}}^{(i)}}

174-1787: Is a two-word mix function. Let X {\displaystyle X} and Y {\displaystyle Y} be words. The two-word mix function Mix j , l : W 2 → W 2 {\displaystyle {\textrm {Mix}}_{j,l}:{\mathcal {W}}^{2}\rightarrow {\mathcal {W}}^{2}} is defined as follows. {\displaystyle \qquad } X ← X ⊞ Y {\displaystyle X\leftarrow X\boxplus Y} ; X ← X ⋘ α j {\displaystyle \qquad X\leftarrow X^{\lll \alpha _{j}}} ; {\displaystyle \qquad } X ← X ⊕ S C j [ l ] {\displaystyle X\leftarrow X\oplus SC_{j}[l]} ; {\displaystyle \qquad } Y ← X ⊞ Y {\displaystyle Y\leftarrow X\boxplus Y} ; Y ← Y ⋘ β j {\displaystyle \qquad Y\leftarrow Y^{\lll \beta _{j}}} ; {\displaystyle \qquad } X ← X ⊞ Y {\displaystyle X\leftarrow X\boxplus Y} ; Y ← Y ⋘ γ l {\displaystyle \qquad Y\leftarrow Y^{\lll \gamma _{l}}} ; {\displaystyle \qquad } return X {\displaystyle X} , Y {\displaystyle Y} ; The two-word mix function Mix j , l {\displaystyle {\textrm {Mix}}_{j,l}}

203-437: Is as follows. In the following tables, all values are expressed in hexadecimal form. In this stage, the t {\displaystyle t} 32-word array message blocks { M ( i ) } i = 0 t − 1 {\displaystyle \{{\textsf {M}}^{(i)}\}_{i=0}^{t-1}} , which are generated from a message m {\displaystyle m} in

232-792: Is considered as a 4 w t {\displaystyle 4wt} -byte array m a = ( m [ 0 ] , … , m [ 4 w t − 1 ] ) {\displaystyle m_{a}=(m[0],\ldots ,m[4wt-1])} , where 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)}} for all 0 ≤ k ≤ ( 4 w t − 1 ) {\displaystyle 0\leq k\leq (4wt-1)} . The 4 w t {\displaystyle 4wt} -byte array m

261-430: Is defined as follows. The initial 8-word array constant SC 0 = ( S C 0 [ 0 ] , … , S C 0 [ 7 ] ) {\displaystyle {\textsf {SC}}_{0}=(SC_{0}[0],\ldots ,SC_{0}[7])} is defined in the following table. For 1 ≤ j < N s {\displaystyle 1\leq j<N_{s}} ,

290-495: Is initialized to the initialization vector IV {\displaystyle {\textsf {IV}}} . CV ( 0 ) [ l ] ← IV [ l ] {\displaystyle {\textsf {CV}}^{(0)}[l]\leftarrow {\textsf {IV}}[l]} ( 0 ≤ l ≤ 15 ) {\displaystyle (0\leq l\leq 15)} The initialization vector IV {\displaystyle {\textsf {IV}}}

319-2120: Is proceeded, and the ( i + 1 ) {\displaystyle (i+1)} -th chaining variable CV ( i + 1 ) {\displaystyle {\textsf {CV}}^{(i+1)}} is set to T {\displaystyle {\textsf {T}}} . The process of a compression function in detail is as follows. {\displaystyle \qquad } { M j ( i ) } j = 0 N s ← MsgExp ( M ( i ) ) {\displaystyle \{{\textsf {M}}_{j}^{(i)}\}_{j=0}^{N_{s}}\leftarrow {\textrm {MsgExp}}\left({\textsf {M}}^{(i)}\right)} {\displaystyle \qquad } T ← CV ( i ) {\displaystyle {\textsf {T}}\leftarrow {\textsf {CV}}^{(i)}} {\displaystyle \qquad } for j = 0 {\displaystyle j=0} to ( N s − 1 ) {\displaystyle (N_{s}-1)} do {\displaystyle \qquad } {\displaystyle \qquad } T ← Step j ( T , M j ( i ) ) {\displaystyle {\textsf {T}}\leftarrow {\textrm {Step}}_{j}\left({\textsf {T}},{\textsf {M}}_{j}^{(i)}\right)} {\displaystyle \qquad } end for {\displaystyle \qquad } CV ( i + 1 ) ← MsgAdd ( T , M N s ( i ) ) {\displaystyle {\textsf {CV}}^{(i+1)}\leftarrow {\textrm {MsgAdd}}\left({\textsf {T}},{\textsf {M}}_{N_{s}}^{(i)}\right)} {\displaystyle \qquad } return CV ( i + 1 ) {\displaystyle {\textsf {CV}}^{(i+1)}} Here

SECTION 10

#1732790316245

348-444: Is shown in the following figure. The bit rotation amounts α j {\displaystyle \alpha _{j}} , β j {\displaystyle \beta _{j}} , γ l {\displaystyle \gamma _{l}} used in Mix j , l {\displaystyle {\textrm {Mix}}_{j,l}} are shown in

377-824: Is shown in the following figure. The hash function LSH has the wide-pipe Merkle-Damgård structure with one-zeros padding. The message hashing process of LSH consists of the following three stages. {\displaystyle \qquad } One-zeros padding of m {\displaystyle m} {\displaystyle \qquad } Generation of t {\displaystyle t} message blocks { M ( i ) } i = 0 t − 1 {\displaystyle \{{\textsf {M}}^{(i)}\}_{i=0}^{t-1}} , where t = ⌈ | m | + 1 32 w ⌉ {\displaystyle t={\Big \lceil }{\frac {|m|+1}{32w}}{\Big \rceil }} from

406-485: Is the permutation over Z 16 {\displaystyle \mathbb {Z} _{16}} defined as follows. For two 16-word arrays X = ( X [ 0 ] , … , X [ 15 ] ) {\displaystyle {\textsf {X}}=(X[0],\ldots ,X[15])} and Y = ( Y [ 0 ] , … , Y [ 15 ] ) {\displaystyle {\textsf {Y}}=(Y[0],\ldots ,Y[15])} ,

435-544: Is the smallest integer not less than x {\displaystyle x} . Let m p = m 0 ‖ m 1 ‖ … ‖ m ( 32 w t − 1 ) {\displaystyle m_{p}=m_{0}\|m_{1}\|\ldots \|m_{(32wt-1)}} be the one-zeros-padded 32 w t {\displaystyle 32wt} -bit string of m {\displaystyle m} . Then m p {\displaystyle m_{p}}

464-498: The i {\displaystyle i} -th 32-word array message block. The message expansion function MsgExp {\displaystyle {\textrm {MsgExp}}} generates ( N s + 1 ) {\displaystyle (N_{s}+1)} 16-word array sub-messages { M j ( i ) } j = 0 N s {\displaystyle \{{\textsf {M}}_{j}^{(i)}\}_{j=0}^{N_{s}}} from

493-513: The i {\displaystyle i} -th 32-word message block M ( i ) {\displaystyle {\textsf {M}}^{(i)}} . And it returns the ( i + 1 ) {\displaystyle (i+1)} -th 16-word chaining variable CV ( i + 1 ) {\displaystyle {\textsf {CV}}^{(i+1)}} . Here and subsequently, W t {\displaystyle {\mathcal {W}}^{t}} denotes

522-444: The j {\displaystyle j} -th step function Step j {\displaystyle {\textrm {Step}}_{j}} of a compression function. Let M ( i ) = ( M ( i ) [ 0 ] , … , M ( i ) [ 31 ] ) {\displaystyle {\textsf {M}}^{(i)}=(M^{(i)}[0],\ldots ,M^{(i)}[31])} be

551-803: The j {\displaystyle j} -th step function Step j : W 16 × W 16 → W 16 {\displaystyle {\textrm {Step}}_{j}:{\mathcal {W}}^{16}\times {\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}} is as follows. 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))} The following figure shows

580-573: The 16-word array T = ( T [ 0 ] , … , T [ 15 ] ) {\displaystyle {\textsf {T}}=(T[0],\ldots ,T[15])} by mixing every two-word pair; T [ l ] {\displaystyle T[l]} and T [ l + 8 ] {\displaystyle T[l+8]} for ( 0 ≤ l < 8 ) {\displaystyle (0\leq l<8)} . For 0 ≤ j < N s {\displaystyle 0\leq j<N_{s}} ,

609-517: The following table. The j {\displaystyle j} -th 8-word array constant SC j = ( S C j [ 0 ] , … , S C j [ 7 ] ) {\displaystyle {\textsf {SC}}_{j}=(SC_{j}[0],\ldots ,SC_{j}[7])} used in Mix j , l {\displaystyle {\textrm {Mix}}_{j,l}} for 0 ≤ l < 8 {\displaystyle 0\leq l<8}

SECTION 20

#1732790316245

638-678: The hash function LSH are as follows. Let m {\displaystyle m} be a given bit string message. The given m {\displaystyle m} is padded by one-zeros, i.e., the bit ‘1’ is appended to the end of m {\displaystyle m} , and the bit ‘0’s are appended until a bit length of a padded message is 32 w t {\displaystyle 32wt} , where t = ⌈ ( | m | + 1 ) / 32 w ⌉ {\displaystyle t=\lceil (|m|+1)/32w\rceil } and ⌈ x ⌉ {\displaystyle \lceil x\rceil }

667-557: The initialization stage, are compressed by iteration of compression functions. The compression function CF : W 16 × W 32 → W 16 {\displaystyle {\textrm {CF}}:{\mathcal {W}}^{16}\times {\mathcal {W}}^{32}\rightarrow {\mathcal {W}}^{16}} has two inputs; the i {\displaystyle i} -th 16-word chaining variable CV ( i ) {\displaystyle {\textsf {CV}}^{(i)}} and

696-411: The link to point directly to the intended article. Retrieved from " https://en.wikipedia.org/w/index.php?title=LSH&oldid=1173887021 " Category : Disambiguation pages Hidden categories: Short description is different from Wikidata All article disambiguation pages All disambiguation pages LSH (hash function) The overall structure of the hash function LSH

725-943: The message addition function MsgAdd : W 16 × W 16 → W 16 {\displaystyle {\textrm {MsgAdd}}:{\mathcal {W}}^{16}\times {\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}} is defined as follows. 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])} The j {\displaystyle j} -th mix function Mix j : W 16 → W 16 {\displaystyle {\textrm {Mix}}_{j}:{\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}} updates

754-603: The mix function Mix j {\displaystyle {\textrm {Mix}}_{j}} proceeds as follows. ( 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 < 8 ) {\displaystyle (0\leq l<8)} Here Mix j , l {\displaystyle {\textrm {Mix}}_{j,l}}

783-1236: The padded bit string {\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)},{\textsf {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} The specifications of

812-1021: The set of all t {\displaystyle t} -word arrays for t ≥ 1 {\displaystyle t\geq 1} . The following four functions are used in a compression function: The overall structure of the compression function is shown in the following figure. In a compression function, the message expansion function MsgExp {\displaystyle {\textrm {MsgExp}}} generates ( N s + 1 ) {\displaystyle (N_{s}+1)} 16-word array sub-messages { M j ( i ) } j = 0 N s {\displaystyle \{{\textsf {M}}_{j}^{(i)}\}_{j=0}^{N_{s}}} from given M ( i ) {\displaystyle {\textsf {M}}^{(i)}} . Let T = ( T [ 0 ] , … , T [ 15 ] ) {\displaystyle {\textsf {T}}=(T[0],\ldots ,T[15])} be

841-911: The word array M {\displaystyle {\textsf {M}}} , we define the t {\displaystyle t} 32-word array message blocks { M ( i ) } i = 0 t − 1 {\displaystyle \{{\textsf {M}}^{(i)}\}_{i=0}^{t-1}} as follows. 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))} The 16-word array chaining variable CV ( 0 ) {\displaystyle {\textsf {CV}}^{(0)}}

#244755