Криптосистема Уильямса

Криптосистема Уильямса (Williams System) — система шифрования с открытым ключом, созданная Хью Коуи Уильямсом (Hugh Cowie Williams) в 1984 году.

История

Алгоритм был разработан в 1984 году как альтернатива более известному RSA. Целью разработки было избавиться от уязвимостей криптосистемы.

Об алгоритме

Для любой криптосистемы желательно, чтобы было доказано, что её взлом имеет вычислительную сложность аналогичную вычислительной сложности задачи, которую на данный момент невозможно решить за обозримое время. Как и RSA, криптосистема Уильямса опирается на предположение о сложности факторизации больших чисел, и было доказано, что для любого взлома шифротекста с помощью предварительного криптоанализа (имея лишь открытый ключ) необходимо провести факторизацию, то есть решить уравнение $pq=n$ относительно $p$ и $q$. Это утверждение не было доказано для системы RSA. Вычислительная сложность задачи факторизации неизвестна, но считается, что она достаточно высока. Но, как и RSA, криптосистема Уильямса уязвима для атаки на основе подобранного шифротекста.

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

Алгоритм системы Уильямса, не являясь вычислительно более сложным, чем RSA, намного более громоздкий в описании. Для него существует лемма, которая будет описана в разделе о математическом аппарате — она играет ключевую роль в этой криптосистеме.

Математический аппарат

Для начала следует определить терминологию — она заимствована из теории квадратичных полей, но для криптосистемы требуются лишь самые начальные знания. Рассмотрим элемент

$\alpha =a+b{\sqrt {c}}=(a,b),$

где $a,b,c$ — целые числа, а ${\sqrt {c}}$ — условный элемент, квадрат которого равен $c$. Тогда будут справедливы следующие формулы:

$\alpha _{1}+\alpha _{2}=(a_{1}+a_{2},b_{1}+b_{2}),$

$\alpha _{1}\cdot \alpha _{2}=(a_{1}a_{2}+c\cdot b_{1}b_{2},a_{1}b_{2}+a_{2}b_{1})$

Сопряжённым к $\alpha$ числом называется

${\bar {\alpha }}=a-b{\sqrt {c}}$

Определим также функции, которые помогут нам выразить степень этого числа. Пусть

$\alpha ^{i}=X_{i}(\alpha )+Y_{i}(\alpha ){\sqrt {c}},$

тогда $X_{i}$ и $Y_{i}$ можно выразить через $\alpha ^{i}$ следующим образом:

$X_{i}(\alpha )=(\alpha ^{i}+{\bar {\alpha }}^{i})/2$

$Y_{i}(\alpha )=b(\alpha ^{i}-{\bar {\alpha }}^{i})/(\alpha -{\bar {\alpha }})=(\alpha ^{i}-{\bar {\alpha }}^{i})(2{\sqrt {c}})$

Последнее выражение предназначено только для упрощения понимания. Так как функции определены для пар $(a,b)$, то не содержат $c$. Если предположить теперь, что $a^{2}-b^{2}c=1$, то можно записать следующие рекуррентные соотношения:

$X_{2i}=2{X_{i}}^{2}-1$

$Y_{2i}=2X_{i}Y_{i}$

$X_{2i+1}=2X_{i}X_{i+1}-X_{1}$

$Y_{2i+1}=2X_{i}Y_{i+1}-Y_{1}$

Эти формулы предназначены для быстрого вычисления $X_{i}$ и $Y_{i}$. Так как $X_{0}=1$ и $X_{1}=a$, то $X_{i}(\alpha )$ также не зависит от $b$.

Лемма

Пусть $n$ является произведением двух нечётных простых чисел $p$ и $q$; $a,b,c$ - целые числа, удовлетворяющие уравнению $a^{2}-cb^{2}=1{\pmod {n}}$. Пусть символы Лежандра $\delta _{p}=$$\textstyle \left({\frac {c}{p}}\right)$ и $\delta _{q}=\textstyle \left({\frac {c}{q}}\right)$ удовлетворяют сравнениям

$\delta _{p}=-p{\pmod {4}}$ $\delta _{q}=-q{\pmod {4}}$.

Пусть далее $gcd(cb,n)=1$ и Символ Якоби $\textstyle \left({\frac {2(a+1)}{n}}\right)$ равен 1. Обозначим

$m=(p-\delta _{p})(q-\delta _{q})/4$

и полагаем, что $e$ и $d$ удовлетворяют сравнению

$ed=(m+1)/2{\pmod {m}}$.

При этих предположениях

