Например TDA7294

Форум РадиоКот • Просмотр темы - Хитрые, необычные алгоритмы и код
Форум РадиоКот
Здесь можно немножко помяукать :)



Текущее время: Вт мар 09, 2021 13:41:16

Часовой пояс: UTC + 3 часа


ПРЯМО СЕЙЧАС:



Начать новую тему Ответить на тему  [ Сообщений: 186 ]     ... , , , 8, ,  
Автор Сообщение
Не в сети
 Заголовок сообщения: Re: Хитрые, необычные алгоритмы и код
СообщениеДобавлено: Вт фев 26, 2019 14:05:45 
Поставщик валерьянки для Кота
Аватар пользователя

Карма: 41
Рейтинг сообщений: 302
Зарегистрирован: Пт сен 07, 2018 20:20:02
Сообщений: 2253
Рейтинг сообщения: 0
Медали: 1
Получил миской по аватаре (1)
Еще проще просто сумма, качество обнаружения ошибки падает, но не критично

На самом деле зависит от конкретной ситуации. Например, при параллельной передаче байте, если одна из шин битая (всегда 0 или 1), то "просто сумма" этой ошибки не увидит вообще, а CRC - увидит.

Если же говорить о МК, то лучше сочетать "просто сумму" с контролем четности. Тогда не только всегда выявим двойную ошибку в блоке данных, но и сможем исправить одиночную.
Для примера. Пусть мы передает по последовательному каналу байты. Пусть блок у нас 8 байт. Добавляем к каждому передаваемому байту бит четности и после каждых 8 байт пересылаем сумму (XOR) этих 8 байтов девятым контрольным байтом. Тогда, если ошибка была в одном бите, то не совпадет бит четности в ошибочном байте и один бит в контрольной сумме. То есть, если инвертировать в ошибочном байте тот бит, который не совпал в контрольной сумме - ошибка будет исправлена.


Вернуться наверх
 
Не в сети
 Заголовок сообщения: Re: Хитрые, необычные алгоритмы и код
СообщениеДобавлено: Ср фев 27, 2019 01:30:34 
Это не хвост, это антенна
Аватар пользователя

Карма: 17
Рейтинг сообщений: 20
Зарегистрирован: Чт апр 04, 2013 22:22:57
Сообщений: 1306
Откуда: Белгород, РФ
Рейтинг сообщения: 0
На самом деле зависит от конкретной ситуации. Например, при параллельной передаче байте, если одна из шин битая (всегда 0 или 1), то "просто сумма" этой ошибки не увидит вообще, а CRC - увидит.


Увидит, передаем 0000 и 0000 сумма 0000, битая шина в 1 установлена, в итоге приняли 0001 и 0001, посчитали контрольную контрольную сумму 0010, ничего не совпадает.

Совпадет XOR, сумма по модулю 2, двойная ошибка может легко проскочить. А полная сумма немного перемешивает биты между собой и это хорошо.

Цитата:
Если же говорить о МК, то лучше сочетать "просто сумму" с контролем четности. Тогда не только всегда выявим двойную ошибку в блоке данных, но и сможем исправить одиночную.


Цитата:
Для примера. Пусть мы передает по последовательному каналу байты. Пусть блок у нас 8 байт. Добавляем к каждому передаваемому байту бит четности и после каждых 8 байт пересылаем сумму (XOR) этих 8 байтов девятым контрольным байтом. Тогда, если ошибка была в одном бите, то не совпадет бит четности в ошибочном байте и один бит в контрольной сумме. То есть, если инвертировать в ошибочном байте тот бит, который не совпал в контрольной сумме - ошибка будет исправлена.


Да, типа по столбикам и строкам отдельно биты четности.

Только контрольная сумма очень слабая. 2 сбойных бита в одном столбике и 2 бита в строке дадут иллюзию правильных данных.
Или 3 сбойных бита, а мы восстанавливая данные портим 4й бит и получаем иллюзию целых данных.
Нужна гарантия что сбойных бит всего 1.
По хорошему всё это хозяйство нужно подписать правильной CRC.


Вернуться наверх
 
Друзья! Скоро Новый Год! Китайский! Но мы работаем и в праздники тоже!

JLCPCB, всего $2 за прототип печатной платы! Цвет - любой!

Отличное качество, подтвержденное более чем 600,000 пользователей! Более 10,000 заказов в день.

Зарегистрируйтесь и получите два купона по 5$ каждый:https://jlcpcb.com/quote

Не в сети
 Заголовок сообщения: Re: Хитрые, необычные алгоритмы и код
СообщениеДобавлено: Ср фев 27, 2019 06:06:55 
Потрогал лапой паяльник

