LUC

(перенаправлено с «Luc»)

LUC — криптосистема с открытым ключом, разработанная исследователем из Новой Зеландии — Питером Смитом. Так же как RSA, эта система поддерживает шифрование и цифровую подпись. Отличительной чертой системы является использование последовательностей Люка(Lucas) вместо возведения в степень[1].

Описание алгоритма

править

Введение

править

Как уже упоминалось ранее, в системе LUC используются последовательности Люка. Они задаются следующими рекурентными соотношениями:

 
 
 
 
 
 
 
 
Где P,Q — целые неотрицательные числа.

В основном используется последовательность  . Поэтому далее будем рассматривать только её. Однако все сформулированные свойства будут справедливы и для  .

Пример последовательностей Люка для P = 3, Q = 1
     
0 2 0
1 3 1
2 7 3
3 18 8
4 47 21
5 123 55
6 322 144
7 843 377
8 2207 987
9 5778 2584
10 15127 6765
11 39603 17711
12 103682 46368
13 271443 121393
14 710647 317811
15 1860498 832040
16 4870847 2178309
17 12752043 5702887
18 33385282 14930352
19 87403803 39088169
20 228826127 102334155
21 599074578 267914296
22 1568397607 701408733
23 4106118243 1836311903
24 10749957122 4807526976

Из таблицы видно, что элементы последовательностей Люка растут очень быстро. Поэтому использовать их в виде (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

править

Для доказательства необходимо проверить следующее равенство:

 , где
 

Сначала сформулируем две леммы.

  •  
  • Для простых  ,  ,   и любых целых   верно:
 
 
Оставим эту лемму без доказательства[2].

Используя эти две леммы, определение последовательностей Люка и (1.4) получаем:

из уравнения (1.4)
 
по определению e и d:
 
по определению (1.2), полагая что Q = 1:
 
из леммы 1:
 
так как  
 

из Леммы 2:

 

То есть верно равенство:  

Алгоритм LUCDIF

править

Алгоритм LUCDIF является комбинацией алгоритма LUC и протокола Диффи-Хеллмана. Основным назначением этого алгоритма является разделение двумя сторонами общего секретного ключа. Реализуется это следующим образом:

  • Сначала Алиса выбирает простое число p, число g, такое что g < p и какое-то секретное число a.
  • Затем Алиса вычисляет число:
 
  • После этого Алиса отправляет Бобу сообщение
 
  • Боб выбирает своё секретное число b. Используя его, он во-первых, получает общий секретный ключ:
 
  • И затем отправляет Алисе сообщение:
 
  • Алиса, в свою очередь, тоже вычисляет общий секретный ключ:
 

Из свойств последовательностей Люка, следует, что выражения полученные в конечном итоге Алисой и Бобом будут равны. Следовательно, Алиса и Боб будут иметь общий секретный ключ[3].

Алгоритм LUCELG

править

Алгоритм LUCELG строится на Схеме Эль-Гамаля и последовательностях Люка. Схема Эль-Гамаля используется для шифрования/расшифрования и генерации цифровой подписи. Рассмотрим работу этого алгоритма при шифровании сообщения.

1) Генерация пары открытого и закрытого ключа:

  • Выбираем простое число P
  • Затем выбираем λ такое, что для любых t>1 и делящих (p+1) верно:
 
  • Выбираем случайное число x, которое и будет секретным ключом.
  • Вычисляем открытый ключ следующим образом:
 

2) Шифрование сообщения:

  • Сначала выбирается случайное число k, такое что 1 ≤ k ≤ p — 1.
  • После этого, используя открытый ключ y, вычисляется параметр G:
 
  • Первая часть криптограммы:
 
  • Вторая часть:
 

3) Дешифровка сообщения:

  • Используя закрытый ключ вычисляется G:
 
  • Далее, получая обратный элемент к G по модулю p, получаем исходное сообщение:
 

Примечания

править
  1. Peter Smith. Luc Public-Key Encryption // Dr. Dobb's journal. — January 1993. Архивировано 11 ноября 2014 года.
  2. Paulo Ribenboim. The little book of bigger primes. — Springer-Verlag New York. — 2004.
  3. Peter Smith. Cryptography Without Exponentiation // Dr. Dobb's journal. — April 01, 1994. Архивировано 7 августа 2016 года.

Литература

править
  • 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