[ViKo 1]

Имею идею шифровать код прошивки с помощью CRC. Конкретно, декодировать его с помощью встроенной в STM32F2xx CRC-32 с полиномом:

X32 + X26 + X23 + X22 + X16 + X12 + X11 + X10 +X8 + X7 + X5 + X4 + X2+ X +1

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

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

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

[SM 0]

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

[demiurg_spb 0]

Извините, не понял сути сначала.

По сути ИМХО это не очень здоровая идея.

Во первых ключ шифрования известен всем и сразу - полином от STM32.

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

И в третьих, чем не устраивает легковесный и стойкий алгоритм RTEA?

 

[yes 6]

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

 

upd:

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

[ViKo 1]

Пытаюсь понять на простом примере. Вот в этом калькуляторе

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

 

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

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

 

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

А если задать данные, равные полиному (вместе со старшим битом), то CRC равна 0. Для верхнего примера CRC-08(0x0107) = 0.

[SM 0]

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

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

[ViKo 1]

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

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

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

[SM 0]

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

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

[ViKo 1]

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

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

[SM 0]

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

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

[ViKo 1]

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

 

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

 

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

[SM 0]

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

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

 

Допустим, размер 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 соответствует два варианта входной последовательности.

 

 

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

 

Есть очень простой (на ксорах) и вполне стойкий шифр - 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 1]

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

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

 

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

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

[SM 0]

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

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

[ViKo 1]

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

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

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