Форум разработчиков электроники ELECTRONIX.ru > Полином для вычисления обратной CRC

Помощь - Поиск - Пользователи - Календарь

Полная версия этой страницы: Полином для вычисления обратной CRC

Форум разработчиков электроники ELECTRONIX.ru > Cистемный уровень проектирования > Математика и Физика

Страницы: 1, 2

ViKo

Mar 16 2015, 09:08

Имею идею шифровать код прошивки с помощью CRC. Конкретно, декодировать его с помощью встроенной в STM32F2xx CRC-32 с полиномом:
X32 + X26 + X23 + X22 + X16 + X12 + X11 + X10 +X8 + X7 + X5 + X4 + X2+ X +1
То есть, каждое исходное слово заменяется CRC, вычисленной с его участием, следующее слово заменяется следующей CRC.
Вопрос, как закодировать, чтобы после декодирования получить исходный код? Каким полиномом? Думаю, перекрутить 32 в 1, и т. п.
Пока читаю пару статей о CRC, может, кто-то уже знает точный ответ?

Mar 16 2015, 11:05

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

demiurg_spb

Mar 16 2015, 11:22

Извините, не понял сути сначала.
По сути ИМХО это не очень здоровая идея.
Во первых ключ шифрования известен всем и сразу - полином от STM32.
Во вторых надо быть неплохим специалистом, чтобы изобретать новые криптоалгоритмы и уметь доказывать их стойкость.
И в третьих, чем не устраивает легковесный и стойкий алгоритм RTEA?

yes

Mar 16 2015, 12:32

может я что-то непонимаю - но не уверен, обратима ли эта операция?

upd:
да, наверно, давно не брал в руки шашки - для примитивного полинома должна быть обратима

ViKo

Mar 16 2015, 13:12

Пытаюсь понять на простом примере. Вот в этом калькуляторе
http://www.zorc.breitbandkatze.de/crc.html
задаю полином 8 порядка 100000111 (hex 7), все реверсы убираю, для данных 0 получаю результат 0x90. Никак, деля вручную, не могу получить. Получается 0xFD.

upd. Ага, вышло, когда посчитал на бумаге не для 0, а для 0x30 ('0'). Значит, в строке Data sequence задаются символы. Ух...
Вот эта программа помогла понять. Там свои тараканы.
http://depa.usst.edu.cn/chenjq/www2/softwa...calculation.htm

Цитата(yes @ Mar 16 2015, 15:32)

может я что-то непонимаю - но не уверен, обратима ли эта операция?

Обратима, так как основана на xor.

Похоже, если задать данные 0x01, то CRC выдаст результат, равный ее полиному (без старшего разряда. Так, как она описывается в форме 0xXXXX). CRC-08(0x01) = 0x07.
А если задать данные, равные полиному (вместе со старшим битом), то CRC равна 0. Для верхнего примера CRC-08(0x0107) = 0.

Mar 16 2015, 14:19

Цитата(ViKo @ Mar 16 2015, 16:12)

Обратима, так как основана на xor.

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

ViKo

Mar 16 2015, 14:21

Цитата(SM @ Mar 16 2015, 17:19)

Это зависит от длины данных. Думаю, если данные короче или равны размеру полинома, то будет однозначное соответствие. Я так и хочу использовать.
Пример из обычной математики - если имеем байт, то остаток от деления байта на 256 будет однозначно определять исходные данные.

Mar 16 2015, 14:24

Цитата(ViKo @ Mar 16 2015, 17:21)

Это зависит от длины данных. Думаю, если данные короче или равны размеру полинома, то будет однозначное соответствие. Я так и хочу использовать.

Тогда перед каждым новым словом придется переинициализировать регистр CRC.

ViKo

Mar 16 2015, 14:31

Цитата(SM @ Mar 16 2015, 17:24)

Тогда перед каждым новым словом придется переинициализировать регистр CRC.

