Перейти к содержанию
🌲 С 2026 годом! 🥂
Пусть он будет победным! 🌟

LUC

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис
(перенаправлено с «Luc»)

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

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

Введение

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

[math]\displaystyle{ U_{n+2}(P,Q)=P\cdot U_{n+1}(P,Q) - Q\cdot U_n(P,Q),\,n\geq 0 \quad (1.1) }[/math]
[math]\displaystyle{ \quad }[/math]
[math]\displaystyle{ V_{n+2}(P,Q)=P\cdot V_{n+1}(P,Q) - Q\cdot V_n(P,Q),\,n\geq 0 \quad (1.2) }[/math]
[math]\displaystyle{ \quad }[/math]
[math]\displaystyle{ U_0(P,Q) = 0,\quad U_1(P,Q)=1 }[/math]
[math]\displaystyle{ \quad }[/math]
[math]\displaystyle{ V_0(P,Q) = 2,\quad V_1(P,Q)=P }[/math]
[math]\displaystyle{ \quad }[/math]
Где P,Q — целые неотрицательные числа.

В основном используется последовательность [math]\displaystyle{ V_{n}(P,Q) }[/math]. Поэтому далее будем рассматривать только её. Однако все сформулированные свойства будут справедливы и для [math]\displaystyle{ U_{n}(P,Q) }[/math].

Пример последовательностей Люка для P = 3, Q = 1
[math]\displaystyle{ n }[/math] [math]\displaystyle{ V_{n}(3,1) }[/math] [math]\displaystyle{ U_{n}(3,1) }[/math]
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) затруднительно. Эту проблему решает следующее свойство:

  • [math]\displaystyle{ V_{n}(P\mod N, Q\mod N) = V_{n}(P,Q)\mod N \quad N\gt 2 \quad(1.3) }[/math]
Доказательство
Для доказательства воспользуемся методом математической индукции по n
  • База индукции:
1) для n = 0 - выражение (1.3) верно, т.к. по определению (1.1):
[math]\displaystyle{ V_{0}(P\mod N, Q\mod N) = 2 }[/math]
[math]\displaystyle{ (V_{0}(P,Q))\mod N = 2 }[/math]
2) для n = 1 аналогично:
[math]\displaystyle{ V_{1}(P\mod N, Q\mod N) = P\mod N }[/math]
[math]\displaystyle{ (V_{1}(P,Q))\mod N = P\mod N }[/math]
  • Предположение индукции.Пусть (1.3) верно для всех значений k≤n-1 :
[math]\displaystyle{ V_{k}(P\mod N, Q\mod N) = (V_{k}(P,Q))\mod N }[/math]
  • Шаг индукции. Докажем, что (1.3) выполняется и для k = n:
1) по определению последовательности Люка:
[math]\displaystyle{ (V_{n}(P,Q))\mod N = (P \cdot V_{n-1}(P,Q) - Q \cdot V_{n-2}(P,Q))\mod N = (P\mod N)\cdot(V_{n-1}(P,Q))\mod N - }[/math]
[math]\displaystyle{ (Q\mod N)\cdot(V_{n-2}(P,Q))\mod N }[/math]
2) Воспользуемся предположением индукции:
[math]\displaystyle{ (V_{n}(P,Q))\mod N = (P\mod N)\cdot(V_{n-1}(P\mod N,Q\mod N)) - (Q\mod N)\cdot(V_{n-2}(P\mod N,Q\mod N)) }[/math]
В 2) получили определение последовательности Люка. А следовательно (1.3) верно для k = n. Свойство доказано.

Так же используется ещё одно важное утверждение:

  • [math]\displaystyle{ V_{n}(V_{k}(P,Q),Q^{k}) = V_{nk}(P,Q) \quad(1.4) }[/math]
