[SM 0]

А на заборе еще что-то написано.

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

[ViKo 1]

А на заборе еще что-то написано.

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

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

[SM 0]

Может, просчет где-то на вашем заборе?

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

[ViKo 1]

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

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

upd. Проверил весь список из сообщения №37 - все совпадает!

 

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

[SM 0]

что я посчитал на бумаге

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

[ViKo 1]

Подождем...

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

[SM 0]

Я же показал частное и остаток.

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

[MrYuran 18]

Не совсем понял, о чем идет речь, но для CRC (и вообще любого циклического кода) кодер и декодер - одно и то же.

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

Но "шифровать" так прошивку имхо неправильно.

 

[Timmy 1]

То есть, каждое исходное слово заменяется CRC, вычисленной с его участием, следующее слово заменяется следующей CRC.

Вопрос, как закодировать, чтобы после декодирования получить исходный код? Каким полиномом? Думаю, перекрутить 32 в 1, и т. п.

Пока читаю пару статей о CRC, может, кто-то уже знает точный ответ?

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

crc = secret;
for(i=0; i<ldata; i++){
  crc = next_crc(crc, encrypted_data[i]);
  decrypted_data[i] = crc;
}

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

[ViKo 1]

Не совсем понял, о чем идет речь, но для CRC (и вообще любого циклического кода) кодер и декодер - одно и то же.

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

Но "шифровать" так прошивку имхо неправильно.

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

 

 

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

 

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

[SM 0]

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

 

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

[ViKo 1]

SM, я вижу, упорствование - ваш конек. Разберитесь уже сами в своих косяках.

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

[SM 0]

SM, я вижу, упорствование - ваш конек. Разберитесь уже сами в своих косяках.

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

 

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

 

Мне-то в чем разбираться? У меня все работает в соответствии с теорией.

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

[ViKo 1]

Ладно, делим. Получим для CRC-4 из 0x30 частное и остаток.

Сверху - частное. Ниже делимое 0x30, дополненное четырьмя нулями (для нахождения остатка). Под ним - делитель 0x13, сдвигаемый каждый раз на разряд. Если в разряде делимого 1, производим вычитание (полиномиальное), и в частное пишем 1, если 0, продвигаемся дальше, пишем в частное 0. Внизу получили остаток от деления, CRC.

upd. как и говорил, все цифры сдвинулись. Сейчас в код кину, там моноширинный шрифт? Эй, модераторы, когда ж?

Могу провести и проверку. Тем же делением из 0x35F получу 0x30 и остаток 0x2, из 0x30F получу остаток 0.

 

110101

110000.0000
10011
-------
10110
10011
------
  01010
   10100
   10011
   ------
    01110
     11100
     10011
     -----
      1111

[SM 0]

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

 

110000 -> текущий остаток больше делителя, продолжаем.
10011_
---------- -> в частное идет бит 1
010110  -> текущий остаток больше делителя, продолжаем.
_10011
---------- -> в частное идет бит 1
000101 -> текущий остаток меньше делителя, деление закончено.

 

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