LUC

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

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

Введение

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

${\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)}$

${\displaystyle \quad }$

${\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)}$

${\displaystyle \quad }$

${\displaystyle U_{0}(P,Q)=0,\quad U_{1}(P,Q)=1}$

${\displaystyle \quad }$

${\displaystyle V_{0}(P,Q)=2,\quad V_{1}(P,Q)=P}$

${\displaystyle \quad }$

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

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

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

• ${\displaystyle V_{n}(P\mod N,Q\mod N)=V_{n}(P,Q)\mod N\quad N>2\quad (1.3)}$

Доказательство

Для доказательства воспользуемся методом математической индукции по n

• База индукции:

1) для n = 0 - выражение (1.3) верно, т.к. по определению (1.1):

${\displaystyle V_{0}(P\mod N,Q\mod N)=2}$

${\displaystyle (V_{0}(P,Q))\mod N=2}$

2) для n = 1 аналогично:

${\displaystyle V_{1}(P\mod N,Q\mod N)=P\mod N}$

${\displaystyle (V_{1}(P,Q))\mod N=P\mod N}$

• Предположение индукции.Пусть (1.3) верно для всех значений k≤n-1 :

${\displaystyle V_{k}(P\mod N,Q\mod N)=(V_{k}(P,Q))\mod N}$

• Шаг индукции. Докажем, что (1.3) выполняется и для k = n:

1) по определению последовательности Люка:

${\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-}$

${\displaystyle (Q\mod N)\cdot (V_{n-2}(P,Q))\mod N}$

2) Воспользуемся предположением индукции:

${\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))}$

В 2) получили определение последовательности Люка. А следовательно (1.3) верно для k = n. Свойство доказано.

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

• ${\displaystyle V_{n}(V_{k}(P,Q),Q^{k})=V_{nk}(P,Q)\quad (1.4)}$

Вывод

• Для доказательства воспользуемся следующими формулами для последовательностей Люка:

${\displaystyle X^{2}-P\cdot X+Q=0\quad (0)}$

${\displaystyle V_{n}(P,Q)=\alpha ^{n}+\beta ^{n}\quad (1)}$

${\displaystyle P=\alpha +\beta \quad (2)}$

${\displaystyle Q=\alpha \cdot \beta \quad (3)}$

• Теперь подставим в характеристическое уравнение ${\displaystyle (0)}$ следующие выражения ${\displaystyle P'=V_{k}(P,Q),Q'=Q^{k}}$ :

${\displaystyle X^{2}-V_{k}(P,Q)\cdot X+Q^{k}=0\quad (4)}$

• Выведем формулы аналогичные формулам ${\displaystyle (1)-(3)}$, полученным для уравнения ${\displaystyle (0)}$:

${\displaystyle \alpha ^{'}+\beta ^{'}=V_{k}(P,Q)\quad (5)}$

${\displaystyle \alpha ^{'}\cdot \beta ^{'}=Q^{k}\quad (6)}$

• По определению последовательностей Люка:

${\displaystyle V_{n}(P,Q)=\alpha ^{n}+\beta ^{n}\quad }$ и следовательно:

${\displaystyle V_{n}(V_{k}(P,Q),Q^{k})=(\alpha ')^{n}+(\beta ')^{n}\quad (7)}$

• Из (7) и (5) для ${\displaystyle V_{k}(P,Q)}$ получим:

${\displaystyle V_{k}(P,Q)=\alpha ^{k}+\beta ^{k}=\alpha '+\beta '\quad (8)}$

• Аналогично для ${\displaystyle Q^{k}\quad }$ :

${\displaystyle Q^{k}=\alpha ^{k}\cdot \beta ^{k}=\alpha '\cdot \beta '\quad (9)}$

• Из (8) и (9) получаем:

${\displaystyle \alpha ^{k}=\alpha ',\beta ^{k}=\beta '\quad (10)}$

• Подставим (10) в (7):

${\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)}$

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

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

${\displaystyle V_{de}(X,1)=X\mod N}$

Тогда из (1.3):

${\displaystyle V_{de}(X\mod N,1)=V_{de}(X,1)\mod N=X\mod N}$

А из (1.4):

