Secure hash algorithm
Secure hash algorithm буюу SHA-г NIST компаниас хөгжүүлэгдсэн. 1993 онд SHA-г Federal Information Processing Standard (FIPS)-с нийтэлсэн анхны хувилбар нь 160 битийн хаш функц юм. Secure hash algorithm нь message authentication, түлхүүр үүсгэх функцууд ба адилтган танин баталгаажуулахад ашиглагдана. Хаш алгоритм нь дурын битийн уртыг тогтмол битийн урттай болгон гаргадаг функц. SHA нь SHA-0, SHA-1, SHA-2, SHA-3 гэсэн хувилбаруудтай. SHA-n гэдэг тэмдэглэгээ нь хэш функцийн үр дүнд n-битийн утга гарна гэдгийг илэрхийлнэ. Харин SHA-1-ийн хувьд NIST FIPS PUB 180-1-д анх тодорхойлсны дагуу 160-битийн утга гаргана.
SHA төрөл
SHA-0:
1993 онд SHA нэрээр нийтэд хэвлэгдсэн 64 бит Хаш функцийн анхны хувилбар юм. Үүнийг retronym хэмээн нэрийддэг. 160 битийн хаш утгыг ашигладаг.
SHA-1:
160 бит Хаш функц. NSA-с тоон гарын үсгийн алгоритмийн хэсэг болгож загварчилсан. SHA-1 нь аюулгүй байдлын найдваржилтаар хангалтгүйд тооцогдох болсон тул ашиглахыг татгалз хэмээх болсон. Оролтонд нь 264 битээс бага мессеж, гаралтанд нь 160 битийн мессеж гарна. Энэхүү стандартын хүрээнд аюулгүй байдлын ажиллагааны турш SHA-384 ба SHA-512 алгоритмууд нь аюулгүй байдлын хамгаалалтаар хамгийн өндөрт байдаг.
Хөгжүүлэгчид
SHA1 нь MD4 болон MD5 алгоритмын зарчим дээр суурьлан ашиглан MIT дизайнер L.Rivest адил зарчим дээр суурилсан байдлаар илүү уламжлалт байдалтайгаар хөгжүүлсэн юм. Алгоритмийн анхны загварыг Америкийн нэгдсэн улсын NIST буюу стандарт технологийн үндэсний хүрээлэнгээс гаргасан байдаг. Энэхүү хувилбарыг FIPS PUB 180 хэмээн 1993 онд анх үүсгэсэн.
SHA1 алгоритмийн нэг давталтын цикл
Энэ нь SHA-1 хэрэгжүүлэх хэш функцийг шахах үйл ажиллагаа санаан дээр барьсан. Орц шахалт үйл ажиллагаа 512 битийн зурвас блок урт, өмнөх блок албан тушаалын гаралт нь юм. Гаралт Энэ хүртэл бүх блок хэш утга юм. Өөрөөр хэлбэл, хэш нэгж тэнцүү . Бүх мэдээний хэш утга нь сүүлийн блок үр дүн юм.
Жишээ болон pseudocode
SHA1(Өгөгдөл: "The quick brown fox jumps over the lazy dog") 16-тын утгаар: 2fd4e1c67a2d28fced849ee1bb76e7391b93eb12 Base64 бинари ASCII кодчилолын утгаар: L9ThxnotKPzthJ7hu3bnORuT6xI=
Энэхүү "The quick brown fox jumps over the lazy dog" гэсэн өгөгдлийг SHA функцаар encryption хийхэд хэдэн битийн утга орж ирж байгаа нь чухал биш. Жишээ нь "The quick brown fox jumps over the lazy dog" өгөдлийг 160 битийн утгаар 81 хэмжээтэй болгон өөрчилөн гаргаж байна.
SHA1(Өгөгдөл: "The quick brown fox jumps over the lazy cog") 16-тын утгаар: de9f2c7fd25e1b3afad3e85a0bd17d9b100db4b3 Base64 бинари ASCII кодчилолын утгаар: 3p8sf9JeGzr60+haC9F9mxANtLM=
Энэхүү хаш функцийн утга нь тэг буюу ямарч өгөгдөлгүй байна: SHA1("") 16-тын утгаар: da39a3ee5e6b4b0d3255bfef95601890afd80709 Base64 бинари ASCII кодчилолын утгаар: 2jmj7l5rSw0yVb/vlWAYkK/YBwk=
SHA-1 pseudocode
Тэмдэглэл 1: Бүх хувьсагчууд нь 32 битийн тоон хэмжээтэй ба бусад тооцоололд 232 зэрэгтийн модулаар бодогдоно.
ml, мессежний урт, аль аль нь 64 бит, ба
hh, тэр мессежийн задаргаа, 16 битийн тооцоолол юм.
Тэмдэглэл 2: Том endian нь бүх pseudo-д тогтмол байна.
Үг бүрийн доторх хамгийн чухал байт нь хамгийн зүүн талын байтын байрлалд хадгалагдаж байна.
Хувьсагчуудыг тохируулах:
h0 = 0x67452301 h1 = 0xEFCDAB89 h2 = 0x98BADCFE h3 = 0x10325476 h4 = 0xC3D2E1F0
ml = мессежийн уртыг битээр (олон битийн үргэлжлэл нь тоон утгатай байна).
Pre-processing: 8 битийн олон өгөгдлүүдийг 0х80 гэх мессежийн урттай болгох гэх мэтчилэн 1 битийг мессежийн утганд нэмсээр байна.
0 ≤ k < 512 bits '0', тухайн мессежний өгөгдлийн урт нэмнэ. энэхүү утгаар нэмнэгдэнэ −64 ≡ 448 (mod 512)
Нэмнэ ml, 64-bit-ийн big-endian integer хувьсагч нэмэгдэнэ. Тиймээс нийт урт нь 512 битээр урт байна.
Дараагийн 512 битийн дараагийн процесс: 512 битийн мэдээ болгон засварлана. Хэсэг бүрт:
32-bit big-endian өгөгдлийг 16-тын тооллын системд w[i], 0 ≤ i ≤ 15
8-тын 32 бит үг нь 16-тын 32 бит үг болон сунгагдана.
for i from 16 to 79
w[i] = (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) leftrotate 1
Хаш утгын хэсгүүдийн хуваалт: a = h0 b = h1 c = h2 d = h3 e = h4
Main loop:[44][2]
for i from 0 to 79
if 0 ≤ i ≤ 19 then
f = (b and c) or ((not b) and d)
k = 0x5A827999
else if 20 ≤ i ≤ 39
f = b xor c xor d
k = 0x6ED9EBA1
else if 40 ≤ i ≤ 59
f = (b and c) or (b and d) or (c and d)
k = 0x8F1BBCDC
else if 60 ≤ i ≤ 79
f = b xor c xor d
k = 0xCA62C1D6
temp = (a leftrotate 5) + f + e + k + w[i]
e = d
d = c
c = b leftrotate 30
b = a
a = temp
Хаш функцийн хүсэлтүүд дээр нэмэгдэнэ. h0 = h0 + a h1 = h1 + b h2 = h2 + c h3 = h3 + d h4 = h4 + e
160 битийн хаш утга нь (big-endian) урт hh = (h0 leftshift 128) or (h1 leftshift 96) or (h2 leftshift 64) or (h3 leftshift 32) or h4
hh тооны мессежний зардаргаа нь 16тын тооллын системд бичигдэж болно. Гэвч ихэвчлэн ASCII кодчиллоор бичигдсэн байдаг.
Тогтмол утгуудыг ашиглаж сонгосн байна: K тооны утга нь тогтмол 230 байх бөгөөд к тоо нь 2, 3, 5, 10-ын зэрэгтүүд байна. Эхний эхлүүлж буй утгууд нь h0 болон h3 байх бөгөөд MD5 алгоритм ба тав дахь нь T4 тэй төстэй байна.
Харин анхны FIPS PUB 180-1 тооцоолол нь боловсрууланд дараах тэнцэх илэрхийллүүд дээр гол давталтыг е тоог тооцоолоход хэрэглэж болно:
Bitwise b хянаж с болон d утгуудыг сонсоно
(0 ≤ i ≤ 19): f = d xor (b and (c xor d)) (alternative 1)
(0 ≤ i ≤ 19): f = (b and c) xor ((not b) and d) (alternative 2)
(0 ≤ i ≤ 19): f = (b and c) + ((not b) and d) (alternative 3)
(0 ≤ i ≤ 19): f = vec_sel(d, c, b) (alternative 4)
Bitwise majority функц. (40 ≤ i ≤ 59): f = (b and c) or (d and (b or c)) (alternative 1) (40 ≤ i ≤ 59): f = (b and c) or (d and (b xor c)) (alternative 2) (40 ≤ i ≤ 59): f = (b and c) + (d and (b xor c)) (alternative 3) (40 ≤ i ≤ 59): f = (b and c) xor (b and d) xor (c and d) (alternative 4) (40 ≤ i ≤ 59): f = vec_sel(c, b, c xor d) (alternative 5) Макс Zolotukhin мөн харуулж байгаа бөгөөд 32-79 хоорондох утгыг тооцох нь:
w[i] = (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) leftrotate 1 Сольж болно:
w[i] = (w[i-6] xor w[i-16] xor w[i-28] xor w[i-32]) leftrotate 2
Энэ өөрчлөлтийг 64 битийн бүх operand-ууд хадгалж байдаг. үүний утгыг w[i] болон w[3], болон SIMD хөгжүүлэлтийг x86 SSE-с тайлбарладаг.
SHA-2:
Өөр өөр блокуудтай 2 ижил хаш функцийн бүлэг юм. SHA-256, SHA-512 SHA-256 нь SHA-1 ба MD4, MD5-н аргаар үйл ажиллагаа явуулдаг. SHA-256 шахалтын функц нь 256 битийн завсрын хаш утга ба 512 битийн мессежийн блок дээр ажилладаг. Энэ нь үндсэндээ 256 битийн блок шифрлэлтийн алгоритм юм. SHA-224, SHA-324, SHA-512/224 ба SHA-512/256 гэсэн тус бүрийн стандарт байдаг. Эдгээрийг NSA зохион бүтээсэн. 2 гол бүрэлдэхүүн хэсэгтэй. 1. SHA-256 шахалтын функц 2. SHA-256 мессежний хуваарь SHA-256 нь 32 битийн үсэгт ашиглагдана. Доорх тэмдэглэгээг ашиглана.
SHA-512 шахалтын функц нь 512 битийн хаш утга ба 1024 битийн мессежийн блок дээр ажилладаг. Энэ нь үндсэндээ 512 битийн блок шифрлэлт юм.
SHA-2 төрлүүдийн жишээ
String төрлийн хаш функцийн утгууд:
SHA224("")
0x d14a028c2a3a2bc9476102bb288234c415a2b01f828ea62ac5b3e42f
SHA256("")
0x e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855
SHA384("")
0x 38b060a751ac96384cd9327eb1b1e36a21fdb71114be07434c0cc7bf63f6e1da274edebfe76f65fbd51ad2f14898b95b
SHA512("")
0x cf83e1357eefb8bdf1542850d66d8007d620e4050b5715dc83f4a921d36ce9ce47d0d13c5d85f2b0ff8318d2877eec2f63b931bd47417a81a538327af927da3e
SHA512/224("")
0x 6ed0dd02806fa89e25de060c19d3ac86cabb87d6a0ddd05c333b84f4
SHA512/256("")
0x c672b8d1ef56ed28ab87c3622c5114069bdd3ad7b8f9737498d0c01ecef0967a
SHA224("The quick brown fox jumps over the lazy dog")
0x 730e109bd7a8a32b1cb9d9a09aa2325d2430587ddbc0c38bad911525
SHA224("The quick brown fox jumps over the lazy dog.")
0x 619cba8e8e05826e9b8c519c0a5c68f4fb653e8a3d8aa04bb2c8cd4c
Pseudocode
Note 1: All variables are 32 bit unsigned integers and addition is calculated modulo 232 Note 2: For each round, there is one round constant k[i] and one entry in the message schedule array w[i], 0 ≤ i ≤ 63 Note 3: The compression function uses 8 working variables, a through h Note 4: Big-endian convention is used when expressing the constants in this pseudocode,
and when parsing message block data from bytes to words, for example, the first word of the input message "abc" after padding is 0x61626380
Initialize hash values: (first 32 bits of the fractional parts of the square roots of the first 8 primes 2..19): h0 := 0x6a09e667 h1 := 0xbb67ae85 h2 := 0x3c6ef372 h3 := 0xa54ff53a h4 := 0x510e527f h5 := 0x9b05688c h6 := 0x1f83d9ab h7 := 0x5be0cd19
Initialize array of round constants: (first 32 bits of the fractional parts of the cube roots of the first 64 primes 2..311): k[0..63] :=
0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5, 0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174, 0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da, 0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967, 0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85, 0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070, 0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3, 0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
Pre-processing: append the bit '1' to the message append k bits '0', where k is the minimum number >= 0 such that the resulting message
length (modulo 512 in bits) is 448.
append length of message (without the '1' bit or padding), in bits, as 64-bit big-endian integer
(this will make the entire post-processed length a multiple of 512 bits)
Process the message in successive 512-bit chunks: break message into 512-bit chunks for each chunk
create a 64-entry message schedule array w[0..63] of 32-bit words (The initial values in w[0..63] don't matter, so many implementations zero them here) copy chunk into first 16 words w[0..15] of the message schedule array
Extend the first 16 words into the remaining 48 words w[16..63] of the message schedule array:
for i from 16 to 63
s0 := (w[i-15] rightrotate 7) xor (w[i-15] rightrotate 18) xor (w[i-15] rightshift 3)
s1 := (w[i-2] rightrotate 17) xor (w[i-2] rightrotate 19) xor (w[i-2] rightshift 10)
w[i] := w[i-16] + s0 + w[i-7] + s1
Initialize working variables to current hash value: a := h0 b := h1 c := h2 d := h3 e := h4 f := h5 g := h6 h := h7
Compression function main loop:
for i from 0 to 63
S1 := (e rightrotate 6) xor (e rightrotate 11) xor (e rightrotate 25)
ch := (e and f) xor ((not e) and g)
temp1 := h + S1 + ch + k[i] + w[i]
S0 := (a rightrotate 2) xor (a rightrotate 13) xor (a rightrotate 22)
maj := (a and b) xor (a and c) xor (b and c)
temp2 := S0 + maj
h := g
g := f
f := e
e := d + temp1
d := c
c := b
b := a
a := temp1 + temp2
Add the compressed chunk to the current hash value: h0 := h0 + a h1 := h1 + b h2 := h2 + c h3 := h3 + d h4 := h4 + e h5 := h5 + f h6 := h6 + g h7 := h7 + h
Produce the final hash value (big-endian): digest := hash := h0 append h1 append h2 append h3 append h4 append h5 append h6 append h7
SHA512 болон SHA256 нь бүтцийн хувьд ижилхэн байна. Мэдээ нь 1024 битэд хуваагдсан байна. Эхний утгууд 64 битийн тогтмолууд бөгөөд цааш 64 болон 80 үе шаттай байна. Мэдээний урт нь 64 32 битийн ялгаатай массивт 80 64 битийн үгсийг 16-63 болон 16-79 хүртэл хоорон байдаг. Тойргийн 2..409 нь эхний 80 primes дээр үндэслэсэн байдаг. Тооцооллын хувьд тухайн үгийн хэмжээ 64 бит урттай байна.
SHA-512 initial hash values (in big-endian):
h[0..7] := 0x6a09e667f3bcc908, 0xbb67ae8584caa73b, 0x3c6ef372fe94f82b, 0xa54ff53a5f1d36f1,
0x510e527fade682d1, 0x9b05688c2b3e6c1f, 0x1f83d9abfb41bd6b, 0x5be0cd19137e2179
SHA-512 round constants:
k[0..79] := [ 0x428a2f98d728ae22, 0x7137449123ef65cd, 0xb5c0fbcfec4d3b2f, 0xe9b5dba58189dbbc, 0x3956c25bf348b538,
0x59f111f1b605d019, 0x923f82a4af194f9b, 0xab1c5ed5da6d8118, 0xd807aa98a3030242, 0x12835b0145706fbe,
0x243185be4ee4b28c, 0x550c7dc3d5ffb4e2, 0x72be5d74f27b896f, 0x80deb1fe3b1696b1, 0x9bdc06a725c71235,
0xc19bf174cf692694, 0xe49b69c19ef14ad2, 0xefbe4786384f25e3, 0x0fc19dc68b8cd5b5, 0x240ca1cc77ac9c65,
0x2de92c6f592b0275, 0x4a7484aa6ea6e483, 0x5cb0a9dcbd41fbd4, 0x76f988da831153b5, 0x983e5152ee66dfab,
0xa831c66d2db43210, 0xb00327c898fb213f, 0xbf597fc7beef0ee4, 0xc6e00bf33da88fc2, 0xd5a79147930aa725,
0x06ca6351e003826f, 0x142929670a0e6e70, 0x27b70a8546d22ffc, 0x2e1b21385c26c926, 0x4d2c6dfc5ac42aed,
0x53380d139d95b3df, 0x650a73548baf63de, 0x766a0abb3c77b2a8, 0x81c2c92e47edaee6, 0x92722c851482353b,
0xa2bfe8a14cf10364, 0xa81a664bbc423001, 0xc24b8b70d0f89791, 0xc76c51a30654be30, 0xd192e819d6ef5218,
0xd69906245565a910, 0xf40e35855771202a, 0x106aa07032bbd1b8, 0x19a4c116b8d2d0c8, 0x1e376c085141ab53,
0x2748774cdf8eeb99, 0x34b0bcb5e19b48a8, 0x391c0cb3c5c95a63, 0x4ed8aa4ae3418acb, 0x5b9cca4f7763e373,
0x682e6ff3d6b2b8a3, 0x748f82ee5defb2fc, 0x78a5636f43172f60, 0x84c87814a1f0ab72, 0x8cc702081a6439ec,
0x90befffa23631e28, 0xa4506cebde82bde9, 0xbef9a3f7b2c67915, 0xc67178f2e372532b, 0xca273eceea26619c,
0xd186b8c721c0c207, 0xeada7dd6cde0eb1e, 0xf57d4f7fee6ed178, 0x06f067aa72176fba, 0x0a637dc5a2c898a6,
0x113f9804bef90dae, 0x1b710b35131c471b, 0x28db77f523047d84, 0x32caab7b40c72493, 0x3c9ebe0a15c9bebc,
0x431d67c49c100d4c, 0x4cc5d4becb3e42b6, 0x597f299cfc657e2a, 0x5fcb6fab3ad6faec, 0x6c44198c4a475817]
SHA-512 Sum & Sigma:
S0 := (a rightrotate 28) xor (a rightrotate 34) xor (a rightrotate 39) S1 := (e rightrotate 14) xor (e rightrotate 18) xor (e rightrotate 41)
s0 := (w[i-15] rightrotate 1) xor (w[i-15] rightrotate 8) xor (w[i-15] rightshift 7) s1 := (w[i-2] rightrotate 19) xor (w[i-2] rightrotate 61) xor (w[i-2] rightshift 6) SHA-384 is identical to SHA-512, except that:
the initial hash values h0 through h7 are different (taken from the 9th through 16th primes), and the output is constructed by omitting h6 and h7. SHA-384 initial hash values (in big-endian):
h[0..7] := 0xcbbb9d5dc1059ed8, 0x629a292a367cd507, 0x9159015a3070dd17, 0x152fecd8f70e5939,
0x67332667ffc00b31, 0x8eb44a8768581511, 0xdb0c2e0d64f98fa7, 0x47b5481dbefa4fa4
SHA-3:
Одоо ажиллаж буй NIST hash competition функцийн хувилбарт санал болгосон хаш функцийн стандарт. 2012 оны 10 сард SHA-3 гэсэн шинэ стандартыг бий болгон сонгосон. Тоон гарын үсэг болон хаш дээр суурилсан MACs, PRFs, RNGs, KDFs-г дэмждэг. Аюулгүй байдлын хувьд маш өндөр нарийвчлалтай. SHA-3 нь SHA3-224, SHA3-256, SHA3-384 ба SHA3-512 гэсэн 4 криптографын хаш функцээс бүрдэнэ. 2 гол бүрэлдэхүүн хэсэгийг тайлбарлья. 1 SHA-512 шахалтын функц ба SHA-512 мессежийн хуваарь Энэ нь доорх тэмдэглэгээг ашиглана.
SHA-512 нь 64 битийн үсэгт ашиглагдана.
Examples of SHA-3 variants
SHA3-224("")
6b4e03423667dbb73b6e15454f0eb1abd4597f9a1b078e3f5b5a6bc7
SHA3-256("")
a7ffc6f8bf1ed76651c14756a061d662f580ff4de43b49fa82d80a4b80f8434a
SHA3-384("")
0c63a75b845e4f7d01107d852e4c2485c51a50aaaa94fc61995e71bbee983a2ac3713831264adb47fb6bd1e058d5f004
SHA3-512("")
a69f73cca23a9ac5c8b567dc185a756e97c982164fe25859e0d1dcc1475c80a615b2123af1f5f94c11e3e9402c3ac558f500199d95b6d3e301758586281dcd26
SHAKE128("", 256)
7f9c2ba4e88f827d616045507605853ed73b8093f6efbc88eb1a6eacfa66ef26
SHAKE256("", 512)
46b9dd2b0ba88d13233b3feb743eeb243fcd52ea62b81b82b50c27646ed5762fd75dc4ddd8c0f200cb05019d67b592f6fc821c49479ab48640292eacb3b7c4be
Changing a single bit results in each bit in the output to change with 50% probability, demonstrating an avalanche effect:
SHAKE128("The quick brown fox jumps over the lazy dog", 256)
f4202e3c5852f9182a0430fd8144f0a74b95e7417ecae17db0f8cfeed0e3e66e
SHAKE128("The quick brown fox jumps over the lazy dof", 256)
853f4538be0db9621a6cea659a06c1107b1f83f02b13d18297bd39d7411cf10c
The block permutation
This is defined for any power-of-two word size, w = 2ℓ bits. The main SHA-3 submission uses 64-bit words, ℓ = 6.
The state can be considered to be a 5 × 5 × w array of bits. Let a[i][ j][k] be bit (5i + j) × w + k of the input, using a little-endian bit numbering convention and row-major indexing. I.e. i selects the column, j the row, and k the bit.
Index arithmetic is performed modulo 5 for the first two dimensions and modulo w for the third. The basic block permutation function consists of 12 + 2ℓ iterations of five sub-rounds, each individually very simple:
θ Compute the parity of each of the 5w (320, when w = 64) 5-bit columns, and exclusive-or that into two nearby columns in a regular pattern. To be precise, a[i][ j][k] ← a[i][ j][k] ⊕ parity(a[0...4][ j−1][k]) ⊕ parity(a[0...4][ j+1][k−1])
ρ Bitwise rotate each of the 25 words by a different triangular number 0, 1, 3, 6, 10, 15, .... To be precise, a[0][0] is not rotated, and for all 0 ≤ t < 24, a[i][ j][k] ← a[i][ j][k−(t+1)(t+2)/2], where .
π
Permute the 25 words in a fixed pattern. a[ j][2i+3 j] ← a[i][ j].
χ
Bitwise combine along rows, using a ← a ⊕ (¬b & c). To be precise, a[i][ j][k] ← a[i][ j][k] ⊕ ¬a[i][ j+1][k] & a[i][ j+2][k]. This is the only non-linear operation in SHA-3.
ι
Exclusive-or a round constant into one word of the state. To be precise, in round n, for 0 ≤ m ≤ ℓ, a[0][0][2m−1] is exclusive-ORed with bit m + 7n of a degree-8 LFSR sequence. This breaks the symmetry that is preserved by the other sub-rounds.
Round constants
The round constants RC[i] are given in the table below for the maximum lane size 64. For smaller sizes, they are simply truncated. The formula can be found in [1].
| RC [0] | 0x0000000000000001 | RC [12] | 0x000000008000808B |
|---|---|---|---|
| RC [1] | 0x0000000000008082 | RC [13] | 0x800000000000008B |
| RC [2] | 0x800000000000808A | RC [14] | 0x8000000000008089 |
| RC [3] | 0x8000000080008000 | RC [15] | 0x8000000000008003 |
| RC [4] | 0x000000000000808B | RC [16] | 0x8000000000008002 |
| RC [5] | 0x0000000080000001 | RC [17] | 0x8000000000000080 |
| RC [6] | 0x8000000080008081 | RC [18] | 0x000000000000800A |
| RC [7] | 0x8000000000008009 | RC [19] | 0x800000008000000A |
| RC [8] | 0x000000000000008A | RC [20] | 0x8000000080008081 |
| RC [9] | 0x0000000000000088 | RC [21] | 0x8000000000008080 |
| RC [10] | 0x0000000080008009 | RC [22] | 0x0000000080000001 |
| RC [11] | 0x000000008000000A | RC [23] | 0x8000000080008008 |
Rotation offsets
The rotation offsets r[x,y] are given in the table below. The formula can be found in [1].
| x = 3 | x = 4 | x = 0 | x = 1 | x = 2 | |
|---|---|---|---|---|---|
| y = 2 | 25 | 39 | 3 | 10 | 43 |
| y = 1 | 55 | 20 | 36 | 44 | 6 |
| y = 0 | 28 | 27 | 0 | 1 | 62 |
| y = 4 | 56 | 14 | 18 | 2 | 61 |
| y = 3 | 21 | 8 | 41 | 45 | 15 |
SHA үйл ажиллагааны харьцуулалт
| Aлгоримт болон вариант | Гаралтын хэмжээ (bits) | Дотоод байдлын хэмжээ (bits) | Блокын хэмжээ (bits) | Хамгийн их мессежний хэмжээ (bits) | Үгийн хэмжээ (bits) | Rounds | Үйл ажиллагаа | Онолын дүгнэлт |
|---|---|---|---|---|---|---|---|---|
| MD5 | 128 | 128 | 512 | 264 -1 | 32 | 64 | +,and,or,xor,rot | yes |
| SHA 0 | 160 | 160 | 512 | 264 -1 | 32 | 80 | +,and,or,xor,rot | yes |
| SHA 1 | 160 | 160 | 512 | 264 -1 | 32 | 80 | +,and,or,xor,rot | Theoretical халдлага (260) |
| SHA2->SHA224,SHA256 | 224, 256 | 256 | 512 | 264 -1 | 32 | 64 | +,and,or,xor,rot | дурын |
| SHA2->SHA384,SHA512,SHA512/224,SHA512/256 | 384,512,224,256 | 512 | 1024 | 2128 -1 | 64 | 80 | +,and,or,xor,rot | дурын |
| SHA3 | 224/256/384/512 | 1600 | 64 | 24 | and,or,xor,rot | дурын |
Secure Hash Algorithm-ын олон хувилбаруудын харьцуулалт
| Параметр | SHA-1 | SHA-256 | SHA-384 | SHA-512 |
|---|---|---|---|---|
| Мессеж задаргааны хэмжээ (bits) | 160 | 256 | 384 | 512 |
| Мессежний хэмжээ (bits) | 264 | 264 | 264 | 264 |
| Блокын хэмжээ (bits) | 512 | 512 | 1024 | 1024 |
| Үгийн хэмжээ (bits) | 32 | 32 | 64 | 64 |
| Алгоритмын алхамууд | 80 | 64 | 80 | 80 |
Pseudo-code description
We first start with the description of Keccak-f in the pseudo-code below. The number of rounds nr depends on the permutation width, and is given by n = 12+2l, where 2l = w. This gives 24 rounds for Keccak-f[1600].
Keccak-f[b](A) {
forall i in 0…nr-1 A = Round[b](A, RC[i]) return A
} Round[b](A,RC) {
θ step C[x] = A[x,0] xor A[x,1] xor A[x,2] xor A[x,3] xor A[x,4], forall x in 0…4 D[x] = C[x-1] xor rot(C[x+1],1), forall x in 0…4 A[x,y] = A[x,y] xor D[x], forall (x,y) in (0…4,0…4)
ρ and π steps B[y,2*x+3*y] = rot(A[x,y], r[x,y]), forall (x,y) in (0…4,0…4)
χ step A[x,y] = B[x,y] xor ((not B[x+1,y]) and B[x+2,y]), forall (x,y) in (0…4,0…4)
ι step A[0,0] = A[0,0] xor RC
return A
}
Keccak[r,c](M) {
Initialization and padding S[x,y] = 0, forall (x,y) in (0…4,0…4) P = M || 0x01 || 0x00 || … || 0x00 P = P xor (0x00 || … || 0x00 || 0x80)
Absorbing phase forall block Pi in P S[x,y] = S[x,y] xor Pi[x+5*y], forall (x,y) such that x+5*y < r/w S = Keccak-f[r+c](S)
Squeezing phase Z = empty string while output is requested Z = Z || S[x,y], forall (x,y) such that x+5*y < r/w S = Keccak-f[r+c](S)
return Z
}
SHA алгоритмын математик тооцоолол
Secure Hash Algorithm нь санамсаргүй байдлаар нууцлал буюу encryption хийдэг. Тухайн нууц үг нь хэдэн ч битийн урттай орж ирхэд тухайн нууц үгийг secure hash algorithm-н төрлөөс хамааран хэдэн үг үсэг, тэмдэгт, тоо орж ирэх нь хамаагүй нэг л хэмжээнд encryption хийдэг. Их хэмжээний өгөгдлийг encryption хийхэд ч мөн адил хийгдэнэ. Энэхүү нууцлалын протокол нь нэг битийн өөрчлөлтөнд тухайн encryption хийсэн өгөгдөл нь бүхэлдээ өөрчлөгддөг.
Жишээ нь: SHA1: encryption хийх өгөгдөл: хишгээ
encryption хийгдсэн байдал: e096d9b2b126eaf1ff75b84c8f2da3074b97d6a9
SHA1: өгөгдөл: Өгөгдөл гэдэг үг нь ерөнхий тохиолдолд яриан бус мэдээллээр илэрхийлэгдэх бөгөөд хэн бүхэнд харагдах ойлгогдохоор үүсгэж болох баримт, үзэл санаа, заавар зөвлөгөө, мэдээлэл гэх мэтийг илэрхийлэх утгатай. Өгөгдөл дамжуулах холбооны үндэс нь морзе кодын дамжуулал, телеграфын холбоо, тоон мэдээлэл дамжуулах онол дээр үндэслэгддэг. Аналог технологитой цахилгаан холбооны сүлжээний сувгаар кодлогдсон мэдээллийг бага хурдтай дамжуулдаг холбооны төрлийг телеграфын холбоо гэнэ. Телеграфын холбооны сүлжээний онцлог нь хурд бага, өгөгдлийн тоон битийн цувааг аналог хэлбэрт дамжуулах технологитой байсан.
боловсруулалт: 309a02a81be7db58b51d13a61fa867169fdaf1d0
SHA256: encryption хийх өгөгдөл: хишгээ
encryption хийгдсэн байдал: 33c81a747b02a62011290e334033045b8a1dfd4a757e4d4a4d5c5f0988325a36
SHA256: өгөгдөл: Өгөгдөл гэдэг үг нь ерөнхий тохиолдолд яриан бус мэдээллээр илэрхийлэгдэх бөгөөд хэн бүхэнд харагдах ойлгогдохоор үүсгэж болох баримт, үзэл санаа, заавар зөвлөгөө, мэдээлэл гэх мэтийг илэрхийлэх утгатай. Өгөгдөл дамжуулах холбооны үндэс нь морзе кодын дамжуулал, телеграфын холбоо, тоон мэдээлэл дамжуулах онол дээр үндэслэгддэг. Аналог технологитой цахилгаан холбооны сүлжээний сувгаар кодлогдсон мэдээллийг бага хурдтай дамжуулдаг холбооны төрлийг телеграфын холбоо гэнэ. Телеграфын холбооны сүлжээний онцлог нь хурд бага, өгөгдлийн тоон битийн цувааг аналог хэлбэрт дамжуулах технологитой байсан.
боловсруулалт:8acf51a95639a442cdb12a9384a393b52bbd29c898a768a38cec13e38696d71e
SHA3: encryption хийх өгөгдөл: хишгээ
encryption хийгдсэн байдал: 5cdf5ffc84ec3b54b52fb097728990b1592054da9caf125302b0b72f95207afc6b2726b183cd9fd4c1ec4a152dfde7c3f
0a4125dbca0848c32812ed16a3f9541
SHA3: өгөгдөл: Өгөгдөл гэдэг үг нь ерөнхий тохиолдолд яриан бус мэдээллээр илэрхийлэгдэх бөгөөд хэн бүхэнд харагдах ойлгогдохоор үүсгэж болох баримт, үзэл санаа, заавар зөвлөгөө, мэдээлэл гэх мэтийг илэрхийлэх утгатай. Өгөгдөл дамжуулах холбооны үндэс нь морзе кодын дамжуулал, телеграфын холбоо, тоон мэдээлэл дамжуулах онол дээр үндэслэгддэг. Аналог технологитой цахилгаан холбооны сүлжээний сувгаар кодлогдсон мэдээллийг бага хурдтай дамжуулдаг холбооны төрлийг телеграфын холбоо гэнэ. Телеграфын холбооны сүлжээний онцлог нь хурд бага, өгөгдлийн тоон битийн цувааг аналог хэлбэрт дамжуулах технологитой байсан.
боловсруулалт: 8acf51a95639a442cdb12a9384a393b52bbd29c898a768a38cec13e38696d71e
SHA512: encryption хийх өгөгдөл: хишгээ
encryption хийгдсэн байдал: 22901342db3f3b24008ed375daa3464e8b985a3492d4a6f2105daf90c274a8f872ba19f2d38602a7dece5aae46e90261
f3ecb18b562816676c2532eb969a0ade
SHA512: өгөгдөл: Өгөгдөл гэдэг үг нь ерөнхий тохиолдолд яриан бус мэдээллээр илэрхийлэгдэх бөгөөд хэн бүхэнд харагдах ойлгогдохоор үүсгэж болох баримт, үзэл санаа, заавар зөвлөгөө, мэдээлэл гэх мэтийг илэрхийлэх утгатай. Өгөгдөл дамжуулах холбооны үндэс нь морзе кодын дамжуулал, телеграфын холбоо, тоон мэдээлэл дамжуулах онол дээр үндэслэгддэг. Аналог технологитой цахилгаан холбооны сүлжээний сувгаар кодлогдсон мэдээллийг бага хурдтай дамжуулдаг холбооны төрлийг телеграфын холбоо гэнэ. Телеграфын холбооны сүлжээний онцлог нь хурд бага, өгөгдлийн тоон битийн цувааг аналог хэлбэрт дамжуулах технологитой байсан.
боловсруулалт: 2c8740f21e4519de72431c45c21fdc18fac8695213eddf5a7951e862edb0325b57bc62e2ea492834b686b7706dc4cc87dda81a65
98e147f600d58ff13d281cb7
SHA хэрэглээ
Secure hash algorithm нь нууцлал хамгаалалтын хувьд бусад алгоритмуудаас хамаагүй өндөр нууцлалтай. Энэхүү давуу тал нь аливаа өгөгдөл, мэдээлэл, хэрэглэгчийн бүртгэл, password гэх мэтийг нууцлахад хамгийн боломжтой. Энэ давуу талыг social network-ийн сайтууд болох facebook, twitter болон gmail гэх мэтэд ашиглагдаж байна. Мөн онлайн гүйлгээний сайтууд болон хувийн хэвшлийн нууцлал шаардсан байгууллагуудад өргөн ашиглагддаг. SHA алгоритмийг банк санхүү, батлан хамгаалах салбарт өргөн ашигладаг.
SHA сул тал
Secure Hash Algorithm нь нэг битийн өөрчлөлтөнд бүхэлдээ өөрчлөгддөг. Үүнээс үзвэл хэдэн битийн өгөгдөл байсан ч тухайн өгөгдлийг боловсруулах нь компьютерт их хэмжээний ачааллыг бий болгоно. Гэхдээ энэхүү ачаалал нь тийм ч чухал асуудал биш юм.
Тайлагдах боломж
Secure Hash Algoritm нь маш өндөр нарийвчлалтай учир тайлагдах боломжгүй. Тухайн нэг битийн өөрчлөлтөн encryption хийсэн түлхүүр үг нь бүхэлдээ өөрчлөгддөг. Тиймээс тайлагдах боломж бараг байхгүй. Харин Brote Force attack ашиглан нууц үгийг олох боломжтой боловч тухайн боловсруулалтыг хийх гэж их хэмжээний хугацаа ашиглагдана. Ийм учраас эвдэгдэх боломжгүй юм.