$\alpha ^{2ed}=\pm \alpha {\pmod {n}}$

Создание ключа

Сначала выбираются два простых числа $p$ и $q$, вычисляется их произведение $n$. С помощью перебора выбирается число $c$ так, чтобы символы Лежандра $\delta _{p}$ и $\delta _{q}$ удовлетворяли условиям, наложенным в лемме. Затем (также подбором) определяется число $s$ такое, что символ Якоби

$\textstyle \left({\frac {s^{2}-c}{n}}\right)=-1$

и $gcd\textstyle \left(s,n\right)=1.$ Число $m$ выбирается так же, как и в лемме:

$m=(p-\delta _{p})(q-\delta _{q})/4$

Затем выбираются числа $d,e$, удовлетворяющие условиям, наложенным в лемме. Выберем случайное, например, $d:gcd\textstyle \left(d,m\right)=1$, а $e$ вычислим по формуле

$e={\frac {m+1}{2}}d^{-1}{\pmod {m}}$

Тогда ${n,e,c,s}$ — открытый ключ, а ${p,q,m,d}$ — секретный ключ.

Зашифрование

Все вычисления здесь ведутся по модулю $n$. Запись $a+b{\sqrt {c}}{\pmod {n}}$ здесь означает $(a\mod n)+(b\mod n){\sqrt {c}}.$ Представим открытый текст в виде числа $w\in {2,3,...,n-1}$. Определим $\gamma$ и $b_{1}$: если символ Якоби $\textstyle \left({\frac {w^{2}-c}{n}}\right)$ равен $+1$, то

$b_{1}=0$ и $\gamma =w+{\sqrt {c}},$

иначе определим $\gamma$ через произведение

$b_{1}=1$ и $\gamma =(w+{\sqrt {c}})(s+{\sqrt {c}}).$

Тогда легко убедиться, что символ Якоби

$\textstyle \left({\frac {\gamma {\bar {\gamma }}}{n}}\right)=1,$

что проверяется прямым вычислением (во втором случае с учётом выбора $s$ и мультипликативности символа Якоби). Далее находим число

$\alpha ={\frac {\gamma }{\bar {\gamma }}}.$

Представим $\alpha$ в виде $\alpha =a+b{\sqrt {c}}.$ $\alpha$ удовлетворяет условиям, накладываемым в лемме. Действительно, $p,q,n,c,d,e$ удовлетворяют условиям по построению, и

$\alpha {\bar {\alpha }}={\frac {\gamma }{\bar {\gamma }}}{\frac {\bar {\gamma }}{\gamma }}=1.$

$2(a+1)={\frac {\gamma }{\bar {\gamma }}}+{\frac {\bar {\gamma }}{\gamma }}+2={\frac {(\gamma +{\bar {\gamma }})^{2}}{{\bar {\gamma }}\gamma }}{\pmod {n}}$

Из последней формулы следует, что

$\textstyle \left({\frac {2(a+1)}{n}}\right)=1.$

Получив $\alpha ,$ следует его зашифровать возведением в степень $e$ — результат может быть представлен через $X_{e}(\alpha )$ и $Y_{e}(\alpha ),$ которые могут быть быстро (за количество операций порядка $\log e$) найдены с помощью рекуррентных формул. Введём обозначение

$E={\frac {X_{e}(\alpha )}{Y_{e}(\alpha )}}$

Тогда криптотекстом будет являться тройка чисел $(E,b_{1},b_{2}),$ где $b_{2}=a\mod 2.$

Расшифрование

Расшифрование проводится проще. Сначала вычисляется

$\alpha ^{2e}={\frac {\alpha ^{2e}}{{(\alpha {\bar {\alpha }})}^{e}}}={\frac {E+{\sqrt {c}}}{E-{\sqrt {c}}}},$

что может сделать и злоумышленник. Но для окончательного расшифрования необходимо вычислить, как показано в лемме, $\alpha ^{2ed}$ — при том, что $d$ держится в секрете.

$\alpha ^{2ed}=X_{d}(\alpha ^{2e})+Y_{d}(\alpha ^{2e}){\sqrt {c}}=\pm \alpha$

Число $b_{2},$ передаваемое в сообщении, укажет, какой из знаков верен — тот, что даёт чётный результат или тот, что даёт нечётный. Число $b_{1}$ покажет, следует ли умножить результат на $(s-{\sqrt {c}})/(s+{\sqrt {c}})$. В результате мы получим число

$\alpha '={\frac {w+{\sqrt {c}}}{w-{\sqrt {c}}}}$

