А на заборе еще что-то написано.
Мы сейчас обсуждаем конкретно, деление полиномов, и проверку их умножением, математику. И тема про математику. Которую для 4 битного полинома на раз-два на бумаге ручкой сделать.

Я дал ссылку на статью, именно на бумаге и посчитал, дал ссылку на онлайн калькулятор, и там результаты расчетов совпадают. Может, просчет где-то на вашем заборе?

Нет. Мои расчеты я расписал до последней скобки по всем этапам, и они проверяются умножением на 100%. Любой может посмотреть и проверить. Ваш результат не выдерживает проверку умножением, и это я тоже показал открыто и полностью.

Ваша ошибка работает в обе стороны - при делении и при умножении. Мне нет смысла не доверять калькулятору, который выдает те же результаты, что я посчитал на бумаге. Лень набирать (цифры все равно сползут вбок) и лень фотографировать - выкладывать.
upd. Проверил весь список из сообщения №37 - все совпадает!

Расчеты показывают, что есть однозначное соответствие CRC исходным данным, если размер данных не превышает размер CRC.

Их никто не видел. Я, в отличие от некоторых, ни один этап расчета не скрываю. И ошибок в них нет, иначе бы давно уже кто-то ткнул носом в ошибку, да и сам бы давно нашел.

Подождем...
Я же показал частное и остаток. Программа на сайте дает только остаток. Расчеты дома, специально пересчитывать не буду. Все точно по статье.

Вот именно. А я показал, что при этом частном есть член x^9, что сразу говорит, что частное не верно. То есть, верно, но если делимое 0x300, а не 0x30. И он там однозначно есть, x^5*x^4, и ничем не сокращается.

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

Давайте для начала чётко опишем задачу, а то опять получится спор ни о чём. Пусть есть функция, вычисляющая следующую CRC32 от 32-битных данных: uint32_t next_crc(uint32_t crc, uint32_t data); Алгоритм следующий:

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

Верно, но не совсем. Для той же CRC-4 x^4 + x + 1, подал (и рассчитал на бумаге) число 0x30, получил частное 0x35 и остаток (CRC) 0xF. Рассчитал для 0x35F, получил свое 0x30 (здорово!), но остаток не 0, а 0x2. Это если бы я свое исходное 0x30 с CRC 0xF = 0x30F рассчитал, то получил бы 0.


Одно плохо - CRC-32 в STM32 не выдает частного, а только остаток. Так что аппаратно декодировать не получится.

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

Вы прежде чем утверждать, хоть бы вникли. Там речь о порождающих полиномов для полей GF(2^m), у нас тут простое поле GF(2), m=1, так что все манипуляции отменяются. Остается прямое простое перемножение. Эти манипуляции нужны для кодов Рида-Соломона и подобных (недвоичных), но не для кодов с однобитными символами, двоичных, как CRC. Хотя я об этом уже писал... Ну откройте учебник по математике наконец то! Совсем лень что ли?

SM, я вижу, упорствование - ваш конек. Разберитесь уже сами в своих косяках.
Мне-то в чем разбираться? У меня все работает в соответствии с теорией. Две программы подтверждают мои расчеты.

У меня нет косяков Я даже знакомому математику свой пример деления и проверки умножением показал. ОШИБОК НЕТ! Проверка умножением сделана корректно.

А у Вас в примере присутствует домножение на x^4 - то есть, вы посчитали (D(x)*x^4) mod G(x), вместо D(x) mod G(x), которые считаю я.


Так и у меня все работает в соответствии с теорией. Остатки от делений на 0x13 получаются в диапазоне 0x00...0x12, как формально и должно быть для остатка. И, в отличие от Ваших решений, они проверяются умножением корректно. Вы же в доказательство своей правоты тут ни разу не привели проверку. Одни голые слова. Это не математическое доказательство - "работает, потому что программа подтверждает". Проверку в студию.

Ладно, делим. Получим для CRC-4 из 0x30 частное и остаток.
Сверху - частное. Ниже делимое 0x30, дополненное четырьмя нулями (для нахождения остатка). Под ним - делитель 0x13, сдвигаемый каждый раз на разряд. Если в разряде делимого 1, производим вычитание (полиномиальное), и в частное пишем 1, если 0, продвигаемся дальше, пишем в частное 0. Внизу получили остаток от деления, CRC.
upd. как и говорил, все цифры сдвинулись. Сейчас в код кину, там моноширинный шрифт? Эй, модераторы, когда ж?
Могу провести и проверку. Тем же делением из 0x35F получу 0x30 и остаток 0x2, из 0x30F получу остаток 0.

Так ясно, откуда у Вас ошибка. Приписывание четырех нулей - это добножение на x^4 - следовательно, Вы и делите не 0x30, а 0x300. Правильно деление полиномов делается так:



итого, частное 0011 (3), остаток 5.

Проверяем:
частное, 3, это (x+1)
остаток, 5, это (x^2+1)
(x+1)*(x^4+x+1)+(x^2+1) = x^5 + x^2 + x + x^4 + x + 1 + x^2 + 1 = x^5 + x^4 (исходное 0x30). Проверка подтвердила правильность деления.