Начало работы с криптосистемой SRVB

Введение

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

Криптография теперь является одним из многих анонимных технологических героев нашей повседневной жизни. Социальные сети, веб-банкинг, военная разведка и любая другая информационная система, работающая с конфиденциальной информацией, — все они в значительной степени зависят от криптографии. Криптография позволяет нам сохранять конфиденциальность, что некоторые считают 12-м правом человека.

Эта статья познакомит вас с принципами криптосистем с открытым ключом и познакомит вас с криптосистемой Santana Rocha-Villas Boas (SRVB), разработанной автором статьи и профессором Даниэлем Сантана Роча. На момент написания статьи авторы алгоритма готовят кампанию, включающую финансовое вознаграждение каждому, кто сумеет взломать код. Поскольку в статье будет подробно описан функционал алгоритма, это лучшее место для начала погони за призом. Более подробная информация доступна на сайте SRVB.

Что такое криптосистема?

Криптография — это любой метод, препятствующий интерпретации сообщения, в то же время позволяющий его интерпретировать, если предоставляется конкретная инструкция, которая обычно является так называемым «ключом». Хотя это очень широкое определение, охватывающее даже самые ранние методы, стоит отметить, что оно не охватывает всего, что касается информационной безопасности.

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

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

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

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

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

Криптосистемы с открытым ключом

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

До сих пор мы видели создание безопасной связи после безопасного обмена секретными параметрами (ключами), но проблема обмена параметрами по общедоступному каналу остается. Прямо сейчас мы представим концепцию, которая решает чуть более осязаемую проблему: создание безопасного канала.

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

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

Решение заключается в разработке криптосистемы, для которой параметра шифрования недостаточно для того, чтобы реально интерпретировать исходное сообщение ^[1] , и сохранения при себе параметра, позволяющего интерпретировать сообщение. Мы называем этот параметр закрытым ключом. На основе закрытого ключа можно сгенерировать набор параметров для инструмента шифрования, не делая сами эти новые параметры способными раскрыть, что такое закрытый ключ. Этот набор параметров может быть общедоступным, потому что не так важно, кто может что-то зашифровать, если только один человек может это расшифровать. Поскольку этот набор параметров инструмента шифрования может быть обнародован, он называется открытым ключом.

Криптография, в которой ключи шифрования и дешифрования различаются и первый невозможно использовать для вывода второго, называется асимметричной криптографией, тогда как симметричная криптография — это то, что мы имеем, когда эти ключи одинаковы или легко выводятся друг из друга.

Алиса отправляет Бобу свой открытый ключ, который может использоваться только для шифрования вещей, которые может расшифровать только она (с помощью своего закрытого ключа, который она хранит в тайне), и, наоборот, Боб отправляет Алисе свой открытый ключ, который может использоваться только для шифрования вещей. что он один может расшифровать (с помощью своего закрытого ключа, который он также хранит в тайне). Но как можно опубликовать параметр алгоритма шифрования, из которого невозможно вывести точный обратный алгоритм?

Ответ лежит в области математики, наиболее тесно связанной с программированием, в теории сложности вычислений. Любой, кто достаточно глубоко вникал в математические проблемы, слышал о преобразованиях, которые легко выполнить одним способом, но трудно сделать обратным. В математическом анализе, например, нахождение производной из учебника обычно является простым упражнением, в то время как выполнение обратного (например, решение любого немного нетривиального интеграла или физического ОДУ или УЧП из учебника) требует более тщательного процесса предварительного выдвижения гипотез о семействах функций, которые гарантированно (или, по крайней мере, правдоподобно) содержат решение (решения) и решают обратные задачи, чтобы найти решения из этих семейств.

Примером, который на самом деле используется в криптосистеме RSA, является умножение больших простых чисел по сравнению с разложением на множители результирующего произведения без знания множителей. Выполнение умножения тривиально, но факторинг требует, чтобы вы случайным образом ^[2] угадывали простые множители, которые состоят из сотен цифр. Важным свойством операции является необходимость ее хорошего масштабирования. Добавление нескольких цифр к размеру простых чисел в RSA приведет к тому, что ключ, для взлома которого потребуется в тысячи раз больше операций, при незначительном увеличении сложности процесса шифрования. Грубо говоря, произведение простых чисел используется для шифрования, а пара простых множителей используется для расшифровки.

Имея все это в виду, давайте посмотрим, как работает криптосистема SRVB.

Лежащий в основе алгоритм — взгляд на SRVB

Проблема суммы подмножества

Как и любая другая криптосистема с открытым ключом, SRVB полагается на сложность решения конкретной проблемы, которую легко создать. В случае SRVB это проблема суммы подмножества, которую можно описать следующим образом:

По заданным целым числам $w$ и $v_1, \cdot \cdot \cdot, v_N \in Z$ найдите последовательность $b_1, \cdot \cdot \cdot, b_N \in {0,1}$, такую, что $ \sum_ {я = 1}^{N} v_i b_i = w $.

Ясно, что эта проблема может быть получена путем случайного выбора N целых чисел, случайного выбора их подмножества и суммирования этого подмножества, что тривиально.

Поиск грубой силы будет иметь сложность $ O( N * 2^N ) $, вычисляя для каждой комбинации значений $b$s. Более эффективный подход был предложен Горовицем и Сахни в 1972 году со сложностью $O(N*2^{N/2})$. Проблема становится не менее сложной, если мы заменим $b$s и $w$ на $k$-мерные векторы целых чисел. Однако область, в которой должна решаться эта более сложная проблема, также должна иметь изоморфизм с кольцом, где имеет место более простая версия той же проблемы, как мы увидим ниже. По этой причине SRVB использует проблему суммы подмножеств в пределах целых чисел Гаусса, где $k = 2$.

Существует особый случай, когда эту задачу легко решить с помощью жадного алгоритма. Если мы отсортируем масштабные коэффициенты последовательности $ v_1, \cdot \cdot \cdot, v_N $, в которой каждое целое число в последовательности больше суммы всех предшествующих ему целых чисел ($ \forall i , \sum_{j= 1}^{i-1} v_j < v_i $), можно использовать жадный подход, чтобы найти последовательность b за линейное время. Последовательность с описанными свойствами называется сверхвозрастающей последовательностью .

Вот простое описание жадного решения для этого случая:

1. Начните с $i = N$, текущего наблюдаемого фактора, и $w' = w$, остатка от $w$

2. Если текущий коэффициент масштабирования слишком велик, чтобы вписаться в то, что осталось от $w$, то есть $v_i > w'$, установите $b_i = 0$ и перейдите к следующему шагу. В противном случае мы знаем, что коэффициент масштабирования должен быть в последовательности (поскольку остальные коэффициенты меньше, чем $v_i$), и мы устанавливаем $b_i = 1$.

3. $ w' \Leftarrow w' - v_i * b_i$, $i \Leftarrow i - 1$. Если $i > 0$, вернитесь к шагу 2.

4. Убедитесь, что теперь $w' == 0$, иначе проблема была повреждена

Это работает, потому что мы знаем, что все множители, меньшие наблюдаемого в настоящее время, не могут вместе покрыть столько же (суб)суммы $ w' $, сколько может текущий множитель. Таким образом, если оставшаяся сумма больше, чем текущий фактор, мы точно знаем, что все последующие факторы вместе взятые не смогут составить ее без помощи текущего фактора. С другой стороны, поскольку все множители положительны, если текущий множитель $ v_i $ больше, чем оставшаяся сумма $ w' $, добавление любого другого множителя приведет к тому, что результат превзойдет $ w' $ еще больше.

Давайте настроим нотацию для остальной части статьи. Мы выбираем $ v_1, \cdot \cdot \cdot, v_n $ и $w$ в качестве множителей и суммы сверхвозрастающей последовательности, а $ u_1, \cdot \cdot \cdot, u_n $ и $y$ будут публично доступные параметры, которые предоставляются для восстановления $b_1,\cdot\cdot\cdot,b_n$.

Если последовательность $ u_1, \cdot \cdot \cdot, u_n $ выбрана таким образом, что она не является супервозрастающей, а число $y$ общедоступно, общедоступной информации для восстановления последовательности $ b_1, \cdot \cdot \cdot недостаточно. , б_н $. Однако, если существует сверхвозрастающая последовательность $ v_1, \cdot \cdot \cdot, v_n $, которая могла бы заменить последовательность $ u_1, \cdot \cdot \cdot, u_n $, то эту последовательность можно было бы использовать для решения задачи с жадный подход.

Ниже мы покажем, как это работает.

Использование сумм подмножества в предыдущей криптосистеме

В 1978 году Ральф Меркл и Мартин Хелман разработали способ использования этих двух парадигм рюкзака и линейности операции модуля для построения связи между двумя последовательностями, описанными в предыдущем разделе, — таким образом, возникла криптосистема с открытым ключом. Идея состояла в том, чтобы с помощью линейной операции (модуля) с секретными операндами превратить легкий рюкзак (состоящий из сверхвозрастающего вектора целых чисел) в сложный (не имеющий этого свойства). Преобразование состоит в умножении каждого $v_i$ на $\theta$ и взятии остатка от этого произведения на $\alpha$, где $\alpha \gt \sum_{i=1}^N v_i$ и $\gcd (\alpha, \theta) = 1$ (два ограничения, которые вскоре будут подтверждены). В результате последовательность $u_1, \ldots, u_N$ больше не является сверхвозрастающей и может считаться жестким рюкзаком .

