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

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

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

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

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

1. Выбрать конечное поле $\mathbb {F} _{\mathit {q}}$ характеристики ${\mathit {p}}$, где ${\mathit {q}}={\mathit {p}}^{\mathit {h}}$, ${\mathit {p}}\geq {\mathit {h}}$, и для которого возможно эффективно решать задачу дискретного логарифмирования (см. Особенности криптосистемы 3)
2. Выбрать случайный монотонный неприводимый многочлен ${\mathit {f}}{\bigl (}x{\bigr )}$ степени ${\mathit {h}}$ над $\mathbb {Z} _{\mathit {p}}$. Элементы $\mathbb {F} _{\mathit {q}}$ будут представлены как многочлены от $\mathbb {Z} _{\mathit {p}}[{\mathit {x}}]$ степени меньше ${\mathit {h}}$, причем умножение можно выполняться по модулю ${\mathit {f}}{\bigl (}x{\bigr )}$.
3. Выбрать случайный примитивный многочлен ${\mathit {g}}{\bigl (}x{\bigr )}$ поля $\mathbb {F} _{\mathit {q}}$.
4. Вычислить дискретный логарифм ${\mathit {a}}_{\mathit {i}}=\log _{\mathit {g(x)}}({\mathit {x}}+{\mathit {i}})$ элемента поля $({\mathit {x}}+{\mathit {i}})$.
5. Выбрать случайную перестановку $\pi$ на множестве целых чисел $\{0,1,2,...,p-1\}$
6. Выбрать случайное целое число $d$, $0\leq d\leq p^{h}-2$
7. Вычислить $c_{i}=(a_{\pi (i)}+d){\bmod {(}}p^{h}-1)$ , $0\leq i\leq p-1$

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

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

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

ВЫХОД: монотонный неприводимый многочлен ${\mathit {f}}{\bigl (}x{\bigr )}$ степени $m$ в $\mathbb {Z} _{\mathit {p}}[{\mathit {x}}]$.

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

• Случайно выбрать целые числа $a_{0},a_{1},a_{2},...,a_{m-1}$ между $0$ и $p-1$ с $a_{0}\neq 0$. Представить многочлен ${\mathit {f}}{\bigl (}x{\bigr )}$ в виде" $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}{\bmod {f}}(x)$. (Заметить, что $u(x)$ является многочленом от $\mathbb {Z} _{\mathit {p}}[{\mathit {x}}]$ степени меньше $m$)
2. Вычислить $d(x)=\gcd(f(x),u(x)-x)$
3. Если $d(x)\neq 1$ вернуть ${\mathit {f}}{\bigl (}x{\bigr )}$ «приводимый».

• Если ${\mathit {f}}{\bigl (}x{\bigr )}$ приводимый — повторить шаги алгоритма. Иначе вернуть ${\mathit {f}}{\bigl (}x{\bigr )}$

  Неприводимый многочлен $f(x)\in \mathbb {Z} _{\mathit {p}}[{\mathit {x}}]$ степени $m$ является примитивным многочленом тогда и только тогда, когда ${\mathit {f}}{\bigl (}x{\bigr )}$ делит $x^{k}-1$ для $k=p^{m}-1$ и для не меньшего положительного целого $k$.

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

ВХОД: простое $p$, целое число $m$ ≥ 1 и различные простые множители $r_{1},r_{2},...,r_{t}$ из $p^{m}-1$.

ВЫХОД: монотонный примитивный многочлен ${\mathit {f}}{\bigl (}x{\bigr )}$ степени $m$ в $\mathbb {Z} _{\mathit {p}}[{\mathit {x}}]$.

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

1. Вычислить $l(x)=x^{{(p^{m}-1)}/r_{i}}{\bmod {f}}(x)$
2. Если $l(x)=1$ вернуть ${\mathit {f}}{\bigl (}x{\bigr )}$ «не примитивный».

• Если ${\mathit {f}}{\bigl (}x{\bigr )}$ примитивный — повторить шаги алгоритма. Иначе вернуть ${\mathit {f}}{\bigl (}x{\bigr )}$

Шифрование

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

