Ранцевая криптосистема Шора-Ривеста

Ранцевая криптосистема Шора-Ривеста была предложена в 1985 году (Chor, 1985; Chor and Rivest, 1988). В настоящее время она является единственной известной схемой шифрования, основанной на задаче о ранце, которая не использует модульного умножения для маскировки простой задачи о ранце На данный момент создано множество рюкзачных криптосистем, например ранцевая криптосистема Меркла — Хеллмана. Однако практически все существующие на сегодняшний день взломаны или признаны потенциально небезопасными, примечательным исключением является схема Шор-Ривеста. Криптосистема Шора-Ривеста является одной из немногих не взломанных систем.

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

Пусть пользователь B хочет отправить зашифрованное сообщение A. Для этого:

Для генерации открытого и закрытого ключей нужно:

1. Выбрать конечное поле ${𝔽}_{𝑞}$ характеристики $𝑝$, где $𝑞={𝑝}^{ℎ}$, $𝑝\ge ℎ$, и для которого возможно эффективно решать задачу дискретного логарифмирования (см. Особенности криптосистемы 3)
2. Выбрать случайный монотонный неприводимый многочлен $𝑓\left(x\right)$ степени $ℎ$ над ${\mathbb{Z}}_{𝑝}$. Элементы ${𝔽}_{𝑞}$ будут представлены как многочлены от ${\mathbb{Z}}_{𝑝}[𝑥]$ степени меньше $ℎ$, причем умножение можно выполняться по модулю $𝑓\left(x\right)$.
3. Выбрать случайный примитивный многочлен $𝑔\left(x\right)$ поля ${𝔽}_{𝑞}$.
4. Вычислить дискретный логарифм ${𝑎}_{𝑖}={\log }_{𝑔\mathit{(}𝑥\mathit{)}}(𝑥+𝑖)$ элемента поля $(𝑥+𝑖)$.
5. Выбрать случайную перестановку $\pi$ на множестве целых чисел $\{0,1,2,...,p-1\}$
6. Выбрать случайное целое число $d$, $0\le d\le p^h-2$
7. Вычислить $c_i=(a_{\pi (i)}+d)mod(p^h-1)$ , $0\le i\le p-1$

Открытым ключом $𝖠$ является $((c_0,c_1,...,c_{p-1}),p,h)$; закрытым ключом $𝖠$ является $(f(x),g(x),\pi ,d)$

Для генерации случайного мононического неприводимого многочлена можно использовать следующий алгоритм:

ВХОД: простое $p$ и положительное целое число $m$.

ВЫХОД: монотонный неприводимый многочлен $𝑓\left(x\right)$ степени $m$ в ${\mathbb{Z}}_{𝑝}[𝑥]$.

Полученный многочлен будет неприводимым, ввиду следующей теоремы:

• Случайно выбрать целые числа $a_0,a_1,a_2,...,a_{m-1}$ между $0$ и $p-1$ с $a_0\ne 0$. Представить многочлен $𝑓\left(x\right)$ в виде" $f(x)=x^m+a_{m-1}{x}^{m-1}+...+a_2{x}^2+a_{1}x+a_0$
• Выбрать $u(x)=x$
• Для $i$ от $1$ до $\lfloor \frac{m}{2}\rfloor$ сделать следующие действия:

1. Вычислить $u(x)=u(x{)}^{p}modf(x)$. (Заметить, что $u(x)$ является многочленом от ${\mathbb{Z}}_{𝑝}[𝑥]$ степени меньше $m$)
2. Вычислить $d(x)=\gcd (f(x),u(x)-x)$
3. Если $d(x)\ne 1$ вернуть $𝑓\left(x\right)$ «приводимый».

• Если $𝑓\left(x\right)$ приводимый — повторить шаги алгоритма. Иначе вернуть $𝑓\left(x\right)$

  Неприводимый многочлен

  $f(x)\in {\mathbb{Z}}_{𝑝}[𝑥]$

  степени

  $m$

  является примитивным многочленом тогда и только тогда, когда

  $𝑓\left(x\right)$

  делит

  $x^k-1$

  для

  $k=p^m-1$

  и для не меньшего положительного целого

  $k$

  .

Для генерации случайного мононического примитивного многочлена можно использовать следующий алгоритм:

ВХОД: простое $p$, целое число $m$ ≥ 1 и различные простые множители $r_1,r_2,...,r_t$ из $p^m-1$.

ВЫХОД: монотонный примитивный многочлен $𝑓\left(x\right)$ степени $m$ в ${\mathbb{Z}}_{𝑝}[𝑥]$.