И с лёгкостью найдём исходный текст, что и завершит процесс расшифрования.

$w={\frac {\alpha '+1}{\alpha '-1}}{\sqrt {c}}$

Безопасность

Как и на RSA, на криптосистему может быть проведена атака на основе подобранного шифротекста. Предположим, что криптоаналитик нашёл некоторый алгоритм, позволяющий с вероятностью $\delta >0$ расшифровать криптотекст. Тогда он может поступить следующим образом:

1. Выбрать число $\phi$ такое, что символ Якоби $\textstyle \left({\frac {\phi ^{2}-c}{n}}\right)=-1$;

2. Зашифровать $\phi$, но таким образом, как будто упомянутый символ Якоби равен $+1$ и $b_{1}=0$, получив на выходе криптотекст $(E,0,b_{2})$;

3. Расшифровать полученный криптотекст, получив некоторый $\psi \neq \phi$.

Тогда с вероятностью $\delta >0$ криптоаналитик может получить

$\phi -\psi =p{\pmod {n}}$

или

$\phi -\psi =q{\pmod {n}}$

Что позволяет произвести факторизацию $n$ и взломать криптосистему.

Быстродействие

После генерации ключа основные вычисления происходят при возведении числа $\alpha$ в степень, а это может быть произведено за $O(\log e)$ умножений по модулю, каждое из которых происходит за $O(\log e)$ операций сложения, в свою очередь выполняющихся за $O(\log e)$ элементарных операций сложения неизменной скорости — то есть за $O(\log ^{3}e)$, с той же скоростью, что и возведение в степень целого числа по модулю, которое требуется для использования RSA.

Пример

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

Выберем, например, $p=11$ и $q=13$, произведением которых является $n=143$. Так как

$\left({\frac {5}{11}}\right)=1=-11{\pmod {4}}$

и

$\left({\frac {5}{13}}\right)=-1=-13{\pmod {4}}$

Можно выбрать $c=5$. Также, если выбрать $s=2$, получим

$\left({\frac {s^{2}-c}{n}}\right)=\left({\frac {-1}{11}}\right)\left({\frac {-1}{13}}\right)=-1$

Что удовлетворяет условию теоремы. Далее получим

$m=\left({\frac {10\cdot 14}{4}}\right)=35$

И, наконец, выберем экспоненты шифрования и расшифрования: так как

$23\cdot 16=18{\pmod {m}}$

Можно выбрать

$e=23$

$d=16$

Зашифрование

Пусть исходный текст будет $\omega =21$. Так как

$\left({\frac {21^{2}-5}{143}}\right)=\left({\frac {7}{11}}\right)\left({\frac {7}{13}}\right)=(-1)\cdot (-1)=1$

Имеем $b_{1}=0$, $\gamma =21+{\sqrt {5}}$ и

$\alpha =\left({\frac {21+{\sqrt {5}}}{21-{\sqrt {5}}}}\right)=125+6{\sqrt {5}}{\pmod {143}}$

Так как $125$ нечётно, получаем $b_{2}=1$. После вычисления $X_{23}(\alpha )=68$ и $Y_{23}(\alpha )=125$ получаем

$E=68\cdot {125}^{-1}=68\cdot 135=28{\pmod {143}}$

Таким образом, шифротекстом является тройка $(28,1,1)$.

Расшифрование

Теперь следует вычислить $\alpha ^{2e}$:

$\alpha ^{2e}=\left({\frac {28^{2}+5}{28^{2}-5}}\right)+2\cdot \left({\frac {28}{28^{2}-5}}\right){\sqrt {5}}=95+126{\sqrt {5}}{\pmod {143}}$

Так как $d=16$, вычисляем также

$X_{16}(\alpha ^{2e})=18$

$Y_{16}(\alpha ^{2e})=137$

Так как $b_{2}=1$, то $a$ должно быть нечётным и

$\alpha '=-(18+137{\sqrt {5}})=125+6{\sqrt {5}}{\pmod {143}}$

Учитывая, что вторая компонента шифротекста $b_{1}=0$, заключаем, что $\alpha '=\alpha$. В таком случае

$\omega ={\frac {126+6{\sqrt {5}}}{124+6{\sqrt {5}}}}{\sqrt {5}}=21{\pmod {143}}$.

Таким образом, мы получили $\omega =21$, который и являлся первоначальным открытым текстом.

Литература

• Hugh C. Williams. Some Public-Key Crypto-Functions as Intractable as Factorization. — 1985.
• Kwangio Kim (Ed.). Public Key Criptography. — 1992. — С. 1—17.