• Получить открытый ключ ${\mathsf {A}}$ $((c_{0},c_{1},...,c_{p-1}),p,h)$
• Представить сообщение $m$ как двоичную строку длины $\lfloor \lg {\binom {p}{h}}\rfloor$, где ${\binom {p}{h}}$ является биномиальным коэффициентом ${\binom {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\geq {\binom {p-i}{l}}$ то выбрать $M_{i-1}=1$, $m=m-{\binom {p-i}{l}}$, $l=l-1$. В противном случае выбрать $M_{i-1}=0$. (Примечание: ${\binom {n}{0}}=1$ для $n\geq 0$ ;${\binom {0}{l}}=0$ для $l\geq 1$)

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

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

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

• Вычислить $r=(c-hd){\bmod {(}}p^{h}-1)$
• Вычислить $u(x)={g(x)}^{r}{\bmod {f}}(x)$
• Вычислить $s(x)=u(x)+f(x)$, монотонный многочлен степени ${\mathit {h}}$ над $\mathbb {Z} _{\mathit {p}}$
• Разложить $s(x)$ на произведение линейных множителей над $\mathbb {Z} _{\mathit {p}}$: $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\leq j\leq h$. Остальные компоненты равны $0$.
• Сообщение $m$ восстанавливается из $M$ следующим образом:

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

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

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

${\begin{aligned}u(x)&=g(x)^{r}{\bmod {f}}(x)\\&\equiv g(x)^{c-hd}\equiv g(x)^{(\textstyle \sum _{i=0}^{p-1}M_{i}c_{i}\displaystyle )-hd}({\bmod {f}}(x))\\&\equiv g(x)^{\textstyle (\sum _{i=0}^{p-1}M_{i}{(a_{\pi (i)}+d))-hd}\displaystyle }\equiv g(x)^{\textstyle \sum _{i=0}^{p-1}M_{i}a_{\pi (i)}\displaystyle }({\bmod {f}}(x))\\&\equiv \textstyle \prod _{i=0}^{p-1}[g(x)^{a_{\pi (i)}}]^{M_{i}}\displaystyle \equiv \textstyle \prod _{i=0}^{p-1}(x+\pi (i))^{M_{i}}\displaystyle ({\bmod {f}}(x))\\\end{aligned}}$

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

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

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

Пример

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

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

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

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

${\begin{array}{lcl}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}{lcl}c_{o}&=&(a_{6}+d){\bmod {2}}400&=&1925\\c_{1}&=&(a_{4}+d){\bmod {2}}400&=&2081\\c_{2}&=&(a_{0}+d){\bmod {2}}400&=&330\\c_{3}&=&(a_{2}+d){\bmod {2}}400&=&1356\\c_{4}&=&(a_{1}+d){\bmod {2}}400&=&1237\\c_{5}&=&(a_{5}+d){\bmod {2}}400&=&1082\\c_{6}&=&(a_{3}+d){\bmod {2}}400&=&310\\\end{array}}$

• Открытым ключом ${\mathsf {A}}$ является $((c_{o},c_{1},c_{2},c_{3},c_{4},c_{5},c_{6}),p=7,h=4)$, а закрытый ключ ${\mathsf {A}}=(f(x),g(x),\pi ,d)$

Шифрование

Чтобы зашифровать сообщение $m=22$ для ${\mathsf {A}}$, ${\mathsf {B}}$ делает следующее:

• Получает открытый ключ ${\mathsf {A}}$ открытого ключа
• Представляет $m$ как двоичную строку длиной $5$: $m=10110$. (так как $\lfloor \lg {\binom {7}{4}}=5\rfloor$)
• Использует метод, описанный на шаге 3 " алгоритма Шифрования ", для преобразования $m$ в бинарный вектор $M=(1,0,1,1,0,0,1)$ длины $7$.
• Вычисляет $c=(c_{0}+c_{2}+c_{3}+c_{6}){\bmod {2}}400=1521$
• Отправляет $c=1521$ в ${\mathsf {A}}$

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

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

• Вычисляет $r=(c-hd){\bmod {(}}2400)=1913$
• Вычисляет $u(x)={g(x)}^{1913}{\bmod {f}}(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$ в некотором представлении $\mathbb {F} _{\mathit {q}}$ или если $f(x)$ известно, или если $\pi$ известен
• Хотя схема Шор-Ривеста была описана только для случая $p$ простой, она распространяется на случай, когда базовое поле $\mathbb {Z} _{\mathit {p}}$ заменяется полем первичного степенного порядка
• Чтобы сделать задачу дискретного логарифма выполнимой на шаге 1 алгоритма " Генерация ключей ", параметры $p$ и $h$ могут быть выбраны так, что $q=p^{h}-1$ имеет только малые множители. В этом случае для эффективного вычисления дискретных логарифмов можно использовать алгоритм Полига — Хеллмана в конечном поле $\mathbb {F} _{\mathit {q}}$
• На практике рекомендуемый размер параметров: $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\}$ (базовое поле $\mathbb {F} _{3^{5}}$) и $\{p=2^{8},h=25\}$ (базовое поле $\mathbb {F} _{2^{8}}$)
• Шифрование — очень быстрая операция. Расшифровка выполняется намного медленнее, узким местом является вычисление $u(x)$ на шаге 2 " алгоритма дешифрования ". Корни $s(x)$ на шаге 4 можно найти, просто попробовав все возможности в $\mathbb {Z} _{\mathit {p}}$
• Основным недостатком схемы Шор-Ривеста является то, что открытый ключ довольно велик, а именно бит $(ph.\lg p)$. Для параметров $p=197$ и $h=24$ это около 36000 бит
• Расширение сообщения происходит в $\lg {p^{h}}/\lg {\binom {p}{h}}$. Для $p=197$ и $h=24$, это $1.797$

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

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

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

1. элемент $t\in \mathbb {F} _{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$

Найдем линейную комбинацию с формой $\textstyle \sum _{i=1}^{p-1}\displaystyle x_{i}(c_{i}-c_{0})=0$ с относительно небольшими интегральными коэффициентами $x_{i}$. Это можно выполнить с помощью алгоритма Lenstra-Lenstra-Lovász. Мы можем ожидать, что $|x_{i}|\leq B$ с $B\approx p^{\tfrac {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
• Задача о ранце в криптографии
• Ранцевая криптосистема Меркла — Хеллмана
• Конечное поле
• Дискретное логарифмирование
• Неприводимый многочлен
• Биномиальный коэффициент