Важная информация

User Tag List

Страница 1 из 4 1234 ПоследняяПоследняя
Показано с 1 по 10 из 33

Тема: хеширование

  1. #1
    Member
    Регистрация
    14.02.2005
    Адрес
    Владивосток
    Сообщений
    111
    Благодарностей: 4
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию хеширование

    Доброго всем времени суток! Подскажите пожалуйста следующее - есть последовательность из 12 байт - существует ли алгоритм позволяющий ОДНОЗНАЧНО идентифицировать (не восстановить) эту последовательность чтобы хеш был равен 3-4 байтам и если таковой существует расскажите плз на пальцах как он работает

  2. #1
    С любовью к вам, Yandex.Direct
    Размещение рекламы на форуме способствует его дальнейшему развитию

  3. #2
    Guru
    Регистрация
    08.10.2005
    Адрес
    Москва
    Сообщений
    9,937
    Благодарностей: 3436
    Mentioned
    2 Post(s)
    Tagged
    1 Thread(s)

    По умолчанию

    Нет.
    А если просто с большой долей вероятности, то любые типа CRC32, например.

  4. Этот пользователь поблагодарил Titus за это полезное сообщение:
    mishutka (21.10.2011)

  5. #3
    Moderator
    Регистрация
    25.11.2007
    Адрес
    Симферополь
    Сообщений
    1,970
    Благодарностей: 386
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Ну если надо тебе быстро сделать подпись блока данных то 4ре байта твоей подписи могут выглядеть например так : первые два байта это просто сумма блока побайтно а вторые 2 байта - это XOR вордов входящих в последовательность.
    Если в 3 байта укладываться то первое так и оставляй сумму а третим байтом пускай побайтное исключающее ИЛИ.
    Это если я правильно понял задачу.
    Amiga 1200+Blizzard 1260 72 Mb+Mtek 68030,Compozit 128, Leningrad 2,
    Atari STE 1040,ZX Spectrum +2,Pentagon 48, Speccy2007 - 2 , ATAS 256k.
    ZX Evo 4Mb- в строю.
    Speccy2010 v1
    Специалист (пока готовлюсь к восстановлению).
    Это все мое!
    Родное!
    Все люблю на свете я! Это родина моя!

  6. #4
    Veteran Аватар для Destr
    Регистрация
    26.03.2008
    Адрес
    Питкяранта
    Сообщений
    1,426
    Благодарностей: 643
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от mishutka Посмотреть сообщение
    ОДНОЗНАЧНО идентифицировать
    По сути это пароль получается.
    Методов паролирования - как грязи.
    Выбирайте на вкус

  7. #5
    Moderator
    Регистрация
    25.11.2007
    Адрес
    Симферополь
    Сообщений
    1,970
    Благодарностей: 386
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Да просто вопрос кривовато поставлен и не совсем ясно что именно нужно топикстартеру. вопрос получается звучит примерно так - "у меня в руках электролампочка - как достоверно узнать что это электролампочка?".
    И ответов может быть сотня минимум.
    Amiga 1200+Blizzard 1260 72 Mb+Mtek 68030,Compozit 128, Leningrad 2,
    Atari STE 1040,ZX Spectrum +2,Pentagon 48, Speccy2007 - 2 , ATAS 256k.
    ZX Evo 4Mb- в строю.
    Speccy2010 v1
    Специалист (пока готовлюсь к восстановлению).
    Это все мое!
    Родное!
    Все люблю на свете я! Это родина моя!

  8. #6
    Veteran Аватар для ZXMAK
    Регистрация
    30.01.2006
    Адрес
    Харьков
    Сообщений
    1,288
    Благодарностей: 749
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от mishutka Посмотреть сообщение
    Доброго всем времени суток! Подскажите пожалуйста следующее - есть последовательность из 12 байт - существует ли алгоритм позволяющий ОДНОЗНАЧНО идентифицировать (не восстановить) эту последовательность чтобы хеш был равен 3-4 байтам и если таковой существует расскажите плз на пальцах как он работает
    однозначно идентифицировать 4-мя байтами массив из 12 байт невозможно. т.к. в 12 байтах можно разместить наааамного больше комбинаций, чем в 4-ех. Хеши используются для идентификации с некоторой вероятностью.
    Простейшая хеш функция - это просто сумма всех байт, также популярна функция xor. Однако эти простые функции плохо идентифицируют периодические последовательности. Поэтому для идентификации используют более сложные функции, обычно принято пользоваться полиномиальным представлением. На 8 битных машинах часто использовали CRC8 и CRC16. Сейчас мощности машин стали выше, объемы данных больше, поэтому используют более сложные хеш функции типа MD5, SHA1, RIPEMD128, TIGER и т.п.
    По сути суть таких функций сводится все к той-же операции xor, которая выполняется не с фиксированным ключем, а с потоком псевдослучайных чисел формируемым генератором ПСП.

    Особенность таких сложных функций заключается в том что математически сложно подобрать исходные данные под конкретное значение хеша. Поэтому можно говорить об идентификации, но это не значит что идентификация "однозначная".
    Последний раз редактировалось ZXMAK; 21.10.2011 в 22:24.
    ZXMAK2 - Виртуальная Машина ZX Spectrum http://zxmak2.codeplex.com
    ZXMAK.NET - спектрум на C# http://sourceforge.net/projects/zxmak-dotnet

  9. Эти 2 пользователя(ей) поблагодарили ZXMAK за это полезное сообщение:
    Barmaley_m (25.10.2011), GriV (27.10.2011)

  10. #7
    Moderator
    Регистрация
    25.11.2007
    Адрес
    Симферополь
    Сообщений
    1,970
    Благодарностей: 386
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Александр, пока топик стартер не выразится яснее - на чем( система или проц) с какими данными ( может это просто последовательность цифр от 0 до 11 например, а не рандомные данные), сколько разных данных в посылке может быть( например может всего 4 разных посылки существует так для такого случая хэш вообще не нужен), сколько памяти в системе где будет крутится алгоритм ( может это C51 старый контроллер и там рама всего 128 байт посему мд5 или SHA-1 особо не влезет туда) ,
    какое быстродействие системы.

    Без четкого понимания как будет работать система и в каких условиях - невозможно дать правильный совет. А давать сотню советов на каждый конкретный случай - просто не интересно.
    Последний раз редактировалось balu_dark; 21.10.2011 в 22:00.
    Amiga 1200+Blizzard 1260 72 Mb+Mtek 68030,Compozit 128, Leningrad 2,
    Atari STE 1040,ZX Spectrum +2,Pentagon 48, Speccy2007 - 2 , ATAS 256k.
    ZX Evo 4Mb- в строю.
    Speccy2010 v1
    Специалист (пока готовлюсь к восстановлению).
    Это все мое!
    Родное!
    Все люблю на свете я! Это родина моя!

  11. Этот пользователь поблагодарил balu_dark за это полезное сообщение:
    Barmaley_m (25.10.2011)

  12. #8
    Master
    Регистрация
    08.05.2007
    Адрес
    Dnepropetrovsk
    Сообщений
    880
    Благодарностей: 470
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Добавлю свои 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.

  13. Эти 4 пользователя(ей) поблагодарили Barmaley_m за это полезное сообщение:
    GriV (27.10.2011), mishutka (22.10.2011), Titus (21.10.2011), Urguk (07.03.2012)

  14. #9
    Guru
    Регистрация
    08.10.2005
    Адрес
    Москва
    Сообщений
    9,937
    Благодарностей: 3436
    Mentioned
    2 Post(s)
    Tagged
    1 Thread(s)

    По умолчанию

    Цитата Сообщение от Barmaley_m Посмотреть сообщение
    Добавлю свои 5 копеек. В этой теме не был упомянут один быстрый алгоритм хеширования, который лучше, чем просто сумма, хотя и хуже, чем CRC. Алгоритм называется "Fletcher's checksum" (контрольная сумма Флетчера).
    Хороший и быстрый алгоритм. Главное устойчив к перестановке байт, в отличие от простой суммы или простого XOR. Единственное, считаю, что можно в итоге пользоватьс лишь C2, т.к. именно она усточйчива к перемене мест байт в потоке.

  15. #10
    Veteran Аватар для ZXMAK
    Регистрация
    30.01.2006
    Адрес
    Харьков
    Сообщений
    1,288
    Благодарностей: 749
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от Titus Посмотреть сообщение
    Хороший и быстрый алгоритм. Главное устойчив к перестановке байт, в отличие от простой суммы или простого XOR. Единственное, считаю, что можно в итоге пользоватьс лишь C2, т.к. именно она усточйчива к перемене мест байт в потоке.
    лучше всего использовать MD5

    я себе для удобства написал расширение для проводника, позволяет считать кучу разных хешей, см аттачмент
    Поддерживает и командную строку, например:
    Код:
    hash.exe md5 filename.iso



    Вложения Вложения
    Последний раз редактировалось ZXMAK; 21.10.2011 в 23:44.
    ZXMAK2 - Виртуальная Машина ZX Spectrum http://zxmak2.codeplex.com
    ZXMAK.NET - спектрум на C# http://sourceforge.net/projects/zxmak-dotnet

  16. Этот пользователь поблагодарил ZXMAK за это полезное сообщение:
    GriV (27.10.2011)

Страница 1 из 4 1234 ПоследняяПоследняя

Информация о теме

Пользователи, просматривающие эту тему

Эту тему просматривают: 1 (пользователей: 0 , гостей: 1)

Ваши права

  • Вы не можете создавать новые темы
  • Вы не можете отвечать в темах
  • Вы не можете прикреплять вложения
  • Вы не можете редактировать свои сообщения
  •