Карма: 5
Рейтинг сообщений: 42
Зарегистрирован: Ср янв 04, 2012 11:57:40
Сообщений: 342
Откуда: Алчевск
Рейтинг сообщения: 0
В своей задумке я воспользовался аппаратными возможностями STM32. Расчет КС может быть по ширине 16 или 32 бита. По скорости все равно 1 такт (по datasheet ?). Расчет остатков всяко дольше.


Вернуться наверх
 
PCBWay - всего $5 за 10 печатных плат, первый заказ для новых клиентов БЕСПЛАТЕН

Сборка печатных плат от $30 + БЕСПЛАТНАЯ доставка по всему миру + трафарет

Онлайн просмотровщик Gerber-файлов от PCBWay + Услуги 3D печати
Не в сети
 Заголовок сообщения: Re: Хитрые, необычные алгоритмы и код
СообщениеДобавлено: Ср фев 27, 2019 10:08:29 
Поставщик валерьянки для Кота
Аватар пользователя

Карма: 41
Рейтинг сообщений: 302
Зарегистрирован: Пт сен 07, 2018 20:20:02
Сообщений: 2253
Рейтинг сообщения: 0
Медали: 1
Получил миской по аватаре (1)
Только контрольная сумма очень слабая. 2 сбойных бита в одном столбике и 2 бита в строке дадут иллюзию правильных данных.

Если у Вас прут три ошибки на 64 бита, то Вам уже никакое CRC не поможет, только БЧХ-коды. Потому что CRC не позволяет исправлять ошибки и Вы ни один пакет через такой зашумленный канал доставить не сможете.

Почти вся ECC память ошибку в одном бите 64-х битного слова (8 байт, как и у меня) исправляет, в двух детектирует, в трех может пропустить. Разница только в том, что ECC память, обычно, использует код Хемминга и избыточность всего 8 бит на 64 бита, тогда как у меня избыточность 17 бит на те же 64 бита.

Добавлено after 3 hours 11 minutes 49 seconds:
Только контрольная сумма очень слабая. 2 сбойных бита в одном столбике и 2 бита в строке дадут иллюзию правильных данных.

Что-то у Вас не то с математикой. Нечетное количество ошибок механизм расчета битов четности и по строкам и по столбцам детектирует всегда. Он может пропустить 4 ошибки, причем в очень специфичной ситуации, когда эти ошибки расположены "квадратом" - в одной и той же паре столбцов и строк. На практике, за несколько лет работы с ЕС-овскими магнитными лентами, использующие именно такой принцип кодирования, на блоках данных в 80 байт (такие приходили из СПД), я с пропуском ошибочных данных не столкнулся ни разу!


Вернуться наверх
 
Как сделать ИП с ультрашироким диапазоном?

Ключевыми особенностями высоковольтных SiC MOSFET Wolfspeed являются малое сопротивление канала в открытом состоянии и минимальное значение паразитных емкостей, что позволяет максимально снизить статические и динамические потери, и, соответственно, увеличить рабочую частоту преобразователей.

Читать статью>>
Не в сети
 Заголовок сообщения: Re: Хитрые, необычные алгоритмы и код
СообщениеДобавлено: Ср фев 27, 2019 11:39:20 
Это не хвост, это антенна
Аватар пользователя

Карма: 17
Рейтинг сообщений: 20
Зарегистрирован: Чт апр 04, 2013 22:22:57
Сообщений: 1306
Откуда: Белгород, РФ
Рейтинг сообщения: 0
Он может пропустить 4 ошибки, причем в очень специфичной ситуации, когда эти ошибки расположены "квадратом" - в одной и той же паре столбцов и строк. На практике, за несколько лет работы с ЕС-овскими магнитными лентами, использующие именно такой принцип кодирования, на блоках данных в 80 байт (такие приходили из СПД), я с пропуском ошибочных данных не столкнулся ни разу!


Ну я и написал про 4 ошибки, 2+2 ошибки. Кроме 4 ошибок может пропустить 8 ошибок, 12 и так далее. Вплоть до случая с инвертированием данных всех. Вероятность пропуска ошибки в блоке 8*10 байт выше 1/262144 (потому что 2^18), сыпались бы ошибки массово, они бы проходили. Если бы вы считывали 20 971 520 байт очень шумной информации, ошибка бы вылезла на 50% бы, хотя бы одна. И это без восстановления. Если делаем попытки восстановления, изредка будем восстанавливать одни сбойные блоки в другие сбойные блоки. Например если как вы написали сбойные биты пришли по квадрату, только не все 4, а 3 сбойных бита, мы воостанавливаем еще один и получаем квадрат из сбойных битов сделанный из трех сбойных битов. В итоге без восстановления ошибок пропускаем только 4 сбойных бита по квадрату, а с восстановлением данных пропускаем и 3 сбойных бита, которые алгоритм по ошибке восстановит до 4х сбойных бит.
Можно в принципе проверить. Программку простую написать и имитировать сбойные пакеты. По моим ощущениям будет чуть хуже CRC по статистике (биты не перемешиваются при ошибке), но работать будет нормально всё ))


