ViKo 1 16 марта, 2015 Опубликовано 16 марта, 2015 · Жалоба Имею идею шифровать код прошивки с помощью 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 16 марта, 2015 Опубликовано 16 марта, 2015 · Жалоба Математически точный ответ я дать могу - для того, чтобы получить заданное CRC, надо найти такие данные, чтобы остаток от деления полинома, представляющего эти данные на порождающий полином CRC был равен заданному числу. А вот готовый алгоритм решения этой задачи я не готов дать. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
demiurg_spb 0 16 марта, 2015 Опубликовано 16 марта, 2015 · Жалоба Извините, не понял сути сначала. По сути ИМХО это не очень здоровая идея. Во первых ключ шифрования известен всем и сразу - полином от STM32. Во вторых надо быть неплохим специалистом, чтобы изобретать новые криптоалгоритмы и уметь доказывать их стойкость. И в третьих, чем не устраивает легковесный и стойкий алгоритм RTEA? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
yes 6 16 марта, 2015 Опубликовано 16 марта, 2015 · Жалоба может я что-то непонимаю - но не уверен, обратима ли эта операция? upd: да, наверно, давно не брал в руки шашки - для примитивного полинома должна быть обратима Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
ViKo 1 16 марта, 2015 Опубликовано 16 марта, 2015 · Жалоба Пытаюсь понять на простом примере. Вот в этом калькуляторе 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 16 марта, 2015 Опубликовано 16 марта, 2015 · Жалоба Обратима, так как основана на xor. То, что она основана на XOR, не говорит о том, что одному выходному значению строго соответствует одно входное при любых начальных условиях. И, кстати, это, действительно, не факт. Я даже подозреваю обратное, по причине того, что при делении на полином, имеющий максимальную степень, равную размеру слова, но имеющий еще компоненты меньших степеней, остаток может содержать этот самый старший бит, который реально отбрасывается, а может и не содержать. При этом оставшиеся биты могут быть одинаковыми. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
ViKo 1 16 марта, 2015 Опубликовано 16 марта, 2015 · Жалоба То, что она основана на XOR, не говорит о том, что одному выходному значению строго соответствует одно входное при любых начальных условиях. И, кстати, это, действительно, не факт. Это зависит от длины данных. Думаю, если данные короче или равны размеру полинома, то будет однозначное соответствие. Я так и хочу использовать. Пример из обычной математики - если имеем байт, то остаток от деления байта на 256 будет однозначно определять исходные данные. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
SM 0 16 марта, 2015 Опубликовано 16 марта, 2015 · Жалоба Это зависит от длины данных. Думаю, если данные короче или равны размеру полинома, то будет однозначное соответствие. Я так и хочу использовать. Тогда перед каждым новым словом придется переинициализировать регистр CRC. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
ViKo 1 16 марта, 2015 Опубликовано 16 марта, 2015 · Жалоба Тогда перед каждым новым словом придется переинициализировать регистр CRC. Идея такая. На каждое слово, посланное в блок CRC-32, STM32 выдает 32-битовую CRC. Она и должна быть расшифрованным кодом прошивки. Получив следующее слово, с использованием предыдущей CRC, нужно получить следующее слово прошивки. И так до конца. Без инициализации, только в самом начале однажды (это слово инициализации и будет главным секретом). Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
SM 0 16 марта, 2015 Опубликовано 16 марта, 2015 · Жалоба Без инициализации, только в самом начале однажды (это слово инициализации и будет главным секретом). Вот поэтому однозначности точно не будет. Для начального значения, равному нулю (даже не FFFFFFF, а именно нулевой остаток), я допускаю, что однозначность имеется. Но для любых других начальных условий однозначности, на сколько я понимаю, не будет. Ведь добавление очередных 32 бит - это домножение полинома, соответствующего всем предыдущим данным, на полином, соответствующий этим 32 битам. То есть, был, например, полином 1536-го порядка, после обработки 48 слов, и стал 1568-го порядка. И, вроде как, никакой гарантии нет, что не будет двух одинаковых остатков для двух разных домножений для каждого из слов, кроме самого первого после инициализации. Я не могу строго это доказать, но чисто интуитивно уверен, что для каких-то определенных данных, прошедших перед текущим данным, однозначности не будет по причине того, что полином имеет степень, равную длине слова, и компоненты, меньшие этой степени. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
ViKo 1 16 марта, 2015 Опубликовано 16 марта, 2015 · Жалоба А мне интуиция говорит, что, поскольку я имею те же объемы исходной и выходной информации, то и восстановить его я могу. Я пропускаю через некую числомолотилку - регистр с обратными связями и исключающими или поток битов. Если я результирующий поток пропущу через некую реверсную числомолотилку, то получу исходный поток. Пораскинув мозгами, не нахожу достаточной стойкости данного способа ко взлому. Допустим, кого-то осенит, или подслушает, или купит, принцип действия. А дальше - подобрать начальное значение, и все. Не проще ли заксорить массив каким-нибудь длинным выражением, которое подбирать замучаешься? Разве что, для общего развития, сотворить. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
SM 0 16 марта, 2015 Опубликовано 16 марта, 2015 · Жалоба А мне интуиция говорит, что, поскольку я имею те же объемы исходной и выходной информации, то и восстановить его я могу. Для сравнения, чтобы более понятно было. А то деление полиномов для Вас это, видимо, некий "космос". А я вот приземленный пример приведу. С алгебраическим делением, имеющим все те же свойства, что и деление полиномов. Допустим, размер 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 16 марта, 2015 Опубликовано 16 марта, 2015 · Жалоба Каждое последующее число домножается к аккумулятору (и в нем остается произведение) - это эквивалент домножения текущего полинома данных на полином... Вот здесь, по-моему, кроется ошибка. Мы не перемножаем числа, а сдвигаемся. Как по длинному числу, потоку. То есть, разбили поток на слова, чтобы хранить его в массиве. А при расчете CRC с сохранением предыдущего результата (без инициализации) мы бит выдвинули, бит задвинули. Только результат выдаем сразу для целого слова этих битов. По поводу UPD - у вас аккумулятор безразмерный, растет и растет число в нем... :) Надо от старья избавляться. Приведите пример нормальный, "космический". Простейший, CRC-4: x4 + x1 + 1 Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
SM 0 16 марта, 2015 Опубликовано 16 марта, 2015 · Жалоба Надо от старья избавляться. CRC то не избавляется. CRC - это остаток от деления полинома, представляющего все входные данные, от момента инициализации. Поэтому в таком эквиваленте следует иметь безразмерный аккумулятор. И поэтому в CRC будут аналогичные "дубли", зависящие от всех предыдущих данных. Засада кроется не в обрезании "полинома данных" - сделать, как бы, CRC со скользящим окном, а именно в том, что генерирующий полином имеет единицу в разряде, на 1 старше, чем размер CRC. (этот бит для любого полинома = 1, и обычно скрыт, так как вроде как, лишний, в расчете непосредственно не участвует ) Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
ViKo 1 16 марта, 2015 Опубликовано 16 марта, 2015 · Жалоба CRC то не избавляется. CRC - это остаток от деления полинома, представляющего все входные данные, от момента инициализации. Избавляется. Старший бит породил остаток и улетел в космос. Я ведь не последний результат расчета CRC использую. А все, что рассчитал. Представьте, выполнил один первый раз, получил CRC. Могу я выполнить обратное действие, получить исходное слово? Очевидно, могу. На этом о том исходном слове забываю, как будто и нет его. Дальше вычисляю... в-общем, рекурсия, наша песня хороша... только выполнить ее нужно задом наперед при кодировании, чтобы при аппаратном декодировании передом назад все летало. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться