Алгоритм шифрования Cayley–Purser: история и анализ

Введение

Алгоритм криптографии с открытым ключом 1999 года

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

История

Во время стажировки в Baltimore Technologies Фланнери была ознакомлена с неопубликованной работой Майкла Пёрсера, в которой описывалась новая криптографическая схема с открытым ключом, использующая некоммутативное умножение. Ей было предложено написать реализацию этой схемы на Mathematica. До этого Фланнери участвовала в выставке молодых ученых и технологий ESAT 1998 года с проектом, демонстрирующим уже существующие криптографические методы – от шифра Цезаря до RSA. Это принесло ей награду Intel Student Award, которая включала возможность участия в Международной научной и инженерной ярмарке Intel 1998 года в Соединенных Штатах. Почувствовав необходимость в оригинальной работе для дополнения своего выставочного проекта, Фланнери попросила Майкла Пёрсера разрешения включить в него материалы, основанные на его криптографической схеме. По совету своего отца-математика, Фланнери решила использовать матрицы для реализации схемы Пёрсера, поскольку умножение матриц обладает необходимым свойством – некоммутативностью. Поскольку полученный алгоритм будет основан на умножении, он должен был быть значительно быстрее алгоритма RSA, использующего экспоненциальную операцию. Для своего проекта Intel Science Fair Фланнери подготовила демонстрацию, в которой один и тот же открытый текст шифровался как с помощью RSA, так и с помощью ее нового алгоритма Cayley–Purser, и действительно показала существенное увеличение скорости. Вернувшись на выставку ESAT Young Scientist and Technology Exhibition в 1999 году, Фланнери формализовала время работы алгоритма Cayley–Purser и проанализировала различные известные атаки, ни одна из которых не оказалась эффективной. Фланнери не заявляла, что алгоритм Cayley–Purser заменит RSA, понимая, что любая новая криптографическая система должна выдержать проверку временем, прежде чем ее можно будет признать безопасной. Однако СМИ проявили меньше осторожности, и когда она получила первую премию на выставке ESAT, газеты по всему миру сообщили о том, что юный гений совершил революцию в криптографии. Вскоре после этого была обнаружена атака на алгоритм, но она проанализировала ее и включила в качестве приложения в последующие конкурсы, в том числе в общеевропейский конкурс, где она завоевала престижную награду.

During a work experience placement with Baltimore Technologies, Flannery was shown an unpublished paper by Michael Purser which outlined a new public key cryptographic scheme using non commutative multiplication. She was asked to write an implementation of this scheme in Mathematica. Before this placement, Flannery had attended the 1998 ESAT Young Scientist and Technology Exhibition with a project describing already existing cryptographic techniques from the Caesar cipher to RSA. This had won her the Intel Student Award which included the opportunity to compete in the 1998 Intel International Science and Engineering Fair in the United States. Feeling that she needed some original work to add to her exhibition project, Flannery asked Michael Purser for permission to include work based on his cryptographic scheme. On advice from her mathematician father, Flannery decided to use matrices to implement Purser's scheme as matrix multiplication has the necessary property of being non commutative. As the resulting algorithm would depend on multiplication it would be a great deal faster than the RSA algorithm which uses an exponential step. For her Intel Science Fair project Flannery prepared a demonstration where the same plaintext was enciphered using both RSA and her new Cayley–Purser algorithm and it did indeed show a significant time improvement. Returning to the ESAT Young Scientist and Technology Exhibition in 1999, Flannery formalised Cayley Purser's runtime and analyzed a variety of known attacks, none of which were determined to be effective. Flannery did not make any claims that the Cayley–Purser algorithm would replace RSA, knowing that any new cryptographic system would need to stand the test of time before it could be acknowledged as a secure system. The media were not so circumspect however and when she received first prize at the ESAT exhibition, newspapers around the world reported the story that a young girl genius had revolutionised cryptography. In fact an attack on the algorithm was discovered shortly afterwards but she analyzed it and included it as an appendix in later competitions, including a Europe wide competition in which she won a major award.

Обзор

Нотация, используемая в данном обсуждении, соответствует нотации, представленной в оригинальной работе Фланнери.

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

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

Эта группа выбрана, поскольку она имеет большой порядок (для большого полупростого n), равный (p²−1)(p²−p)(q²−1)(q²−q). Пусть и – две такие матрицы из GL(2,n), выбранные таким образом, что Выберите некоторое натуральное число r и вычислите:

Публичный ключ – это , , , а приватный ключ – это .