LUC — криптосистема с открытым ключом, разработанная исследователем из Новой Зеландии — Питером Смитом. Так же как RSA, эта система поддерживает шифрование и цифровую подпись. Отличительной чертой системы является использование последовательностей Люка(Lucas) вместо возведения в степень.
Описание алгоритма
Введение Как уже упоминалось ранее, в системе LUC используются последовательности Люка. Они задаются следующими рекурентными соотношениями:
Где P,Q — целые неотрицательные числа.
В основном используется последовательность . Поэтому далее будем рассматривать только её. Однако все сформулированные свойства будут справедливы и для .
Пример последовательностей Люка для P = 3, Q = 1 020131273318844721512355632214478433778220798795778258410151276765113960317711121036824636813271443121393147106473178111518604988320401648708472178309171275204357028871833385282149303521987403803390881692022882612710233415521599074578267914296221568397607701408733234106118243183631190324107499571224807526976
Из таблицы видно, что элементы последовательностей Люка растут очень быстро. Поэтому использовать их в виде (1.1) затруднительно. Эту проблему решает следующее свойство:
Так же используется ещё одно важное утверждение:
Использование последовательностей Люка в криптографии Допустим, что существуют такие и , что
Тогда из (1.3):
А из (1.4):
Сначала от символьного сообщения берётся хеш-функция, которая возвращает цифровое значение X. В качестве функции шифрования используется:
А для дешифрования:
В этом алгоритме шифрования открытым ключом будет являться пара {e,N}, а закрытым {d,N}.
Генерация ключа Сначала выбираются два простых числа p и q. Вычисляется их произведение Выбирается число e, взаимнопростое с числом (p-1)(q-1)(p+1)(q+1):
Вычисляется D: , где P — наше сообщение Вычисляются следующие символы Лежандра и Находится наименьшее общее кратное
Вычисляется d
открытый ключ:
закрытый ключ:
Шифрование и дешифрование сообщения 1) Шифрование сообщения P, при условии P < N :
2) Дешифрование сообщения:
Пример Рассмотрим криптосистему LUC на конкретном примере:
1) Выбираем два простых числа:
2) Вычисляем N:
3) Вычисляем открытый ключ e из уравнения :
4) Шифровать будем следующее сообщение P = 11111, далее вычисляем символ Лежандра : параметр :
Используя критерий Эйлера находим:
5) Теперь вычисляем функцию S(N):
6) Закрытый ключ:
7) Зашифрованное сообщение:
8)Дешифрованное сообщение:
Некоторые сложности При использовании криптосистемы LUC возникают некоторые вычислительные трудности. Во-первых, вычисление больших чисел Люка может оказаться довольно сложной задачей, так как они задаются рекуррентно, а следовательно придётся перебрать все предыдущие числа. Однако, эту проблему решают следующие свойства последовательностей Люка:
Используя эти свойства можно довольно быстро получить нужное число, раскладывая номер элемента последовательности по степеням двойки. Этот алгоритм аналогичен алгоритму быстрого возведения в степень, который используется в криптосистеме RSA. Во-вторых, приватный ключ d зависит от исходного сообщения P. Для каждого e существует четыре возможных значений функции S(N):
И следовательно существует четыре возможных значений закрытого ключа d:
Получая сообщение С, зашифрованное открытым ключом e, первым делом считаем символы Лежандра:
По их значениям определяем какой из четырёх закрытых ключей d нужно использовать для дешифровки.
Корректность схемы LUC Для доказательства необходимо проверить следующее равенство: , где
Сначала сформулируем две леммы.
Для простых , , и любых целых верно:
Оставим эту лемму без доказательства .
Используя эти две леммы, определение последовательностей Люка и (1.4) получаем: из уравнения (1.4)
по определению e и d:
по определению (1.2), полагая что Q = 1:
из леммы 1:
так как
из Леммы 2:
То есть верно равенство:
Алгоритм LUCDIF Алгоритм LUCDIF является комбинацией алгоритма LUC и протокола Диффи-Хеллмана. Основным назначением этого алгоритма является разделение двумя сторонами общего секретного ключа. Реализуется это следующим образом: Сначала Алиса выбирает простое число p, число g, такое что g < p и какое-то секретное число a. Затем Алиса вычисляет число:
После этого Алиса отправляет Бобу сообщение
Боб выбирает своё секретное число b. Используя его, он во-первых, получает общий секретный ключ:
И затем отправляет Алисе сообщение:
Алиса, в свою очередь, тоже вычисляет общий секретный ключ:
Из свойств последовательностей Люка, следует, что выражения полученные в конечном итоге Алисой и Бобом будут равны. Следовательно, Алиса и Боб будут иметь общий секретный ключ.
Алгоритм LUCELG Алгоритм LUCELG строится на Схеме Эль-Гамаля и последовательностях Люка. Схема Эль-Гамаля используется для шифрования/расшифрования и генерации цифровой подписи. Рассмотрим работу этого алгоритма при шифровании сообщения. 1) Генерация пары открытого и закрытого ключа: Выбираем простое число P Затем выбираем λ такое, что для любых t>1 и делящих (p+1) верно:
Выбираем случайное число x, которое и будет секретным ключом. Вычисляем открытый ключ следующим образом:
2) Шифрование сообщения: Сначала выбирается случайное число k, такое что 1 ≤ k ≤ p — 1. После этого, используя открытый ключ y, вычисляется параметр G:
Первая часть криптограммы:
Вторая часть:
3) Дешифровка сообщения: Используя закрытый ключ вычисляется G:
Далее, получая обратный элемент к G по модулю p, получаем исходное сообщение:
Примечания
Литература William Stallings, Network and Internetwork Security Principles and Practice, 1995 — ISBN 0-02-415438-0. Peter Smith, LUC Public-Key Encryption : Dr. Dobb’s journal Jan 1993 pp.44-49. Брюс Шнайер, Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си, 2000 — М : Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4. Daniel Bleichenbache, Wieb Bosma, Arjen K.Lenstra, Some Remarks on Lucas-Based Cryptosystems
Категория:Криптография с открытым ключом Категория:Шифры Категория:Электронная подпись