Вернуться наверх
 
STM32L5 – первое семейство ST на ядре Cortex-M33 с ультранизким потреблением

Первое семейство STM32L5 на базе ядра ARM Cortex-M33, флагман семейств ST с низким потреблением. Область применения IoT, расходомеры, умные часы, промышленные датчики и многое другое. Опубликованы материалы двух практических вебинаров по расчету энергопотребления и работой с TrustZone. Рассмотрены особенности и примеры практической реализации CAN FD на STM32L5.

Подробнее>>
Не в сети
 Заголовок сообщения: Re: Хитрые, необычные алгоритмы и код
СообщениеДобавлено: Ср фев 27, 2019 12:44:30 
Поставщик валерьянки для Кота
Аватар пользователя

Карма: 41
Рейтинг сообщений: 302
Зарегистрирован: Пт сен 07, 2018 20:20:02
Сообщений: 2253
Рейтинг сообщения: 0
Медали: 1
Получил миской по аватаре (1)
Вероятность пропуска ошибки в блоке 8*10 байт выше 1/262144
По моим ощущениям будет чуть хуже CRC

Вероятность пропуска ошибки в таком же блоке для CRC16 существенно выше (по Вашему упрощенному расчету - 1/65536), при том, что исправить ошибку он не позволит в принципе. А CRC32 потребует два дополнительных байта, то бишь сравнение некорректно.
На самом деле, я не понимаю вообще смысла сравнения кодирования с исправлением ошибок и кодирования с расчетом контрольной суммы. В первом случае, при определенной избыточности, Вы всегда данные передадите. Во втором, в общем случае - никогда.


Вернуться наверх
 


Не в сети
 Заголовок сообщения: Re: Хитрые, необычные алгоритмы и код
СообщениеДобавлено: Ср фев 27, 2019 13:27:28 
Это не хвост, это антенна
Аватар пользователя

Карма: 17
Рейтинг сообщений: 20
Зарегистрирован: Чт апр 04, 2013 22:22:57
Сообщений: 1306
Откуда: Белгород, РФ
Рейтинг сообщения: 0
Вероятность пропуска ошибки в таком же блоке для CRC16 существенно выше (по Вашему упрощенному расчету - 1/65536), при том, что исправить ошибку он не позволит в принципе.


Тоже не корректно сравнивать 16 и 18 бит избыточных данных. В CRC каждый дополнительный бит снижает вероятность ошибки в 2 раза, это очень круто. А вот XOR так не работает, там эффективность растет намного слабее. Может даже в 10 раз хуже CRC будет, лень проверять ))
Исправление ошибки достигается высокой ценой, так как снижается надежность обнаружения ошибок и появляется вероятность пропустить 3, 7, 11 бит ошибок расположенных по неполному квадрату в матрице общей.
Но это можно компенсировать большой CRC на большом блоке данных. Вот как вы написали блоки маленькие по 80 байт, их можно объединить в огромный блок по 800 байт и подписать CRC32, надежность будет высочайшая и возможность исправления ошибок. И небольшая избыточность.

Цитата:
На самом деле, я не понимаю вообще смысла сравнения кодирования с исправлением ошибок и кодирования с расчетом контрольной суммы. В первом случае, при определенной избыточности, Вы всегда данные передадите. Во втором, в общем случае - никогда


Вообще-то сравнивать можно, так как главное, обычно, это передать без ошибок. Оба метода это пытаются обеспечить своими силами. CRC лучше выявит наличие ошибок, а кодирование с избыточными данными не потребует повторного запроса (на дисках и лентах это вообще невозможно).


Вернуться наверх
 


Не в сети
 Заголовок сообщения: Re: Хитрые, необычные алгоритмы и код
СообщениеДобавлено: Ср фев 27, 2019 13:58:10 
Поставщик валерьянки для Кота
Аватар пользователя

Карма: 41
Рейтинг сообщений: 302
Зарегистрирован: Пт сен 07, 2018 20:20:02
Сообщений: 2253
Рейтинг сообщения: 0
Медали: 1
Получил миской по аватаре (1)
Вообще-то сравнивать можно, так как главное, обычно, это передать без ошибок.