Случайная перестановка последовательности $u_1, \ldots, u_N$ будет передана стороне, которая хочет зашифровать и отправить нам сообщение. Перестановка делается для того, чтобы третьему лицу было труднее угадать исходную сверхвозрастающую последовательность. В качестве коэффициентов $b_1, \ldots, b_N$ используются битовые блоки сообщения. Шифрование выполняется путем умножения последовательности ключей на эту последовательность коэффициентов и суммирования умножений в результат, который мы обозначим как $y$. Только владелец закрытого ключа может преобразовать $y$ в соответствующие $w$, которые были бы получены, если бы эти самые блоки $b_1, \ldots, b_N$ были умножены на простые целые числа (последовательность $v_1, \ldots , v_N$). Это делается путем умножения $y$ на $\theta^{-1}$, мультипликативную обратную величину $\theta$ модуля $\alpha$ (существование которого зависит от условия $\gcd(\alpha, \ тета) = 1$). Другими словами, $(\theta * \theta^{-1}) \bmod \alpha = 1$. После этого вычисляем $w = (y * \theta^{-1}) \bmod a$. Причина, по которой это гарантированно работает, заключается в линейности модуля , т. е. в том, что линейная комбинация остатков равна остатку линейной комбинации.

Если последовательно применить определение $u$, факторкольца и свойство линейности оператора модуля, то увидим соответствие:

$ \begin{align} y & = \sum_{i=1}^N b_iu_i \newline & = \sum_{i=1}^N b_i (v_i * \theta \bmod \alpha) \newline & = \sum_{ i=1}^N b_i * v_i * \theta \bmod \alpha \newline & = \left[ \sum_{i=1}^N b_i * v_i * \theta \right] \bmod \alpha \newline & = \ влево[ \sum_{i=1}^N b_i * v_i \right] * \theta \bmod \alpha \newline & = w * \theta \bmod \alpha \end{align} $

Таким образом, простая сумма $w$ может быть восстановлена ​​путем умножения обеих частей на $\theta^{-1}$ и взятия модуля на $\alpha$. Для этого нужно знать как $\alpha$, так и $\theta$ (которые позволяют легко вычислить $\theta^{-1}$), которые должны храниться в секрете как части закрытого ключа.

Одно единственное ограничение, $\alpha \gt \sum_{i=1}^N v_i$, было оставлено необоснованным, и вот объяснение этого: Равенство между второй и третьей строками состоит из равенства между классами вычетов частного кольцо целых чисел по модулю $\alpha$. Другими словами, в нем утверждается только равенство остатка членов при делении на $\alpha$, что не является достаточным условием равенства самих членов . В результате более одного вектора значений $b$ могут быть отображены в один $y$, что предотвращается ограничением максимально возможной подсуммы (т.е. суммы всех посылок $v_i$) $w_{max}$ до быть меньше $\alpha$ для любой комбинации значений $b$.

Как и в любом другом случае повседневной жизни, полное знание всех гипотез часто невозможно и никогда не бывает легким. В результате нам приходится полагаться на математическую интуицию при оценке безопасности использования криптосистемы, что не дает нам реальных гарантий. Через шесть лет после создания криптосистема MH была взломана атакой А. Шамира. Было еще несколько попыток реанимировать МЗ, многие из которых также не увенчались успехом.

Криптосистема Santana Rocha - Villas Boas (SRVB)

В 2016 году, после нескольких мозговых штурмов с автором этой статьи о различных вдохновленных ^[3] возможностях криптосистемы, Даниэлю Сантана Роша пришла в голову идея заменить $\theta$ и $\alpha$ на гауссовы целые числа. По более техническим причинам такой подход приводит к сопротивлению вышеупомянутой атаке Шамира.

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

Другое и все же элегантно аналогичное ограничение применяется к $\alpha$, которое теперь является целым числом по Гауссу. Нам требуется $w_{max} \leq \vert\alpha\vert^2$. Причину очень сложно формализовать, но, к счастью, ее легко понять по элегантному описанию:

Представьте себе квадратную решетку на плоскости комплексных чисел, сторона которой является гипотенузой прямоугольного треугольника из катетов a и b, параллельных действительной и мнимой осям. Пример такой решетки приведен ниже. Целые числа Гаусса по модулю $\alpha = a + bi$ могут быть представлены точками, расположенными внутри такой решетки. Внутри такой решетки есть $\vert\alpha\vert^2$ различных точек. Если мы выберем достаточно большой $\alpha$, мы сможем поместить все линейные комбинации легкого рюкзака.

