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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle {\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}}}$

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

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

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

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

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

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

${\displaystyle {\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}}}$

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

${\displaystyle {\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}}}$

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

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

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

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

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

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

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

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

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

Атака с раскрытием части ${\displaystyle t}$

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

${\displaystyle c_{0}=d+{\frac {\log(t+\alpha _{i})}{\log g}}}$

${\displaystyle c_{1}=d+{\frac {\log(t+\alpha _{j})}{\log g}}}$ с неизвестными ${\displaystyle d}$ и ${\displaystyle \log {g}}$^[17]

Атака с раскрытием части ${\displaystyle g}$

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

${\displaystyle g^{c_{0}-c_{1}}={\frac {t+\alpha _{i}}{t+\alpha _{j}}}}$

затем разрешить ${\displaystyle t}$

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

Найдем линейную комбинацию с формой ${\displaystyle \textstyle \sum _{i=1}^{p-1}\displaystyle x_{i}(c_{i}-c_{0})=0}$ с относительно небольшими интегральными коэффициентами ${\displaystyle x_{i}}$. Это можно выполнить с помощью алгоритма Lenstra-Lenstra-Lovász^[19]. Мы можем ожидать, что ${\displaystyle |x_{i}|\leq B}$ с ${\displaystyle B\approx p^{\tfrac {h}{p-1}}}$. Обозначая это, получаем некоторое уравнение:

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

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

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

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

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