Алгоритм Кэли – Персера

Алгоритм Кэли-Персера — алгоритм криптографии с открытым ключом , опубликованный в начале 1999 года 16-летней ирландкой Сарой Фланнери и основанный на неопубликованной работе Майкла Персера , основателя Baltimore Technologies , дублинской компании по обеспечению безопасности данных. Фланнери назвал его в честь математика Артура Кэли . С тех пор было обнаружено, что он несовершенен как алгоритм с открытым ключом, но стал предметом значительного внимания средств массовой информации.

История

Во время стажировки в компании Baltimore Technologies Фланнери показали неопубликованную статью Майкла Персера, в которой описывалась новая криптографическая схема с открытым ключом, использующая некоммутативное умножение. Ее попросили написать реализацию этой схемы в системе Mathematica .

Перед этим назначением Фланнери посетил выставку молодых ученых и технологий ESAT 1998 года с проектом, описывающим уже существующие криптографические методы, от шифра Цезаря до RSA . Это принесло ей студенческую награду Intel, которая включала в себя возможность участвовать в Международной выставке науки и техники Intel 1998 года в США. Чувствуя, что ей нужно добавить в свой выставочный проект какую-нибудь оригинальную работу, Фланнери попросила у Майкла Персера разрешения включить работу, основанную на его криптографической схеме.

По совету своего отца-математика Фланнери решила использовать матрицы для реализации схемы Персера, поскольку умножение матриц обладает необходимым свойством некоммутативности. Поскольку результирующий алгоритм будет зависеть от умножения, он будет намного быстрее, чем алгоритм RSA, который использует экспоненциальный шаг. Для своего проекта Intel Science Fair Фланнери подготовила демонстрацию, в которой один и тот же открытый текст был зашифрован с использованием как RSA, так и ее нового алгоритма Кэли-Персера, и это действительно показало значительное улучшение времени.

Вернувшись на выставку молодых ученых и технологий ESAT в 1999 году, Фланнери формализовал среду выполнения Кэли-Персера и проанализировал множество известных атак, ни одна из которых не была признана эффективной.

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

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

Обзор

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

Генерация ключей

Как и RSA, Кэли-Персер начинает с генерации двух больших простых чисел p и q и их произведения n , полупростого числа . Далее рассмотрим GL (2, n ), общую линейную группу матриц 2×2 с целыми элементами и модулярной арифметикой по модулю n . Например, если n = 5, мы могли бы написать:

${\begin{bmatrix}0&1\\2&3\end{bmatrix}}+{\begin{bmatrix}1&2\\3&4\end{bmatrix}}={\begin{bmatrix}1&3\\5&7\end{bmatrix}}\equiv {\begin{bmatrix}1&3\\0&2\end{bmatrix}}$

${\begin{bmatrix}0&1\\2&3\end{bmatrix}}{\begin{bmatrix}1&2\\3&4\end{bmatrix}}={\begin{bmatrix}3&4\\11&16\end{bmatrix}}\equiv {\begin{bmatrix}3&4\\1&1\end{bmatrix}}$

Эта группа выбрана потому, что она имеет большой порядок (при больших полупростых n ), равный ( p ² −1)( п ² - п )( q ² −1)( q ² - q ).

Позволять $\chi$ и $\alpha$ — две такие матрицы из GL(2, n ), выбранные так, что $\chi \alpha \not =\alpha \chi$. Выберите какое-нибудь натуральное число r и вычислите:

$\beta =\chi ^{-1}\alpha ^{-1}\chi ,$

$\gamma =\chi ^{r}.$

Открытый ключ $n$, $\alpha$, $\beta$, и $\gamma$. Закрытый ключ $\chi$.

Шифрование

Отправитель начинает с генерации случайного натурального числа s и вычисления:

$\delta =\gamma ^{s}$

$\epsilon =\delta ^{-1}\alpha \delta$

$\kappa =\delta ^{-1}\beta \delta$

Затем, чтобы зашифровать сообщение, каждый блок сообщения кодируется как число (как в RSA), и они помещаются по четыре одновременно как элементы матрицы открытого текста. $\mu$. Каждый $\mu$ шифруется с помощью:

$\mu '=\kappa \mu \kappa .$

Затем $\mu '$ и $\epsilon$ отправляются получателю.

Расшифровка

Получатель восстанавливает исходную матрицу открытого текста. $\mu$ с помощью:

$\lambda =\chi ^{-1}\epsilon \chi ,$

$\mu =\lambda \mu '\lambda .$

Безопасность

Восстановление закрытого ключа $\chi$ от $\gamma$ вычислительно невозможно, по крайней мере так же сложно, как найти квадратные корни по модулю n (см. квадратичный вычет ). Его можно было восстановить из $\alpha$ и $\beta$ если система $\chi \beta =\alpha ^{-1}\chi$ можно решить, но число решений этой системы велико, пока элементы в группе имеют большой порядок, который можно гарантировать почти для каждого элемента.

Однако систему можно сломать, если найти несколько $\chi '$ из $\chi$ решив для $d$ в следующем сопоставлении:

$d\left(\beta -\alpha ^{-1}\right)\equiv \left(\alpha ^{-1}\gamma -\gamma \beta \right){\pmod {n}}$

Заметим, что решение существует, если для некоторого $i,j\in \left|\gamma \right|$ и $x,y\in \mathbb {Z} _{n}$

$x\left(\beta _{ij}^{-1}-\alpha _{ij}\right)\equiv y{\pmod {n}}.$

Если $d$ известно, $d\mathrm {I} +\gamma =\chi '$ - кратное $\chi$. Любое кратное $\chi$ урожайность $\lambda =\kappa ^{-1}=v^{-1}\chi ^{-1}\epsilon v\chi$. Это представляет собой фатальную слабость системы, с которой еще не удалось примириться.

Этот недостаток не исключает использования алгоритма как смешанного алгоритма с закрытым и открытым ключом, если отправитель передает $\epsilon$ тайно, но этот подход не дает преимуществ перед обычным подходом, заключающимся в передаче симметричного ключа шифрования с использованием схемы шифрования с открытым ключом и последующим переключением на симметричное шифрование, которое быстрее, чем Кэли-Персер.

См. также

• Некоммутативная криптография

Ссылки

• Сара Флэннери и Дэвид Флэннери. В коде: математическое путешествие . ISBN   0-7611-2384-9