Это графическое представление изоморфизма $f : Z/n \rightarrow Z[i]/(\alpha)$, где $n = 13$ и $\alpha = a + bi = 3 + 2i$ (обратите внимание, что $ n$ и $\alpha$ действительно удовлетворяют $n = \vert \alpha \vert ^ 2 = a^2 + b^2 $, как и требовалось). Точки представляют гауссовские целые числа, т. е. комплексные числа $a + bi$, где $a$ и $b$ — целые числа. Как обычно, горизонтальная ось представляет реальную часть, а вертикальная — мнимую часть. Таким образом, перемещение одной точки вправо или влево эквивалентно прибавлению +1 или -1 к ее текущему значению соответственно. Точно так же перемещение одной точки вверх или вниз соответствует добавлению +i или -i соответственно.

Красные точки — это эквиваленты $0 \bmod(\alpha)$. Помимо них, мы также раскрасили еще 4 пары точек.

Изоморфизм $f$ определяется преобразованием $i$-го элемента циклической последовательности $(0,1,2,\cdot\cdot\cdot,10,11,12,0,1,2,\cdot \cdot\cdot)$ в $i$-й элемент также циклической последовательности точек на рисунке, которая подчиняется следующим правилам:

1. Начинается с красной точки первого ряда;
2. Он следует за горизонтальными стрелками вправо; Кроме этого
3. Когда следование по стрелкам ведет последовательность за пределы решетки, она достигает одной из нечерных точек. Вместо того, чтобы идти к этой точке, он переходит к точке того же цвета (т. е. к эквивалентной точке по модулю $\alpha$) внутри того же квадрата; и наконец
4. Когда эта нечерная точка оказывается красной (что происходит после того, как все остальные цвета пройдены), последовательность переходит к самой верхней красной точке, тем самым повторяя цикл;

Чтобы отобразить хотя бы $Y$ натуральных чисел, нужно взять квадрат с площадью $\vert\alpha\vert^2$ (где $\vert\alpha\vert = \sqrt{a^2 + b^2} $ есть, по теореме Пифагора, мера его стороны) по крайней мере такой же большой.

Обратите внимание, что каждый «скачок» изменяет номер строки $r$ на $r \leftarrow (r + b)(mod a + b)$, если считать строки сверху вниз, и, что то же самое, на $r \leftarrow (r + a)(mod a + b)$, если считать снизу вверх. Таким образом, необходимое и достаточное условие для того, чтобы каждая строка (и точка) перемещалась ровно один раз в каждом цикле, состоит в том, что размер переходов взаимно прост с количеством строк, или, другими словами, $gcd(a,a + б) = НОД(Ь, а + Ь) = 1$. Из-за свойств оператора наибольшего общего делителя оба они эквивалентны $gcd(a,b) = 1$.

YS Villas Boas заметил необходимость взаимной простоты $a$ и $b$. Чтобы сохранить сверхвозрастание, каждое новое целое число $w$, добавляемое в конце последовательности, должно превосходить сумму всех текущих ($w > \sum_{i=1}^k v_i$). Он заметил, что для этого их умножающие коэффициенты $b_i$ должны быть не меньше 1, и, таким образом, каждый бит нельзя преобразовать в коэффициенты 0 и 1. Если бы коэффициенты были равны 0 и 1, только блок состоящая только из единиц, удовлетворяла бы сверхвозрастанию. По этой причине биты 0 и 1 затем были сопоставлены соответственно с коэффициентами умножения 1 и 2.

Наконец, что менее тривиально: на каждом шаге декодирования нужно найти одно новое целое число $v_1$ как решение уравнения $b_1 v_1 = v_{n+1} - \sum_{i = 2}^{n} b_i v_i$, где все $v_i$ и $b_i$ известны при $1 < i \leq n$. Поскольку мы также не знаем $b_1$, мы получаем систему с одним уравнением и двумя переменными, что оставляет нам одну степень свободы. Чтобы исправить это, мы должны решить, что одно положительное значение (для простоты, 1) всегда будет присваиваться $b_1$, тем самым устраняя двусмысленность. Таким образом, поскольку первый коэффициент равен 1, для кодирования $n$ битов на каждом шаге наша последовательность целых чисел должна состоять из $n + 1$ элементов.

Еще одна техническая проблема, которую необходимо решить, — это случай, когда размер сообщения в байтах не кратен размеру блока. Другими словами, что делать с возможными оставшимися байтами последнего блока данных, чтобы при восстановлении блоков данных сохранялись все байты исходного содержимого, но не более того? Мы решили эту проблему, повторив последний байт сообщения один раз. Затем за этой копией следует случайная последовательность, в которой требуется, чтобы каждый компонент отличался только от предыдущего. Таким образом, при извлечении блоков данных последний из них или, в худшем случае, предпоследний усекается в последнем повторении байтов. ^[4]

