Большое количество совпадений в MD5 и SHA1

@n1056 · Регистрация: 17.04.2016

Author24 — интернет-сервис помощи студентам

Коллеги, добрый день!

Подскажите в чем проблема. Вопрос в следующем.
На досуге решил проверить сколько совпадение дайджестов даст MD5 из входного сообщения длиной 1 символ при переборе кода символа от 0 до 255. Результат 112 совпадений. Многовато.
Решил проверить по той же схеме на алгоритме SHA1. Результат тот же -112 совпадений. И на тех же шагах N: 129-152,154-160,162-164,166,169,171,176,179-181,185-187,189-256.
Умом понимаю, что чудес не бывает. Во первых такого большого количества совпадений быть не должно. Во вторых на разных алгоритмах не должно быть совпадений на одних и тех же шагах.
Что я упускаю из вида?

Поиск совпадений на MD5:

Delphi

var
  Form1: TForm1;
  A,B,C,D,E,F,I,N,P,Q: Integer;
  Pass: String[3];     //пароль введенный 1й раз
  KeyMD5, KeyMD5c : String[32];
  KeyMD5m, St, St1: String[64];
  FBD, FSO,FSW: TFileStream;
  FRES: TextFile;
  KeyHC, B0: Byte;
  KeyHCS : String[8];
  Ch: Char;
  MasHex : String[16];
  CRC32, I32: DWORD;
  I64: Int64;
  B32: array [0.. 3] of Byte absolute I32;
  HashSHA1:THashSHA1;
 
procedure TForm1.Button1Click(Sender: TObject);
 
begin
  A:=0;B:=0;C:=0;
  N:=0; P:=0; Q:=0;
  CRC32 := 0;
  St := '';
   FBD := TFileStream.Create('c:\temp\bd.txt', fmCreate or fmOpenReadWrite or fmShareExclusive);
  AssignFile(FRES, 'c:\temp\res.txt');
  Rewrite(FRES);
  //repeat  // C
  //repeat  // B
  repeat  // A
    //HashSHA1.Reset;
    Pass := char(A); //+char(B); //+char(C);
    Label2.Caption := Pass;
    KeyMD5 := MD5DigestToStr(MD5String(Pass));
    FBD.Seek(0, soFromEnd);
    Label4.Caption := KeyMD5;
    Label16.Caption := Pass;
    KeyHCS := IntToHex(CRC32,8);
    Label9.Caption := KeyHCS;
    KeyMD5c := KeyHCS;
    Label10.Caption := KeyMD5c;
    KeyMD5m := KeyMD5 + KeyMD5c;
    Label14.Caption := KeyMD5m;
    Application.ProcessMessages;
    for I := 1 to 32 do
    Begin
      FBD.Write(KeyMD5[I], 1);
    End;
    N:=N+1;
    repeat
      St := '';
      FBD.Seek(P*32, soFromBeginning);
      for I := 1 to 32 do
      begin
        FBD.Read(Ch, 1);
        St := St+ Ch;
      end;
      P:=P+1;
      if KeyMD5=St Then Q:=Q+1;
      if Q=2 then
        Writeln(FRES, IntToStr(N)+' '+KeyMD5);
      if Q=2 Then break;
    until N=P;
    P:=0; Q:=0;
    A:=A+1;
    Label6.Caption := IntToStr(N);
    Application.ProcessMessages;
  until A=256;
 
  Label8.Caption := 'End.';
  CloseFile(FRES);
  FBD.Free;
end;

Поиск совпадений на SHA1:

Delphi

var
  Form1: TForm1;
  A,B,C,D,E,F,I,N,P,Q: Integer;
  Pass: String[3];     //пароль введенный 1й раз
  KeyMD5, KeyMD5c : String[40];
  KeyMD5m, St, St1: String[64];
  FBD, FSO,FSW: TFileStream;
  FRES: TextFile;
  KeyHC, B0: Byte;
  KeyHCS : String[8];
  Ch: Char;
  MasHex : String[16];
  CRC32, I32: DWORD;
  I64: Int64;
  B32: array [0.. 3] of Byte absolute I32;
  HashSHA1:THashSHA1;
 
procedure TForm1.Button1Click(Sender: TObject);
 
