Русская Википедия:LUC
LUC — криптосистема с открытым ключом, разработанная исследователем из Новой Зеландии — Питером Смитом. Так же как RSA, эта система поддерживает шифрование и цифровую подпись. Отличительной чертой системы является использование последовательностей Люка(Lucas) вместо возведения в степень[1].
Описание алгоритма
Введение
Как уже упоминалось ранее, в системе LUC используются последовательности Люка. Они задаются следующими рекурентными соотношениями:
- <math> 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> \quad </math>
- <math> 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> \quad </math>
- <math>U_0(P,Q) = 0,\quad U_1(P,Q)=1 </math>
- <math> \quad </math>
- <math>V_0(P,Q) = 2,\quad V_1(P,Q)=P </math>
- <math> \quad </math>
- Где P,Q — целые неотрицательные числа.
В основном используется последовательность <math>V_{n}(P,Q)</math>. Поэтому далее будем рассматривать только её. Однако все сформулированные свойства будут справедливы и для <math>U_{n}(P,Q)</math>.
Пример последовательностей Люка для P = 3, Q = 1 | ||
---|---|---|
<math>n</math> | <math>V_{n}(3,1)</math> | <math>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>V_{n}(P\mod N, Q\mod N) = V_{n}(P,Q)\mod N \quad N>2 \quad(1.3)</math>
Так же используется ещё одно важное утверждение:
- <math>V_{n}(V_{k}(P,Q),Q^{k}) = V_{nk}(P,Q) \quad(1.4)</math>
Использование последовательностей Люка в криптографии
Допустим, что существуют такие <math>e</math> и <math>d</math> , что
- <math>V_{de}(X,1)=X\mod N</math>
Тогда из (1.3):
- <math>V_{de}(X\mod N,1) = V_{de}(X,1)\mod N = X\mod N</math>
А из (1.4):
- <math>V_{de}(X\mod N,1) = V_{d}(V_{e}(X\mod N,1),1)=X\mod N</math>
Сначала от символьного сообщения берётся хеш-функция, которая возвращает цифровое значение X. В качестве функции шифрования используется:
- <math>Y = V_{e}(X\mod N,1)</math>
А для дешифрования:
- <math>V_{d}(Y\mod N,1) = X\mod N</math>
В этом алгоритме шифрования открытым ключом будет являться пара {e,N}, а закрытым {d,N}.
Генерация ключа
- Сначала выбираются два простых числа p и q.
- Вычисляется их произведение <math> \textstyle N = p \cdot q </math>
- Выбирается число e, взаимнопростое с числом (p-1)(q-1)(p+1)(q+1):
- <math>gcd[(p-1) \cdot (q-1) \cdot (p+1) \cdot (q+1),e ] = 1</math>
- Вычисляется D:
- <math>D = P^{2}-4</math>,
- где P — наше сообщение
- Вычисляются следующие символы Лежандра <math> \textstyle ( \frac{D}{p} )</math> и <math> \textstyle ( \frac{D}{q} )</math>
- Находится наименьшее общее кратное
- <math> \textstyle S(N) = lcm[(p - (\frac{D}{p})),(q - (\frac{D}{q})) ] </math>
- Вычисляется d
- <math> d = e^{-1}\mod S(N) </math>
- открытый ключ:
- <math> KU = (e,N) </math>
- закрытый ключ:
- <math> KR = (d,N) </math>
Шифрование и дешифрование сообщения
1) Шифрование сообщения P, при условии P < N :
- <math> C = V_{e}(P,1)\mod N </math>
2) Дешифрование сообщения:
- <math> P = V_{d}(C,1)\mod N </math>
Пример
Рассмотрим криптосистему LUC на конкретном примере:
- 1) Выбираем два простых числа:
- <math>p = 1949, \quad q = 2089</math>
- 2) Вычисляем N:
- <math>N = p \cdot q = 4071461 </math>
- 3) Вычисляем открытый ключ e из уравнения <math>gcd[(p-1) \cdot (p+1) \cdot (q-1) \cdot (q+1),\quad e ] = 1 </math> :
- <math>gcd[1948 \cdot 2088 \cdot 1950 \cdot 2090,\quad e ] = 1 \quad => \quad e = 1103 </math>
- 4) Шифровать будем следующее сообщение P = 11111, далее вычисляем символ Лежандра <math> \textstyle ( \frac{D}{p} ) </math> :
- параметр <math>D</math>:
- <math>D^{2} = P^{2} - 4 = 123454317</math>
- Используя критерий Эйлера находим:
- <math> \textstyle ( \frac{D}{p} ) = -1 </math>
- <math> \textstyle ( \frac{D}{q} ) = -1 </math>
- 5) Теперь вычисляем функцию S(N):
- <math>S(N) = lcm[(1949 + 1),(2089 + 1)] = 407550 </math>
- 6) Закрытый ключ:
- <math> d = e^{-1}\mod 407550 = 24017 </math>
- 7) Зашифрованное сообщение:
- <math> C = V_{1103}(11111,1)\mod 4071461 = 3975392 </math>
- 8)Дешифрованное сообщение:
- <math> P = V_{24017}(3975392,1)\mod 4071461= 11111 </math>
Некоторые сложности
При использовании криптосистемы LUC возникают некоторые вычислительные трудности.
- Во-первых, вычисление больших чисел Люка может оказаться довольно сложной задачей, так как они задаются рекуррентно, а следовательно придётся перебрать все предыдущие числа. Однако, эту проблему решают следующие свойства последовательностей Люка:
- <math> V_{2n}(P,Q) = [V_{n}(P,Q)]^{2} - 2\cdot Q^{n} </math>
- <math> 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> lcm[(p+1),(q+1)] </math>
- <math> lcm[(p+1),(q-1)] </math>
- <math> lcm[(p-1),(q+1)] </math>
- <math> lcm[(p-1),(q-1)] </math>
- И следовательно существует четыре возможных значений закрытого ключа d:
- <math> d = e^{-1}\mod (lcm [(p+1),(q+1)]) </math>
- <math> d = e^{-1}\mod (lcm [(p+1),(q-1)]) </math>
- <math> d = e^{-1}\mod (lcm [(p-1),(q+1)]) </math>
- <math> d = e^{-1}\mod (lcm [(p-1),(q-1)]) </math>
- Получая сообщение С, зашифрованное открытым ключом e, первым делом считаем символы Лежандра:
- <math>\textstyle ( \frac{C^{2}-4}{p} ), ( \frac{C^{2}-4}{q} ) </math>
- По их значениям определяем какой из четырёх закрытых ключей d нужно использовать для дешифровки.
Корректность схемы LUC
Для доказательства необходимо проверить следующее равенство:
- <math> V_{d}[V_{e}(P,1),1] = P \quad </math>, где
- <math> 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> \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>
- Для простых <math>p,q\quad </math>, <math>N = p\cdot q\quad </math>, <math>\quad S(N)\quad</math> и любых целых <math>\quad k \quad</math> верно:
- <math>U_{kS(N)}(P,1) = 0 \mod N</math>
- <math>V_{kS(N)}(P,1) = 2 \mod N</math>
- Оставим эту лемму без доказательства[2].
Используя эти две леммы, определение последовательностей Люка и (1.4) получаем:
- из уравнения (1.4)
- <math> V_{d}(V_{e}(P,1),1) = V_{de}(P,1) \quad </math>
- по определению e и d:
- <math> = V_{kS(N)+1}(P,1) \quad </math>
- по определению (1.2), полагая что Q = 1:
- <math> = P\cdot V_{kS(N)}(P,1) - V_{kS(N)-1}(P,1) \quad </math>
- из леммы 1:
- <math> = 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> \quad V_{1}(P,1) = P,\quad U_{1}(P,1) = 1</math>
- <math> = 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> = 2P - \frac{1}{2}[2P - 0] = P \mod N </math>
То есть верно равенство: <math> V_{d}(V_{e}(P,1),1) = P </math>
Алгоритм LUCDIF
Алгоритм LUCDIF является комбинацией алгоритма LUC и протокола Диффи-Хеллмана. Основным назначением этого алгоритма является разделение двумя сторонами общего секретного ключа. Реализуется это следующим образом:
- Сначала Алиса выбирает простое число p, число g, такое что g < p и какое-то секретное число a.
- Затем Алиса вычисляет число:
- <math>V_{a}(g,1) \mod p</math>
- После этого Алиса отправляет Бобу сообщение
- <math>(V_{a}(g,1) \mod p,\quad p,\quad g )</math>
- Боб выбирает своё секретное число b. Используя его, он во-первых, получает общий секретный ключ:
- <math>V_{b}(V_{a}(g,1)) \mod p</math>
- И затем отправляет Алисе сообщение:
- <math>V_{b}(g,1) \mod p</math>
- Алиса, в свою очередь, тоже вычисляет общий секретный ключ:
- <math>V_{a}(V_{b}(g,1)) \mod p</math>
Из свойств последовательностей Люка, следует, что выражения полученные в конечном итоге Алисой и Бобом будут равны. Следовательно, Алиса и Боб будут иметь общий секретный ключ[3].
Алгоритм LUCELG
Алгоритм LUCELG строится на Схеме Эль-Гамаля и последовательностях Люка. Схема Эль-Гамаля используется для шифрования/расшифрования и генерации цифровой подписи. Рассмотрим работу этого алгоритма при шифровании сообщения.
1) Генерация пары открытого и закрытого ключа:
- Выбираем простое число P
- Затем выбираем λ такое, что для любых t>1 и делящих (p+1) верно:
- <math> V_{\frac{p+1}{t}}(\lambda,1) \ne 2 \bmod p</math>
- Выбираем случайное число x, которое и будет секретным ключом.
- Вычисляем открытый ключ следующим образом:
- <math> y = V_{x}(\lambda,1) \bmod p </math>
2) Шифрование сообщения:
- Сначала выбирается случайное число k, такое что 1 ≤ k ≤ p — 1.
- После этого, используя открытый ключ y, вычисляется параметр G:
- <math> G = V_{k}(y,1)\bmod p </math>
- Первая часть криптограммы:
- <math> d_{1} = V_{k}(\lambda,1)\bmod p </math>
- Вторая часть:
- <math> d_{2} = G \cdot M\bmod p </math>
3) Дешифровка сообщения:
- Используя закрытый ключ вычисляется G:
- <math> G = V_{x}(d_{1},1)\bmod p </math>
- Далее, получая обратный элемент к G по модулю p, получаем исходное сообщение:
- <math> M = d_{2}(G^{-1})\bmod p </math>
Примечания
Литература
- 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