Категорически не согласен. Главное, для начала, вообще передать. Контрольная сумма позволит Вам что-то передать только по каналу связи, в котором вероятность одиночной ошибки в блоке данных существенно меньше единицы. Тогда как использование кодов корректирующих ошибки позволяет передать данные, когда вероятность одиночной ошибки в одном блоке данных вообще равна единице или пренебрежимо близка к ней.
Что толку в том, что Вы выявите ошибку, если данные без ошибки Вы не сможете получить?

Условно говоря, мой метод позволяет передавать данные вплоть до вероятности ошибки в 1/4 - матрицей 2х2 на каждый бит. Ваш же способ не пригоден при вероятности ошибки в 1/24 (CRC16 на каждый байт).


Вернуться наверх
 
Не в сети
 Заголовок сообщения: Re: Хитрые, необычные алгоритмы и код
СообщениеДобавлено: Ср фев 27, 2019 14:08:38 
Ум, честь и совесть. И скромность.
Аватар пользователя

Карма: 93
Рейтинг сообщений: 1833
Зарегистрирован: Чт дек 28, 2006 08:19:56
Сообщений: 15706
Откуда: Новочеркасск
Рейтинг сообщения: 0
Медали: 2
Получил миской по аватаре (1) Мявтор 3-й степени (1)
друзья, перечитайте еще раз название темы и сравните ваши последние 7-10 сообщений с темой - соответствуют ли они ей?
в применении CRC нет ничего оригинального, необычного или хитрого, особенно если применяются стандартные полиномы и т.п.

_________________
если рассматривать человека снизу, покажется, что мозг у него глубоко в жопе
удивительно, но при взгляде на многих сверху ничего не меняется...


Вернуться наверх
 
Не в сети
 Заголовок сообщения: Re: Хитрые, необычные алгоритмы и код
СообщениеДобавлено: Ср фев 27, 2019 16:45:46 
Это не хвост, это антенна
Аватар пользователя

Карма: 17
Рейтинг сообщений: 20
Зарегистрирован: Чт апр 04, 2013 22:22:57
Сообщений: 1306
Откуда: Белгород, РФ
Рейтинг сообщения: 0
Категорически не согласен. Главное, для начала, вообще передать. Контрольная сумма позволит Вам что-то передать только по каналу связи, в котором вероятность одиночной ошибки в блоке данных существенно меньше единицы. Тогда как использование кодов корректирующих ошибки позволяет передать данные, когда вероятность одиночной ошибки в одном блоке данных вообще равна единице или пренебрежимо близка к ней.


Это в теории. На практике где вероятность есть вероятность ошибки ~1 на блок данных, чуть реже будет проскакивать и 2 ошибки (восстановить невозможно), и 3 ошибки (можно восстановить с ошибкой, если расположены "квадратом" неполным)

Вот нормальное распредедение, ждем 1 ошибку, а будут отклонения во все стороны
Изображение

Цитата:
Что толку в том, что Вы выявите ошибку, если данные без ошибки Вы не сможете получить?


Тут можно сразу 2-3 раза передавать данные. И восстанавливать хитрым алгоритмом. Или применять более сложные алгоритмы, жесткий матан, я там ничего не понял, коды Рида-Соломона
https://habr.com/ru/post/191418/

Но там тоже противоречие, вокруг которого и мы тут ходим. Чем больше избыточных данных, тем надежнее восстановление. Нужен компромисс.

Цитата:
Условно говоря, мой метод позволяет передавать данные вплоть до вероятности ошибки в 1/4 - матрицей 2х2 на каждый бит.


Чуть хуже, 3 бита в этой матрице 2х2, алгоритм "подумает" что это одиночная ошибка, исправит добавив сбойный бит до матрицы 2х2 и отрапортует что справился ))

На глазок, думаю будет примерно так. Передаем 1 млн. сбойных пакетов где 1,2,3..10 бит с ошибкой. И смотрим результат.
CRC16 пропускает 15 ошибок и 0 восстанавливает.
Ваш метод, при 18 выделенных битах пропустит как-бы не 500 ошибок. Но при этом часть восстановит, может 20% или 200 000 пакетов, из которых 500 будут с ошибками. Я даже не знаю хорошо это или плохо, наверное есть задачи где именно это и нужно.

Добавлено after 9 minutes 20 seconds:
в применении CRC нет ничего оригинального, необычного или хитрого, особенно если применяются стандартные полиномы и т.п.


CRC тоже можно считать по табличке, черех XOR побитно и аппаратно через сдвиги по кругу. И тут не про CRC, а другие оригинальные методы, которые сравниваются с CRC. А если речь пойдет о коде Рида-Соломона, то это будет взрыв мозга и на ночь такое лучше вообще не читать, куда еще хитрее то ))