Идея такая. На каждое слово, посланное в блок CRC-32, STM32 выдает 32-битовую CRC. Она и должна быть расшифрованным кодом прошивки. Получив следующее слово, с использованием предыдущей CRC, нужно получить следующее слово прошивки. И так до конца. Без инициализации, только в самом начале однажды (это слово инициализации и будет главным секретом).

Mar 16 2015, 14:39

Цитата(ViKo @ Mar 16 2015, 17:31)

Без инициализации, только в самом начале однажды (это слово инициализации и будет главным секретом).

Вот поэтому однозначности точно не будет. Для начального значения, равному нулю (даже не FFFFFFF, а именно нулевой остаток), я допускаю, что однозначность имеется. Но для любых других начальных условий однозначности, на сколько я понимаю, не будет. Ведь добавление очередных 32 бит - это домножение полинома, соответствующего всем предыдущим данным, на полином, соответствующий этим 32 битам. То есть, был, например, полином 1536-го порядка, после обработки 48 слов, и стал 1568-го порядка. И, вроде как, никакой гарантии нет, что не будет двух одинаковых остатков для двух разных домножений для каждого из слов, кроме самого первого после инициализации. Я не могу строго это доказать, но чисто интуитивно уверен, что для каких-то определенных данных, прошедших перед текущим данным, однозначности не будет по причине того, что полином имеет степень, равную длине слова, и компоненты, меньшие этой степени.

ViKo

Mar 16 2015, 14:47

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

Пораскинув мозгами, не нахожу достаточной стойкости данного способа ко взлому. Допустим, кого-то осенит, или подслушает, или купит, принцип действия. А дальше - подобрать начальное значение, и все. Не проще ли заксорить массив каким-нибудь длинным выражением, которое подбирать замучаешься?

Разве что, для общего развития, сотворить.

Mar 16 2015, 15:25

Цитата(ViKo @ Mar 16 2015, 17:47)

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

Для сравнения, чтобы более понятно было. А то деление полиномов для Вас это, видимо, некий "космос". А я вот приземленный пример приведу. С алгебраическим делением, имеющим все те же свойства, что и деление полиномов.