Теперь покажем пример криптосистемы SRVB.

Начнем с параметров:

$к = 4$;

$м = 4$;

что дает длину блока $l = 4 * 4 = 16$ и сверхвозрастающую последовательность из $k + 1 = 5$ натуральных целых чисел, которая обрабатывается , т. е. линейно комбинируется, к которой добавляется результат этой линейной комбинации, и сводится к последним $k + 1$ элементам —$m = 4$ раз;

Для простоты пусть следующим будет (супервозрастающий) вектор $v_i$:

$(1,2,4,8,16)$

В самом деле, последовательность первых пяти степеней двойки только потому, что это сверхвозрастающая последовательность с пятью элементами и наименьшими строго положительными возможными значениями (таким образом избегая 0 в открытом ключе, который тривиально выдал бы соответствующий 0 своего аналога ).

Как мы сказали ранее, для $\alpha = a + bi$ целые числа $a$ и $b$ должны быть взаимно простыми, и в соответствии с упомянутым новым ограничением мы должны потребовать, чтобы $a^2 + b^2 = \vert\alpha\vert^2 \geq W$. Быстрый расчет дает $W = 1590$. Поскольку $\sqrt{1590} \simeq 39,8$, очень удобно выбрать $\alpha$, равное $\alpha = 39 + 40i$, поскольку оно достаточно велико, чтобы вместить изоморфизм с кольцом целых чисел с at минимум 1590 компонентов, а также $gcd(a,b)=1$. Кроме того, нам нужно выбрать $\theta$ таким образом, чтобы $gcd(a,\theta)=1$ ^[5] и желательно не слишком низким, чтобы $(a_1 * \theta) \% \alpha \neq v_1 * \theta$ (также во избежание выдачи информации). $\theta = 60$ выполняет свою работу, давая:

$-19-1i,1+38i,3-3i,6-6i,12-12i$ ^[6]

Тогда давайте испачкаем руки. Возьмите сообщение Hello Toptal! . Сначала мы отображаем его в массив байтов в соответствии с ASCII и нашим соглашением об усечении блоков данных:

 01001000 01100101 01101100 01101100 01101111 00100000 01010100 01101111 01110000 01110100 01100001 01101100 00100001 00100001

Поскольку наш блок данных имеет длину 16 бит = 2 байта, а наше сообщение состоит из 13 символов, мы получаем 7 блоков данных по 2 байта каждый, где последний содержит в два раза больше битового представления символа '!' . Давайте зашифруем первый блок шаг за шагом. Обратите особое внимание, потому что биты каждого байта берутся в порядке их значимости.

$м=01001000 01100101$

• Первая часть первого байта: $(0,0,0,1)\стрелка вправо(1,1,1,1,2)\cdot(-19-1i,1+38i,3-3i,6-6i,12 -12i)=15+4i$
• Второй фрагмент первого байта: $(0,0,1,0)\rightarrow(1,1,1,2,1)\cdot(1+38i,3-3i,6-6i,12-12i,15+ 4)=49+9i$
• Первая часть второго байта: $(0,1,0,0)\rightarrow(1,1,2,1,2)\cdot(3-3i,6-6i,12-12i,15+4i,49+ 9i)=106-10i$
• Второй фрагмент второго байта: $(0,1,1,0)\стрелка вправо(1,1,2,2,1)\cdot(6-6i,12-12i,15+4i,49+9i,106- 10i)=252-2i$

Таким образом, мы только что нанесли на карту

«Он» $\Rightarrow(12-12i,15+4i,49+9i,106-10i,252-2i)$

Остальная часть зашифрованного сообщения выглядит следующим образом:

«ll» $\Rightarrow(12-12i,21-2i,61-3i,185-31i,367-59i)$

"o" $\Rightarrow(12-12i,25+33i,65+32i,111+44i,244+124i)$

«Кому» $\Rightarrow(12-12i,9+10i,46+12i,149+5i,277+31i)$

«pt» $\Rightarrow(12-12i,3+16i,46+12i,73+23i,201+49i)$

"al" $\Rightarrow(12-12i,4+54i,44+53i,117+193i,231+389i)$

«!! $\Rightarrow(12-12i,4+54i,32+65i,63+92i,121+247i)$

Теперь для расшифровки имеем $\theta^{-1}=60^{-1}=27+i$:

