Если это ваш первый визит, рекомендуем почитать справку по форуму. Для размещения своих сообщений необходимо зарегистрироваться. Для просмотра сообщений выберите раздел. |
CRC32 и его восстановление. |
Философия, технологии, алгоритмы! |
|
Опции темы |
02.08.2014, 17:32 | #1 |
Форумец
Сообщений: 595
Регистрация: 27.03.2004
Возраст: 45
Не в сети |
CRC32 и его восстановление.
Приветствую уважаемые кодеры.
Собственно накопилось пару вопросов по CRC32. 1) В php есть функция hash. Так вот crc32 можно посчитать 2-мя алгоритмами: crc32 и crc32b. Теперь вопрос - где найти описание алгоритма формирования crc32 и буду благодарен за пример реализации его на Delphi. 2) Почитал статью про восстановление crc. В статье все вроде расписано, даны примеры. Но когда в соответствии с примером пытаюсь рассчитать дополнительные 4 байта (для теста считаю на бумаге) - результат не сходится. Вот пример такого вычисления. Код:
f3 f2 f1 f0 = 2B 6A D1 BD a3 a2 a1 a0 = 46 6F FE 2F e3 = f3 = 2B -> BA (4) e3 e2 e1 e0 = 2B B4 5A 92 d3 = f2 XOR e2 = 6A XOR B4 = DE -> ED (3) d3 d2 d1 d0 = DE BB 9E C5 c3 = f1 XOR e1 XOR d2 = D1 XOR 5A XOR BB = 30 -> EF (2) c3 c2 c1 c0 = 30 B5 FF E9 b3 = f0 XOR e0 XOR d1 XOR c2 = BD XOR 92 XOR 9E XOR B5 = 04 -> 86 (1) b3 b2 b1 b0 = 04 DB 26 15 X = (1) XOR a0 = 86 XOR 2F = A9 Y = (2) XOR b0 XOR a1 = EF XOR 15 XOR FE = 04 Z = (3) XOR c0 XOR b1 XOR a2 = ED XOR E9 XOR 26 XOR 6F = 4D W = (4) XOR d0 XOR c1 XOR b2 XOR a3 = BA XOR C5 XOR FF XOR DB XOR 46 = 1D Т.е. чтобы получить значение CRC32=2B6AD1BD для файла с CRC32=466FFE2F необходимо в этот файл дописать 4 байта со значением XYZW. А по факту мы получаем конечное CRC32=0A2E0EA1 что не соответствует необходимому CRC32. PeID выдает значение XYZW=340E9470. Что собственно соответствует действительности. При таком значении XYZW CRC32 будет соответствовать необходимому. Собственно где косяк закрался в моих вычислениях? Что делаю не верно? Статья во вложении. 3) И собственно что в итоге необходимо - необходимо найти значения XYZW для алгоритма идентичного php hash(crc32) на Dlphi. Благодарю за любую помощь и подсказки. |
02.08.2014, 18:03 | #2 |
Форумец
Сообщений: 40,850
Регистрация: 27.05.2003
Возраст: 46
Не в сети |
http://ru.wikipedia.org/wiki/%D0%A6%...BA%D0%BE%D0%B4
если я правильно понимаю, то CRC32 - это четырехбайтовый int, четырехбайтовая (32-х битная) контрольная сумма, какие еще ДОПОЛНИТЕЛЬНЫЕ четыре байта ты пытаешься подсчитать? З.Ы. http://www.tools4noobs.com/online_php_functions/crc32/ |
02.08.2014, 18:11 | #3 | |
highly mean
Сообщений: 1,128
Регистрация: 26.05.2011
Возраст: 35
Не в сети |
Цитата:
Сгенерировать коллизию он пытается, я так понимаю. |
|
02.08.2014, 19:06 | #5 | |
Форумец
Сообщений: 595
Регистрация: 27.03.2004
Возраст: 45
Не в сети |
Цитата:
Вообще тут 2 варианта - первый тупо перебор этих 4 байт (XYZW) до тех пор, пока CRC32 не будет равно нужному. Но этот алгоритм очень медленный. Перебор на 8 потоках занимает до 4 часов. А второй вариант - обратную функцию просчитать. Что и описано в статье. Но на практике почему-то не получается. |
|
02.08.2014, 19:16 | #7 | |
highly mean
Сообщений: 1,128
Регистрация: 26.05.2011
Возраст: 35
Не в сети |
Цитата:
https://github.com/php/php-src/blob/...h/hash_crc32.c https://github.com/php/php-src/blob/...crc32_tables.h |
|
02.08.2014, 19:29 | #8 | |
Форумец
Сообщений: 595
Регистрация: 27.03.2004
Возраст: 45
Не в сети |
Цитата:
Да. Получается каждый раз. А по-другому в php не получается. |
|
02.08.2014, 19:36 | #9 | |
Форумец
Сообщений: 40,850
Регистрация: 27.05.2003
Возраст: 46
Не в сети |
Цитата:
Вот примерно это нужно осознать и сделать: http://nayuki.eigenstate.org/page/fo...c-to-any-value встроенной в PHP функции для выполнения этой задачи наверняка нет, она нестандартная. |
|
02.08.2014, 20:32 | #10 | |
Форумец
Сообщений: 595
Регистрация: 27.03.2004
Возраст: 45
Не в сети |
Цитата:
Суть не в этом. Имеем 2 разных файла. Один файл имеет CRC32=ABCDEF11 Второй: ABCDEF22 Чтобы изменить CRC32 1-го файла так, чтобы оно равнялось CRC32 2-го файла в файл необходимо добавить данные. Для CRC32 это 4 байта - XYZW. Так вот. Используя перебор мы изменяем XYZW от 00000000 до FFFFFFFF и каждый раз пересчитываем получившееся CRC32 и сравниваем его с CRC32 2-го файла до тех пор, пока они не будут равны. |
|
02.08.2014, 20:35 | #11 |
Форумец
Сообщений: 595
Регистрация: 27.03.2004
Возраст: 45
Не в сети |
Такс. Теперь другой вопрос.
Перепилил исходники имеющего расчета CRC32 в соответствии с алгоритмом crc32 в php. Но что-то не сходится. Кто сможет сказать где собака порылась? Код:
unit Crc32; interface uses Classes; type TCRC32Digest = LongWord; // Evaluate crc32 digest function Crc32File(const FileName: string): TCRC32Digest; function Crc32Stream(const Stream: TStream): TCRC32Digest; function Crc32Buffer(const Buffer; Size: Integer): TCRC32Digest; // Converting function Crc32DigestToStr(const Digest: TCRC32Digest): string; function StrToCrc32Digest(const Digest: string): TCRC32Digest; // Compare two crc32 digest function Crc32DigestEquals(const D1, D2: TCRC32Digest): Boolean; implementation uses SysUtils; type PByteArray = ^TByteArray; TByteArray = array [0..3] of Byte; const Crc32Table: array[Byte] of LongWord = ($00000000, $04C11DB7, $09823B6E, $0D4326D9, $130476DC, $17C56B6B, $1A864DB2, $1E475005, $2608EDB8, $22C9F00F, $2F8AD6D6, $2B4BCB61, $350C9B64, $31CD86D3, $3C8EA00A, $384FBDBD, $4C11DB70, $48D0C6C7, $4593E01E, $4152FDA9, $5F15ADAC, $5BD4B01B, $569796C2, $52568B75, $6A1936C8, $6ED82B7F, $639B0DA6, $675A1011, $791D4014, $7DDC5DA3, $709F7B7A, $745E66CD, $9823B6E0, $9CE2AB57, $91A18D8E, $95609039, $8B27C03C, $8FE6DD8B, $82A5FB52, $8664E6E5, $BE2B5B58, $BAEA46EF, $B7A96036, $B3687D81, $AD2F2D84, $A9EE3033, $A4AD16EA, $A06C0B5D, $D4326D90, $D0F37027, $DDB056FE, $D9714B49, $C7361B4C, $C3F706FB, $CEB42022, $CA753D95, $F23A8028, $F6FB9D9F, $FBB8BB46, $FF79A6F1, $E13EF6F4, $E5FFEB43, $E8BCCD9A, $EC7DD02D, $34867077, $30476DC0, $3D044B19, $39C556AE, $278206AB, $23431B1C, $2E003DC5, $2AC12072, $128E9DCF, $164F8078, $1B0CA6A1, $1FCDBB16, $018AEB13, $054BF6A4, $0808D07D, $0CC9CDCA, $7897AB07, $7C56B6B0, $71159069, $75D48DDE, $6B93DDDB, $6F52C06C, $6211E6B5, $66D0FB02, $5E9F46BF, $5A5E5B08, $571D7DD1, $53DC6066, $4D9B3063, $495A2DD4, $44190B0D, $40D816BA, $ACA5C697, $A864DB20, $A527FDF9, $A1E6E04E, $BFA1B04B, $BB60ADFC, $B6238B25, $B2E29692, $8AAD2B2F, $8E6C3698, $832F1041, $87EE0DF6, $99A95DF3, $9D684044, $902B669D, $94EA7B2A, $E0B41DE7, $E4750050, $E9362689, $EDF73B3E, $F3B06B3B, $F771768C, $FA325055, $FEF34DE2, $C6BCF05F, $C27DEDE8, $CF3ECB31, $CBFFD686, $D5B88683, $D1799B34, $DC3ABDED, $D8FBA05A, $690CE0EE, $6DCDFD59, $608EDB80, $644FC637, $7A089632, $7EC98B85, $738AAD5C, $774BB0EB, $4F040D56, $4BC510E1, $46863638, $42472B8F, $5C007B8A, $58C1663D, $558240E4, $51435D53, $251D3B9E, $21DC2629, $2C9F00F0, $285E1D47, $36194D42, $32D850F5, $3F9B762C, $3B5A6B9B, $0315D626, $07D4CB91, $0A97ED48, $0E56F0FF, $1011A0FA, $14D0BD4D, $19939B94, $1D528623, $F12F560E, $F5EE4BB9, $F8AD6D60, $FC6C70D7, $E22B20D2, $E6EA3D65, $EBA91BBC, $EF68060B, $D727BBB6, $D3E6A601, $DEA580D8, $DA649D6F, $C423CD6A, $C0E2D0DD, $CDA1F604, $C960EBB3, $BD3E8D7E, $B9FF90C9, $B4BCB610, $B07DABA7, $AE3AFBA2, $AAFBE615, $A7B8C0CC, $A379DD7B, $9B3660C6, $9FF77D71, $92B45BA8, $9675461F, $8832161A, $8CF30BAD, $81B02D74, $857130C3, $5D8A9099, $594B8D2E, $5408ABF7, $50C9B640, $4E8EE645, $4A4FFBF2, $470CDD2B, $43CDC09C, $7B827D21, $7F436096, $7200464F, $76C15BF8, $68860BFD, $6C47164A, $61043093, $65C52D24, $119B4BE9, $155A565E, $18197087, $1CD86D30, $029F3D35, $065E2082, $0B1D065B, $0FDC1BEC, $3793A651, $3352BBE6, $3E119D3F, $3AD08088, $2497D08D, $2056CD3A, $2D15EBE3, $29D4F654, $C5A92679, $C1683BCE, $CC2B1D17, $C8EA00A0, $D6AD50A5, $D26C4D12, $DF2F6BCB, $DBEE767C, $E3A1CBC1, $E760D676, $EA23F0AF, $EEE2ED18, $F0A5BD1D, $F464A0AA, $F9278673, $FDE69BC4, $89B8FD09, $8D79E0BE, $803AC667, $84FBDBD0, $9ABC8BD5, $9E7D9662, $933EB0BB, $97FFAD0C, $AFB010B1, $AB710D06, $A6322BDF, $A2F33668, $BCB4666D, $B8757BDA, $B5365D03, $B1F740B4); procedure Init(var Digest: TCRC32Digest); begin Digest := $FFFFFFFF; end; procedure Update(var Digest: TCRC32Digest; const Buffer; Count: Integer); var i: Integer; P: PByte; begin P := @Buffer; for i := 0 to Count - 1 do begin Digest := Digest shl 8 xor CRC32Table[Digest shr 24] xor (P^ and $FF); Inc(P); end; end; procedure Final(var Digest: TCRC32Digest); begin Digest := not Digest; end; function Crc32String(const S: string): TCRC32Digest; begin Result := Crc32Buffer(PChar(S)^, Length(S)); end; function Crc32File(const FileName: string): TCRC32Digest; var F: TFileStream; begin F := TFileStream.Create(FileName, fmOpenRead); try Result := Crc32Stream(F); finally F.Free; end; end; function Crc32Stream(const Stream: TStream): TCRC32Digest; var Buffer: array[0..4095] of Byte; ReadBytes, SavePos: Integer; Size, TotalBytes: Int64; begin Init(Result); Size := Stream.Size; SavePos := Stream.Position; TotalBytes := 0; try Stream.Seek(0, soFromBeginning); repeat ReadBytes := Stream.Read(Buffer, SizeOf(Buffer)); Inc(TotalBytes, ReadBytes); Update(Result, Buffer, ReadBytes); until (ReadBytes = 0) or (TotalBytes = Size); finally Stream.Seek(SavePos, soFromBeginning); end; Final(Result); end; function Crc32Buffer(const Buffer; Size: Integer): TCRC32Digest; begin Init(Result); Update(Result, Buffer, Size); Final(Result); end; function Crc32DigestToStr(const Digest: TCRC32Digest): string; begin Result := IntToHex(Digest, 8); end; function StrToCrc32Digest(const Digest: string): TCRC32Digest; function HexCharToByte(C: Char): Byte; begin Result := 0; case C of '0'..'9': Result := Ord(C) - 48; 'a'..'f': Result := Ord(C) - 87; end; end; var LCDigest: string; i: Byte; P: PByteArray; begin Result := 0; LCDigest := LowerCase(Trim(Digest)); if Length(LCDigest) <> 8 then Exit; P := @Result; for i := 0 to 3 do P[3 - i] := HexCharToByte(LCDigest[i * 2 + 1]) shl 4 + HexCharToByte(LCDigest[i * 2 + 2]); end; function Crc32DigestEquals(const D1, D2: TCRC32Digest): Boolean; begin Result := D1 = D2; end; end. |
02.08.2014, 20:39 | #12 | |
highly mean
Сообщений: 1,128
Регистрация: 26.05.2011
Возраст: 35
Не в сети |
Не, это как раз тот редкий случай, когда Spectator полностью понял поставленный вопрос, и предложил вроде адекватное решение.
Цитата:
https://github.com/php/php-src/blob/...andard/crc32.c https://github.com/php/php-src/blob/...andard/crc32.h и соответствует crc32b в приведенном выше исходнике |
|
02.08.2014, 20:46 | #13 | |
Форумец
Сообщений: 595
Регистрация: 27.03.2004
Возраст: 45
Не в сети |
Цитата:
А так все вопросы актуальны. |
|
02.08.2014, 21:31 | #14 |
Форумец
Сообщений: 40,850
Регистрация: 27.05.2003
Возраст: 46
Не в сети |
топикстартер в состоянии внятно объяснить, что ему конкретно нужно...
задача элементарная. легче всего Вам будет найти пыхапера, который её за вечер-неделю-месяц закодит. не говорю конкретный срок, чтобы потом меня палками за углом потенциальный исполнитель не побил за упущенный заработок. но реально там работы немного. сформулируйте конкретно отдельным абзацем задачу от и до, на основе того что обсудили, изложите её здесь отдельным сообщением и огласите сумму с которой готовы расстаться. всем форумом / разделом дружно Вам объяснять что и как там нужно сделать - это не самый оптимальный вариант. хотя может кто и захочет, я не знаю. |
03.08.2014, 13:44 | #15 |
Форумец
Сообщений: 595
Регистрация: 27.03.2004
Возраст: 45
Не в сети |
Собственно разобрался где не так считалось.
Собственно вот рабочий листинг. Имеем CRC32 1-го файла: AF80DB34 Имеем CRC32 2-го файла: 27F5F19D (в данном листинге используем его в качестве инициализатора). Считаем новое CRC32 для коллизии 17E7122E (файл test.tst размером 4 байта). После выполнения получаем значение CRC32 равное значению CRC32 1-го файла. Код:
unit Crc32; interface uses Classes; type TCRC32Digest = LongWord; function Crc32File(const FileName: string): TCRC32Digest; function Crc32Stream(const Stream: TStream): TCRC32Digest; function Crc32DigestToStr(const Digest: TCRC32Digest): string; implementation uses SysUtils; const Crc32Table: array[Byte] of LongWord = ($00000000, $04C11DB7, $09823B6E, $0D4326D9, $130476DC, $17C56B6B, $1A864DB2, $1E475005, $2608EDB8, $22C9F00F, $2F8AD6D6, $2B4BCB61, $350C9B64, $31CD86D3, $3C8EA00A, $384FBDBD, $4C11DB70, $48D0C6C7, $4593E01E, $4152FDA9, $5F15ADAC, $5BD4B01B, $569796C2, $52568B75, $6A1936C8, $6ED82B7F, $639B0DA6, $675A1011, $791D4014, $7DDC5DA3, $709F7B7A, $745E66CD, $9823B6E0, $9CE2AB57, $91A18D8E, $95609039, $8B27C03C, $8FE6DD8B, $82A5FB52, $8664E6E5, $BE2B5B58, $BAEA46EF, $B7A96036, $B3687D81, $AD2F2D84, $A9EE3033, $A4AD16EA, $A06C0B5D, $D4326D90, $D0F37027, $DDB056FE, $D9714B49, $C7361B4C, $C3F706FB, $CEB42022, $CA753D95, $F23A8028, $F6FB9D9F, $FBB8BB46, $FF79A6F1, $E13EF6F4, $E5FFEB43, $E8BCCD9A, $EC7DD02D, $34867077, $30476DC0, $3D044B19, $39C556AE, $278206AB, $23431B1C, $2E003DC5, $2AC12072, $128E9DCF, $164F8078, $1B0CA6A1, $1FCDBB16, $018AEB13, $054BF6A4, $0808D07D, $0CC9CDCA, $7897AB07, $7C56B6B0, $71159069, $75D48DDE, $6B93DDDB, $6F52C06C, $6211E6B5, $66D0FB02, $5E9F46BF, $5A5E5B08, $571D7DD1, $53DC6066, $4D9B3063, $495A2DD4, $44190B0D, $40D816BA, $ACA5C697, $A864DB20, $A527FDF9, $A1E6E04E, $BFA1B04B, $BB60ADFC, $B6238B25, $B2E29692, $8AAD2B2F, $8E6C3698, $832F1041, $87EE0DF6, $99A95DF3, $9D684044, $902B669D, $94EA7B2A, $E0B41DE7, $E4750050, $E9362689, $EDF73B3E, $F3B06B3B, $F771768C, $FA325055, $FEF34DE2, $C6BCF05F, $C27DEDE8, $CF3ECB31, $CBFFD686, $D5B88683, $D1799B34, $DC3ABDED, $D8FBA05A, $690CE0EE, $6DCDFD59, $608EDB80, $644FC637, $7A089632, $7EC98B85, $738AAD5C, $774BB0EB, $4F040D56, $4BC510E1, $46863638, $42472B8F, $5C007B8A, $58C1663D, $558240E4, $51435D53, $251D3B9E, $21DC2629, $2C9F00F0, $285E1D47, $36194D42, $32D850F5, $3F9B762C, $3B5A6B9B, $0315D626, $07D4CB91, $0A97ED48, $0E56F0FF, $1011A0FA, $14D0BD4D, $19939B94, $1D528623, $F12F560E, $F5EE4BB9, $F8AD6D60, $FC6C70D7, $E22B20D2, $E6EA3D65, $EBA91BBC, $EF68060B, $D727BBB6, $D3E6A601, $DEA580D8, $DA649D6F, $C423CD6A, $C0E2D0DD, $CDA1F604, $C960EBB3, $BD3E8D7E, $B9FF90C9, $B4BCB610, $B07DABA7, $AE3AFBA2, $AAFBE615, $A7B8C0CC, $A379DD7B, $9B3660C6, $9FF77D71, $92B45BA8, $9675461F, $8832161A, $8CF30BAD, $81B02D74, $857130C3, $5D8A9099, $594B8D2E, $5408ABF7, $50C9B640, $4E8EE645, $4A4FFBF2, $470CDD2B, $43CDC09C, $7B827D21, $7F436096, $7200464F, $76C15BF8, $68860BFD, $6C47164A, $61043093, $65C52D24, $119B4BE9, $155A565E, $18197087, $1CD86D30, $029F3D35, $065E2082, $0B1D065B, $0FDC1BEC, $3793A651, $3352BBE6, $3E119D3F, $3AD08088, $2497D08D, $2056CD3A, $2D15EBE3, $29D4F654, $C5A92679, $C1683BCE, $CC2B1D17, $C8EA00A0, $D6AD50A5, $D26C4D12, $DF2F6BCB, $DBEE767C, $E3A1CBC1, $E760D676, $EA23F0AF, $EEE2ED18, $F0A5BD1D, $F464A0AA, $F9278673, $FDE69BC4, $89B8FD09, $8D79E0BE, $803AC667, $84FBDBD0, $9ABC8BD5, $9E7D9662, $933EB0BB, $97FFAD0C, $AFB010B1, $AB710D06, $A6322BDF, $A2F33668, $BCB4666D, $B8757BDA, $B5365D03, $B1F740B4); procedure Init(var Digest: TCRC32Digest); begin Digest := not $9DF1F527; end; procedure Update(var Digest: TCRC32Digest; const Buffer; Count: Integer); var i: Integer; P: PByte; begin P := @Buffer; for i := 0 to Count - 1 do begin Digest := (Digest shl 8) xor (CRC32Table[(Digest shr 24) xor (P^ and $000000FF)]); Inc(P); end; end; procedure Final(var Digest: TCRC32Digest); begin Digest := not Digest; end; function Crc32File(const FileName: string): TCRC32Digest; var F: TFileStream; begin F := TFileStream.Create(FileName, fmOpenRead); try Result := Crc32Stream(F); finally F.Free; end; end; function Crc32Stream(const Stream: TStream): TCRC32Digest; var Buffer: array[0..4095] of Byte; ReadBytes, SavePos: Integer; Size, TotalBytes: Int64; begin Init(Result); Size := Stream.Size; SavePos := Stream.Position; TotalBytes := 0; try Stream.Seek(0, soFromBeginning); repeat ReadBytes := Stream.Read(Buffer, SizeOf(Buffer)); Inc(TotalBytes, ReadBytes); Update(Result, Buffer, ReadBytes); until (ReadBytes = 0) or (TotalBytes = Size); finally Stream.Seek(SavePos, soFromBeginning); end; Final(Result); end; function Crc32DigestToStr(const Digest: TCRC32Digest): string; begin Result := IntToHex(Digest, 8); end; end. Код:
program Crc32Sample; {$APPTYPE CONSOLE} uses Crc32; procedure CalcCrc32(Value: string); begin WriteLn('MD5 (''', Value, ''') = ', Crc32DigestToStr(Crc32File(Value))); end; begin CalcCrc32('c:\test.tst'); ReadLn; end. |
04.08.2014, 00:15 | #16 |
Форумец
Сообщений: 595
Регистрация: 27.03.2004
Возраст: 45
Не в сети |
Такс. Алгоритм распилил вроде.
Код:
e0 = f0 (4) (e3 e2 e1 e0) d0 = f1 XOR e1 (3) (d3 d2 d1 d0) c0 = f2 XOR e2 XOR d1 (2) (c3 c2 c1 c0) b0 = f3 XOR e3 XOR d2 XOR c1 (1) (b3 b2 b1 b0) X = (1) XOR a3 Y = (2) XOR b3 XOR a2 Z = (3) XOR c3 XOR b2 XOR a1 W = (4) XOR d3 XOR c2 XOR b1 XOR a0 |
04.08.2014, 10:33 | #18 |
Форумец
Сообщений: 595
Регистрация: 27.03.2004
Возраст: 45
Не в сети |
|