LUC

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

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

Введение

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

U_{n+2}(P,Q)=P\cdot U_{n+1}(P,Q)-Q\cdot U_{n}(P,Q),\,n\geq 0\quad (1.1)

\quad

V_{n+2}(P,Q)=P\cdot V_{n+1}(P,Q)-Q\cdot V_{n}(P,Q),\,n\geq 0\quad (1.2)

\quad

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

\quad

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

\quad

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

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

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

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

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

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

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

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

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

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

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

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

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

(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-

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

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

(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. Свойство доказано.

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

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

Вывод

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

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

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

P=\alpha +\beta \quad (2)

Q=\alpha \cdot \beta \quad (3)

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

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

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

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

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

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

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

и следовательно:

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

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

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

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

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

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

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

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

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)

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

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

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

Тогда из (1.3):

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

А из (1.4):

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

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

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

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

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

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

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

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

gcd[(p-1)\cdot (q-1)\cdot (p+1)\cdot (q+1),e]=1

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

D=P^{2}-4

,

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

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

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

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

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

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

KU=(e,N)

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

KR=(d,N)

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

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

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

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

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

Пример

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

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

p=1949,\quad q=2089

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

N=p\cdot q=4071461

3) Вычисляем открытый ключ e из уравнения

gcd[(p-1)\cdot (p+1)\cdot (q-1)\cdot (q+1),\quad e]=1

:

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

4) Шифровать будем следующее сообщение P = 11111, далее вычисляем символ Лежандра

\textstyle ({\frac {D}{p}})

:

параметр $D$ :

D=P^{2}-4=123454317

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

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

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

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

S(N)=lcm[(1949+1),(2089+1)]=407550

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

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

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

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

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

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

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

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

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

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

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):

lcm[(p+1),(q+1)]

lcm[(p+1),(q-1)]

lcm[(p-1),(q+1)]

lcm[(p-1),(q-1)]

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

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

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

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

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

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

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

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

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

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

V_{d}[V_{e}(P,1),1]=P\quad

, где

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

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

$\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) Из свойств последовательностей Люка имеем:

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) Подставим эти формулы в условие леммы:

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

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

=(\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})

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

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

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

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

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

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

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

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

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

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

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

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

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

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

из леммы 1:

=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)]

так как

\quad V_{1}(P,1)=P,\quad U_{1}(P,1)=1

=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:

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

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

Алгоритм LUCDIF

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм LUCELG

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

↑ Peter Smith. Luc Public-Key Encryption // Dr. Dobb's journal. — January 1993. Архивировано 11 ноября 2014 года.
↑ Paulo Ribenboim. The little book of bigger primes. — Springer-Verlag New York. — 2004.
↑ 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