$($"He" $\Rightarrow)$ $(12-12i,15+4i,49+9i,106-10i,252-2i)*\theta^{-1}\%\alpha=(16,47 ,93 223 527)$

Теперь идет жадный алгоритм:

Во-первых, мы вычитаем каждый содействующий фактор, умноженный на единицу, потому что известно, что они способствовали хотя бы один раз для последнего, что дает:

• Второй фрагмент второго байта:

$T \leftarrow (527-233-93-47-16) = 148$

$(T \geq 223) = (148 \geq 223) = false \Rightarrow b_1=0 ; T \leftarrow (T - 0 * 223) = 148$

$(T \geq 93) = (148 \geq 93) = true \Rightarrow b_2 = 1; T \leftarrow (T - 1 * 93) = 55$

$(T \geq 47) = 55 \geq 47) = true \Rightarrow b_3 = 1; T \leftarrow (T - 1 * 47) = 8$

$(T \geq 16) = 8 \geq 16) = false \Rightarrow b_4 = 0; T \leftarrow (T - 0 * 16) = 8$

Результат: 0110;

Остаток: 8 (добавлено в начало последовательности как новый младший элемент);

Отбросьте 527 из финала текущей последовательности;

• Первая часть второго байта:

$T \leftarrow (233-93-47-16-8) = 59$

$(T \geq 93) = (59 \geq 93) = false \Rightarrow b_1 = 0; Т \leftarrow(T - 0 * 93) = 59$

$(T \geq 47) = (59 \geq 47) = true \Rightarrow b_2 = 1; T \leftarrow (T - 1 * 47) = 12$

$(T \geq 16) = (12 \geq 16) = false \Rightarrow b_3 = 0; Т \leftarrow (T - 0 8 16) = 12$

$(T \geq 8) = (12 \geq 8) = true \Rightarrow b_4 = 1; T \leftarrow (T - 0 * 12) = 4$

Результат: 0101;

Остаток: 4 (добавлено в начало последовательности как новый младший элемент);

Отбросьте 233 из финала текущей последовательности;

• Второй кусок первого байта:

$T \leftarrow (93 - 47 - 16 - 8 - 4) = 18$

$(T \geq 47) = (18 \geq 47) = false \Rightarrow b_1 = 0; T \leftarrow (T - 0 * 47) = 18$

$(T \geq 16) = (18 \geq 16) = true \Rightarrow b_2 = 1; T \leftarrow (T - 1 * 16) = 2$

$(T \geq 8) = (2 \geq 8) = false \Rightarrow b_3 = 0; T \leftarrow (T - 0 * 8) = 2$

$(T \geq 4) = (2 \geq 4) = false \Rightarrow b_4 = 0; T \leftarrow (T - 0 * 4) = 2$

Результат: 0100;

Остаток: 2 (добавлено в начало последовательности как новый младший элемент);

Выпадение 93 из финала текущей последовательности;

• Первая часть первого байта:

$T \leftarrow (47-16-8-4-2) = 17$

$(T \geq 16) = (17 \geq 16) = true \Rightarrow b_1 = 1; T \leftarrow (T - 1 * 16) = 1$

$(T \geq 8) = (1 \geq 8) = false \Rightarrow b_2 = 0; T \leftarrow (T - 0 * 8) = 1$

$(T \geq 4) = (1 \geq 4) = false \Rightarrow b_3 = 0; T \leftarrow (T - 0 * 4) = 1$

$(T \geq 2) = (1 \geq 4) = false \Rightarrow b_4 = 0; T \leftarrow (T - 0 * 2) = 1$

Результат: 1000;

Остаток: 1 (добавляется в начало последовательности как новый младший элемент);

Выбросьте 47 из финала текущей последовательности;

В результате мы восстановили блок данных: «01001000 01100101», содержащий первые два символа «He» нашего сообщения. Мало того, мы также правильно получили нашу супервозрастающую последовательность закрытого ключа $(1,2,4,8,16)$.

Карты других блоков данных идут таким же образом.

Сравнение с основными криптосистемами с открытым ключом

СРВБ это:

1. Полностью бесплатный и общедоступный;

2. Значительно проще и легче понять и реализовать, чем ECC ^[7] ;

3. Изобилие ключей и, следовательно, практически бесплатное, в отличие, например, от RSA, который полагается на простые числа, которые дороги.

Мы уже можем суммировать наиболее вероятные уязвимости. Поскольку SRVB происходит от MH, легко заподозрить, что он будет уязвим для обобщения атаки Shamir или какой-либо другой атаки, которая его сломает. Хотя у автора были основания полагать, что это не так, подтверждения этому пока не сделано (что очень характерно при работе с криптосистемами).

Что дальше?

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

Линейное алгебраическое затемнение

