---

Значення Y' виходу циклової функції для другої матриці Z' буде таким:

2А 98 7Е А4 0F 91 70 61

F5 D6 F0 АО Е4 64 4F 48

8А 7А 5А 52 DE ЕЕ 65 62

07 С5 62 F9 88 Е9 5С 69

16 BD C8 03 IB C5 BE IB

7B 94 76 39 FE 05 OB 56

93 9B AA AO AD FF 9A E6

74 5B 7B 18 IC ЗВ E3 FD

Геш-кодом для цього рядка буде такий 512-бітний рядок:

2А987ЕА40F917061 F5D6F0A0E4644F48 8А7А5А52DEEE6562 07С562F988Е95С69 16BDC80З1ВС5ВЕ1В 7В947639FE050В56 939BAAA0ADFF9AE6 745В7В181СЗВЕЗFD

А.7.9 Приклад 9

У цьому прикладі рядок даних — це 1000000-байтний рядок, утворений з ASCII-кодів символів рядка, що містить 10⁶ символів ‘а¹.

Геш-кодом для цього рядка буде такий 512-бітний рядок:

0C99005BEB57EFF5 0A7CF005560DDF5D 29057FD86В20BFD6 2DECA0F1CCEA4AF5 1FC15490EDDC47AF 32ВВ2В66С34FF9AD 8С6008AD677F7712 695ЗВ226E4ED8B01

ДОДАТОК В
(довідковий)

ФОРМАЛЬНІ СПЕЦИФІКАЦІЇ

В.О Вступ

У наступних розділах наведено повні специфікації спеціалізованих геш-функцій 1, 2 та 3 на мові специфікацій Z. Нотація Z описана в [1].

Z-специфікація зберігає більшість імен, структур тощо, використовуваних в основній частині цього стандарту.

Z-специфікація написана винятково на мові Z, охоплюючи коментарі. У коментарях зазначено розділи основного тексту цього стандарту, з яких виведено Z-специфікацію.

Z-специфікація моделює повідомлення як послідовність натуральних чисел 0 та 1 (рядок).

#3 Терміни та визначення понять

Циклова функція

Bit== (0,1}

Sfring =— szqBit

Д: N

Z₂: Мт