Вернуться наверх
 
Не в сети
 Заголовок сообщения: Re: Хитрые, необычные алгоритмы и код
СообщениеДобавлено: Ср фев 27, 2019 16:57:21 
Ум, честь и совесть. И скромность.
Аватар пользователя

Карма: 93
Рейтинг сообщений: 1833
Зарегистрирован: Чт дек 28, 2006 08:19:56
Сообщений: 15706
Откуда: Новочеркасск
Рейтинг сообщения: 0
Медали: 2
Получил миской по аватаре (1) Мявтор 3-й степени (1)
вы как-то упускаете, что тем, кто знает, вы ничего нового не принесете, а тем кто не знает, ваша заумь непонятна.
я думаю, для многих будет открытием алгоритм обмена значений двух переменных без использования третьей... а вы про Рида с Соломоном...

_________________
если рассматривать человека снизу, покажется, что мозг у него глубоко в жопе
удивительно, но при взгляде на многих сверху ничего не меняется...


Вернуться наверх
 
Не в сети
 Заголовок сообщения: Re: Хитрые, необычные алгоритмы и код
СообщениеДобавлено: Ср фев 27, 2019 18:29:35 
Это не хвост, это антенна
Аватар пользователя

Карма: 17
Рейтинг сообщений: 20
Зарегистрирован: Чт апр 04, 2013 22:22:57
Сообщений: 1306
Откуда: Белгород, РФ
Рейтинг сообщения: 0
вы как-то упускаете, что тем, кто знает, вы ничего нового не принесете, а тем кто не знает, ваша заумь непонятна.
я думаю, для многих будет открытием алгоритм обмена значений двух переменных без использования третьей... а вы про Рида с Соломоном...


Заморачиваться на экономии байта это не заумь (это вообще-то задача компилятора), а CRC-подобные алгоритмы, которые обсуждает 3 человека, для вас не нужно. Вам надо чтобы только ваши интересы все разделяли? или просто потроллить? ))


Вернуться наверх
 
Не в сети
 Заголовок сообщения: Re: Хитрые, необычные алгоритмы и код
СообщениеДобавлено: Ср фев 27, 2019 18:34:40 
Поставщик валерьянки для Кота
Аватар пользователя

Карма: 41
Рейтинг сообщений: 302
Зарегистрирован: Пт сен 07, 2018 20:20:02
Сообщений: 2253
Рейтинг сообщения: 0
Медали: 1
Получил миской по аватаре (1)
Это в теории. На практике где вероятность есть

И на практике, и в теории, в тех случаях, когда вероятность ошибки не нулевая, рано или поздно, какие бы способы контроля Вы не использовали, произойдет ошибка, которую Вы не обнаружите. И Вам это не изменить.

С точки зрения передачи по USART, когда бит четности формируется автоматически, послать после блока данных контрольный байт, полученный обыкновенным XOR из всех ранее переданных байтов, сможет даже начинающий. И при этом, уже по желанию, может или исправлять одиночные ошибки, или детектировать до трех ошибок в блоке.
Альтернативный предложенный Вами вариант простого суммирования позволит детектировать только одиночные ошибки, не позволит детектировать двойные и, тем более, не позволит ничего исправить. Хотя по сложности реализации ничем не отличается от перекрестного контроля на четность.
Использование же CRC, с расчетом контрольной суммы по полиному, на многих МК (без аппаратной поддержки CRC) вообще не факт, что совместимо с высокими скоростями передачи, да и на порядок сложней в реализации, чем предыдущие два способа. Но требует избыточных 2-4 байта на блок данных, который у многих здесь редко превышает нескольких байт.
Про БЧХ-коды вести тут речь вообще не факт, что имеет смысл, как заметил ARV.

В итоге, первый алгорит прост, в два раза более устойчив, чем второй, не менее устойчив, чем третий, хоть и проще его на порядок, позволяет корректировать ошибки и легко масштабируется для слов с любым количеством бит (для USART от 5 до 9). Чем он Вам не угодил? Излишней избыточностью? Так это вполне адекватная цена за простоту реализации.


Вернуться наверх
 
Не в сети
 Заголовок сообщения: Re: Хитрые, необычные алгоритмы и код
СообщениеДобавлено: Ср фев 27, 2019 19:48:27 
Это не хвост, это антенна
Аватар пользователя

Карма: 17
Рейтинг сообщений: 20
Зарегистрирован: Чт апр 04, 2013 22:22:57
Сообщений: 1306
Откуда: Белгород, РФ
Рейтинг сообщения: 0
И на практике, и в теории, в тех случаях, когда вероятность ошибки не нулевая, рано или поздно, какие бы способы контроля Вы не использовали, произойдет ошибка, которую Вы не обнаружите. И Вам это не изменить.