${\displaystyle V_{de}(X\mod N,1)=V_{d}(V_{e}(X\mod N,1),1)=X\mod N}$

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

${\displaystyle Y=V_{e}(X\mod N,1)}$

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

${\displaystyle V_{d}(Y\mod N,1)=X\mod N}$

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

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

• Сначала выбираются два простых числа p и q.
• Вычисляется их произведение ${\displaystyle \textstyle N=p\cdot q}$
• Выбирается число e, взаимнопростое с числом (p-1)(q-1)(p+1)(q+1):

${\displaystyle gcd[(p-1)\cdot (q-1)\cdot (p+1)\cdot (q+1),e]=1}$

• Вычисляется D:

${\displaystyle D=P^{2}-4}$,

где P — наше сообщение

• Вычисляются следующие символы Лежандра ${\displaystyle \textstyle ({\frac {D}{p}})}$ и ${\displaystyle \textstyle ({\frac {D}{q}})}$
• Находится наименьшее общее кратное

${\displaystyle \textstyle S(N)=lcm[(p-({\frac {D}{p}})),(q-({\frac {D}{q}}))]}$

• Вычисляется d

${\displaystyle d=e^{-1}\mod S(N)}$

• открытый ключ:

${\displaystyle KU=(e,N)}$

• закрытый ключ:

${\displaystyle KR=(d,N)}$

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

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

${\displaystyle C=V_{e}(P,1)\mod N}$

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

${\displaystyle P=V_{d}(C,1)\mod N}$

Пример

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

1) Выбираем два простых числа:

${\displaystyle p=1949,\quad q=2089}$

2) Вычисляем N:

${\displaystyle N=p\cdot q=4071461}$

3) Вычисляем открытый ключ e из уравнения ${\displaystyle gcd[(p-1)\cdot (p+1)\cdot (q-1)\cdot (q+1),\quad e]=1}$ :

${\displaystyle gcd[1948\cdot 2088\cdot 1950\cdot 2090,\quad e]=1\quad =>\quad e=1103}$

4) Шифровать будем следующее сообщение P = 11111, далее вычисляем символ Лежандра ${\displaystyle \textstyle ({\frac {D}{p}})}$ :

• параметр ${\displaystyle D}$:

${\displaystyle D=P^{2}-4=123454317}$

• Используя критерий Эйлера находим:

${\displaystyle \textstyle ({\frac {D}{p}})=-1}$

${\displaystyle \textstyle ({\frac {D}{q}})=-1}$

5) Теперь вычисляем функцию S(N):

${\displaystyle S(N)=lcm[(1949+1),(2089+1)]=407550}$

6) Закрытый ключ:

${\displaystyle d=e^{-1}\mod 407550=24017}$

7) Зашифрованное сообщение:

${\displaystyle C=V_{1103}(11111,1)\mod 4071461=3975392}$

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

${\displaystyle P=V_{24017}(3975392,1)\mod 4071461=11111}$

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

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

• Во-первых, вычисление больших чисел Люка может оказаться довольно сложной задачей, так как они задаются рекуррентно, а следовательно придётся перебрать все предыдущие числа. Однако, эту проблему решают следующие свойства последовательностей Люка:

${\displaystyle V_{2n}(P,Q)=[V_{n}(P,Q)]^{2}-2\cdot Q^{n}}$

${\displaystyle V_{n+m}(P,Q)=V_{n}(P,Q)\cdot V_{m}(P,Q)-Q^{n}\cdot V_{n-m}}$

Используя эти свойства можно довольно быстро получить нужное число, раскладывая номер элемента последовательности по степеням двойки. Этот алгоритм аналогичен алгоритму быстрого возведения в степень, который используется в криптосистеме RSA.

• Во-вторых, приватный ключ d зависит от исходного сообщения P.

Для каждого e существует четыре возможных значений функции S(N):

${\displaystyle lcm[(p+1),(q+1)]}$

${\displaystyle lcm[(p+1),(q-1)]}$

${\displaystyle lcm[(p-1),(q+1)]}$

${\displaystyle lcm[(p-1),(q-1)]}$

И следовательно существует четыре возможных значений закрытого ключа d:

${\displaystyle d=e^{-1}\mod (lcm[(p+1),(q+1)])}$

