Меню Главная Случайная статья Настройки LUC Материал из https://ru.wikipedia.org LUC — криптосистема с открытым ключом, разработанная исследователем из Новой Зеландии — Питером Смитом. Так же как RSA, эта система поддерживает шифрование и цифровую подпись. Отличительной чертой системы является использование последовательностей Люка(Lucas) вместо возведения в степень[1]. Содержание 1 Описание алгоритма 1.1 Введение 1.2 Использование последовательностей Люка в криптографии 1.3 Генерация ключа 1.4 Шифрование и дешифрование сообщения 1.5 Пример 1.6 Некоторые сложности 2 Корректность схемы LUC 3 Алгоритм LUCDIF 4 Алгоритм LUCELG 5 Примечания 6 Литература Описание алгоритма Введение Как уже упоминалось ранее, в системе 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) верно для всех значений kn-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)}$