begin
  Font.Charset := RUSSIAN_CHARSET;
  HashSHA1:=THashSHA1.Create;
  A:=0;B:=0;C:=0;
  N:=0; P:=0; Q:=0;
  CRC32 := 0;
  St := '';
  //AssignFile(FBD, 'c:\temp\bd.txt');
  FBD := TFileStream.Create('c:\temp\bd.txt', fmCreate or fmOpenReadWrite or fmShareExclusive);
  AssignFile(FRES, 'c:\temp\res.txt');
  Rewrite(FRES);
  //repeat  // C
  //repeat  // B
  repeat  // A
    HashSHA1.Reset;
    Pass := char(A); //+char(B); //+char(C);
    Label2.Caption := Pass;
 
    FBD.Seek(0, soFromEnd);
    HashSHA1.Update(Pass);
    KeyMD5:=HashSHA1.HashAsString;
    Label4.Caption := KeyMD5;
    Label16.Caption := Pass;
 
    KeyHCS := IntToHex(CRC32,8);
    Label9.Caption := KeyHCS;
    KeyMD5c := KeyHCS;
    Label10.Caption := KeyMD5c;
    KeyMD5m := KeyMD5 + KeyMD5c;
 
    Label14.Caption := KeyMD5m;
    Application.ProcessMessages;
    for I := 1 to 40 do
    Begin
      FBD.Write(KeyMD5[I], 1);
    End;
    N:=N+1;
     repeat
      St := '';
      FBD.Seek(P*40, soFromBeginning);
      for I := 1 to 40 do
      begin
        FBD.Read(Ch, 1);
        St := St+ Ch;
      end;
      P:=P+1;
      if KeyMD5=St Then Q:=Q+1;
      if Q=2 then
        Writeln(FRES, IntToStr(N)+' '+KeyMD5);
      if Q=2 Then break;
    until N=P;
    P:=0; Q:=0;
    A:=A+1; 
    Label6.Caption := IntToStr(N);
    Application.ProcessMessages;
 
  until A=256;
 
  Label8.Caption := 'End.';
  CloseFile(FRES);
  FBD.Free;
end;

@gazlan · 04.11.2016, 20:31

Очевидно, неверно считаете.

C++

#include "stdafx.h"
 
#include <stdio.h>
#include "..\shared\hash_md5.h"
#include "..\shared\hash_sha160.h"
 
#define ASCII_SIZE               (256)
 
int main()
{
   MD5         HashMD5;
   SHA160      HashSHA160;
 
   for (int ii = 0; ii < ASCII_SIZE; ++ii)   
   {
      HashMD5.Reset();
      HashMD5.Update((BYTE*)&ii,1);
      HashMD5.Finalize();
 
      HashSHA160.Reset();
      HashSHA160.Update((BYTE*)&ii,1);
      HashSHA160.Finalize();
 
      printf("%02X:  %s  %s\n",ii,HashMD5.Signature(),HashSHA160.Signature());
   }
 
   return 0;
}

@n1056 · 04.11.2016, 21:29 **[ТС]**

Согласен. Хочу разобраться.
На Finalize и FinalizeHash (для MD5) Delphi ругается. Сообщает, что компонент не содержит данной процедуры. Странно, в описании я ее вижу.
И не много вопрос в сторону, есть реализация SHA160 для Delphi.

@gazlan · 04.11.2016, 21:52

Про Delphi ничего не знаю. Но уверен, что реализацию SHA160 можно найти в почти любом крипто-пакете.

@n1056 · 05.11.2016, 00:19 **[ТС]**

И все-таки не пойму, почему появляются одинаковые дайджесты и так много. Не должно быть такого.
Попробовал разные реализации MD5 в Delphi (модуль md5 и System.Hash). Количество повторений дают одинаковое и на одинаковых шагах.
Для разнообразия попробовал удлинить входной текст с 1 символа до 64. В итоге дайджесты от разных модулей оказались разные, а вот картина с повторами осталась та же.

@gazlan · 05.11.2016, 01:41

Ну, об этом лучше спрашивать в разделе Delphi. Для MD5 вероятность коллизии 1/2^64, так что никаких повторов быть не может. Возьмите любой хэш-калькулятор и сверьте ваши дайджесты. Меня, например (насколько я могу понять ваш код), настораживает отсутствие финализации.

@n1056 · 05.11.2016, 23:36 **[ТС]**

gazlan,

Проблема в переменной Pass. Если использовать на прямую char(A) при обращении к функции все Ок. Или если Pass:string; тоже все Ок.
Спасибо за участие.

