Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.intsys.msu.ru/magazine/archive/v14(1-4)/lyovin-203-212.pdf Дата изменения: Mon Jun 6 07:19:24 2011 Дата индексирования: Mon Oct 1 23:58:46 2012 Кодировка:

-
. .

. . - . . , , . , . -, , MD4, MD5, RIPEMD, SHA, 34 11­94. : -, , , .

- , , (message digest). (DSA, DSS). : , , ; (-), . . {0, 1} .


204

. .

. ( ) : {0, 1} {0, 1} , - , : 1) - {0, 1} ; 2) {0, 1} - ; 3) {0, 1} ( ) ; 4)
2

{0, 1} , ( 1 ) = ( 2 );
1

2

{0, 1} :

1

=

5) ( 1, 2) : {0, 1} , = 1, 2, ( 1 ) = 1 = 2, ( 2 ). , , - [1]. 4, 5 . , : CRC, XOR ( RXOR), , 4, 5. ( ) - . , -. , . : , , , , . , . [1, 2]. -.


-

205

- , , . , -. , , .

- ( )
- , {0, 1} ( ). {0, 1} , ( ) = ( ). , {0, 1} , ( ) = - , ( ), 2 - . , 1 ( , ) , {0, 1} {0, 1} = 1, . . . , : ( ) = ( ). 1, . . . , :
1

( , ) = 1 - (1 - 2- ) 2- . (, ) 0,01 0,5 0,99

1

2 - 2 - 2

7 1

1. 1 1 ( , ) . , - 2 -7 . 1%. , . 128 - (MD2, MD4, MD5, RIPEMD128, HAVAL3­4) 2120 . .


206

. .

-
- . : 2 ( , ) , , 2 , . 2 ( , ). , , 2 (2 - 1) . . . (2 - + 1) = 2! (2 - )! . 2 . ,
2

( , ) = 1-

2! (2 - )!

2- . , 2-
- -1 2

2

( , ) = 1-
2 - +1 2 -
( -1) 2

(2 (2 - 1) . . . (2 - - 1)) 1 - 1 - 21 1 - 22 . . . 1 - , 1 -
2

= 1- .

2 -1 2


2

2 -2 2

...

= .

, ,
-3
2

( , )>1-

(, ) 0,01 0,5 0,99

22 2 22

+2

2. 2 = 2 2 50%. , , 0,5, 23 . , , , , - , . , - 256 , (2128 ). , 128- .


-

207

, 256 - . , 10 6 , - .

- ( )
-. , - ( ). ( 512 ) - = ( -1 , ). , : ( + ) = ( ). . - MD4, . MD4 128 , -. , [3], = (0, 231 , 231 - 228 , 0, 0, 0, 0, 0, 0, 0, 0, 0, -216 , 0, 0, 0). : MD4( + ) = MD4( ). 3. RIPEMD128. RIPEMD RIPE [2]. - MD4, . : = (0, 0, 0, 220 , 0, 0, 0, 0, 0, 0, 218 + 231 , 0, 0, 0, 0, 231 ). : RIPEMD128( + ) = RIPEMD128( ) ( 4). , . -. MD4, MD5, RIPEMD128, SHA1 , . -


208

. .

2

MD4(

1

) = MD4(
1

2

)

2

MD4(

1

) = MD4(

2

)

4d7a9c83 56cb927a b9d5a578 57a7a5ee de748a3c dcc366b3 b683a020 3b2a5d9f c69d71b3 f9e99198 d79f805e a63bb2e8 45dd8e31 97e31fe5 2794bf08 b9e8c3e9 4d7a9c83 d6cb927a 29d5a578 57a7a5ee de748a3c dcc366b3 b683a020 3b2a5d9f c69d71b3 f9e99198 d79f805e a63bb2e8 45dc8e31 97e31fe5 2794bf08 b9e8c3e9 5f5c1a0d 71b36046 1b5435da 9b0d807a 4d7a9c83 56cb927a b9d5a578 57a7a5ee de748a3c dcc366b3 b683a020 3b2a5d9f c69d71b3 f9e99198 d79f805e a63bb2e8 45dd8e31 97e31fe5 f713c240 a7b8cf69 4d7a9c83 d6cb927a 29d5a578 57a7a5ee de748a3c dcc366b3 b683a020 3b2a5d9f c69d71b3 f9e99198 d79f805e a63bb2e8 45dc8e31 97e31fe5 f713c240 a7b8cf69 e0f76122 c429c56c ebb5e256 b809793 3.