Так получилось, что во время разработки и документирования SRVB Виллаш Боаш придумал еще один подход к улучшению концепции ранцевой криптосистемы с открытым ключом, который не будет подробно объясняться здесь, чтобы эта статья не стала слишком длинной. и утомительно, но вот вкратце. Если вам не удастся это понять, не волнуйтесь, просто следите за выпуском нашей следующей статьи, в которой мы более подробно рассмотрим детали: см. сумму подмножества $y$, скажем, $N$ элементов фактор-кольца $u_i$ (которые, как и прежде, изоморфно соответствуют натуральным числам $v_i$ супервозрастающей последовательности) как произведение вектора-строки этих $u_i$ на вектор-столбец $B$ ( для двоичного) нулей и единиц ^[8] .

$y = \sum_{i=1}^n u_i b_i = (u_1,\cdot\cdot\cdot,u_n)^T\cdot(b_1,\cdot\cdot\cdot,b_n)$=UB,

где $b_i \in {0,1}$

Теперь представьте, что вместо этого вектора из $u_i$ у вас слева $n$ на $N$ (с $n < N$) матрица V, имеющая $v_i$ (целые числа из сверхвозрастающей sequence) как (без ограничения общности) его первая строка, а все остальные элементы заполнены шумом. Обратите внимание, что теперь, умножая V на тот же вектор битов B, вы получаете вектор-столбец W, который имеет $w$ в качестве первой записи и шум в остальных. Теперь возьмите эту матрицу V и умножьте ее на случайную ^[9] n на n матрицу R слева, определяя n на N матрицу P:

П = РВ

Идея состоит в том, что Боб использует P в качестве своего нового открытого ключа. Из-за случайности R вектор

$Y = PB = RV B = RW$

имеет информацию $w$, скрытую шумом в других строках V. Боб также заранее вычисляет и сохраняет вектор-строку S, который удовлетворяет:

$R^TS^T = e_1$

Когда Алиса отправляет Y Бобу, он просто находит SY, потому что:

$SY=S(PB)=S((RV)B)=SRVB= {e_1}^TR^{-1}((RV)B)=$

(пока только определения)

${e_1}^T (VB)={e_1}^TW = w$

(Теперь, используя ассоциативность, чтобы отменить Rs)

and then proceeds as before to extract the vector of $b_i$ from $w$ by means of the greedy algorithm.

So, in one word, the Linear Algebraic Obscuring exploits the associativity of matricial multiplication (the fact that we could expand the terms and then operate their components in a new order provided we that preserved the sequence of all the operands in the sequence) to 'linearly' scramble and then filter (in the encryption and in the decryption respectively) noise to/from $w$. And in limit case $n = 1$, the system elegantly goes back to original to Rocha's approach.

The SRVB Campaign – a prize challenge

As explained before, in accordance to Kerckhoffs' principle, experience shows that antiquity of a publicly known unbroken cryptosystem is the main source of reliability of it, far more than any theoretical argumentation by the own authors, apart from anything else, because definitive proof of efficacy of the algorithms usually are not available.

And here it is our great chance to put these concepts to practice to earn a big money prize: Aware of this fact, we launched the aforementioned campaign, which is basically a crowdfunding for a prize automatically awarded to the first one that manages to break a message. The money is going to be converted to bitcoins in a given wallet whose private key will be SRVB encrypted and published so that anyone able to decipher it can simply take the money anonymously, no questions asked.

Благодарности

This article in particular and the whole SRVB Crypto project in general have been greatly helped by Prof. Charles F. de Barros, assistant professor at the Federal University of Sao Joao Del Rei. Prof. Barros provided us a technical review of the SRVB cryptosystem itself. I judged it necessary to submit to before daring to publish, and that I would certainly take much longer to do by myself.

In addition, I also would like to extend my deep gratitude to professor Adnan Ademovic for his extraordinarily insightful, attentive, and patient work as the editor of this article.

Глоссарий

