Просмотр полной версии : хеширование
mishutka
21.10.2011, 15:11
Доброго всем времени суток! Подскажите пожалуйста следующее - есть последовательность из 12 байт - существует ли алгоритм позволяющий ОДНОЗНАЧНО идентифицировать (не восстановить) эту последовательность чтобы хеш был равен 3-4 байтам и если таковой существует расскажите плз на пальцах как он работает
Нет.
А если просто с большой долей вероятности, то любые типа CRC32, например.
balu_dark
21.10.2011, 17:05
Ну если надо тебе быстро сделать подпись блока данных то 4ре байта твоей подписи могут выглядеть например так : первые два байта это просто сумма блока побайтно а вторые 2 байта - это XOR вордов входящих в последовательность.
Если в 3 байта укладываться то первое так и оставляй сумму а третим байтом пускай побайтное исключающее ИЛИ.
Это если я правильно понял задачу.
ОДНОЗНАЧНО идентифицировать
По сути это пароль получается.
Методов паролирования - как грязи.
Выбирайте на вкус :)
balu_dark
21.10.2011, 22:01
Да просто вопрос кривовато поставлен и не совсем ясно что именно нужно топикстартеру. вопрос получается звучит примерно так - "у меня в руках электролампочка - как достоверно узнать что это электролампочка?".
И ответов может быть сотня минимум.
Доброго всем времени суток! Подскажите пожалуйста следующее - есть последовательность из 12 байт - существует ли алгоритм позволяющий ОДНОЗНАЧНО идентифицировать (не восстановить) эту последовательность чтобы хеш был равен 3-4 байтам и если таковой существует расскажите плз на пальцах как он работает
однозначно идентифицировать 4-мя байтами массив из 12 байт невозможно. т.к. в 12 байтах можно разместить наааамного больше комбинаций, чем в 4-ех. Хеши используются для идентификации с некоторой вероятностью.
Простейшая хеш функция - это просто сумма всех байт, также популярна функция xor. Однако эти простые функции плохо идентифицируют периодические последовательности. Поэтому для идентификации используют более сложные функции, обычно принято пользоваться полиномиальным представлением. На 8 битных машинах часто использовали CRC8 и CRC16. Сейчас мощности машин стали выше, объемы данных больше, поэтому используют более сложные хеш функции типа MD5, SHA1, RIPEMD128, TIGER и т.п.
По сути суть таких функций сводится все к той-же операции xor, которая выполняется не с фиксированным ключем, а с потоком псевдослучайных чисел формируемым генератором ПСП.
Особенность таких сложных функций заключается в том что математически сложно подобрать исходные данные под конкретное значение хеша. Поэтому можно говорить об идентификации, но это не значит что идентификация "однозначная".
balu_dark
21.10.2011, 22:58
Александр, пока топик стартер не выразится яснее - на чем( система или проц) с какими данными ( может это просто последовательность цифр от 0 до 11 например, а не рандомные данные), сколько разных данных в посылке может быть( например может всего 4 разных посылки существует так для такого случая хэш вообще не нужен), сколько памяти в системе где будет крутится алгоритм ( может это C51 старый контроллер и там рама всего 128 байт посему мд5 или SHA-1 особо не влезет туда) ,
какое быстродействие системы.
Без четкого понимания как будет работать система и в каких условиях - невозможно дать правильный совет. А давать сотню советов на каждый конкретный случай - просто не интересно.
Barmaley_m
21.10.2011, 23:44
Добавлю свои 5 копеек. В этой теме не был упомянут один быстрый алгоритм хеширования, который лучше, чем просто сумма, хотя и хуже, чем CRC. Алгоритм называется "Fletcher's checksum" (контрольная сумма Флетчера). Согласно английской Википедии, алгоритм реализуется следующим образом.
Пусть исходная последовательность из n чисел представлена в виде байтов x[1], x[2], ..., x[n], Тогда определим последовательность частичных сумм:
c1[i] = x[1] + x[2] + ... + x[i] - сумма всех чисел последовательности с 1-го по i-e включительно (i<n)
Контрольная сумма Флетчера состоит из двух чисел. Первое из них - это простая сумма всех чисел исходной последовательности:
C1 = c1[n] = x[1] + x[2] + ... + x[n]
Второй компонент суммы Флетчера - это сумма последовательности частичных сумм, определенной ранее:
C2 = c1[1] + c1[2] + ... + c1[n].
Алгоритм вычисления на бейсике следующий:
10 LET n = 100
20 DIM x(n)
30 REM ... заполнить массив x какими-нибудь данными ...
40 LET C1 = 0
50 LET C2 = 0
60 FOR i=1 TO n
70 LET C1 = C1 + x(i)
80 LET C2 = C2 + C1
90 NEXT i
100 REM после выполнения программы C1 и C2 - сумма Флетчера от массива x.
Добавлю свои 5 копеек. В этой теме не был упомянут один быстрый алгоритм хеширования, который лучше, чем просто сумма, хотя и хуже, чем CRC. Алгоритм называется "Fletcher's checksum" (контрольная сумма Флетчера).
Хороший и быстрый алгоритм. Главное устойчив к перестановке байт, в отличие от простой суммы или простого XOR. Единственное, считаю, что можно в итоге пользоватьс лишь C2, т.к. именно она усточйчива к перемене мест байт в потоке.
Хороший и быстрый алгоритм. Главное устойчив к перестановке байт, в отличие от простой суммы или простого XOR. Единственное, считаю, что можно в итоге пользоватьс лишь C2, т.к. именно она усточйчива к перемене мест байт в потоке.
лучше всего использовать MD5 :)
я себе для удобства написал расширение для проводника, позволяет считать кучу разных хешей, см аттачмент :)
Поддерживает и командную строку, например:
hash.exe md5 filename.iso
http://img692.imageshack_.us/img692/3507/hash1.png
http://img508.imageshack_.us/img508/9909/hash2.png
лучше всего использовать MD5 :-)
Где? В задаче, о которой спрашивал топикстартер? Мд5, в котором хеш 16 байт? Ну-ну... Не в обиду будет сказано, но желательно читать ветки целиком, дабы не представляться в виде Капитана Очевидности, или же енотика из мультфильма, любимая фраза которого была 'А вот я, например...'
Где? В задаче, о которой спрашивал топикстартер? Мд5, в котором хеш 16 байт? Ну-ну...
а почему бы и нет? по крайней мере хоть одна реализация MD5 на спектруме появится :)
а почему бы и нет? по крайней мере хоть одна реализация MD5 на спектруме появится :)
Человек просил хеш до 4 байт для 12 байтной последовательности. Какая реализация? Аааа! )
mishutka
22.10.2011, 12:57
Всем спасибо за ответы! уточню задачу. кол-во байт всегда 12 (не больше не меньше). значение каждого байта может быть любым (от 0 до 255). подскажите плз алгоритм (напишите на sinclair basice в идеале) что бы идентификация была близка к той же md5
balu_dark
22.10.2011, 17:54
где оно будет работать? скорость проца и количество памяти?
Всем спасибо за ответы! уточню задачу. кол-во байт всегда 12 (не больше не меньше). значение каждого байта может быть любым (от 0 до 255). подскажите плз алгоритм (напишите на sinclair basice в идеале) что бы идентификация была близка к той же md5
ADD в помощь. Ну и зачем такой изврат на спеке?
подскажите плз алгоритм (напишите на sinclair basice в идеале) что бы идентификация была близка к той же md5
таки crc32 не устраивает? или что?
mishutka
23.10.2011, 01:22
таки crc32 не устраивает? хочется точность чуть выше чем у crc32
где оно будет работать? скорость проца и количество памяти? работать будет дома на столе 3.5MHz 49152 байт
хочется точность чуть выше чем у crc32
работать будет дома на столе 3.5MHz 49152 байт
тогда прийдется MD5 реализовывать :v2_dizzy_army:
хочется точность чуть выше чем у crc32
Имхо, не исключено, что тебе и crc16 вполне может хватить.
интересно, как в 4 байта сделать точность выше, чем у crc32?? crc32 - вполне себе хороший некриптографический хеш. изменение только одного входного бита сильно влияет на результат. так чего же еще нужно-то? если надо длиннее сам хеш и не хочется заморачиваться со сложными md5, sha, посчитайте тот же crc32 но задом-наперед. будет 8 байт хеша...
прошу прощения а разве crc32 не 4 байта занимает?
Barmaley_m
24.10.2011, 00:15
Автор, а почему, зачем тебе нужна "точность" выше, чем у CRC32? Какие ты можешь себе представить себе гипотетические ситуации, чтобы "точность" CRC32 оказалась недостаточной?
MD5, SHA1 и прочие - это стрельба из пушки по воробьям. Вычисление этих хеш-функций чрезвычайно затратно по вычислительным ресурсам. Поэтому оно оправдано только в тех случаях, когда необходима криптографическая защита, то есть защита от _умышленного_ создания хеш-коллизий _разумным_существом_. По отношению к случайным модификациям данных у этих криптографических хеш-функций нет никаких преимуществ по сравнению с более простыми, некриптографическими, хеш-функциями той же длины.
Для оценки хеш-фукнций с точки зрения защиты от случайных совпадений используется понятие "дистанция Хэмминга" - минимальное количество бит, которые необходимо инвертировать в исходных данных для получения хеш-коллиции. Имеется в виду инверсия не любых бит, а наиболее неудачное их сочетание. Для CRC32 дистанция Хэмминга составляет 6 бит, для XOR она составляет два бита, для ADD примерно столько же, для суммы Флетчера что-то среднее между 2 и 6 (3 кажется). Я некоторое время назад исследовал этот вопрос и пришел к выводу, что для обеспечения хорошей (некриптографической) защиты от коллизии следует использовать CRC, но этот алгоритм довольно затратен по вычислениям, поэтому, когда важна скорость, можно использовать сумму Флетчера.
---------- Post added at 22:15 ---------- Previous post was at 22:13 ----------
А вообще, автор, расскажи, зачем тебе нужен хеш, в какой ситуации ты планируешь его использовать? Может мы подскажем, что лучше, исходя из решаемой задачи.
balu_dark
24.10.2011, 01:06
Может человек переделывает платку Igrosoft раз упорно не признается для чего ему это. но для таких применений уже как раз нужен хотя бы MD5.
mishutka
24.10.2011, 11:54
Благодарю всех за ответы - я остановлюсь на crc32 - просьба - напишите на basice плз алгоритм как его подсчитать?
реализация на PC асм (http://www.manhunter.ru/assembler/106_raschet_crc32_na_assemblere.html)врядли на басике будет быстро
Barmaley_m
24.10.2011, 23:25
Для реализации CRC есть два варианта. Первый - быстрый, но использует память. Так, например, для CRC32 требуется 256*4 = 1024 байт памяти. Однако при этом удается избежать дорогостоящей операции побитового сдвига. Другой алгоритм, который не использует память, кроме как для счетчиков и текущего значения CRC, более приспособлен для применения в микроконтроллерах, где обычно очень мало памяти, однако этот алгоритм в несколько раз медленнее.
Вот быстрый алгоритм на 386 asm, который я использовал в своей программе CRC Wacher. На современных процах такой алгоритм может обрабатывать сотни мегабайт в секунду с неполной нагрузкой на проц. Автор программы - не я (нашел где-то в интернете исходник). Сначала требуется подготовить таблицу в памяти, это делает следующая программка:
// Build CRC table
DWORD* ctbl = crctable;
__asm
{
mov edx,ctbl;
xor ebx,ebx // table pointer
InitTableLoop:
xor eax,eax // eax=0 for new position
mov al,bl // low 8 bytes of ebx new position
xor cx,cx
entryLoop:
test eax,1
jz no_topbit
shr eax,1
xor eax,0xEDB88320 // poly
jmp entrygoon
no_topbit:
shr eax,1
entrygoon:
inc cx
test cx,8
jz entryLoop
mov dword ptr[ebx*4+edx],eax
inc ebx
test ebx,256
jz InitTableLoop
}
Та же подпрограмма, переведенная на язык С:
DWORD* edx = ctbl;
DWORD ebx = 0;
DWORD eax;
unsigned short cx;
do
{
eax = 0; // eax=0 for new position
eax = ebx & 0xFF; // low 8 bits of ebx new position
cx = 0;
do
{
if(eax & 1)
{
eax>>=1;
eax ^= 0xEDB88320; // poly
}
else
{
eax>>=1;
}
cx++;
} while(cx<8);
*(edx+ebx) = eax;
ebx++;
} while(ebx<256);
Для вычисления CRC, когда исходная таблица в памяти подготовлена, используется следующая программа (в двух вариантах, на асме и на си):
DWORD comp_crc(DWORD* crctbl, const char* data, DWORD inicrc, int dsize)
{
#ifdef _M_IX86
__asm
{
mov eax,inicrc
mov esi,data
mov ecx,dsize
mov edx,crctbl
xor ebx,ebx
compCrcLoop:
xor al,byte ptr[esi]
mov bl,al
shr eax,8
xor eax,dword ptr[4*ebx+edx]
inc esi
loop compCrcLoop
}
#else
DWORD eax = inicrc;
const unsigned char* esi = (const unsigned char*)data;
int ecx = dsize;
DWORD* edx = crctbl;
DWORD ebx = 0;
do
{
eax ^= *esi;
ebx = eax & 0x000000FF;
eax >>= 8;
eax ^= *(edx+ebx);
esi++;
} while(--ecx);
return eax;
#endif
}
аргументы программы:
crctbl - таблица, рассчитанная приведенной выше программой подготовки;
data - блок данных, по которым надо посчитать crc
inicrc - исходное значение CRC
dsize - размер данных, в байтах
возвращаемое значение - обновленное значение CRC
Данная программа позволяет обрабатывать большие блоки данных по частям. Сначала нужно проинициализировать исходное значение CRC числом FFFFFFFF. После этого нужно вызвать comp_crc для каждой части последовательно, при этом каждый раз обновляя текущее значение CRC. По окончании обработки большого файла текущее значение CRC нужно проинвертировать - это и будет искомый CRC32.
Если файл маленький и влезает в память целиком - то comp_crc нужно вызывать только один раз. Сценарий примерно такой:
DWORD crc = 0xFFFFFFFF;
crc = comp_crc(crctbl, data, crc, dsize);
crc = ~crc;
В результате исполнения этих трех строк в переменной crc будет значение crc32 от блока данных.
mishutka
25.10.2011, 12:32
Оно спасибо конечно за процедуры на x86, но хотелось бы увидеть ВЫЧИСЛЕНИЕ (а не табличное копирование) CRC32 на Sinclair Basic - скорость пускай вас не беспокоит
на синклер-бейсике нет ни сдвигов, ни ксора... лучше посмотреть реализацию на си и понять смысл. там кратко и ёмко. а потом уже переписать на бейсик для понимания.
Ну ты конечно серьезно предлагаешь всем тут шевелить ушами через верхнюю левую пятку wiki (http://ru.wikipedia.org/wiki/%D0%A6%D0%B8%D0%BA%D0%BB%D0%B8%D1%87%D0%B5%D1%81%D 0%BA%D0%B8%D0%B9_%D0%B8%D0%B7%D0%B1%D1%8B%D1%82%D0 %BE%D1%87%D0%BD%D1%8B%D0%B9_%D0%BA%D0%BE%D0%B4#CRC-32)
---------- Post added at 14:02 ---------- Previous post was at 13:57 ----------
вот тут еще пакет вариантов (http://pascal.sources.ru/crc/crc-32.htm)
mishutka
25.10.2011, 14:23
Всем спасибо. топик закрыт
вот вариант без таблиц, думаю, не составит труда разобраться (наверное;)).
unsigned long crc_octets(const unsigned char *octets, int len)
{
unsigned long crc = 0xFFFFFFFF;
unsigned long temp;
int j;
while (len--)
{
temp = (unsigned long)((crc & 0xFF) ^ *octets++);
for (j = 0; j < 8; j++)
{
if (temp & 0x1)
temp = (temp >> 1) ^ 0xEDB88320;
else
temp >>= 1;
}
crc = (crc >> 8) ^ temp;
}
return crc ^ 0xFFFFFFFF;
}
Barmaley_m
25.10.2011, 21:02
Для остальных присутствующих хочу заметить важный момент о CRC. Существует много вариантов вычисления CRC даже при одинаковой ее длине (32 бита): во-первых может быть разным направление сдвига (в "стандартной" CRC32 он идет слева направо), во-вторых, может быть разным значение полинома (в "стандартной" CRC32 полином равен 0xEDB88320). Под "Стандартной" CRC-32 имеется в виду та, которая используется в Ethernet и вообще наиболее распространена на PC: так, например, архиваторы ZIP и RAR используют именно этот алгоритм для вычисления CRC для контроля целостности файлов в архивах.
В последнем сообщении от psb приведена программа для расчета именно этой "стандартной" CRC. Этим она ценна, а также своей краткостью и простотой. Хотя нетабличный расчет CRC выполняется намного дольше табличного: данные обрабатываются побитно, и внутренний цикл выполняется для каждого бита входных данных. При табличном же расчете внутренний цикл выполняется для каждого байта, а не бита. Прирост в скорости более чем в 8 раз.
Примеры, которые приведены в Википедии, используют другой полином и поэтому могут доставить неприятности программисту, пытающемуся повторить стандартный алгоритм и получить совместимые с ним результаты.
Powered by vBulletin® Version 4.2.5 Copyright © 2026 vBulletin Solutions, Inc. All rights reserved. Перевод: zCarot