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

Вот именно. А я показал, что при этом частном есть член 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). Проверка подтвердила правильность деления.

Приписывание нулей - чтобы было из чего остаток набрать. Статья вам в помощь. В конце концов, возьмите свой любимый аппаратный вычислитель CRC, и сравните его результаты с вашими.
еще раз дам, а то и сам чуть нашел: http://electronix.ru/redirect.php?http://w...y/algo/crc1.pdf

Вы предупреждайте, что домножаете полином данных на X^4 перед тем, как его делить. С учетом этого - у Вас ошибки нет. И проверка работает, показывая, что было домножение на x^4 - я же ее Вам и сделал, получив 0x300 вместо ожидаемых 0x30. Но скрывать это не следует. Я честно делил полином данных на порождающий полином, без дополнительных операций по припискам нулей. Сразу можно говорить, что Вы выполняете дополнительную операцию - домножение на x^4 перед делением???? Это сверхсекретная информация, чтобы врага (меня) с толку сбить?

"Чтобы остаток набрать" - нули они приписали не для этого. Честно говоря, понятия не имею, зачем. Остаток вычисляется от ЛЮБОГО деления, с приписыванием, и без приписывания тоже. Возможно, домножение на x^4 сделано как раз для получения той самой однозначности, которой без этого домножения, при нахождении остатка в чистом его виде, и взятии 4-х бит от него, нет.

Причем тут вычислители CRC, когда спор чисто в математической области, про тупое деление двух полиномов - 0x30 (x^5+x^4) на 0x13 (x^4+x+1)

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

Вот как раз и я, и Вы делили согласно правилам полиномиального деления. Но я вычислял D(x) mod G(x), о чем честно и говорил. А Вы - (D(x)*x^4) mod G(x).
И поэтому у меня проверка показывала, что я делю правильно, получая в итоге проверки 0x30, а у Вас проверка показывала глюк - 0x300 - и, как оказалось, лишь потому, что Вы скрыли домножение на x^4.

Над блочными кодами не стоит долго размышлять. Берите XTEA - проще нету при приемлемой криптостойкости.

Конечно не было возможности всё прочитать, может уже предлагали, но если хочется задействовать встроенный ЦРЦ для шифрования, то делать нужно не так.
Его нужно просто использовать как генератор ПСП, и тупо ксорить данные с этим ПСП.
А вообще, если уж на то пошло, так в STM и AES тоже встроенный..

Да, спасибо, годный метод. Особенно, если еще перемешать биты этой ПСП, чтобы взломщик не догадался. А то криптостойкость будет на уровне постоянного слова для xor.

Для чего дополняем нулями данные при делении на полином для вычисления CRC. Мы получаем остаток от деления, который потом запишем на место этих нулей. И при проверке - делении данных вместе с CRC (опять дополняем нулями, чтобы каждый битик поучаствовал в делении) получим остаток 0.

С каких щей? "Ключом" к этому "шифру" может быть первое 32-бит слово, скормленное ЦРЦатору, а также то, что вы будете делать на следующей итерации: то ли просто подавать на ЦРЦатор результат первой итерации, то ли его предварительно ксорить с ещё каким-то "ключом".
А если вы будете "перемешивать биты", то вся эта идея коту под хвост, потому что перемешивание битов ресурсоёмко.

Зная, что используется встроенный блок CRC, только это первое слово и будет ключом. Вероятность подбора 2^32.

Что делать дальше - вопрос второй. Можно и без CRC запутать шпиона. Например, ксорить со следующим словом.
А перемешивать биты можно по-разному. Даже одной командой.
Можно CRC запустить X раз, прежде, чем использовать. Еще один "секрет".

Ну тогда 2-3-4 первых слова :-)))))))