Вывод
[math]\displaystyle{ X^{2} - P \cdot X + Q = 0 \quad (0) }[/math]
[math]\displaystyle{ V_n(P,Q) = \alpha^n + \beta^n \quad (1) }[/math]
[math]\displaystyle{ P = \alpha + \beta \quad (2) }[/math]
[math]\displaystyle{ Q = \alpha \cdot \beta \quad (3) }[/math]
  • Теперь подставим в характеристическое уравнение [math]\displaystyle{ (0) }[/math] следующие выражения [math]\displaystyle{ P'=V_{k}(P,Q), Q'=Q^{k} }[/math] :
[math]\displaystyle{ X^{2} - V_{k}(P,Q) \cdot X + Q^{k} = 0 \quad (4) }[/math]
  • Выведем формулы аналогичные формулам [math]\displaystyle{ (1) - (3) }[/math], полученным для уравнения [math]\displaystyle{ (0) }[/math]:
[math]\displaystyle{ \alpha^{'} + \beta^{'} = V_{k}(P,Q) \quad (5) }[/math]
[math]\displaystyle{ \alpha^{'} \cdot \beta^{'} = Q^{k} \quad (6) }[/math]
  • По определению последовательностей Люка:
[math]\displaystyle{ V_{n}(P,Q) = \alpha^{n} + \beta^{n} \quad }[/math] и следовательно:
[math]\displaystyle{ V_{n}(V_{k}(P,Q),Q^{k}) = (\alpha')^{n} + (\beta')^{n} \quad (7) }[/math]
  • Из (7) и (5) для [math]\displaystyle{ V_{k}(P,Q) }[/math] получим:
[math]\displaystyle{ V_{k}(P,Q) = \alpha^{k} + \beta^{k} = \alpha' + \beta' \quad (8) }[/math]
  • Аналогично для [math]\displaystyle{ Q^{k} \quad }[/math] :
[math]\displaystyle{ Q^{k} = \alpha^{k} \cdot \beta^{k} = \alpha' \cdot \beta' \quad (9) }[/math]
  • Из (8) и (9) получаем:
[math]\displaystyle{ \alpha^{k} = \alpha', \beta^{k} = \beta' \quad (10) }[/math]
  • Подставим (10) в (7):
[math]\displaystyle{ V_{n}(V_{k}(P,Q),Q^{k}) = (\alpha')^{n} + (\beta')^{n} = (\alpha^{k})^{n} + (\beta^{k})^{n} = \alpha^{kn} + \beta^{kn} = V_{nk}(P,Q) }[/math]

Использование последовательностей Люка в криптографии

Допустим, что существуют такие [math]\displaystyle{ e }[/math] и [math]\displaystyle{ d }[/math] , что

[math]\displaystyle{ V_{de}(X,1)=X\mod N }[/math]

Тогда из (1.3):

[math]\displaystyle{ V_{de}(X\mod N,1) = V_{de}(X,1)\mod N = X\mod N }[/math]

А из (1.4):

[math]\displaystyle{ V_{de}(X\mod N,1) = V_{d}(V_{e}(X\mod N,1),1)=X\mod N }[/math]

Сначала от символьного сообщения берётся хеш-функция, которая возвращает цифровое значение X. В качестве функции шифрования используется:

[math]\displaystyle{ Y = V_{e}(X\mod N,1) }[/math]

А для дешифрования:

[math]\displaystyle{ V_{d}(Y\mod N,1) = X\mod N }[/math]

В этом алгоритме шифрования открытым ключом будет являться пара {e,N}, а закрытым {d,N}.

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

  • Сначала выбираются два простых числа p и q.
  • Вычисляется их произведение [math]\displaystyle{ \textstyle N = p \cdot q }[/math]
  • Выбирается число e, взаимнопростое с числом (p-1)(q-1)(p+1)(q+1):
[math]\displaystyle{ gcd[(p-1) \cdot (q-1) \cdot (p+1) \cdot (q+1),e ] = 1 }[/math]
  • Вычисляется D:
[math]\displaystyle{ D = P^{2}-4 }[/math],
где P — наше сообщение
  • Вычисляются следующие символы Лежандра [math]\displaystyle{ \textstyle ( \frac{D}{p} ) }[/math] и [math]\displaystyle{ \textstyle ( \frac{D}{q} ) }[/math]
  • Находится наименьшее общее кратное
[math]\displaystyle{ \textstyle S(N) = lcm[(p - (\frac{D}{p})),(q - (\frac{D}{q})) ] }[/math]
  • Вычисляется d
[math]\displaystyle{ d = e^{-1}\mod S(N) }[/math]
  • открытый ключ:
[math]\displaystyle{ KU = (e,N) }[/math]
  • закрытый ключ:
[math]\displaystyle{ KR = (d,N) }[/math]

Шифрование и дешифрование сообщения

1) Шифрование сообщения P, при условии P < N :

[math]\displaystyle{ C = V_{e}(P,1)\mod N }[/math]

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

[math]\displaystyle{ P = V_{d}(C,1)\mod N }[/math]

Пример

Рассмотрим криптосистему LUC на конкретном примере:

1) Выбираем два простых числа:
[math]\displaystyle{ p = 1949, \quad q = 2089 }[/math]
2) Вычисляем N:
[math]\displaystyle{ N = p \cdot q = 4071461 }[/math]
3) Вычисляем открытый ключ e из уравнения [math]\displaystyle{ gcd[(p-1) \cdot (p+1) \cdot (q-1) \cdot (q+1),\quad e ] = 1 }[/math] :
[math]\displaystyle{ gcd[1948 \cdot 2088 \cdot 1950 \cdot 2090,\quad e ] = 1 \quad =\gt \quad e = 1103 }[/math]
4) Шифровать будем следующее сообщение P = 11111, далее вычисляем символ Лежандра [math]\displaystyle{ \textstyle ( \frac{D}{p} ) }[/math] :
  • параметр [math]\displaystyle{ D }[/math]:
[math]\displaystyle{ D^{2} = P^{2} - 4 = 123454317 }[/math]
[math]\displaystyle{ \textstyle ( \frac{D}{p} ) = -1 }[/math]
[math]\displaystyle{ \textstyle ( \frac{D}{q} ) = -1 }[/math]
5) Теперь вычисляем функцию S(N):
[math]\displaystyle{ S(N) = lcm[(1949 + 1),(2089 + 1)] = 407550 }[/math]
6) Закрытый ключ:
[math]\displaystyle{ d = e^{-1}\mod 407550 = 24017 }[/math]
7) Зашифрованное сообщение:
[math]\displaystyle{ C = V_{1103}(11111,1)\mod 4071461 = 3975392 }[/math]
8)Дешифрованное сообщение:
[math]\displaystyle{ P = V_{24017}(3975392,1)\mod 4071461= 11111 }[/math]

Некоторые сложности

При использовании криптосистемы LUC возникают некоторые вычислительные трудности.

  • Во-первых, вычисление больших чисел Люка может оказаться довольно сложной задачей, так как они задаются рекурентно, а следовательно придётся перебрать все предыдуще числа. Однако, эту проблему решают следующие свойства последовательностей Люка:
[math]\displaystyle{ V_{2n}(P,Q) = [V_{n}(P,Q)]^{2} - 2\cdot Q^{n} }[/math]
[math]\displaystyle{ V_{n+m}(P,Q) = V_{n}(P,Q)\cdot V_{m}(P,Q) - Q^{n}\cdot V_{n-m} }[/math]
Используя эти свойства можно довольно быстро получить нужное число, раскладывая номер элемента последовательности по степеням двойки. Этот алгоритм аналогичен алгоритму быстрого возведения в степень, который используется в криптосистеме RSA.
  • Во-вторых, приватный ключ d зависит от исходного сообщения P.