String—Lі == (s. String J =

= {5: Siring I # j

І Ф: String_Li x String_Lz —* String^Слово

Word == {ж String I # vf = 32}

Wordjcapocity == 2 T 32

Word_capacity_m_l = = (2 T 32) - 1

fWord Q.. Word_copacity_m_l

#4 Познаки та скорочення

Sⁿ () Необхідно тільки визначити S як Sⁿ (ітерація відношення), що визначено в Z.

S: Word -> Word

VA:Word*

(letI = W_to_I(A)*

(let shift _ / = (/ * 2 + (2div (2 T 31))) mo d (2 T 32) •

S(A) = I _to_ W(shift _ /))) av® Визначені тільки для слів, бо це єдина вимога.

BO = Bit х Bit Bit

LO: Word x Word x BO —> Word

V p,q:Wordfto: BO*

LO(p_fq,bo) ='{и: 1 p*nt-t bo(p(n), #(ra))}

x

and :BO

or_, _ or

0 xor 1 = 1

0 xor 0 = 0

1. xor 0 = 1

1. xor 1 = 0

0 or 1 = 1

0 or 0 = 0

lor0 = l

I or 1 = 1

0 and 1 = 0

0 and 0 = 0 landO = 0

1 <mdl = l

_XOR _,_OR_,_ AND_ :flW x Word -> Word

Va^B : Word •

XXORB = LO(A> B_f (_xor_)) л

Я OR В = LO{A,B, (_or J) л

J AND В ® LO(A_tB, (_and_))

NOT W W -> Word

V A : Word •

NOT A = JXORfr :1 .. #A • и )-> 1}

S _ Word x Word —> Word

V A, В : Word •

A 83 B- I_fo_W((Wmod Word^capacity)

#5 Вимоги до об'єкта стандартизації

#6 Модель спеціалізованих геш-функцій

By te *=» {£: String I # b = 8}

Zffyw == 0 .. 255

B_to_/: Вую —> IByte

Vx Byte • B_ro_Z(x) ж

x(l) *217+ .v(2) • 2 ? 6 + л<3) * 2 T 5 + x(4) » 2 T 4 +

45) • 2 f З T j(6) » 2 t 2 + xf7)’ 2 + x(8)

Процес гешування

I IV : String _ L₂

I Maxinnan_Length_ofjString : N

hash : String ■+* String_L^

V D : String ? # D < MaximumJbengthjofJString • hash(D) =

(letPD == po<?(D) •

(letSD == sph't(PD) •

(let/7_g — iterate(SD_fIV) • ггипса№(Н^)У))

Крок 1 (заповнювання)

StrmgMultiple_L_x == (s : String | #s modi] - 0}

I pad: String —> StringMultiple^

Крок 2 (розщеплювання)

StringBlocks -= seq String_L

split : StringMultipl&J^ —> StringBlocks

split — {sml '.StringMultipleJ^ sb : StringBlocks | snill - У sb • smll I—> $d}

Крок 3 (ітерація)

iterate: StringBlocks x String^I^ -** S^rmg_Z₂

V sb : StringBlocks; Н_іЛ: StringJLq | # sb > 1 • iterate(sb, —

(let Di = j5(1) •

(let Ні = Ф(Р^Я_М).

if = 1

then Я и

else iterate(tail sb, #,)))

Крок 4 (відтинання)

=- {s : String I fts — L#}

truncate :String_L-2 —> StringjL^

V sr : _L₂•

truncatefsy) = (1 ...Zg) 1 sy

• 7 Спеціалізована геш-функція 1

Maxjmi(in_Lergth_of_String ~ (2 T 64) - 1

• 7.1 Параметри, функції та константи

• 7.1.1 Параметри

= 512

L₂= 160

Lh = 160

• 7.1.2 Узгодження порядку слідування байтів

Ijoj?: IWard -> Word#7.1 Л Функції

-= {f : seq (ftcW x FFbrr/ x Word -* Word} і #g - SO}

g : Jndaxedjg

(Vj: 1 . 16 *

g(f)(A₀, A) = X_o XORXj XORASJa

(Vf : 17 ... 32 •

g(>Xr₀»AYAy - (X_o ANDX^ORCNOTAq AND A,)) a

(Vf : 33 ... 48 •

g(})(X&X_itX₂) ~ (Xq OR NOT ATJ) XORA’_2)a

(Vf . 49 ... 64 •

g(iXX₉,X_vX₂) =(Х_й ANDA*₂) OR(Xj ANDNOTA'₂))a

(V f : 65 ... 80 •

g(fKX_9fX_vX₂} = X^ XOR(Xj OR NOT A'.))

#7.1.4 Константи

xOOOOOOOO == 0

X5A827999 == 1518500249

X6ED9EBA1 == 1859775393

X8F1BBCDC == 2400959708

XA953FD4E =« 2840853838

X50A28BE6 == 1352829926

X5C4DD124 == 1548603684

X6D703EF3 == 1836072691

X7A6D76E9 == 2053994217

Constants =- {c : StringWord | # c = 80}

С, С': Constants

(11.14,15.12,5,8,7.9,11.13.14.15.6.7,9.8, 7,6.8.13.11.9,7.15.7.12.15.9.11.7.13.12, 11.13.6.7.14.9.13.15.14.8,13.6.5.12.7.5.

11.12.14,15.14,15.9,8,9.14.5.6.8,6.5.12.

9,15.5,11,6.8,13.12,5.12.13,14.11, S, 5.6)

(8,9.9,11.13,15,15,5.7.7.8,11.14,14.12.6, 9.13,15.7.12,8,9,11.7,7,12.7.6.15.13.11.

9.7.15.11.8,6.6.14,12.13.5.14.13.13.7.5,

15.5,8.11,14,14,6,14,6,9.12,9.12.5.15.8,

8,5.12.9.12.5,14.6.8.13,6.5,15.13,11,11)Записані значення для а та а' на одиницю більші ніж в основному тексті, бо послідовності Z починаються з 1.

(1.2.3.4.5. б. 7.8.9.10.11.12.1114.15.16,

8,5.14.2,11.7.16,4,13.1,10,6.3,15.12.9, 4,11,15.5.10,16,9. 2,3,8,1,7,14,12,6.13.

2,10.12.11.1.9.13.5,14,4,8.16.15. 6, 7,3.

5.1.610. 8.13.3.11.16 2.4.9.12.7.1614}

(615.8.1.10. 3.12.5.14. 7.169.2.11.4.13.

7.12.4.8.1.14.6.11.15.169.13,5.10.2.3.

16 6 2.4,8.15.7,10,12.9,13,3,11.1,5.14.

9,7,5,2,4.12,161.613,3,14,10.8.11.15.

13,16.11,5,2.6, 9.S, 7,3,14,15,1.4,10,12}

#7.1.5 Початкове значення

*67452301 1732584193

= 2_/о_Н’(*67452301) xEFCDABS9 = 4023233417 lj = IjeJFfx^CDABW) x98BADCFE = 2562383102 Г₂ = I~roJV(x9SBADCFE) *10325476 = 271733878 Г₃ = />_F(xl0325476) *C3£2£1FO = 3285377520 K₄ == 7^о_Г(лС37)2£1Г0)

iv ~ VJi’r/ iyr₄

#7.2 Метод заповнювання

V D : String • pad(D) = (iea_p = #d • (ktZeros == {и 1 ... «447-Zp)mod512) • и i-4 0} • (ktLength_D_LSH = Mo_fT(L_D mod (2 T 32)) • QetLength_D_MSH = I_JoJF(L₀ div (2 T 32)) •

D ~ (1) " Zeros ~ Length_D_LSH ~ I^ngth_D_MSH)y)

)(((((((«м_£л.г.сіл..ол

• (f).x я (гіг в (і)л = w 4»i)

• (г)<У в (Il¥ a (5).I=U4»I)

• (і).x я (sir и (ш = г.г4ч)

• (s),x в (>).v в (£)I=1.1 »»i)

• frlr в (£ir s (г).{=ox 4»i)

• (I ',Э ‘,о ',І 'В&л 'Л 2)087=«X4»l)

♦ (I 'Э '» '4 ® ‘Л 2)087=Л’1*1)

* == X p[)

• ™ Z ^idl)

» (ду “хОф

« : A J: : ЛТ д

(«(I + ГО 'V 'І '3 7 ^lZ)0S7 «I^е

J «*4»

(08=0 JI

♦ <€X4ZX)_otS LY 41 >X) = .I

* В (to В (0*)z ffi (ЕГ 'or 'Шда S OX) _w,$ = лі *⁴1)

• <£)X •* t-X Xfr)x «• EX -(£)x г X Xe)x IX -(I) X OX **[)

=40'^ ’^77)087

•S = X?V9I = z#108^- 1^jitcisiw3 3

has: о 7 tZ~рвхври/1S .рло^Зищ^ ^x'Z К

рлО^ЗіШ^ <— 08 ‘ [ X

x toy x toy x STp&x&puf

{.$££ ні* .ні* / — у I pjo^Suujg: iHJ :8иьц$ : y}

- oj 8uixj$

рло^Зит^ <- : рло^8иьц$ oi 2шм$ jyd$

bes ==

,і|їіянЛф іраоияиО эиио C*2#В.1.1 Допоміжні функції

Vp: N •

0=1 л

(Vw: -1)))

B.2 Специфікація спеціалізованої геш-функції 2

Секції #3, #4, #5, #6 та В.1.1 додатка В.1 треба повторити для цієї частини додатка.

• 8 Спеціалізована геш-функція 2

Maximum Length_ofJString = (2 ? 64) -1

• 8.1 Параметри, функції та константи

• 8.1.1 Параметри

Ц = 512

L₂ = 128

128

• 8.1.2 Узгодження порядку слідування байтів

Секцію #7.1.2 додатка В.1 тут треба повторити

• 8.1.3 Функції

Секцію #7,1.3 додатка В.1 тут треба повторити g 2==(1 ...64) 1 д

• 8.1.4 Константи

хОООООООО == о

Х5А827999 == 1518500249

X6ED9EBA1 == 1859775393

xBFlBBCDC == 2400959708

х50А28ВЕб == 1352829926

X5C4DD124 == 1548603684

X6D703EF3 == 1836072691

Constants == (г : StringWord | # с ~ 64}

Секцію #7.1.4 додатка В.1 тут треба повторити тільки для і, Г, а, а',

Ї2==(1...64) 1 t

12’==(1...64) 1 Г

а2 == (1...64) 1 а

а2' = (1...64)1а'

#8.1.5 Початкове значення

*67452301 -= 1732584193 7₀ == 7>_йфсб7452301) xEFCDAB$9 == 4023233417 _Г1== IjoJ?(xEFCDABS9) x98BADCFE == 2562383102 7₂== IjoJF(x9ZBADCFE) *10325476 == 271733878 У₅ ==/_?□ JF(*10325476)

#8.2 Метод заповнювання

Секцію #7.2 додатка В. 1 тут треба повторити.

#8.3 Опис циклової функції

Секцію #7.3 додатка В.1 тут треба повторити для означень StringWord та Split_String_to_StringWord.

L64:StringWdrd х StringWord х

Indexed_g х seq N х seq N х

Constants х 1 „64 -> StringWord

V Z,X. StringWord; g: Indexed_g; t, a: seq N;

C:Consmfc;i:1..64|#Z==16A#X=5*

L64(Z_tX_fg,t_ta_tC,i) =

(let X0 = X(l); XI == X(2); X2 = X(3); X3=X(4) •

(letlF==S^r<o(X0 S sOXYl, JG, X3) ffl Z(a(f)) ffl C(0)

(letr==(X3, J7,X1.X2)« if (;=64) then Y

elwL&KZ, Il £ t, a, C, і +1))))

V sx: String_Li; лт: StringJL^ • &(sx,sy')~

(let Z — Split_String_toJStiingWard (sx) • Get Y = Split_Sfring_to_StringWbrd(sy)^ (etX = L64(Z Y, revgl, t2 a2 C, !)• (letX — £64(Z_f £ rev_S2, ґ2', a2 C !)• Get Г0 = Г(2) Ш X(3) E X'(4) •

Get П = 7(3) В X(4) ffl X'(l) *

Get 72 = 7(4) ffl X( 1) ffl X’(2) •

Get 73 = 7(1) ffl X(2) В X'(3) •

70'71" 72 "73))))))))

В.З Специфікація Спеціалізованої геш-функції З

Секції #3, #4, #5, #6 та В.1.1 додатка В.1 треба повторити для цієї частини додатка.

• 9 Спеціалізована геш-функція З

MaximumJLen^th_of_String - (2 Т 64) -1

• 9.1 Параметри, функції та константи

• 9.1.1 Параметри

Ц = 512

L_z = 128

£„=128

• 9.1.2 Узгодження порядку слідування байтів

W_to_I:Ward->lWord

V w: ІГогй • lF_to_/(w) ~

(let Bq — 5_Л?_7((1... 8) I w) •

(let . 16) 5 tv) •

(let = j3_/c?_Z((I7.,. 24) 1 w*) •

(let Л₃ = 1 n)<

Bi + 5₃ *2*8 + Я,*2*16+5_с*2*24))))

'.IWord -+ JFdrrf

#9.1.3 Функції

IndexedJ = {/ :■?<?<? (Word x Word x Word -+ PRW) | # / »80}

/ .IndexedJ _________________

Л0(А'_а, Xi, A”,)=(X_o AND Xj) OR (NOT A'_o AND X₂)) A (Vj:21...4O*

/GXA’o, Хз, A ) = Xq XOR Xj XOR X₂) Л

(W:41 ...60e

/(/)(X_G, Xj, X₂) = (A% AND X]) OR (X₅ AND X,) OR (Xj AND X₂)) л (Vt:61...80«

/(f)(X₀ Д_ьX) = X_o XORX₃ XORX₂)#9.1.4 Константи

0.4827999 = 1518500249

x6ED9EBAl = 1859775393 x8FlBBCDC = 2400959708 аСЛ62С1£>6 == 3395469782

Constants -- (c : SfringPTord ]#c - 80}

C: Cans tan &

(Vrl...2O*

COO=7^_IT(r5 J827999)) л

(Vi:21...4O*

C(0 = IjoJT(x6ED9EBA)) л

(УЛ41...60*

C(f) -2^ГГ(д8ЛЛЛС£>С))л

(Vf:61...8O*

ОД = 2_^n’(xCJ62Cl£)6))

#9.1.5 Початкове значення

Х67452Э01 •« 1732584193

П == Оо_ГЦл-€74523С1)

xEFCDABW == 4023233417

її ==/ to KxEFCDABZ9)

xVSBADCFE == 2562383102

Is == l_to_H^9^BADCFE)

*10325476 271733878

Із == 7_го_Г?'(х10325476)

xC3Z)2£lF0 == 3285377520

K₄ ==7_/o_HVC3Z)2£1M))

iv=vvvvr₄

#9.2 Метод заповнювання

V D: •

pad(D) =

(let Zeros = {m : 1.. .((447 - L&) mod 512) • и 0} •

(let Lwgth_DJ£SH == I_toJF(L_D div (2 T 32» •