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

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

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

Допустим, что существуют такие ${\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 нужно использовать для дешифровки.

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

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

• Для простых ${\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 является комбинацией алгоритма 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 строится на Схеме Эль-Гамаля и последовательностях Люка. Схема Эль-Гамаля используется для шифрования/расшифрования и генерации цифровой подписи. Рассмотрим работу этого алгоритма при шифровании сообщения.

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

• 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