• Генерировать случайный монотонный неприводимый многочлен над ${\mathbb{Z}}_{𝑝}$.
• Для $i$ от $1$ до $t$ сделать следующие действия:

1. Вычислить $l(x)=x^{(p^m-1)/r_i}modf(x)$
2. Если $l(x)=1$ вернуть $𝑓\left(x\right)$ «не примитивный».

• Если $𝑓\left(x\right)$ примитивный — повторить шаги алгоритма. Иначе вернуть $𝑓\left(x\right)$

Шифрование

Для шифрования с открытым ключом $𝖡$ нужно сделать следующее:

• Получить открытый ключ $𝖠$ $((c_0,c_1,...,c_{p-1}),p,h)$
• Представить сообщение $m$ как двоичную строку длины $\lfloor \lg (\genfrac{}{}{0ex}{}{p}{h})\rfloor$, где $(\genfrac{}{}{0ex}{}{p}{h})$ является биномиальным коэффициентом $(\genfrac{}{}{0ex}{}{p}{h})=\frac{p!}{h!(p-h)!}$
• Рассмотреть $m$ как двоичное представление целого числа. Преобразовать это целое число в двоичный вектор $M=(M_0,M_1,...,M_{p-1})$ длины $p$, имеющий ровно $h$ единиц следующим образом:

1. Выбрать $l=h$
2. Для $i$ от $1$ до $p$ выполнить следующие действия: Если $m\ge (\genfrac{}{}{0ex}{}{p-i}{l})$ то выбрать $M_{i-1}=1$, $m=m-(\genfrac{}{}{0ex}{}{p-i}{l})$, $l=l-1$. В противном случае выбрать $M_{i-1}=0$. (Примечание: $(\genfrac{}{}{0ex}{}{n}{0})=1$ для $n\ge 0$ ;$(\genfrac{}{}{0ex}{}{0}{l})=0$ для $l\ge 1$)

• Вычислить $c=\sum _{i=o}^{p-1}(M_i{c}_i)mod(p^h-1)$
• Отправить зашифрованный текст $c$ в $𝖠$

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

Для дешифрования с открытым ключом $𝖠$ нужно сделать следующее:

• Вычислить $r=(c-hd)mod(p^h-1)$
• Вычислить $u(x)={g(x)}^{r}modf(x)$
• Вычислить $s(x)=u(x)+f(x)$, монотонный многочлен степени $ℎ$ над ${\mathbb{Z}}_{𝑝}$
• Разложить $s(x)$ на произведение линейных множителей над ${\mathbb{Z}}_{𝑝}$: $s(x)=\prod _{j=1}^h(x+t_j)$, где $t_j\in {\mathbb{Z}}_p$ (см. Особенности криптосистемы 5)
• Вычислить двоичный вектор $M=(M_0,M_1,...,M_{p-1})$ следующим образом. Компоненты $M$, которые равны $1$, имеют индексы ${\pi }^{-1}(t_j),1\le j\le h$. Остальные компоненты равны $0$.
• Сообщение $m$ восстанавливается из $M$ следующим образом:

1. Выбрать $m=0$, $l=h$
2. Для $i$ от $1$ до $p$ выполнить следующие действия: Если $M_{i-1}=1$, то выбрать $m=m+(\genfrac{}{}{0ex}{}{p-i}{l})$ и $l=l-1$

Доказательство

Для доказательства работы схемы можно заметить, что

$\begin{array}{cc}u(x)& =g(x{)}^{r}modf(x)\\ & \equiv g(x{)}^{c-hd}\equiv g(x{)}^{({\sum }_{i=0}^{p-1}{M}_i{c}_i)-hd}(modf(x))\\ & \equiv g(x{)}^{({\sum }_{i=0}^{p-1}{M}_i(a_{\pi (i)}+d))-hd{\displaystyle }}\equiv g(x{)}^{{\sum }_{i=0}^{p-1}{M}_i{a}_{\pi (i)}{\displaystyle }}(modf(x))\\ & \equiv {\prod }_{i=0}^{p-1}[g(x{)}^{a_{\pi (i)}}{]}^{M_i}\equiv {\prod }_{i=0}^{p-1}(x+\pi (i){)}^{M_i}(modf(x))\\ \end{array}$

Так как ${\prod }_{i=0}^{p-1}(x+\pi (i){)}^{M_i}{\displaystyle }$ и $s(x)$ — монические многочлены степени $ℎ$ и конгруэнтны по модулю $f(x)$, то:

$s(x)=u(x)+f(x)={\prod }_{i=0}^{p-1}(x+\pi (i){)}^{M_i}{\displaystyle }$

Следовательно, $ℎ$ корней $s(x)$ все лежат в ${\mathbb{Z}}_{𝑝}$, и применение ${\pi }^{-1}$ к этим корням дает координаты $M$, которые равны $1$.