${\displaystyle d=e^{-1}\mod (lcm[(p+1),(q-1)])}$

${\displaystyle d=e^{-1}\mod (lcm[(p-1),(q+1)])}$

${\displaystyle d=e^{-1}\mod (lcm[(p-1),(q-1)])}$

Получая сообщение С, зашифрованное открытым ключом e, первым делом считаем символы Лежандра:

${\displaystyle \textstyle ({\frac {C^{2}-4}{p}}),({\frac {C^{2}-4}{q}})}$

По их значениям определяем какой из четырёх закрытых ключей d нужно использовать для дешифровки.

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

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

${\displaystyle V_{d}[V_{e}(P,1),1]=P\quad }$, где

${\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}$

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

• ${\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)}$

Доказательство

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

${\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 }$

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

${\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 }}}$

${\displaystyle =(\alpha ^{n}+\beta ^{n})\cdot (\alpha ^{m}+\beta ^{m})-(\alpha ^{n}-\beta ^{n})\cdot (\alpha ^{m}-\beta ^{m})}$

${\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})}$

${\displaystyle =2\cdot \alpha ^{n}\cdot \beta ^{m}+2\cdot \alpha ^{m}\cdot \beta ^{n}}$

${\displaystyle =\alpha ^{m}\cdot \beta ^{m}\cdot (\alpha ^{n-m}+\beta ^{n-m})}$

${\displaystyle =2\cdot Q^{m}\cdot V_{n-m}(P,Q)}$

• Для простых ${\displaystyle p,q\quad }$, ${\displaystyle N=p\cdot q\quad }$, ${\displaystyle \quad S(N)\quad }$ и любых целых ${\displaystyle \quad k\quad }$ верно:

${\displaystyle U_{kS(N)}(P,1)=0\mod N}$

${\displaystyle V_{kS(N)}(P,1)=2\mod N}$

Оставим эту лемму без доказательства^[2].

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

из уравнения (1.4)

${\displaystyle V_{d}(V_{e}(P,1),1)=V_{de}(P,1)\quad }$

по определению e и d:

${\displaystyle =V_{kS(N)+1}(P,1)\quad }$

по определению (1.2), полагая что Q = 1:

${\displaystyle =P\cdot V_{kS(N)}(P,1)-V_{kS(N)-1}(P,1)\quad }$

из леммы 1:

${\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)]}$

так как ${\displaystyle \quad V_{1}(P,1)=P,\quad U_{1}(P,1)=1}$

${\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 }$

из Леммы 2:

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

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

Алгоритм LUCDIF

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

• Сначала Алиса выбирает простое число p, число g, такое что g < p и какое-то секретное число a.
• Затем Алиса вычисляет число:

${\displaystyle V_{a}(g,1)\mod p}$

• После этого Алиса отправляет Бобу сообщение

${\displaystyle (V_{a}(g,1)\mod p,\quad p,\quad g)}$

• Боб выбирает своё секретное число b. Используя его, он во-первых, получает общий секретный ключ:

${\displaystyle V_{b}(V_{a}(g,1))\mod p}$

• И затем отправляет Алисе сообщение:

${\displaystyle V_{b}(g,1)\mod p}$

• Алиса, в свою очередь, тоже вычисляет общий секретный ключ:

${\displaystyle V_{a}(V_{b}(g,1))\mod p}$

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

Алгоритм LUCELG

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

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

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

${\displaystyle V_{\frac {p+1}{t}}(\lambda ,1)\neq 2{\bmod {p}}}$

• Выбираем случайное число x, которое и будет секретным ключом.
• Вычисляем открытый ключ следующим образом:

${\displaystyle y=V_{x}(\lambda ,1){\bmod {p}}}$

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

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

${\displaystyle G=V_{k}(y,1){\bmod {p}}}$

• Первая часть криптограммы:

${\displaystyle d_{1}=V_{k}(\lambda ,1){\bmod {p}}}$

• Вторая часть:

${\displaystyle d_{2}=G\cdot M{\bmod {p}}}$

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

• Используя закрытый ключ вычисляется G:

${\displaystyle G=V_{x}(d_{1},1){\bmod {p}}}$

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

${\displaystyle M=d_{2}(G^{-1}){\bmod {p}}}$