Новые блоги и статьи
Книги и учебные ресурсы по C# InfoMaster 08.01.2025 Базовые учебники и руководства Одной из лучших книг для начинающих является "C# 10 и . NET 6 для начинающих" Эндрю Троелсена и Филиппа Джепикса . Книга последовательно раскрывает основные концепции. . .	Что такое NullReferenceException и как исправить? InfoMaster 08.01.2025 NullReferenceException - одно из самых распространенных исключений, с которым сталкиваются разработчики на C#. Это исключение возникает при попытке обратиться к членам объекта (методам, свойствам или. . .	Что такое Null Pointer Exception (NPE) и как это исправить? InfoMaster 08.01.2025 Null Pointer Exception (NPE) - это одно из самых распространенных исключений в Java, которое возникает при попытке использовать ссылку на объект, значение которой равно null. Это исключение относится. . .	Русский язык в консоли C++ InfoMaster 08.01.2025 При разработке программ на C++ одной из частых проблем, с которой сталкиваются русскоязычные программисты, является корректное отображение кириллицы в консольных приложениях. Эта проблема особенно. . .	Telegram бот на C# InfoMaster 08.01.2025 Разработка ботов для Telegram стала неотъемлемой частью современной экосистемы мессенджеров. C# предоставляет мощный и удобный инструментарий для создания разнообразных ботов, от простых. . .	Использование GraphQL в Go (Golang) InfoMaster 08.01.2025 Go (Golang) является одним из наиболее популярных языков программирования, используемых для создания высокопроизводительных серверных приложений. Его архитектурные особенности и встроенные. . .
Что лучше использовать при создании класса в Java: сеттеры или конструктор? Alexander-7 08.01.2025 Вопрос подробнее: На вопрос: «Когда одновременно создаются конструктор и сеттеры в классе – это нормально?» куратор уточнил: «Ваш класс может вообще не иметь сеттеров, а только конструктор и геттеры. . .	Как работать с GraphQL на TypeScript InfoMaster 08.01.2025 Введение в GraphQL и TypeScript В современной разработке веб-приложений GraphQL стал мощным инструментом для создания гибких и эффективных API. В сочетании с TypeScript, эта технология. . .	Счётчик на базе сумматоров + регистров и генератора сигналов согласования. Hrethgir 07.01.2025 Создан с целью проверки скорости асинхронной логики: ранее описанного сумматора и предополагаемых fast регистров. Регистры созданы на базе ранее описанного, предполагаемого fast триггера. То-есть. . .	Как перейти с Options API на Composition API в Vue.js BasicMan 06.01.2025 Почему переход на Composition API актуален В мире современной веб-разработки фреймворк Vue. js продолжает эволюционировать, предлагая разработчикам все более совершенные инструменты для создания. . .	Архитектура современных процессоров inter-admin 06.01.2025 Процессор (центральный процессор, ЦП) является основным вычислительным устройством компьютера, которое выполняет обработку данных и управляет работой всех остальных компонентов системы. Архитектура. . .	История создания реляционной модели баз данных, правила Кодда Programming 06.01.2025 Предпосылки создания реляционной модели В конце 1960-х годов компьютерная индустрия столкнулась с серьезными проблемами в области управления данными. Существовавшие на тот момент модели данных -. . .

@n1056 0 / 0 / 1 Регистрация: 17.04.2016 Сообщений: 77
	04.11.2016, 21:29 [ТС]	3
	Согласен. Хочу разобраться. На Finalize и FinalizeHash (для MD5) Delphi ругается. Сообщает, что компонент не содержит данной процедуры. Странно, в описании я ее вижу. И не много вопрос в сторону, есть реализация SHA160 для Delphi. 0

@gazlan 3176 / 1935 / 312 Регистрация: 27.08.2010 Сообщений: 5,131 Записей в блоге: 1
	04.11.2016, 21:52	4
	Про Delphi ничего не знаю. Но уверен, что реализацию SHA160 можно найти в почти любом крипто-пакете. 0

@n1056 0 / 0 / 1 Регистрация: 17.04.2016 Сообщений: 77
	05.11.2016, 00:19 [ТС]	5
	И все-таки не пойму, почему появляются одинаковые дайджесты и так много. Не должно быть такого. Попробовал разные реализации MD5 в Delphi (модуль md5 и System.Hash). Количество повторений дают одинаковое и на одинаковых шагах. Для разнообразия попробовал удлинить входной текст с 1 символа до 64. В итоге дайджесты от разных модулей оказались разные, а вот картина с повторами осталась та же. 0

@gazlan 3176 / 1935 / 312 Регистрация: 27.08.2010 Сообщений: 5,131 Записей в блоге: 1
	05.11.2016, 01:41	6
	Ну, об этом лучше спрашивать в разделе Delphi. Для MD5 вероятность коллизии 1/2^64, так что никаких повторов быть не может. Возьмите любой хэш-калькулятор и сверьте ваши дайджесты. Меня, например (насколько я могу понять ваш код), настораживает отсутствие финализации. 1

@n1056 0 / 0 / 1 Регистрация: 17.04.2016 Сообщений: 77
	05.11.2016, 23:36 [ТС]	7
	gazlan, Проблема в переменной Pass. Если использовать на прямую char(A) при обращении к функции все Ок. Или если Pass:string; тоже все Ок. Спасибо за участие. 0