Пример

В качестве примера можно рассмотреть работу схемы в случае, когда параметры относительно малы

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

Для генерации ключей A выполняет следующее:

• Выбирает $p=7$ и $h=4$
• Выбирает неприводимый многочлен $f(x)=x^4+3x^3+5x^2+6x+2$ степени $4$ над ${\mathbb{Z}}_7$ . Элементы конечного поля ${𝔽}_{7^4}$ представлены как многочлены от ${\mathbb{Z}}_7[𝑥]$ степени меньше $4$, причем умножение выполняется по модулю $f(x)$.
• Выбирает случайный примитивный элемент $g(x)=3x^3+3x^2+6$
• Вычисляет следующие дискретные логарифмы

$\begin{array}{ccccc}{a}_o& =& {\log }_{g(x)}(x)& =& 1028\\ a_1& =& {\log }_{g(x)}(x+1)& =& 1935\\ a_2& =& {\log }_{g(x)}(x+2)& =& 2054\\ a_3& =& {\log }_{g(x)}(x+3)& =& 1008\\ a_4& =& {\log }_{g(x)}(x+4)& =& 379\\ a_5& =& {\log }_{g(x)}(x+5)& =& 1780\\ a_6& =& {\log }_{g(x)}(x+6)& =& 223\end{array}$

• Выбирает случайную перестановку $\pi$ на $\{0,1,2,3,4,5,6\}$, определяемой $\pi (0)=6,\pi (1)=4,\pi (2)=0,\pi (3)=2,\pi (4)=1,\pi (5)=5,\pi (6)=3$
• Выбирает случайное целое число $d=1702$
• Вычисляет

$\begin{array}{ccccc}{c}_o& =& (a_6+d)mod2400& =& 1925\\ c_1& =& (a_4+d)mod2400& =& 2081\\ c_2& =& (a_0+d)mod2400& =& 330\\ c_3& =& (a_2+d)mod2400& =& 1356\\ c_4& =& (a_1+d)mod2400& =& 1237\\ c_5& =& (a_5+d)mod2400& =& 1082\\ c_6& =& (a_3+d)mod2400& =& 310\end{array}$

• Открытым ключом $𝖠$ является $((c_o,c_1,c_2,c_3,c_4,c_5,c_6),p=7,h=4)$, а закрытый ключ $𝖠=(f(x),g(x),\pi ,d)$

Шифрование

Чтобы зашифровать сообщение $m=22$ для $𝖠$, $𝖡$ делает следующее:

• Получает открытый ключ $𝖠$ открытого ключа
• Представляет $m$ как двоичную строку длиной $5$: $m=10110$. (так как $\lfloor \lg (\genfrac{}{}{0ex}{}{7}{4})=5\rfloor$)
• Использует метод, описанный на шаге 3 " алгоритма Шифрования ", для преобразования $m$ в бинарный вектор $M=(1,0,1,1,0,0,1)$ длины $7$.
• Вычисляет $c=(c_0+c_2+c_3+c_6)mod2400=1521$
• Отправляет $c=1521$ в $𝖠$

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

Чтобы расшифровать зашифрованный текст $c=1521$, $𝖠$ делает следующие действия:

• Вычисляет $r=(c-hd)mod(2400)=1913$
• Вычисляет $u(x)={g(x)}^{1913}modf(x)=x^3+3x^2+2x+5$
• Вычисляет $s(x)=u(x)+f(x)=x^4+4x^3+x^2+x$
• Факторизует $s(x)=x(x+2)(x+3)(x+6)$(так $t_1=0$, $t_2=2$, $t_3=3$, $t_4=6$)
• Компоненты $M$, которые равны $1$, имеют индексы ${\pi }^{-1}(0)=2$, ${\pi }^{-1}(2)=3$, ${\pi }^{-1}(3)=6$ и ${\pi }^{-1}(6)=0$. Следовательно, $M=(1,0,1,1,0,0,1)$
• Использует метод, описанный на шаге 6 " алгоритма дешифрования ", чтобы преобразовать $M$ в целое число $m=22$, тем самым восстанавливая исходный текст.

Особенности криптосистемы