CRC64 даст полную надежность, ошибка не успеет возникнуть за время существования вселенной. Маленькие блоки данных подписывать нецелесообразно, а большие, более 200 байт уже не так затратно. С увеличением разрядности CRC она становится круче экспоненциально, в отличие от других вариантов.

Цитата:
В итоге, первый алгорит прост, в два раза более устойчив, чем второй, не менее устойчив, чем третий, хоть и проще его на порядок, позволяет корректировать ошибки и легко масштабируется для слов с любым количеством бит (для USART от 5 до 9). Чем он Вам не угодил? Излишней избыточностью? Так это вполне адекватная цена за простоту реализации


Алгоритм прост, но не устойчив. Я только не могу этого доказать, там небольшую программку надо накидать для тестов.
Почему это он мне не угодил? Интересный алгоритм, можно бесконечно улучшать его, комбинировать с CRC-подобными, что позволит все плюсы объединить. Надо подумать над этим ))


Вернуться наверх
 
Не в сети
 Заголовок сообщения: Re: Хитрые, необычные алгоритмы и код
СообщениеДобавлено: Ср фев 27, 2019 22:11:40 
Поставщик валерьянки для Кота
Аватар пользователя

Карма: 41
Рейтинг сообщений: 302
Зарегистрирован: Пт сен 07, 2018 20:20:02
Сообщений: 2253
Рейтинг сообщения: 0
Медали: 1
Получил миской по аватаре (1)
CRC64 даст полную надежность, ошибка не успеет возникнуть за время существования вселенной.

Вы серьезно или прикалыаетесь? Если CRC32 еще используется из-за простоты его вычисления, но в тех сферах, где действительно требуется надежность, даже от MD5 уже отказываются в пользу SHA-2. Я уж молчу о банковской сфере, где хеши меньше 1024 бита в принципе даже рассматриваются. И при этом вероятность дублирования хеша все равно существует и вполне ожидаема.

Для примера, всего в конце прошлого года была мной найдена интересная бага. Программист, вместо того, чтобы проверять на уникальность набор из десятка полей по одному, тупо считал SHA-256 хеш по всем ним и сравнивал только его. Это проработало чуть больше года, пока неожиданно не выявилось, что в БД размером в несколько десятков терабайт уже дважды(!) уникальность проверялась некорректно: в БД не попали два сообщения, воспринятые, как уже существующие. Какое там время существования вселенной? )))

Про SHA-1 (160 бит) вообще молчу, так как многие сами сталкивались с тем, что файл скачанный по bittorrent оказывался битым, хотя SHA-1 хеш его совпадал с оригиналом.


Вернуться наверх
 
Не в сети
 Заголовок сообщения: Re: Хитрые, необычные алгоритмы и код
СообщениеДобавлено: Чт фев 28, 2019 00:20:37 
Это не хвост, это антенна
Аватар пользователя

Карма: 17
Рейтинг сообщений: 20
Зарегистрирован: Чт апр 04, 2013 22:22:57
Сообщений: 1306
Откуда: Белгород, РФ
Рейтинг сообщения: 0
Цитата:
Вы серьезно или прикалыаетесь? Если CRC32 еще используется из-за простоты его вычисления, но в тех сферах, где действительно требуется надежность, даже от MD5 уже отказываются в пользу SHA-2. Я уж молчу о банковской сфере, где хеши меньше 1024 бита в принципе даже рассматриваются. И при этом вероятность дублирования хеша все равно существует и вполне ожидаема.


Вы путаете криптографию и контрольную сумму. 1024 бита это вообще тема с открытым ключом.

Цитата:
Для примера, всего в конце прошлого года была мной найдена интересная бага. Программист, вместо того, чтобы проверять на уникальность набор из десятка полей по одному, тупо считал SHA-256 хеш по всем ним и сравнивал только его. Это проработало чуть больше года, пока неожиданно не выявилось, что в БД размером в несколько десятков терабайт уже дважды(!) уникальность проверялась некорректно: в БД не попали два сообщения, воспринятые, как уже существующие. Какое там время существования вселенной? )))


Ошибка в алгоритме где-то. Хватило бы и 128 бит. Возможно он из базы данных брал первые 8 байт и по ним считал SHA, или что-то в этом роде.

Цитата:
Про SHA-1 (160 бит) вообще молчу, так как многие сами сталкивались с тем, что файл скачанный по bittorrent оказывался битым, хотя SHA-1 хеш его совпадал с оригиналом