Допустим, размер 8 бит, а генерирующий полином соответствует числу 311 (оно простое, что эквивалентно примитивности полинома). Начальное значение 0. Считаем просто - в начале в некоем аккумуляторе 1. Каждое последующее число домножается к аккумулятору (и в нем остается произведение) - это эквивалент домножения текущего полинома данных на полином, соответствующий новому байту, после чего находится остаток от деления на 311, после чего из него берется 8 бит (еще один остаток от /256) - это алгебраический эквивалент CRC (с точки зрения обратимости операций, а не числового результата.

входные данные:

22 -> 22
33 -> 104
44 -> 222
11 -> 9

и еще:
22 -> 22
33 -> 104
44 -> 222
248 -> 9

получите гранату - числу 9 соответствует два варианта входной последовательности.

Цитата(ViKo @ Mar 16 2015, 17:47)

Не проще ли заксорить массив каким-нибудь длинным выражением, которое подбирать замучаешься?

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

------------------
UPD:

Я неправильно сделал эквивалент формирования входного полинома данных. Для каждого следующего байта аккумулятор должен домножаться на 256 (на x^8) и прибавляться данное. А не домножать аккумулятор на данноею Вот правильный пример:

Код

байт   аккумулятор  "типа-CRC-делением"
22    22                22
33    5665            67
44    1450284            91
11    371272715        37

и второй вариант

Код

байт   аккумулятор  "типа-CRC-делением"
22    22                22
33    5665            67
44    1450284            91
66    371272770        37

Смысл тот же, числу 37 после таких входных данных, 22 33 и 44, соответствует два варианта - 11 или 66.

ViKo

Mar 16 2015, 15:28

Цитата(SM @ Mar 16 2015, 18:14)

Каждое последующее число домножается к аккумулятору (и в нем остается произведение) - это эквивалент домножения текущего полинома данных на полином...

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

По поводу UPD - у вас аккумулятор безразмерный, растет и растет число в нем...

Надо от старья избавляться.
Приведите пример нормальный, "космический". Простейший, CRC-4: x4 + x1 + 1

Mar 16 2015, 15:37

Цитата(ViKo @ Mar 16 2015, 18:28)

Надо от старья избавляться.

CRC то не избавляется. CRC - это остаток от деления полинома, представляющего все входные данные, от момента инициализации. Поэтому в таком эквиваленте следует иметь безразмерный аккумулятор. И поэтому в CRC будут аналогичные "дубли", зависящие от всех предыдущих данных. Засада кроется не в обрезании "полинома данных" - сделать, как бы, CRC со скользящим окном, а именно в том, что генерирующий полином имеет единицу в разряде, на 1 старше, чем размер CRC. (этот бит для любого полинома = 1, и обычно скрыт, так как вроде как, лишний, в расчете непосредственно не участвует )

ViKo

Mar 16 2015, 15:50

Цитата(SM @ Mar 16 2015, 18:37)

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

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

Mar 16 2015, 15:54

Цитата(ViKo @ Mar 16 2015, 18:50)

Избавляется. Старший бит породил остаток и улетел в космос.

Не избавляется!!!!!! Измените хотя бы один бит в начале блока, и результат CRC будет уже совершенно другим. На то она и CRC, что контролирует весь блок в целом, следовательно, не избавляется (не забывает) ни один обработанный бит, где бы он не был. Так вот "аккумулятор" - это эквивалент "блока данных целиком", поэтому НЕЛЬЗЯ в нем ни от чего избавляться.

на делении полиномов проверять не буду, так как в экселе одним шевелением мизинца это не сделать.

ViKo

Mar 16 2015, 16:11

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

Mar 16 2015, 16:29

Цитата(ViKo @ Mar 16 2015, 19:11)

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

Вам эксель файл с тестом что-ли сюда выложить? Чтобы Вы увидели, что в алгебраическом варианте НЕТ однозначности? Причем, почему, это теоретически понятно, даже не напрягая мозг - число, эквивалентное полиному - 311, а бит всего 8. Поэтому остаток от деления на 311 в некоторых случаях больше 8 бит, поэтому и повторы есть.
И, в аналогии для CRC - если полином, например, X^8+x^5+x^4+1, то и остаток от деления на него может содержать X^8, а может и не содержать, а при этом остальные члены будут одинаковые, вот и повтор. А сам X^8, это 0x100, это за пределами байта, его не видно.

Цитата(ViKo @ Mar 16 2015, 18:28)

Приведите пример нормальный, "космический". Простейший, CRC-4: x4 + x1 + 1

О! Даже эксель не нужен.

Первое данное:

x^4 + x^1
Он не делится на x^4 + x^1 + 1, поэтому остаток будет равен x^4 + x^1 (0x12) - а бит всего 4 - то есть, 0x02

Второе данное:

x^1
Он тоже не делится на x^4 + x^1 + 1, поэтому остаток будет равен x^1 (0x02) - а бит всего 4 - то есть, 0x02

Вот и дубль.

AHTOXA

Mar 16 2015, 16:51

Так ему однозначность нужна в другую сторону. Чтобы для закодированных данных crc получалась однозначной. А то, что закодировать можно несколькими способами - это не страшно.
Что до самой идеи, то мне она не нравится. С тем же успехом можно просто xor-ить всё подряд - секретность на том же уровне (чтобы раскодировать, надо знать инициализирующее значение).

Mar 16 2015, 17:00

Цитата(AHTOXA @ Mar 16 2015, 19:51)

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

Так а как раскодировать, если для двух разных данных может быть одинаковая CRC? Как принять решение, какое из этих двух данных корректное?

PS
Правда я не до конца уверен в том, что деление полиномов в данном случае корректно сравнивать с делением арифметическим, так как коэффициенты у полиномов находятся в поле GF(2), а там арифметика другая, по модулю. Поэтому я все же не уверен в том, что существуют такие остатки от деления, которые содержат член со самой старшей степенью из членов многочлена-делителя. По логике - должны. По факту - не уверен. Потому, что там, в этом поле, например, можно единицу разделить на x+1 и получить из этого единицу и остаток x, и это будет корректно, потому, что 1*(x+1) +x = x+1+x = 1

ViKo

Mar 16 2015, 17:19

В CRC-4 полином 5-битовый, а числа и остаток 4-битовые. Поэтому 0x12 не может получиться в принципе. То же относится к другим упоминаемым полиномам.

Mar 16 2015, 17:21

Цитата(ViKo @ Mar 16 2015, 20:19)

В CRC-4 полином 5-битовый, а числа и остаток 4-битовые. Поэтому 0x12 не может получиться в принципе.

Вот поэтому, 0х02 и останется... А числа там не 4 битные, а N-битные, где N делится на 4 без остатка. Чтобы числа стали 4-битным, надо инициализировать CRC в ноль перед каждым таким числом. И, в таком случае, разумеется, обратимость гарантирована на 100%. А иначе все обработанные числа складываются в единый блок данных (единое число) длиной 4*n бит.

krux

Mar 16 2015, 17:32

я таки-извиняюсь, но предположу, что топикстартеру, вероятно, нужен FEC?

Mar 16 2015, 17:36

Цитата(krux @ Mar 16 2015, 20:32)

я таки-извиняюсь, но предположу, что топикстартеру, вероятно, нужен FEC?

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

А коррекция ошибок, да и обнаружение ошибок, не нужны.

krux

Mar 16 2015, 17:51

я опять-таки извиняюсь, но топикстартер в курсе про багофичи аппаратного блока CRC в STM32Fххх?

ViKo

Mar 16 2015, 18:07

Цитата(SM @ Mar 16 2015, 20:21)

Не согласен. Числа там такие, какие я задам. Для CRC-8 числа были бы 8-битовые. Для CRC-32 числа были бы (уже не хочу

) 32-битовые. Однозначность расчетов мне очевидна.
Какая разница, чем инициализирован блок CRC, если он и при кодировании и при декодировании будет инициализирован одним и тем же. В пределах разрядности, в данном случае 32-х. Нулем ли он инициализирован или 0xFFFFFFFF, все эти биты продвинутся при расчетах на 32 шага, втянув за собой биты новых данных. Ну, не просто втянув, а еще и "подпортив" их в соответствии с CRC.

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

Мне, наверное, пригодился бы CRYP, что есть в STM32F21x, но, по-моему, эти мк в Беларусь (и Россию) не поставляются.

Цитата(SM @ Mar 16 2015, 20:36)

А коррекция ошибок, да и обнаружение ошибок, не нужны.

Именно.

Кроме "хоть что-то делать".

Mar 16 2015, 18:11

Цитата(ViKo @ Mar 16 2015, 21:02)

Не согласен. Числа там такие, какие я задам.

Нельзя быть не согласным с определением CRC. Если Вы не согласны, значит Вы ведете разговор не о CRC, а о чем то другом. CRC - по определению - это остаток от деления полинома, соответствующему всему блоку входных данных в целом, на порождающий полином. !!! всему блоку !!!. Началом блока считается момент, когда инициализировали алгоритм деления полиномов, концом блока - когда считали CRC. Таким образом, чтобы данные были N-битные, следует каждые N бит инициализировать CRC. Если Вы считываете CRC через каждые, допустим, 8 бит, и не переинициализируете, то у вас первое CRC соответствует блоку данных из 8 бит, второе блоку из 16 бит, третье - блоку из 24 бит, четвертое - блоку из 32 бит, пятое - из 48 бит, и так далее, пока не переинициализируете его. И нельзя рассматривать деление полинома, соответствующее только последнему байту, когда до этого была еще куча байт - блок данных, он на части не делим (точнее делим, но переинициализацией CRC). Арифметический пример - число 123 при делении на 17 даст остаток 4. А если перед этим было число 1, то весь блок данных станет 1*256+123, то есть 379, и остаток от деления на 17 уже будет 5!.

ViKo

Mar 16 2015, 18:16

Цитата(SM @ Mar 16 2015, 21:11)

Ну и пусть. Где здесь противоречие принципам CRC? Я вычислил CRC для первого байта и сохранил его. Потом продолжаю вычислять для двух байтов и, зная первую CRC, однозначно определю CRC для второго байта, если потребуется. И т.п.
Инициализация блока CRC - это не сброс автомата, а начальное значение. Если я буду каждый раз инициализировать его, например, 0x77776666 при расчете и при проверке, соответствие будет гарантировано. Если я с каждым новым словом буду инкрементировать начальное значение от 0 до 0xFFFFFFFF при расчете и проверке - тоже! Аналогично я могу инициализировать блок CRC предыдущим значением (не трогать, то есть), если при расчете и при проверке они одинаковые.
Главное, чтобы эти начальные значения совпадали при расчете и при проверке. Вот и вся сущность этой инициализации.

Mar 16 2015, 18:26

Цитата(ViKo @ Mar 16 2015, 21:16)

и, зная первую CRC, однозначно определю CRC для второго байта, если потребуется. И т.п.

А я вот в этом сильно не уверен. Возвращась к арифметическому аналогу с делителем 311 и 8 битами... Повторю его еще раз... На аккумулятор не смотрим, так как "весь блок данных нам, типа, не важен". Я его удалил. Смотрим только на данные, и аналог CRC.

22 -> 22
33 -> 67
44 -> 91
11-> 37 или 66->37

И что дало такое априорное знание, что код был равен 91 перед тем, как стал 37? Это как-то может помочь в принятии решения, как декодировать число 37 - в 11, или в 66?

ViKo

Mar 16 2015, 18:48

Давайте возьмем примитивнейший пример. CRC-8 равна сумме того числа-байта, что занесено в блок вычисления и входного байта. И ограничена, естественно, 8 битами. Кодируем ту же последовательность, каждое число не более 8 битов:
22 -> 22
33 -> 55
44 -> 99
66 -> 165
166 -> 330 = 74
255 -> 329 = 73
и т.д. Очевидно, однозначность будет всегда.

Цитата(SM @ Mar 16 2015, 21:26)

И что дало такое априорное знание, что код был равен 91 перед тем, как стал 37? Это как-то может помочь в принятии решения, как декодировать число 37 - в 11, или в 66?

Это говорит о том, что предложенный вариант вычислений как CRC использовать нельзя.
Когда вы умножаете предыдущий результат на 256, вы сильно вылетаете за разрядность числа 311. Видимо, здесь ошибка.

AHTOXA

Mar 16 2015, 18:58

Цитата(SM @ Mar 16 2015, 22:00)

Так а как раскодировать, если для двух разных данных может быть одинаковая CRC? Как принять решение, какое из этих двух данных корректное?

Насколько я понял, раскодирование заключается в вычислении CRC. Это однозначное преобразование. Поэтому в качестве закодированных данных подходит любая последовательность, которая даёт нужную CRC.

Mar 16 2015, 19:04

Цитата(ViKo @ Mar 16 2015, 21:46)

Очевидно,

Это не доказательство. Вот для арифметического деления, доказательство четкое (математически), что однозначности нет. По причине того, что число G, выступающее в роли делителя, больше, чем 2^(N-1), где N - разрядность числа. И, поэтому, остатки от деления DATA mod G, большие, либо равные, чем 2^(N-1), зацикливаются внутри байта из-за отбрасывания старшего бита. Было бы логично распространить это и на полиномы. Потому, что там аналогия полная - полином на 1 разряд больше, чем CRC, поэтому результат от деления полиномов должен бы также зацикливаться внутри этого числа разрядностью на 1 меньше, чем полином, приводя к дублям.

"Очевидно" - нет такого термина. Мне вот, очевидно, что для CRC4 будет для входных данных "0001 0010" , что соответствует полиному x^4+x - остаток от деления на x^4+x^1+1 будет равен x^4+x, что соответствует числу 2, если оставить 4 бита. Проверяем - 0*(x^4+x^1+1) + (x^4+x) = x^4+x - проверка показала, в делении не ошиблись, остаток именно такой. И, одновременно, для данного "0000 0010", что соответствует полиному x^1, остаток от деления на x^4+x^1+1 равен x^1, что также соответствует четырехбитному числу 2. Проверяем - 0*(x^4+x^1+1) + x^1 = x^1. Проверка опять показала, что поделено правильно, и остаток именно такой.

Цитата(AHTOXA @ Mar 16 2015, 21:58)

Насколько я понял, раскодирование заключается в вычислении CRC. Это однозначное преобразование.

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

ViKo

Mar 16 2015, 19:08

Цитата(AHTOXA @ Mar 16 2015, 21:58)

Раскодировать нужно не в одно число, а весь массив. Слово за словом, используя аппаратный блок CRC. Задача, что подсунуть этому блоку, чтобы после каждого вычисления CRC получался исходный код.
В интернете это называется reversing CRC.
http://stackoverflow.com/questions/1514040/reversing-crc32
Вижу, математики запутали своим полиномиальным делением. Куда логичнее по-инженерному пользоваться регистрами сдвига и исключающим ИЛИ. Не вижу препятствий написать реверсивный алгоритм CRC, двигая данные в регистре в обратную сторону.

XOR, естественно, тоже ... тоже что-то с ними сделать.

Цитата(SM @ Mar 16 2015, 22:04)

Мне вот, очевидно, что для CRC4 будет для входных данных "0001 0010"...

Это уже пара данных, требующая в данной задаче двух выходных CRC.

Mar 16 2015, 19:23

Цитата(ViKo @ Mar 16 2015, 22:08)

Это уже пара данных, требующая в данной задаче двух выходных CRC.

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

ViKo

Mar 16 2015, 19:33

Полином CRC известен, он не от балды берется. x^4 + x^1 + 1. Вы подберите два разных 4-битовых числа, которые при делении на 10011 дадут одинаковый результат - остаток. Перед числами можете приписать в старших разрядах любое одно и то же число (от предыдущего расчета) - это к вопросу о начальном значении. Не подберете.

Давайте так.
Я могу подобрать некое 32-битовое число, которое после вычисления CRC-32, инициализированной нулями, даст на выходе нужное мне значение? Да.
Я могу подобрать некое 32-битовое число, которое после вычисления CRC-32, инициализированной неким известным числом, даст на выходе нужное мне значение? Да.

Mar 16 2015, 20:25

Цитата(ViKo @ Mar 16 2015, 22:33)

0x35. 0011 0101 - это x^5+x^4+x^2+1. Делим на x^4+x+1. Получаем частное (x+1), остаток 0 (обрезав до 4 бит, тоже ноль). Проверяем (x+1)*(x^4+x+1) = x^5+x^2+x+x^4+x+1 = x^5+x^4+x^2+1 - сходится.
0x36. 0011 0110 - это x^5+x^4+x^2+x. Делим на x^4+x+1. Получаем частное (x), остаток x^4 (обрезав до 4 бит, тоже ноль). Проверяем x*(x^4+x+1)+x^4 = x^5+x^2+x+x^4 = x^5+x^4+x^2+x - сходится.

Для чисел 0x30...0x3F полные остатки от деления, не обрезая до 4 бит, затем, в скобках, частное, и, в конце, остаток, обрезая до 4-х бит:

30 mod 13 = 05 (div=03) => 5
31 mod 13 = 04 (div=03) => 4
32 mod 13 = 07 (div=03) => 7
33 mod 13 = 06 (div=03) => 6
34 mod 13 = 12 (div=02) => 2
35 mod 13 = 00 (div=03) => 0
36 mod 13 = 10 (div=02) => 0
37 mod 13 = 11 (div=02) => 1
38 mod 13 = 0D (div=03) => D
39 mod 13 = 0C (div=03) => C
3A mod 13 = 0F (div=03) => F
3B mod 13 = 0E (div=03) => E
3C mod 13 = 09 (div=03) => 9
3D mod 13 = 08 (div=03) => 8
3E mod 13 = 0B (div=03) => B
3F mod 13 = 0A (div=03) => A

нет такого числа, чтобы получить с тройкой в старшем полубайте число три на выходе. Зато ноль можно получить двумя способами. Проверить многочлены перемножением можно все - я ради проверки это сам проделал для всех приведенных чисел ручкой на бумаге. Проверки для двух нулей привел выше. UPD: до числа 0x35 - обратимость присутствует везде. И, далее, тоже не все "приписки" необратимы.

А вот, если "переделить" - то есть, продолжать деление, если в остатке присутствует x^4, но остаток уже меньше, чем полином-делитель (то есть, деление по факту уже закончено, так как остаток УЖЕ меньше, чем делитель, и он ну никак не может больше делиться на него, но, все равно, тупо и нагло выполнить итерацию), то обратимость появится, и при этом тоже проверка будет сходиться:

30 mod 13 = 05 (div=03)
31 mod 13 = 04 (div=03)
32 mod 13 = 07 (div=03)
33 mod 13 = 06 (div=03)
34 mod 13 = 01 (div=03)
35 mod 13 = 00 (div=03)
36 mod 13 = 03 (div=03)
37 mod 13 = 02 (div=03)
38 mod 13 = 0D (div=03)
39 mod 13 = 0C (div=03)
3A mod 13 = 0F (div=03)
3B mod 13 = 0E (div=03)
3C mod 13 = 09 (div=03)
3D mod 13 = 08 (div=03)
3E mod 13 = 0B (div=03)
3F mod 13 = 0A (div=03)

ViKo

Mar 16 2015, 20:58

Могу только повторить - 0x30...0x3F не укладываются в диапазон, который дает однозначное соответствие остатка от деления исходному числу. В данном случае CRC 4-битовая, значит, и числа должны быть 4-битовые.
Ага, значит, приписали к 0..F впереди 3... сейчас...
неправильно поделили, остаток от деления 0x36 на 0x13 будет 1 (5 вышло, промахнулся). 0x37 mod 0x13 = 6.

Для 0x30 mod 0x13 я получил частное 0x35 и остаток 0xF.

0x30 / 0x13 = 0x35, 0xF
0x31 / 0x13 = 0x34, 0xC
0x32 / 0x13 = 0x37, 0x9
0x33 / 0x13 = 0x36, 0xA
0x34 / 0x13 = 0x31, 0x3
0x35 / 0x13 = 0x30, 0x0
0x36 / 0x13 = 0x33, 0x5
0x37 / 0x13 = 0x32, 0x6
0x38 / 0x13 = 0x3C, 0x4
0x39 / 0x13 = 0x3D, 0x7
0x3A / 0x13 = 0x3E, 0x2
0x3B / 0x13 = 0x3F, 0x1
0x3C / 0x13 = 0x38, 0x8
0x3D / 0x13 = 0x39, 0xB
0x3E / 0x13 = 0x3A, 0xE
0x3F / 0x13 = 0x3B, 0xD

Методика деления описана в статье http://www.info-system.ru/library/algo/crc1.pdf

upd. Исправляю остатки - выбрасываю старший 0. Тогда CRC от последовательности исходного числа и остатка даст 0. Это связано с разрядностью используемых чисел, в данном случае 4.
Для проверки в CRC калькуляторе нужно задавать 30F0.

Mar 16 2015, 21:43