Комментарии 51
Жаль не могу + поставить.
x^8 + x^7 + x^6 + x + 1
?
Многим из нас нравится мёд, но думаю лишь не все знают как пчелы его делают)
P.S. И не понятно что набросились минусами. Я мнение своё высказал. Если хотя бы 2 человека заинтересуются и продерутся сквозь формулы — уже автор миссию свою выполнил.
я очень умный, я намного лучше понял статью чем вы,
вы сами виноваты что не учились в Институте Математики СОРАН,
я вам ничего объяснять не буду, вы не продрались сквозь формулы — вы сами виноваты.
Спасибо, че.
Пожалуйста че.
P.S. ХахА — сейчас минуса помчатся.
Всё просто. Порождающий полином — это по модулю чего мы берём при умножении в группе Галуа. Соответственно, чтобы после взятия модуля осталось 8 бит — у этого полинома должна быть восьмая степень, т.е. слагаемое x^8.
Английская вики говорит, что полином из статьи предпочтительный и ссылается на «Recommended Elliptic Curves for Government Use», pdf линк. Стр 88, D.1.1.3 Choice of Basis for Binary Fields. Но там тоже нет объяснения, только рекомендация
x^8 + x^7 + x^6 + x + 1делись степени 5, 4, 3 и 2? Почему степеней получается 9 (единица в данном случае — это же x^0? Или это какая-то магическая константа)?
То, что в многочлене не записаны члены со степенями 5,4,3,2 — обозначает, что при этих степенях коэффициент равен нулю. Точно так же пишут x вместо 1*x, и пишут 1 вместо 1*x^0. То есть формулу можно записать как
1*x^8 + 1*x^7 + 1*x^6 + 0*x^5 + 0*x^4 + 0*x^3 + 0*x^2 + 1*x + 1*x^0
Касательно степени 8 — в статье написано, что для создания расширенного поля над p^m — требуется порождающий многочлен степени m, то есть в котором есть m+1 коэффициентов со степенями от 0 до m включительно. Здесь у нас поле над 2^8 — соответственно порождающий многочлен 8 степени, с 9 коэффициентами. И никакой магии.
К вашим вопросам — 1) Многочлен неприводим, потому что не раскладывается на произведение других делителей. Можете взять и проверить. 2) Никаких особых свойств: можно взять любой неприводимый многочлен 8 степени, получится изоморфное поле Галуа, как выше отметил @Wicirellis.
Можете взять и проверить.Звучит как «2^82 589 933 − 1- простое число. Можете взять и проверить», только хуже, потому что непонятно, как упорядочивать многочлены, чтобы применить перебор. Или есть какие-то другие способы исчерпывающей проверки?
Для 9 степени проверять надо не так уж много:
1) построить все неприводимые многочлены до 4 степени включительно.
2) проверить что тестируемый многочлен не делится нацело ни на один из построенных.
Пункт первый необязателен, но тогда придется проверять делимость для всех многочленов до 4 степени включительно.
Если вы не забыли, у нас коэффициенты могут быть только 0 и 1, то есть всего 32 возможных многочлена для проверки. Заметно меньше кандидатов, чем для 2^82 589 933 — 1.
Что насчёт тайминг атак, особенно учитывая что для эффективности желательно использовать таблицу перестановок размером 1792 байта? Существуют ли оптимизированные bitsliced реализации шифра?
Какие реализации оптимизированные под современное железо (SIMD, instruction-level parallelism и т.д.) можете посоветовать?
Там господа из Инфотекса провели некоторый разбор различных вариантов реализации линейного преобразования.
Со своей стороны могу сказать, что все режимы работы со сцеплением или генерацией имитовставки в чистом виде будут неэффективны в реализациях для FPGA.
У вас в методах GOST_Kuz_Encript и GOST_Kuz_Decript лишнее выделение памяти в переменную out_blk
Однако для начала разберем основные операции в более простом поле GF(2^3) с порождающим полиномом x^3+x+1.А дальше по тексту идёт полином x^2+x+1. Так и должно быть?
Сразу обращаю внимание, что знак "+" здесь и далее по тексту обозначает операцию побитового XOR, а не сложение в привычном видеА почему тогда сразу не использовать знак для исключающего или?
x^2+x+1 — полиномиальное представление числа 7, которое используется в примере.
Почему считается, что это дает безопасность?
Sevastyan01, а сможете рассказать простым языком про последние достижения в криптоанализе Кузнечика — https://who.paris.inria.fr/Leo.Perrin/pi.html ?
Говорят, там нашли скрытую алгебраическую структуру в таблице преобразования (которая у вас огромным блоком из байт вставлена), такая же скрытая структура выявлена в белорусском ГОСТовом шифре, а авторы Кузнечика после публикации сливаются, говоря что это всё случайность.
Лично мне особо доставила вставка про французскую лотерею по ссылке Лео Перрена(не уверен в транскрипции). Просто для людей прорвавшихся до этого места необходимости в объяснении масштаба порядка в принципе не должно быть, а у тех, кому это может понадобиться, должно и раньше возникнуть тонна вопросов, так что вставка очень мило и чуждо смотрится в тексте :)
И не Кузнецов, а Кузьмин Алексей Сергеевич
На тему много статей и далеко не все из них я читал, но те, что читал, мне не понравились по выше сказанным причинам.
xakep.ru/2017/02/02/working-with-grasshopper
xakep.ru/2016/07/20/hash-gost-34-11-2012
xakep.ru/2018/05/10/working-with-magma
По простому — зачем в алгоритме 3 шага? Почему недостаточно одного xor-а? Что даёт последующее нелинейное преобразование? Что даёт наложение линейного преобразования?
Возможно, проблема в размере ключа, а всё остальное каким-то образом повышает сложность вскрытия ключа небольшой длины. Но почему бы об этом не написать?
Автор пытался объяснить "простым" языком и сделал немалую работу, но, увы, статья получилась не простая. Например, автор с ходу использует термин "поле", не объясняя, что это такое, и из-за этого многое остается непонятным. Давайте я попробую это восполнить.
Поле — это конечное или бесконечное множество каких-то элементов (например: целых чисел или многочленов или латинских букв), над которыми определены операции "сложения" и "умножения" и соблюдаются определенные условия.
Как известно, есть множество чисел, и над ними можно делать математические операции: складывать, вычитать, умножать, и есть связанные с ними математические правила (вроде x + 0 = x или (a + b) * c = a * c + b * c). Позже математикам захотелось обобщить математические операции, чтобы их можно было выполнять не только с числами, а с любыми объектами: с множеством из чисел от 0 до 9, множеством из многочленов, двумерных векторов, множеством латинских букв, цветных шариков, котят итд. Для этого и были придуманы группы и поля.
Группа — это множество любых элементов (конечное или бесконечное), в котором есть "нулевой" (нейтральный) элемент, определена операция "сложения", и для каждого элемента есть "отрицательный" (противоположный), так, что при сложении с элементом он даст ноль. Естественно, результат сложения тоже должен быть элементом группы.
Пример: множество целых чисел и операция арифметического сложения.
Поле получается, если мы возьмем группу и добавим в нее вторую операцию — умножение, "единичный" элемент и "противоположный" элемент (так, что если x умножить на противоположный элемент, получится 1), а также обеспечим выполнение правила a * (b + c) = a * b + a * c.
По идее, вы можете взять какое-то множество (например, множество чисел от 0 до 9), произвольно определить правила сложения и умножения (1 + 1 = 9, 1 + 2 = 5 и тд), и попробовать получить поле, но на практике у вас скорее всего не будут выполняться все требуемые условия, потому правила сложения и умножения не могут быть произвольными (попробуйте сами, если не верите).
Ну например, математики считают, что если в вашем поле конечное число элементов, то это число должно быть pn, где p — простое число. То есть сделать поле из 72 = 49 элементов можно, а из 48, 50 или 6 (по мнению математиков) — никак не получится.
Самый простой пример конечного поля — это поле остатков от деления на какое-то простое число. Например, поле остатков от деления на 5, состоящее из чисел (0, 1, 2, 3, 4). Пары противоположных чисел по сложению: 1 + 4 = 5 % 5 = 0, 2 + 3 = 0 (соответственно, в нашем поле 0 — 1 = 4, а 0 — 2 = 3). Пары противоположных чисел по умножению: 2 * 3 = 6 % 5 = 1, 4 * 4 = 16 % 5 = 1 (соответственно, 1 ÷ 2 = 3, 1 ÷ 4 = 4).
В статье же используется немного другое поле — поле Галуа. Элементы этого поля GF(28) — это многочлены вида a * x7 + b * x6 + ...g * x + h * 1, где a, b… h — это 0 или 1. Соответственно, эти 8 коэффициентов a… h можно записать в виде двоичного 8-битного числа от 00000000 до 11111111 или от 0 до 255 в десятичной форме. Сложение определено как XOR между элементами в двоичной форме. С умножением сложнее — там используется умножение многочленов, а в случае, если результат будет слишком большим, то он упрощается с использованием порождающего многочлена, который только для этого и нужен (x8 + x7 + x6 + x + 1 = 0).
К счастью, математики также выяснили, что в конечных полях всегда есть примитивный элемент g — такой элемент (то есть, многочлен), что при возведении его в степени от 0 до 255 получатся все другие элементы поля. Соответственно, любой элемент поля можно представить как gn, и вместо сложного умножения многочленов мы приводим их к виду gn * gm (по заранее подготовленной таблице), складываем степени и преобразуем обратно. В данном случае g — это 00010 (в двоичной форме) или x (в форме многочлена). Если вам кажется неочевидным, что возводя x в степень можно получить любой многочлен вроде x3 + x + 1, то напомню, что возведение в степень производится по правилам поля, а не по привычным правилам. При возведении многочлена x в 8-ю степень мы получим x8, который выходит за пределы поля и который надо упрощать через порождающий многочлен.
Таким образом, если мы составим таблицу соответствия двоичной формы многочлена и степени над g, то мы можем забыть про многочлены и далее работать только с числами от 0 до 255 (почему-то в Ява-коде не используется такая таблица, а делается умножение многочленов в "столбик" с упрощением с помощью "вычитания" (XOR) порождающего многочлена).
Жаль, что в источниках вроде википедии все объяснения замудреные, а не написаны простыми словами, и надо ломать голову, пока разберешься.
Кстати, в Википедии написано, что свои поля Галуа открыл и описал в 18 лет в 1830 году. Какой умный!
Добавлю еще про "линейность" и "нелинейность", которые упоминаются в тексте.
Если использовать поле Галуа, то все операции в шифре (кроме операции замены S) — это сложения и умножения в этом поле. Посмотрите на один раунд (шаг) из операций X, S, L:
В начале в операции X каждый байт блока данных C складывается по модулю 2 (ксорится) с ключом K. Это просто сложение в поле Галуа: X(C, K) = C + K.
Затем делается "нелинейная" операция замены по таблице: S(). "Нелинейная" она, так как ее в теории должно быть нельзя записать в виде сложений и умножений.
И наконец, делается линейное преобразование L, где каждый байт умножается в поле Галуа на определенную константу (An) и сдвигается на место соседнего байта в блоке, а на место 16-го байта подставляется сумма всех входящих байтов в поле Галуа. Если мы обозначим n-й байт на входе как In, а на выходе как On, то получим такую связь между входными и выходными данными после выполнения одного раунда шифрования (K — это ключ):
O = L(S(X(I, K)))
O0 = S(I1 + K1) * A1
O1 = S(I2 + K2) * A2
…
O14 = S(I15 + K15) * A14
O15 = S(I0 + K0) * A0 + S(I1 + K1) * A1 +… S(I15 + K15) * A15
Кроме операции S, все остальные операции — это сложения и умножения, они называются "линейными" и они легко обратимы с помощью вычитания и деления. Если операции S нет, то имея несколько пар "исходный текст" — "шифротекст", можно легко восстановить ключ K. Если операция S спроектирована неудачно, то шифр может быть уязвим к криптоанализу. Потому операция S является важным элементом шифра. И, как показали западные исследователи, таблица S не является полностью случайной, а рассчитана по какой-то формуле, о которой знают, но молчат создатели шифра.
Кстати, можно попробовать "обратить" операции, так как константы A и операция S известны. Получается:
I1 = S-1(O0 / A1) — K1
Незнание K мешает нам получить I, и это только один раунд, а их там всего 10.
Чтобы роль S была понятнее, мы можем рассмотреть примитивный шифр без блока S, когда мы просто ксорим исходный текст с ключом: O = I + K. У этого шифра есть недостаток: если мы знаем открытый текст и шифротекст, то ключ вычисляется элементарно: K = O — I (или O + I, так как сложение и вычитание тут одна и та же операция — XOR). Ну например, у нас есть зашифрованный вордовский файл, а мы знаем что заголовок в вордовских файлах всегда содержит известные "магические" байты. По ним мы вычисляем соответствующие байты ключа.
И второй недостаток: если у нас есть 2 шифротекста (или два куска большого шифротекста), зашифрованных одним ключом, то мы можем их поксорить и получим ксор от исходных текстов, так как при ксоре ключи взаимоликвидируются (K + K = 0).
Выше еще спрашивали, почему выбраны эти операции. Операция X — это добавление ключа к данным. S — добавляет нелинейность для защиты от обращения сложений и умножений. Зачем нужна L — я сам не очень понимаю, она просто переставляет байты местами, и заменяет 1 из 16 байтов на сумму.
Элементы этого поля GF(28) — это многочлены вида a * x7 + b * x6 + ...g * x + h * 1, где a, b… h — это 0 или 1. Соответственно, эти 8 коэффициентов a… h можно записать в виде двоичного 8-битного числа от 00000000 до 11111111 или от 0 до 255 в десятичной форме.
Ну а сам-то х — это что? Переменная? В него можно подставить конкретное значение и вычислить конкретное значение полинома, как мы привыкли это делать в школе?
Да, это переменная, да, можно подставить. Но так как идет работа с полиномами целиком, то этого никто не делает до тех пор, пока не понадобится вычислить значение полинома.
Более того эти полиномы нужны только для упрощения вычислений.
Можно обойтись без них. Достаточно привести табличку 256 на 256 для операции "сложения", табличку 256 на 256 для операции "умножения" и доказать, что эти операции удовлетворяют требованиям поля и можно с этим полем работать.
В случае с полиномами: берете неприводимый полином и работаете.
Да, это переменная, да, можно подставитьА вот тут с ссылкой на Кнута пишут, что «x может рассматриваться как формальный символ без определяющего значения» — то есть нет, не переменная и нет, нельзя подставить. Кому верить?
Вы же сами пишете: «x может рассматриваться как формальный символ...»
А может рассматриваться как полноценная переменная. Но пока вы работаете с элементами поля Галуа, в этом нет необходимости.
Элемент можно рассматривать как полином, а можно — как строку элементов.
В первом случае описать произведение элементов поля проще.
Да, x — это обычная переменная из математики. Значение x не дано, дан только многочлен. Если вы хотите вычислить его значение в какой-то точке (точках), то выберите точку (точки) и подставьте вместо x. Можете даже график нарисовать. Это на самом деле неважно, так как элемент поля у нас — сам многочлен, а не его значение. То есть не важно, чему равен x, важны коэффициенты a… h. Мы складываем и умножаем многочлены, а не их значения в какой-то точке.
Также. у нас порождающий многочлен, по которому можно определить его корни, и значения x, но опять же, это ни на что не повлияет, даже если у него нет корней.
Ваша аналогия не совсем верна, так как i является пусть и неизвестной, но константой, а x — нет. Мне кажется, вы делаете ошибку в том, что признаете только операции над числами. Если вы видите формулу, то вы хотите сначала вычислить значения всех переменных, а потом только делать сложения или умножения.
Но математика может гораздо больше. Она может складывать функции или выражения, даже если неизвестны точные значения входящих в них переменных.
Ну например, если у меня есть функция f(x) = 3x + 1 и функция g(x) = 2x. Что такое функция? Это зависимость одной переменной от другой, в данном случае, это зависимость переменных f и g от x, выраженная формулой. Заметьте, что мы не знаем, чему равен x, это не дано, и это нам не важно, так как наша формула справедлива для любых x, и она выражает именно связь между переменными, а не конкретные их значения. Нам дана связь между f и x, а не конкретные значения.
Имея эти функции, я могу их перемножить, даже не зная, чему равен x. Я могу определить функцию h(x) = f(x) * g(x) = (3x + 1) * 2x = 6x2 + 2x. И моя формула верна для любых x — вы можете выбрать любое значение x, вычислить значения f и g в этой точке и увидеть, что их произведение равно значению h в этой точке. То есть я здесь умножил именно функции (зависимости одной переменной от другой). Мне не важно, чему конкретно равен x, так как моя формула справедлива для любых x. Если мне захочется узнать значение функции, например, при x = 5, то я просто подставлю его в формулу.
Вы пытаетесь зафиксировать какое-то одно значение x. А я предлагаю писать формулы, которые справедливы для любых x.
То же самое и с полями Галуа. Мы перемножаем не значения многочленов в какой-то точке (при каком-то конкретном значении x), не числа, а сами многочлены. Многочлен — это по сути функция, зависимость y от x. Мы перемножаем эти функции, эти зависимости, а не их значения в одной определенной точке. То есть мы работаем на более высоком уровне абстракции.
Таким образом, в многочленах x — это переменная, которая может иметь любое значение. Вы должны делать преобразования таким образом, чтобы результаты оставались верными для любых x. То есть если вы складываете многочлены a(x) + b(x) = c(x), то при подстановке любого x в c(x) мы должны получить сумму a(x) и b(x).
Хотя, я тут перечитал Википедию, и возможно, вы отчасти правы насчет аналогии с i. Вот, что там написано:
В 1830 году восемнадцатилетний Эварист Галуа опубликовал работу, которая положила основу общей теории конечных полей. В этой работе Галуа (в связи с исследованиями по теории групп перестановок и алгебраических уравнений) вводит воображаемый корень сравнения F ( x ) ≡ 0 ( mod p ), где F(x) — произвольный многочлен степени ν, неприводимый по модулю p.
После этого рассматривается общее выражение A = a0 + a1 i + a 2 i 2 + … + a ν − 1 i ν − 1, где a0, a1,..., aν − 1 — некие целые числа по модулю p. Если присваивать этим числам всевозможные значения, выражение A будет принимать pν значений.
Независимо от того, будет x константой или нет, правила операций над многочленами не поменяются, так что это не очень принципиально.
А с полиномами из полей Галуа так не получится — мы не можем просто так взять и подставить x=0.5, потому что нам только нули и единицы доступны. Конечно, можно попробовать расширить модульную арифметику на поле вещественных, комплексных, гипер-комплексных и прочих чисел — но нужно ещё доказать непротиворечивость получившейся алгебры и к тому же при этом поле автоматически перестанет быть конечным.
Это язык математиков. Они привыкли называть понятия своими любимыми латинизмами. Но при этом возникают ситуации, когда в математике используются одни термины, а в других областях другие. Например — биекция означает привычное для программистов отношение один к одному, но само слово биекция для программистов совершенно не знакомо, хотя обозначаемое им понятие все они отлично знают, вот и получается «замудрёность», когда математики используют свои любимые названия и без зазубривания всей этой каши из латинизмов стороннему наблюдателю просто невозможно понять, о чём вообще говорят математики.
Хотя вообще обозначение одним словом некоего понятия полезно, но в математике ведь этих понятий миллион, и хоть все они такие же примитивные, как и отношение один к одному, текст из набора таких понятий неподготовленному читателю (не зазубрившему) можно читать только со словарём. При чём в словаре пояснения так же содержат латинизмы, которые нужно опять искать в словаре, и уровень вложенности такого поиска может быть очень глубоким. А при глубокой вложенности человек напрочь забывает, о чём он читал, когда начал искать первое непонятное слово. Поэтому математика — наука со страшным уклоном в зубрёжку. Если весь словарь не зазубрил — вложенность непонятных терминов (а ещё греческие да всякие еврейские буквы) убьёт смысл прочитанного. Отсюда и ассоциации математиков с заучками, сухарями, зубрилками и т.д.
Как-то делал вот такой рендер, мне кажется, будет в тему:
Криптографический алгоритм «Кузнечик»: просто о сложном