Я не сталкивался. А умышленно такое можно сделать искуственно испортив файл, например, чтобы вирус внедрить и подпись осталась корректной. Очень сложно, через уязвимости алгоритма и радужные таблицы, заранее просчитанных чего-то там.

Обратный пример, примитивный RC-72 до сих пор не взломан, энтузиасты сделали распределенную сеть, миллионы компов лет 10 считают, я тоже считал, и ничего. Сначала на процессорах считали, потом на видеокартах, 100 мегахешей в секунду с компа, и всей планетой код не взломали. Приз 10 000$, но принято получившему отдавать на благотворительность, не в деньгах цель.
Вот проект, проверил, до сих пор считают:
http://www.distributed.net/RC5

Я тоже тестировал контрольные суммы, собирал статистику для статьи на Хабре. 8-16 бит нормально, 32 бита уже на часы надо было комп оставлять, чтобы найти коллизии в пакетах. 64 бита ни одной коллизии за неделю работы, что и не удивительно, я и не ждал. Пришлось контрольную сумму обрезать до младших 32 бит и их уже тестировать, там всё совпало с теорией.

Если вы о криптографии, то CRC нельзя использовать как криптографическую подпись или криптоалгоритм, там математика простая, хорошо изучена и хаккеры мигом подберут обратные алгоритмы, у них много приемов для этого.


Вернуться наверх
 
Не в сети
 Заголовок сообщения: Re: Хитрые, необычные алгоритмы и код
СообщениеДобавлено: Чт фев 28, 2019 07:37:25 
Поставщик валерьянки для Кота
Аватар пользователя

Карма: 41
Рейтинг сообщений: 302
Зарегистрирован: Пт сен 07, 2018 20:20:02
Сообщений: 2253
Рейтинг сообщения: 0
Медали: 1
Получил миской по аватаре (1)
Вы путаете криптографию и контрольную сумму.

А чем по Вашему отличается контрольная сумма от значения криптографической функции? Только тем, что к последней предъявляются более жесткие требования.

Цитата:
1024 бита это вообще тема с открытым ключом.

В чем разница? Транзакция подписывается для того, чтобы невозможно было изменить ее содержимое так, чтобы хеш остался прежним. Мы же о хеш функциях говорим, а не о шифровании. И CRC - частный вид хеш функции.

Цитата:
Ошибка в алгоритме где-то. Хватило бы и 128 бит. Возможно он из базы данных брал первые 8 байт и по ним считал SHA, или что-то в этом роде.

Если бы было "что-то в этом роде" то такую багу выявили бы еще при тестировании или промэксплуатации, а не через год работы.

Цитата:
пример, примитивный RC-72 до сих пор не взломан

При чем тут взлом? Приз был объявлен за расшифровку зашифрованных RC5 сообщений.
Мы же говорим о случайном совпадении значения хеша у двух блоков.


Вернуться наверх
 
Не в сети
 Заголовок сообщения: Re: Хитрые, необычные алгоритмы и код
СообщениеДобавлено: Чт фев 28, 2019 15:19:29 
Это не хвост, это антенна
Аватар пользователя

Карма: 17
Рейтинг сообщений: 20
Зарегистрирован: Чт апр 04, 2013 22:22:57
Сообщений: 1306
Откуда: Белгород, РФ
Рейтинг сообщения: 0
А чем по Вашему отличается контрольная сумма от значения криптографической функции? Только тем, что к последней предъявляются более жесткие требования.


Не жесткие, а специфические, для защиты от известных на сегодняшний день атак. Для применения по назначению CRC походит идеально, улучшать нечего.
Та же CRC прекрасно подошла бы как подпись для документов, хеш, но простая математика позволит очень быстро подобрать блок данных с таким же хешем (хотя я бы не смог без посторонней помощи, а перебором бы ждал миллиард лет).

Цитата:
О популярных хэш-алгоритмах
Алгоритмы CRC16/32 — контрольная сумма (не криптографическое преобразование).

Алгоритмы MD2/4/5/6. Являются творением Рона Райвеста, одного из авторов алгоритма RSA.

Алгоритм MD5 имел некогда большую популярность, но первые предпосылки взлома появились еще в конце девяностых, и сейчас его популярность стремительно падает.

Алгоритм MD6 — очень интересный с конструктивной точки зрения алгоритм. Он выдвигался на конкурс SHA-3, но, к сожалению, авторы не успели довести его до кондиции, и в списке кандидатов, прошедших во второй раунд этот алгоритм отсутствует.

Алгоритмы линейки SHA Широко распространенные сейчас алгоритмы. Идет активный переход от SHA-1 к стандартам версии SHA-2. SHA-2 — собирательное название алгоритмов SHA224, SHA256, SHA384 и SHA512. SHA224 и SHA384 являются по сути аналогами SHA256 и SHA512 соответственно, только после расчета свертки часть информации в ней отбрасывается. Использовать их стоит лишь для обеспечения совместимости с оборудованием старых моделей.

Российский стандарт — ГОСТ 34.11-94.


Вот по алгоритмам шифрования или хеширования, даже проще CRC, просто повторят многократно для усложнения.

https://ru.wikipedia.org/wiki/%D0%A1%D0 ... 0%BB%D1%8F


Вернуться наверх
 
Не в сети
 Заголовок сообщения: Re: Хитрые, необычные алгоритмы и код
СообщениеДобавлено: Чт фев 28, 2019 16:08:21 
Поставщик валерьянки для Кота
Аватар пользователя

Карма: 41
Рейтинг сообщений: 302
Зарегистрирован: Пт сен 07, 2018 20:20:02
Сообщений: 2253
Рейтинг сообщения: 0
Медали: 1
Получил миской по аватаре (1)
Для применения по назначению CRC походит идеально, улучшать нечего.


CRC-32 еще используется только благодаря тому, что вычисляется быстрее, чем более надежные криптографические хеш-функции. Ну и еще потому, что зафиксирована в стандартах 802.3 и IPv4. В IPv6 от расчета контрольной суммы вообще отказались. При этом UDP и TCP вполне так обходятся тупой 16-ти битной контрольной суммой.
Если нужна хеш функция, то есть более надежные криптографические. Если нужна надежность передачи - есть БЧХ-коды. Забудьте о CRC. Дни его уже сочтены )

Цитата:
Существующие стандарты CRC-128 (IEEE) и CRC-256 (IEEE) в настоящее время вытеснены криптографическими хеш-функциями.

https://ru.wikipedia.org/wiki/%D0%A6%D0 ... 0%BE%D0%B4


Вернуться наверх
 
Не в сети
 Заголовок сообщения: Re: Хитрые, необычные алгоритмы и код
СообщениеДобавлено: Сб мар 02, 2019 01:21:10 
Это не хвост, это антенна
Аватар пользователя

Карма: 17
Рейтинг сообщений: 20
Зарегистрирован: Чт апр 04, 2013 22:22:57
Сообщений: 1306
Откуда: Белгород, РФ
Рейтинг сообщения: 0
CRC32 остается навсегда похоже, даже еще больше будет использоваться
https://habr.com/ru/post/64592/
Основы IPv6
Цитата:
... Отсутствует Checksum заголовка, соответственно, его не надо проверять, а также пересчитывать для каждого пакета при изменении TTL Hop Limit. Так как checksum больше нет, то вся ответственность за целостность информации должна лежать на протоколе более низкого уровня, так например у Ethernet фреймов есть свой честный CRC32. Так же у UDP пакетов наличие checksum теперь обязательно и UDP/IPv6 пакеты с Checksum 0000 будут просто отбрасываться принимающим хостом;


По CRC128 и даже 256 что нашел, отговаривают использовать тоже

Does anyone have CRC128 and CRC256 Code in C++ and C#?
https://stackoverflow.com/questions/355 ... in-c-and-c

тут жалуются на высокую вероятность коллизий
Цитата:
I agree with you except that the accidental collision rate is higher than 1 in 2^32 or 1 in 2^64 for 32 bit and 64 bit CRCs respectively.

I wrote an app that kept track of things by their CRC values for tracking items. We needed to track potentially millions of items and we started with a CRC32 which in real world practice has a collision rate of around 1 in 2^16 which was an unpleasant surprise. We then re-coded to use a CRC64 which had a real world collision rate of about 1 in 2^23. We tested this after the unpleasant surprise of the 32 bit one we started with and accepted the small error rate of the 64 bit one.


Типа даже CRC64 дает всего 1 на 2^23, а не 1 на 2^64. Может напутали что-то конечно. Мне не верится, если бы CRC была так плоха, её бы не применяли.
Для расчета целостности данных (а не криптоподписи!) она нормально подходит. Как хеш функция для всяких баз данных под вопросом, для индексации и всего такого, у меня нет статистики. Наверное есть и получше алгоритмы.


Вернуться наверх
 
Показать сообщения за:  Сортировать по:  Вернуться наверх
Начать новую тему Ответить на тему  [ Сообщений: 186 ]     ... , , , 8, ,  

Часовой пояс: UTC + 3 часа


Кто сейчас на форуме

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 4


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

Найти:
Перейти:  


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
Русская поддержка phpBB
Extended by Karma MOD © 2007—2012 m157y
Extended by Topic Tags MOD © 2012 m157y