Для каждого e существует четыре возможных значений функции S(N):
[math]\displaystyle{ lcm[(p+1),(q+1)] }[/math]
[math]\displaystyle{ lcm[(p+1),(q-1)] }[/math]
[math]\displaystyle{ lcm[(p-1),(q+1)] }[/math]
[math]\displaystyle{ lcm[(p-1),(q-1)] }[/math]
И следовательно существует четыре возможных значений закрытого ключа d:
[math]\displaystyle{ d = e^{-1}\mod (lcm [(p+1),(q+1)]) }[/math]
[math]\displaystyle{ d = e^{-1}\mod (lcm [(p+1),(q-1)]) }[/math]
[math]\displaystyle{ d = e^{-1}\mod (lcm [(p-1),(q+1)]) }[/math]
[math]\displaystyle{ d = e^{-1}\mod (lcm [(p-1),(q-1)]) }[/math]
Получая сообщение С, зашифрованное открытым ключом e, первым делом считаем символы Лежандра:
[math]\displaystyle{ \textstyle ( \frac{C^{2}-4}{p} ), ( \frac{C^{2}-4}{q} ) }[/math]
По их значениям определяем какой из четырёх закрытых ключей d нужно использовать для дешифровки.

Корректность схемы LUC

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

[math]\displaystyle{ V_{d}[V_{e}(P,1),1] = P \quad }[/math], где
[math]\displaystyle{ d = e^{-1}\mod S(N), \quad gcd[(p-1) \cdot (p+1) \cdot (q-1) \cdot (q+1), e] = 1, \quad N = p \cdot q }[/math]

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

  • [math]\displaystyle{ \quad 2\cdot Q\cdot V_{n-m}(P,Q) = V_{n}(P,Q)\cdot V_{m}(P,Q) - D\cdot U_{n}(P,Q)\cdot U_{m}(P,Q) }[/math]
Доказательство

1) Из свойств последовательностей Люка имеем:

[math]\displaystyle{ U_n(P,Q) = \frac{\alpha^n - \beta^n}{\alpha - \beta}, \quad V_n(P,Q) = \alpha^n + \beta^n, \quad P = \alpha + \beta, \quad Q = \alpha \cdot \beta }[/math]

2) Подставим эти формулы в условие леммы:

[math]\displaystyle{ 2\cdot Q\cdot V_{n-m}(P,Q) = (\alpha^n + \beta^n)\cdot (\alpha^m + \beta^m) - (\alpha - \beta)^{2} \cdot \frac{\alpha^n - \beta^n}{\alpha - \beta} \cdot \frac{\alpha^m - \beta^m}{\alpha - \beta} }[/math]
[math]\displaystyle{ = (\alpha^n + \beta^n)\cdot (\alpha^m + \beta^m) - (\alpha^n - \beta^n)\cdot (\alpha^m - \beta^m) }[/math]
[math]\displaystyle{ = (\alpha^{n+m} + \alpha^n \cdot \beta^m + \alpha^m \cdot \beta^n + \beta^{n+m}) - (\alpha^{n+m} - \alpha^n \cdot \beta^m - \alpha^m \cdot \beta^n + \beta^{n+m}) }[/math]
[math]\displaystyle{ = 2\cdot \alpha^n \cdot \beta^m + 2\cdot \alpha^m \cdot \beta^n }[/math]
[math]\displaystyle{ = \alpha^m \cdot \beta^m \cdot (\alpha^{n-m} + \beta^{n-m}) }[/math]
[math]\displaystyle{ = 2\cdot Q^m\cdot V_{n-m}(P,Q) }[/math]
  • Для простых [math]\displaystyle{ p,q\quad }[/math], [math]\displaystyle{ N = p\cdot q\quad }[/math], [math]\displaystyle{ \quad S(N)\quad }[/math] и любых целых [math]\displaystyle{ \quad k \quad }[/math] верно:
[math]\displaystyle{ U_{kS(N)}(P,1) = 0 \mod N }[/math]
[math]\displaystyle{ V_{kS(N)}(P,1) = 2 \mod N }[/math]
Оставим эту лемму без доказательства[2].

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

из уравнения (1.4)
[math]\displaystyle{ V_{d}(V_{e}(P,1),1) = V_{de}(P,1) \quad }[/math]
по определению e и d:
[math]\displaystyle{ = V_{kS(N)+1}(P,1) \quad }[/math]
по определению (1.2), полагая что Q = 1:
[math]\displaystyle{ = P\cdot V_{kS(N)}(P,1) - V_{kS(N)-1}(P,1) \quad }[/math]
из леммы 1:
[math]\displaystyle{ = P\cdot V_{kS(N)}(P,1) - \frac{1}{2}[V_{kS(N)}(P,1)\cdot V_{1}(P,1) - D\cdot U_{kS(N)}(P,1)\cdot U_{1}(P,1) ] }[/math]
так как [math]\displaystyle{ \quad V_{1}(P,1) = P,\quad U_{1}(P,1) = 1 }[/math]
[math]\displaystyle{ = P\cdot V_{kS(N)}(P,1) - \frac{1}{2}[P\cdot V_{kS(N)}(P,1) - D\cdot U_{kS(N)}(P,1)] \quad }[/math]

из Леммы 2:

[math]\displaystyle{ = 2P - \frac{1}{2}[2P - 0] = P \mod N }[/math]

То есть верно равенство: [math]\displaystyle{ V_{d}(V_{e}(P,1),1) = P }[/math]

Алгоритм LUCDIF

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

  • Сначала Алиса выбирает простое число p, число g, такое что g < p и какое-то секретное число a.
  • Затем Алиса вычисляет число:
[math]\displaystyle{ V_{a}(g,1) \mod p }[/math]
  • После этого Алиса отправляет Бобу сообщение
[math]\displaystyle{ (V_{a}(g,1) \mod p,\quad p,\quad g ) }[/math]
  • Боб выбирает своё секретное число b. Используя его, он во-первых, получает общий секретный ключ:
[math]\displaystyle{ V_{b}(V_{a}(g,1)) \mod p }[/math]
  • И затем отправляет Алисе сообщение:
[math]\displaystyle{ V_{b}(g,1) \mod p }[/math]
  • Алиса, в свою очередь, тоже вычисляет общий секретный ключ:
[math]\displaystyle{ V_{a}(V_{b}(g,1)) \mod p }[/math]

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

Алгоритм LUCELG

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

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

  • Выбираем простое число P
  • Затем выбираем λ такое, что для любых t>1 и делящих (p+1) верно:
[math]\displaystyle{ V_{\frac{p+1}{t}}(\lambda,1) \ne 2 \bmod p }[/math]
  • Выбираем случайное число x, которое и будет секретным ключом.
  • Вычисляем открытый ключ следующим образом:
[math]\displaystyle{ y = V_{x}(\lambda,1) \bmod p }[/math]

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

  • Сначала выбирается случайное число k, такое что 1 ≤ k ≤ p — 1.
  • После этого, используя открытый ключ y, вычисляется параметр G:
[math]\displaystyle{ G = V_{k}(y,1)\bmod p }[/math]
  • Первая часть криптограммы:
[math]\displaystyle{ d_{1} = V_{k}(\lambda,1)\bmod p }[/math]
  • Вторая часть:
[math]\displaystyle{ d_{2} = G \cdot M\bmod p }[/math]

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

  • Используя закрытый ключ вычисляется G:
[math]\displaystyle{ G = V_{x}(d_{1},1)\bmod p }[/math]
  • Далее, получая обратный элемент к G по модулю p, получаем исходное сообщение:
[math]\displaystyle{ M = d_{2}(G^{-1})\bmod p }[/math]

Примечания

  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
Источник — https://xn--h1ajim.xn--p1ai/index.php?title=LUC&oldid=5858282