1. Cryptology/Cryptography: The science/practice of making a message nearly impossible to interpret without a specific set of instructions (in this context, the so-called "key"), thus allowing agents who share these instructions to communicate securely even if tapped by third parties;
2. Steganography: The science/practice of hiding a message within another by means of adding apparently innocuous modifications to the latter;
3. Key generation: the mapping of (expectedly) random inputs into (as random) valid keys;
4. Encryption/Encoding: The easily computable mapping of an easily interpretable message into another that is either hard or impossible to construe, by means of an (as randomly specified) element the one correspondent to the key of a (by Kerckhoffs' principle, publicly known and validated) family of algorithms;
5. Decryption/Decoding: The easily computable mapping that consists of the inverse of the previous, also being definable by an (as randomly specified, and therefore, unknown and hard to be guessed by third parties) element _again, the one correspondent to the key_ of a (by the same principle, usually known) family of algorithms, that thus outputs the original message when input with the encrypted one;
6. Cryptosystem: A triad of the family of encoding algorithms, the family of corresponding decrypting algorithms, and a key generating algorithm;
7. Allies: The agents with whom the communication is intended, and who are expected to act according to the protocol's rules;
8. Enemies/Third Parties: The agents with whom the communication is not intended, but try, nevertheless, to eavesdrop the communication and bypass the security enhanced by the cryptosystem;
9. Secure Channel: Any protocol (procedure) for communication that is easy to use while also effectively preventing third parties to feasibly construe what is meant by its users;
10. Insecure Channel: any channel (ie, protocol or procedure) that, as the name suggests, is not a secure channel;
11. Breaking a Key: The process of discovering a key by means of public pieces of information (like an encrypted message or public key) other than the key itself to be discovered and that was not expected to feasibly allow the discovery of the key. Since the information that results from this process grants the decryption of the messages, this is a particular case of…
12. Breaking/Deciphering a message: Any way to deduce the original content of an encrypted message only by means of the encrypted message itself and other pieces of information that were not expected to suffice for the deduction of the original content;
13. Breaking a Cryptosystem: Discovery of a systematic way to feasibly break whatever message is encrypted by this method under whatever parameter;
14. Kerckhoffs' Principle/Desideratum/Axiom/Law: A cryptologic principle named after the dutch cryptographer Auguste Kerckhoffs, according to which, in order for a cryptosystem to be deemed secure, everything about it except by its (private) keys must be of public knowledge;
15. Key: Secret parametrization of a cryptosystem allowing it to be infeasible to be guessed (and consequently broken) by third parties while also being validated by the community of cryptanalysts (in accordance to Kerckhoffs' principle);
16. Symmetric Cryptosystem: Any cryptosystem on which any parameter for the encoding suffices for easily deducing the parameter for decoding, and, for this reason, must be kept private. One can rephrase it by saying that the encryption and decryption parameters are both equivalent to the key;
17. Asymmetric/Public Key Cryptosystem: Any cryptosystem for which there is a way to express the parameters for the encoding that does not suffice to feasibly deduce the correspondent parameter for decoding, allowing it to be sent to allies through an insecure channel, or even made public, and thus creating a secure channel where there was none;
18. Public Key: A component of an asymmetric cryptosystem that suffices for parameterizing the encryption but does not suffice for feasibly deducing the decryption parameter, ie, the…
19. Private Key: A component of an asymmetric cryptosystem that suffices for parameterizing the decryption and thus must be kept privately and usually also suffices for parameterizing the encryption;

^[1] Note that, here, the phrases decipher or decrypt do not apply, because before a given cryptosystem (with all its components, including its keys) is well defined, one cannot classify a given method of construing the original message from the encrypted one as the intended communication (decryption) or an attack (deciphering).

^[2] Though there are techniques to improve this guessing work, it still remains far more difficult discovering than multiplying them.

^[3] The first inspiration was to look at the tree of the tau conjecture, an infinite tree rooted in the number 1, whose other nodes consist of integers resulting in one binary operation of sum, subtraction, or multiplication between previous nodes, possibly one node operated with itself. The theory's goal relates to the depth, in this tree, in which each integer first appears. It is apparently hard to find large numbers in low branches (even if we relax the need for it), but is it immediate to check if a given sequence of operations indeed produces a given result.

^[4] This is surely not the most natural approach, but by adopting this, one ensures that this byte filling (called padding)…

1. Conceals the size of the padding (differently, for example of ciphertext stealing) and obscures the end of the message, thus rendering chosen-plaintext attacks more difficult;
2. Enhances a distribution of bits as close to uniform as possible;

If the last blocks of every message were known to be systematically biased in a far from uniform distribution, an attacker could exploit this fact to do a statistical cryptanalysis, for any given sample of messages would be statistically more representative than otherwise. In other words, the last blocks being statistically less diverse, they become they become the weakest links of the message.

^[5] Make no mistake: this greatest common divisor is Gaussian, while the previous is real.

^[6] …which is not perfect, because it easily gives away the fact that the last three components are proportional to 1, 2, and 4. But, again, for the sake of simplicity, we will ignore this detail.

^[7] …which is so complex that there are a few notorious cases of failure to implement and maintain protocols based on it.

^[8] Here, we will not adopt Rocha's approach of a multiple linear combinations block, which also allows us to randomly permute the bis to obscure them even more.

^[9] Though not totally random. Its transpose must span the subspace generated by the vector $ e_1 = (1,0,…,0) $.