• Известно, что система небезопасна, если раскрыты части секретного ключа, например, если известны $g(x)$ и $d$ в некотором представлении ${𝔽}_{𝑞}$ или если $f(x)$ известно, или если $\pi$ известен
• Хотя схема Шор-Ривеста была описана только для случая $p$ простой, она распространяется на случай, когда базовое поле ${\mathbb{Z}}_{𝑝}$ заменяется полем первичного степенного порядка
• Чтобы сделать задачу дискретного логарифма выполнимой на шаге 1 алгоритма " Генерация ключей ", параметры $p$ и $h$ могут быть выбраны так, что $q=p^h-1$ имеет только малые множители. В этом случае для эффективного вычисления дискретных логарифмов можно использовать алгоритм Полига — Хеллмана в конечном поле ${𝔽}_{𝑞}$
• На практике рекомендуемый размер параметров: $p\approx 200$ и $h\approx 25$. Один конкретный выбор первоначально предложенных параметров: $p=197$ и $h=24$; в этом случае наибольший простой коэффициент $197^{24}-1$ составляет $10316017$, а плотность набора ранца составляет около $1.077$. Другие первоначально заданные параметры: $\{p=211,h=24\}$,$\{p=3^5,h=24\}$ (базовое поле ${𝔽}_{3^5}$) и $\{p=2^8,h=25\}$ (базовое поле ${𝔽}_{2^8}$)
• Шифрование — очень быстрая операция. Расшифровка выполняется намного медленнее, узким местом является вычисление $u(x)$ на шаге 2 " алгоритма дешифрования ". Корни $s(x)$ на шаге 4 можно найти, просто попробовав все возможности в ${\mathbb{Z}}_{𝑝}$
• Основным недостатком схемы Шор-Ривеста является то, что открытый ключ довольно велик, а именно бит $(ph.\lg p)$. Для параметров $p=197$ и $h=24$ это около 36000 бит
• Расширение сообщения происходит в $\lg p^h/\lg (\genfrac{}{}{0ex}{}{p}{h})$. Для $p=197$ и $h=24$, это $1.797$

Атаки с раскрытием частичного ключа

В этом разделе Шаблон:Iw показывает, что он может монтировать атаку, когда раскрывается какая-либо часть секретного ключа. Несколько таких атак уже опубликованы в документе и некоторые из них были улучшены ниже.

Секретные ключи состоят из:

1. элемент $t\in {𝔽}_q$ с степенью $h$
2. генератор $g$
3. целое число $d\in {\mathbb{Z}}_{q-1}$
4. перестановка $\pi$ на множестве целых чисел $\{0,1,2,...,p-1\}$

Атака с раскрытием части $t$

Если предположим, что $\pi (0)=i$ и $\pi (1)=j$ (из-за симметрии в секретном ключе мы знаем, что будет выполняться произвольный выбор $(i,j)$), мы можем вычислить $\log (t+{\alpha }_i)$ и $\log (t+{\alpha }_j)$, то решим систему уравнения:

$c_0=d+\frac{\log (t+{\alpha }_i)}{\log g}$

$c_1=d+\frac{\log (t+{\alpha }_j)}{\log g}$ с неизвестными $d$ и $\log g$

Атака с раскрытием части $g$

Если предположим, что $\pi (0)=i$ и $\pi (1)=j$ (из-за симметрии в секретном ключе мы знаем, что будет выполняться произвольный выбор $(i,j)$), мы можем вычислить:

$g^{c_0-c_1}=\frac{t+{\alpha }_i}{t+{\alpha }_j}$

затем разрешить $t$

Атака с раскрытием части $\pi$

Найдем линейную комбинацию с формой ${\sum }_{i=1}^{p-1}{x}_i(c_i-c_0)=0$ с относительно небольшими интегральными коэффициентами $x_i$. Это можно выполнить с помощью алгоритма Lenstra-Lenstra-Lovász. Мы можем ожидать, что $|x_i|\le B$ с $B\approx p^{\frac{h}{p-1}}$. Обозначая это, получаем некоторое уравнение:

$\prod _{i\in I}(t+{\alpha }_{\pi (i)}{)}^{x_i}=\prod _{i\in J}(t+{\alpha }_{\pi (j)}{)}^{-x_j}$

с неотрицательными малыми степенями, который является полиномиальным уравнением с малой степенью, которое может быть эффективно разрешено.

Атака с раскрытием части $\pi$ и $g_{p^r}$

Мы можем интерполировать полином $Q(x)$ с $h/r+1$ парами $({\alpha }_{\pi (i)},{g_{p^r}}^{c_i})$. Таким образом, мы получаем многочлен $h/r$ — степени, корни которого являются сопряженными $-t$. Потом мы можем решить его, чтобы получить $t$ и выполнить атаку с раскрытием части $t$

См. также

• Криптосистема с открытым ключом
• Шифрование
• Класс NP
• Задача о ранце в криптографии
• Ранцевая криптосистема Меркла — Хеллмана
• Конечное поле
• Дискретное логарифмирование
• Неприводимый многочлен
• Биномиальный коэффициент