, - (PGP) MS Windows, Linux. . -. - () . .


. {0, 1} . - : ( ) = ( ( ( ))).


-

209

1

2

RIPEMD128( 1 ) = = RIPEMD128( 2 )
1

579faf8e 9ecf579 574a6aba 78413511 a2b410a4 ad2f6c9f b56202c 4d757911 b deaae7 78b c91f2 47b c6d7d 9ab dd1b1 a45d2015 817104ff 264758a8 61064ea5 579faf8e 9ecf579 574a6aba 78513511 a2b410a4 ad2f6c9f b56202c 4d757911 b deaae7 78b c91f2 c7c06d7d 9ab dd1b1 a45d2015 817104ff 264758a8 e1064ea5 1fab152 1654a31b 7a33776a 9e968ba7 579faf8e 9ecf579 574a6aba 78413511 a2b410a4 ad2f6c9f b56202c 4d757911 b deaae7 78b c91f2 47b c6d7d 9ab dd1b1 a45d2015 a0a504ff b18d58a8 e70c66b6 579faf8e 9ecf579 574a6aba 78513511 a2b410a4 ad2f6c9f b56202c 4d757911 b deaae7 78b c91f2 c7c06d7d 9ab dd1b1 a45d2015 a0a504ff b18d58a8 670c66b6 1f2c159f 569b31a6 dfcaa51a 25665d24 4.

2

RIPEMD128( 1 ) = = RIPEMD128( 2 )

[2]. -, . . 5, . , .


, , . {0, 1}


210

. .

1

MD4(
2

1

)

MD4( 2 ) MD4( 1 MD4( MD4( 2 MD4(

1 2

)) ))

4d7a9c83 56cb927a b9d5a578 57a7a5ee de748a3c dcc366b3 b683a020 3b2a5d9f c69d71b3 f9e99198 d79f805e a63bb2e8 45dd8e31 97e31fe5 2794bf08 b9e8c3e9 d8024c54 82a68fec a61bb37e 35a75377 4d7a9c83 d6cb927a 29d5a578 57a7a5ee de748a3c dcc366b3 b683a020 3b2a5d9f c69d71b3 f9e99198 d79f805e a63bb2e8 45dc8e31 97e31fe5 2794bf08 b9e8c3e9 d8024c54 82a68fec a61bb37e 35a75377 4fb7eb59 7b1020d3 d4429ec7 a18b e02e 4fb7eb59 7b1020d3 d4429ec7 a18b e02e 5.

. - : ( ) = ((( ) ) ) .

. , , . , , + , ( ) = ( + ). ( ) , ( + ) = . , . 1 , 2 5, : MD4(MD4( MD4(MD4(
1 2

) )

1 2

) )

14bb2693 eb d1cb d9 28c04dc4 13652941 08372524 65baf1ea 841e560c fed946c4 6.

, - , -


-

211

- () . , - . , . , - .


- : ( ) = 1 ( )2 ( ) . . . ( ). -, - : ( ) = MD4( ) MD5( )SHA1( )RIPEMD128( )HAVAL128( ). -, , - 128. . , -.


- . - : ( ) = ( )(
1

(

)) . . . (

(

)).

, = 1, . . . , . , , . . -, -, - -. , -.


212

. .

, , , - . , . , : ( ) = . . . (
2

((

1

((

)

))

)) . . .

-, .


[1] Handb o ok of Applied Cryptography / A. Menezes, P. Oorschot, S. Vanstone (eds.). CRC Press, 1996. [2] . / 2- . 2002. [3] Wang X., Feng D., Lai X., Yu H. Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD. 2004.