SM 14 March 17, 2015 Posted March 17, 2015 · Report post А на заборе еще что-то написано. Мы сейчас обсуждаем конкретно, деление полиномов, и проверку их умножением, математику. И тема про математику. Которую для 4 битного полинома на раз-два на бумаге ручкой сделать. Quote Share this post Link to post Share on other sites More sharing options...
ViKo 0 March 17, 2015 Posted March 17, 2015 · Report post А на заборе еще что-то написано. Мы сейчас обсуждаем конкретно, деление полиномов, и проверку их умножением, математику. И тема про математику. Которую для 4 битного полинома на раз-два на бумаге ручкой сделать. Я дал ссылку на статью, именно на бумаге и посчитал, дал ссылку на онлайн калькулятор, и там результаты расчетов совпадают. Может, просчет где-то на вашем заборе? Quote Share this post Link to post Share on other sites More sharing options...
SM 14 March 17, 2015 Posted March 17, 2015 · Report post Может, просчет где-то на вашем заборе? Нет. Мои расчеты я расписал до последней скобки по всем этапам, и они проверяются умножением на 100%. Любой может посмотреть и проверить. Ваш результат не выдерживает проверку умножением, и это я тоже показал открыто и полностью. Quote Share this post Link to post Share on other sites More sharing options...
ViKo 0 March 17, 2015 Posted March 17, 2015 · Report post Нет. Мои расчеты я расписал до последней скобки по всем этапам, и они проверяются умножением на 100%. Любой может посмотреть и проверить. Ваш результат не выдерживает проверку умножением, и это я тоже показал открыто и полностью. Ваша ошибка работает в обе стороны - при делении и при умножении. Мне нет смысла не доверять калькулятору, который выдает те же результаты, что я посчитал на бумаге. Лень набирать (цифры все равно сползут вбок) и лень фотографировать - выкладывать. upd. Проверил весь список из сообщения №37 - все совпадает! Расчеты показывают, что есть однозначное соответствие CRC исходным данным, если размер данных не превышает размер CRC. Quote Share this post Link to post Share on other sites More sharing options...
SM 14 March 17, 2015 Posted March 17, 2015 · Report post что я посчитал на бумаге Их никто не видел. Я, в отличие от некоторых, ни один этап расчета не скрываю. И ошибок в них нет, иначе бы давно уже кто-то ткнул носом в ошибку, да и сам бы давно нашел. Quote Share this post Link to post Share on other sites More sharing options...
ViKo 0 March 17, 2015 Posted March 17, 2015 · Report post Подождем... Я же показал частное и остаток. Программа на сайте дает только остаток. Расчеты дома, специально пересчитывать не буду. Все точно по статье. Quote Share this post Link to post Share on other sites More sharing options...
SM 14 March 17, 2015 Posted March 17, 2015 · Report post Я же показал частное и остаток. Вот именно. А я показал, что при этом частном есть член x^9, что сразу говорит, что частное не верно. То есть, верно, но если делимое 0x300, а не 0x30. И он там однозначно есть, x^5*x^4, и ничем не сокращается. Quote Share this post Link to post Share on other sites More sharing options...
MrYuran 34 March 17, 2015 Posted March 17, 2015 · Report post Не совсем понял, о чем идет речь, но для CRC (и вообще любого циклического кода) кодер и декодер - одно и то же. То есть, если прогнать закодированный блок через исходный кодер, то получим исходное слово и ноль в остатке. Но "шифровать" так прошивку имхо неправильно. Quote Share this post Link to post Share on other sites More sharing options...
Timmy 1 March 17, 2015 Posted March 17, 2015 · Report post То есть, каждое исходное слово заменяется 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... Так что смысл сего действа неясен, разве что простейшая обфускация кода. Quote Share this post Link to post Share on other sites More sharing options...
ViKo 0 March 17, 2015 Posted March 17, 2015 · Report post Не совсем понял, о чем идет речь, но для CRC (и вообще любого циклического кода) кодер и декодер - одно и то же. То есть, если прогнать закодированный блок через исходный кодер, то получим исходное слово и ноль в остатке. Но "шифровать" так прошивку имхо неправильно. Верно, но не совсем. Для той же CRC-4 x^4 + x + 1, подал (и рассчитал на бумаге) число 0x30, получил частное 0x35 и остаток (CRC) 0xF. Рассчитал для 0x35F, получил свое 0x30 (здорово!), но остаток не 0, а 0x2. Это если бы я свое исходное 0x30 с CRC 0xF = 0x30F рассчитал, то получил бы 0. Одно плохо - CRC-32 в STM32 не выдает частного, а только остаток. Так что аппаратно декодировать не получится. SM, вы дали ссылку на статью, которая и показывает, в чем была ваша ошибка. Видите, какие там манипуляции при умножении, с участием порождающего полинома. Quote Share this post Link to post Share on other sites More sharing options...
SM 14 March 17, 2015 Posted March 17, 2015 · Report post SM, вы дали ссылку на статью, которая и показывает, в чем была ваша ошибка. Видите, какие там манипуляции при умножении, с участием порождающего полинома. Вы прежде чем утверждать, хоть бы вникли. Там речь о порождающих полиномов для полей GF(2^m), у нас тут простое поле GF(2), m=1, так что все манипуляции отменяются. Остается прямое простое перемножение. Эти манипуляции нужны для кодов Рида-Соломона и подобных (недвоичных), но не для кодов с однобитными символами, двоичных, как CRC. Хотя я об этом уже писал... Ну откройте учебник по математике наконец то! Совсем лень что ли? Quote Share this post Link to post Share on other sites More sharing options...
ViKo 0 March 17, 2015 Posted March 17, 2015 · Report post SM, я вижу, упорствование - ваш конек. Разберитесь уже сами в своих косяках. Мне-то в чем разбираться? У меня все работает в соответствии с теорией. Две программы подтверждают мои расчеты. Quote Share this post Link to post Share on other sites More sharing options...
SM 14 March 17, 2015 Posted March 17, 2015 · Report post SM, я вижу, упорствование - ваш конек. Разберитесь уже сами в своих косяках. У меня нет косяков :) Я даже знакомому математику свой пример деления и проверки умножением показал. ОШИБОК НЕТ! Проверка умножением сделана корректно. А у Вас в примере присутствует домножение на x^4 - то есть, вы посчитали (D(x)*x^4) mod G(x), вместо D(x) mod G(x), которые считаю я. Мне-то в чем разбираться? У меня все работает в соответствии с теорией. Так и у меня все работает в соответствии с теорией. Остатки от делений на 0x13 получаются в диапазоне 0x00...0x12, как формально и должно быть для остатка. И, в отличие от Ваших решений, они проверяются умножением корректно. Вы же в доказательство своей правоты тут ни разу не привели проверку. Одни голые слова. Это не математическое доказательство - "работает, потому что программа подтверждает". Проверку в студию. Quote Share this post Link to post Share on other sites More sharing options...
ViKo 0 March 17, 2015 Posted March 17, 2015 · Report post Ладно, делим. Получим для 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 Quote Share this post Link to post Share on other sites More sharing options...
SM 14 March 17, 2015 Posted March 17, 2015 · Report post Так ясно, откуда у Вас ошибка. Приписывание четырех нулей - это добножение на 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). Проверка подтвердила правильность деления. Quote Share this post Link to post Share on other sites More sharing options...
