, , - . - .
. . Q , 1 Q - 1. , Q,
A mod Q, A2 mod Q,..., AQ - 1 mod Q
1 Q - 1 . Y < Q A Q , , Y = A mod Q, 0 X (Q - 1)
X , Y, A mod Q. indA, Q (Y).
-.
Q | ||
A | A < Q A Q | |
I | ||
i ( ) | Xi < Q | |
Yi ( ) | Yi = AXi mod Q | |
J | |
j ( ) | Xj < Q |
Yj ( ) | Yj = AXj mod Q |
I | |
K = (Yj)Xi mod Q |
J |
K = (Yi)Xj mod Q |
, : Q A, Q. , I J . I i < Q Yi = AXi mod Q. J j < Q Yj = AXj mod Q. Y . I = (Yj)Xi mod Q, J K = (Yi)Xj mod Q. :
K = (Yj)Xi mod Q
= (AXj mod Q)Xi mod Q
= (AXj)Xi mod Q
= AXj Xi mod Q
= (AXj)Xj mod Q
= (AXi mod Q)Xj mod Q
= (Yi)Xj mod Q
, . i j , : Q, A, Yi Yj. , ..
Xj = inda, q (Yj)
- , , , . .
|
|
-
- "" , .
- : h = H (M),
h - .
- , , :
1) - ;
2) - ;
3) () ( ) ;
4) - h M , (M) = h;
5) y x, H(y)=H(x);
6) (, y) , H(y)=H(x).
, - - .
-: - , -. , - . , , - , . - = (SAB || M). -, , , SAB || M = H-1 (C). SAB || M, SAB .
, , - - . -. , , -. , , . , : -, - , -, . - , .
- MD5
MD5 (RFC 1321), MIT.
128 . :
MD5
1:
, 448 512 ( 448 mod 512). , 64 , , 512. , . , 448 , 512 960 . , 1 512.
, .
2:
64- ( ) . , 264, 64 . , 264.
|
|
, 512 . 512- Y0, Y1,..., YL-1, L * 512 . , 32- :
3: MD-
128- -. 32- (A, B, C, D). :
= 01234567; = 89ABCDEF; C = FEDCBA98; D = 76543210
4: 512- (16-) .
(HMD5). , fF, fG, fH fI .
512- Yq, , 128- ABCD, , . 64- T[1... 64], sin. i- T, T[i], , 232 * abs (sin (i)), i . abs (sin (i)) 0 1, , 32 . "" 32- , .
MDq+1 232 MDq. .
5:
L 512- L- 128- .
512- . 16 , ABCD. :
A ← B + CLSs (A + f (B, C, D) + X [k] + T [i]),
A, B, C, D - ; . |
f - fF, fG, fH, fI. |
CLSs - s 32- . |
X [k] - M [q * 16 + k] - k- 32- q- 512 . |
T [i] - i- 32- . |
+ - 232. |
. 32- 32- . , .. n- n- . :
fF = (B & C) (not B & D)
fG = (B & D) V (C & not D)
fH = B C D
fI = C (B & not D)
32- X [0..15] 512- , . 16 , , 64 . 512- 32- , 32- , , , 64 32- , . A, B, C D. ABCD. , 16 , 17- .
|
|
MD5 :
MD0 = IV
MDq+1 = MDq + fI[Yq, fH[Yq, fG[Yq, fF[Yq, MDq]]]]
MD = MDL-1,
IV - ABCD, 3, |
Yq - q- 512- . |
L - ( ). |
MD - . |
- SHA-1
- (Secure Hash Algorithm) (NIST) (FIPS PUB 180) 1993 . SHA-1, MD5, MD4.
264 160 .
:
1:
, 448 512 ( 448 mod 512). , . , 1 512. , .
2:
64 . 64- .
, 512 . 512- Y0, Y1,..., YL-1, L * 512 . , 32- .
3: SHA-1
160- -. 32- A, B, C, D E. :
A=67452301; B=EFCDAB89; C=98BADCFE; D=10325476; E=C3D2E1F0
4: 512- (16-)
, 80 , HSHA. 80 .
512- Yq 160- ABCDE, .
t, :
0 t 19 Kt = 5A827999 ( [230 × 21/2])
20 t 39 Kt = 6ED9EBA1 ( [230 × 31/2])
40 t 59 Kt = 8F1BBCDC ( [230 × 51/2])
60 t 79 Kt = CA62C1D6 ( [230 × 101/2])
SHAq+1 80- SHAq. 232 SHAq.
5:
512- L- 160- .
80 512- . :
A, B, C, D, E (CLS5 (A) + ft (B, C, D) + E + Wt + Kt), A, CLS30 (B), C, D
A, B, C, D, E - . |
t - , 0 t 79. |
ft - . |
CLSs - 32- s . |
Wt - 32- , 512- . |
Kt - . |
+ - 232. |
|
|
32- 32- . , .. n- n- . :
ft (B, C, D) | |
(0 t 19) | (B C) (B D) |
(20 t 39) | B C D |
(40 t 59) | (B C) (B D) (C D) |
(60 t 79) | B C D |
. 0 t 19 : if B then C else D. 20 t 39 60 t 79 . 40 t 59 , .
32- Wt 512- .
16 Wt 16 . :
Wt = Wt-16 Wt-14 Wt-8 Wt-3
16 32- . 64 XOR .
SHA-1 :
SHA0 = IV
SHAq+1 = Σ32 (SHAq, ABCDEq)
SHA = SHAL-1,
IV - ABCDE. |
ABCDEq - q- . |
L - , . |
Σ32 - 232, . |
SHA - . |
SHA-1 MD5
.
MD5 | SHA−1 | |
128 | 160 | |
512 | 512 | |
64 (4 16 ) | ||
, :
: , SHA-1 32 , MD5. , - , , SHA-1 . , , , 2160 , SHA-1, 2128 , MD5. , , , 280 SHA-1, 264 MD5.
: 232, 32- . SHA-1 (80 64) 160- 128- MD5. , SHA-1 25% , MD5 .
: , , . , SHA-1 , MD5. , SHA-1, MD5 .
- SHA-2
2001 NIST - -. - SHA-2 SHA-256, SHA-384 SHA-512 (, -). -, , . -.
( ) | ( ) | ( ) | ( ) | ( ) | |
SHA-1 | <264 | ||||
SHA-256 | <264 | ||||
SHA-384 | <2128 | ||||
SHA-512 | <2128 |
m . SHA-256 m = 512, SHA-384 SHA-512 m = 1024. w- . SHA-256 w = 32, SHA-384 SHA-512 w = 64. , 2w, n SHRn (x), - w- , () n ROTRn (x) ROTLn (x), - w- .
|
|
SHA-256 , 32- , x, y z. 32- .
- 3411
3411 -. SHA-1, 2 MD5, MD4.
-, 3411, 256 . , 256 . , - 256 .
256 .
.
256 .
64- - H Ki (i = 1, 2, 3, 4) 28147 .
.
:
- 256 ;
256 ;
- 2, 3 4 256 : 2 4 , 3
18 08 116 024 116 08 (08 18)2 18 08 (08 18)4 (18 08)4
0 1.
, .
: 256- 8- .
256- y = (x), x - 8- ; y - 8- .
(i + 1 + 4(k - 1)) = 8i + k
i = 0 ÷ 3, k = 1 ÷ 8
A (x) = (x1 x2) || x4 || x3 || x2
xi - 64 256- , |
|| . |
:
i = 1, U = H, V = M.
W = U V, K1 = (W)
K2, K3, K4 :
U = A(U) i,
V = A(A(V)),
W = U V,
Ki = (W)
64- - K1, K2, K3 K4. - 64- :
H = h4 || h3 || h2 || h1
28147:
si = EKi [hi], i = 1, 2, 3, 4
S = s1 || s2 || s3 || s4
. 256- 16- . Ψ :
η16 || η15 ||... || η1 - |
η1 η2 η3 η4 η13 η16 || η16 ||... || η2 - |
- :
Χ(M, H) = 61 (H (M 12(S)))
H - -, |
- , |
Ψi - i- Ψ. |
3411
:
- ;
- , 256 ;
- Σ, 256 ;
- L, .
256 . i :
H = Χ(Mi, H)
Σ = Σ ' Mi
L , 256 2256. L.
' : Σ Mi 256 . 2256. .
, .. ' :
, 256 .
Σ = Σ ' Mi.
L , 2256.
= Χ(', ).
= Χ(L, ).
= Χ(Σ, ).
.