Вид для печати
Доброго всем времени суток! Подскажите пожалуйста следующее - есть последовательность из 12 байт - существует ли алгоритм позволяющий ОДНОЗНАЧНО идентифицировать (не восстановить) эту последовательность чтобы хеш был равен 3-4 байтам и если таковой существует расскажите плз на пальцах как он работает
Нет.
А если просто с большой долей вероятности, то любые типа CRC32, например.
Ну если надо тебе быстро сделать подпись блока данных то 4ре байта твоей подписи могут выглядеть например так : первые два байта это просто сумма блока побайтно а вторые 2 байта - это XOR вордов входящих в последовательность.
Если в 3 байта укладываться то первое так и оставляй сумму а третим байтом пускай побайтное исключающее ИЛИ.
Это если я правильно понял задачу.
По сути это пароль получается.Цитата:
Сообщение от mishutka
Методов паролирования - как грязи.
Выбирайте на вкус :)
Да просто вопрос кривовато поставлен и не совсем ясно что именно нужно топикстартеру. вопрос получается звучит примерно так - "у меня в руках электролампочка - как достоверно узнать что это электролампочка?".
И ответов может быть сотня минимум.
однозначно идентифицировать 4-мя байтами массив из 12 байт невозможно. т.к. в 12 байтах можно разместить наааамного больше комбинаций, чем в 4-ех. Хеши используются для идентификации с некоторой вероятностью.Цитата:
Сообщение от mishutka
Простейшая хеш функция - это просто сумма всех байт, также популярна функция xor. Однако эти простые функции плохо идентифицируют периодические последовательности. Поэтому для идентификации используют более сложные функции, обычно принято пользоваться полиномиальным представлением. На 8 битных машинах часто использовали CRC8 и CRC16. Сейчас мощности машин стали выше, объемы данных больше, поэтому используют более сложные хеш функции типа MD5, SHA1, RIPEMD128, TIGER и т.п.
По сути суть таких функций сводится все к той-же операции xor, которая выполняется не с фиксированным ключем, а с потоком псевдослучайных чисел формируемым генератором ПСП.
Особенность таких сложных функций заключается в том что математически сложно подобрать исходные данные под конкретное значение хеша. Поэтому можно говорить об идентификации, но это не значит что идентификация "однозначная".
Александр, пока топик стартер не выразится яснее - на чем( система или проц) с какими данными ( может это просто последовательность цифр от 0 до 11 например, а не рандомные данные), сколько разных данных в посылке может быть( например может всего 4 разных посылки существует так для такого случая хэш вообще не нужен), сколько памяти в системе где будет крутится алгоритм ( может это C51 старый контроллер и там рама всего 128 байт посему мд5 или SHA-1 особо не влезет туда) ,
какое быстродействие системы.
Без четкого понимания как будет работать система и в каких условиях - невозможно дать правильный совет. А давать сотню советов на каждый конкретный случай - просто не интересно.
Добавлю свои 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.
Хороший и быстрый алгоритм. Главное устойчив к перестановке байт, в отличие от простой суммы или простого XOR. Единственное, считаю, что можно в итоге пользоватьс лишь C2, т.к. именно она усточйчива к перемене мест байт в потоке.Цитата:
Сообщение от Barmaley_m
лучше всего использовать MD5 :)Цитата:
Сообщение от Titus
я себе для удобства написал расширение для проводника, позволяет считать кучу разных хешей, см аттачмент :)
Поддерживает и командную строку, например:
Код:hash.exe md5 filename.iso
http://img692.imageshack_.us/img692/3507/hash1.png
http://img508.imageshack_.us/img508/9909/hash2.png
Где? В задаче, о которой спрашивал топикстартер? Мд5, в котором хеш 16 байт? Ну-ну... Не в обиду будет сказано, но желательно читать ветки целиком, дабы не представляться в виде Капитана Очевидности, или же енотика из мультфильма, любимая фраза которого была 'А вот я, например...'Цитата:
Сообщение от Alexander Makeev
а почему бы и нет? по крайней мере хоть одна реализация MD5 на спектруме появится :)Цитата:
Сообщение от Titus
Человек просил хеш до 4 байт для 12 байтной последовательности. Какая реализация? Аааа! )Цитата:
Сообщение от Alexander Makeev
Всем спасибо за ответы! уточню задачу. кол-во байт всегда 12 (не больше не меньше). значение каждого байта может быть любым (от 0 до 255). подскажите плз алгоритм (напишите на sinclair basice в идеале) что бы идентификация была близка к той же md5
где оно будет работать? скорость проца и количество памяти?
ADD в помощь. Ну и зачем такой изврат на спеке?Цитата:
Сообщение от mishutka
таки crc32 не устраивает? или что?Цитата:
Сообщение от mishutka
хочется точность чуть выше чем у crc32Цитата:
Сообщение от psb
работать будет дома на столе 3.5MHz 49152 байтЦитата:
Сообщение от balu_dark
тогда прийдется MD5 реализовывать :v2_dizzy_army:Цитата:
Сообщение от mishutka
Имхо, не исключено, что тебе и crc16 вполне может хватить.Цитата:
Сообщение от mishutka
интересно, как в 4 байта сделать точность выше, чем у crc32?? crc32 - вполне себе хороший некриптографический хеш. изменение только одного входного бита сильно влияет на результат. так чего же еще нужно-то? если надо длиннее сам хеш и не хочется заморачиваться со сложными md5, sha, посчитайте тот же crc32 но задом-наперед. будет 8 байт хеша...
прошу прощения а разве crc32 не 4 байта занимает?
Автор, а почему, зачем тебе нужна "точность" выше, чем у CRC32? Какие ты можешь себе представить себе гипотетические ситуации, чтобы "точность" CRC32 оказалась недостаточной?
MD5, SHA1 и прочие - это стрельба из пушки по воробьям. Вычисление этих хеш-функций чрезвычайно затратно по вычислительным ресурсам. Поэтому оно оправдано только в тех случаях, когда необходима криптографическая защита, то есть защита от _умышленного_ создания хеш-коллизий _разумным_существом_. По отношению к случайным модификациям данных у этих криптографических хеш-функций нет никаких преимуществ по сравнению с более простыми, некриптографическими, хеш-функциями той же длины.
Для оценки хеш-фукнций с точки зрения защиты от случайных совпадений используется понятие "дистанция Хэмминга" - минимальное количество бит, которые необходимо инвертировать в исходных данных для получения хеш-коллиции. Имеется в виду инверсия не любых бит, а наиболее неудачное их сочетание. Для CRC32 дистанция Хэмминга составляет 6 бит, для XOR она составляет два бита, для ADD примерно столько же, для суммы Флетчера что-то среднее между 2 и 6 (3 кажется). Я некоторое время назад исследовал этот вопрос и пришел к выводу, что для обеспечения хорошей (некриптографической) защиты от коллизии следует использовать CRC, но этот алгоритм довольно затратен по вычислениям, поэтому, когда важна скорость, можно использовать сумму Флетчера.
---------- Post added at 22:15 ---------- Previous post was at 22:13 ----------
А вообще, автор, расскажи, зачем тебе нужен хеш, в какой ситуации ты планируешь его использовать? Может мы подскажем, что лучше, исходя из решаемой задачи.
Может человек переделывает платку Igrosoft раз упорно не признается для чего ему это. но для таких применений уже как раз нужен хотя бы MD5.
Благодарю всех за ответы - я остановлюсь на crc32 - просьба - напишите на basice плз алгоритм как его подсчитать?
реализация на PC асмврядли на басике будет быстро
Для реализации 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 от блока данных.
Оно спасибо конечно за процедуры на x86, но хотелось бы увидеть ВЫЧИСЛЕНИЕ (а не табличное копирование) CRC32 на Sinclair Basic - скорость пускай вас не беспокоит
на синклер-бейсике нет ни сдвигов, ни ксора... лучше посмотреть реализацию на си и понять смысл. там кратко и ёмко. а потом уже переписать на бейсик для понимания.
Ну ты конечно серьезно предлагаешь всем тут шевелить ушами через верхнюю левую пятку wiki
---------- Post added at 14:02 ---------- Previous post was at 13:57 ----------
вот тут еще пакет вариантов
Всем спасибо. топик закрыт
вот вариант без таблиц, думаю, не составит труда разобраться (наверное;)).
Код: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;
}
Для остальных присутствующих хочу заметить важный момент о CRC. Существует много вариантов вычисления CRC даже при одинаковой ее длине (32 бита): во-первых может быть разным направление сдвига (в "стандартной" CRC32 он идет слева направо), во-вторых, может быть разным значение полинома (в "стандартной" CRC32 полином равен 0xEDB88320). Под "Стандартной" CRC-32 имеется в виду та, которая используется в Ethernet и вообще наиболее распространена на PC: так, например, архиваторы ZIP и RAR используют именно этот алгоритм для вычисления CRC для контроля целостности файлов в архивах.
В последнем сообщении от psb приведена программа для расчета именно этой "стандартной" CRC. Этим она ценна, а также своей краткостью и простотой. Хотя нетабличный расчет CRC выполняется намного дольше табличного: данные обрабатываются побитно, и внутренний цикл выполняется для каждого бита входных данных. При табличном же расчете внутренний цикл выполняется для каждого байта, а не бита. Прирост в скорости более чем в 8 раз.
Примеры, которые приведены в Википедии, используют другой полином и поэтому могут доставить неприятности программисту, пытающемуся повторить стандартный алгоритм и получить совместимые с ним результаты.