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

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

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

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

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

Выбрать конечное поле $\mathbb {F} _{\mathit {q}}$ характеристики ${\mathit {p}}$ , где ${\mathit {q}}={\mathit {p}}^{\mathit {h}}$ , ${\mathit {p}}\geq {\mathit {h}}$ , и для которого возможно эффективно решать задачу дискретного логарифмирования (см. Особенности криптосистемы 3)
Выбрать случайный монотонный неприводимый многочлен ${\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 )}$ .
Выбрать случайный примитивный многочлен ${\mathit {g}}{\bigl (}x{\bigr )}$ поля $\mathbb {F} _{\mathit {q}}$ .
Вычислить дискретный логарифм ${\mathit {a}}_{\mathit {i}}=\log _{\mathit {g(x)}}({\mathit {x}}+{\mathit {i}})$ элемента поля $({\mathit {x}}+{\mathit {i}})$ .
Выбрать случайную перестановку $\pi$ на множестве целых чисел $\{0,1,2,...,p-1\}$
Выбрать случайное целое число $d$ , $0\leq d\leq p^{h}-2$
Вычислить $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)$

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

ВХОД: простое $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$ сделать следующие действия:

Вычислить $u(x)=u(x)^{p}{\bmod {f}}(x)$ . (Заметить, что $u(x)$ является многочленом от $\mathbb {Z} _{\mathit {p}}[{\mathit {x}}]$ степени меньше $m$ )
Вычислить $d(x)=\gcd(f(x),u(x)-x)$
Если $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$ .^[6]

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

ВХОД: простое $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$ сделать следующие действия:

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

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

Шифрование править

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

Получить открытый ключ ${\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$ единиц следующим образом:

Выбрать $l=h$
Для $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}}$ нужно сделать следующее^[4]:

Вычислить $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$ следующим образом:

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

Доказательство править

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

{\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$ .

Пример править

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

Генерация ключей править

Для генерации ключей 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$ известен^[10]
Хотя схема Шор-Ривеста была описана только для случая $p$ простой, она распространяется на случай, когда базовое поле $\mathbb {Z} _{\mathit {p}}$ заменяется полем первичного степенного порядка^[11]
Чтобы сделать задачу дискретного логарифма выполнимой на шаге 1 алгоритма " Генерация ключей ", параметры $p$ и $h$ могут быть выбраны так, что $q=p^{h}-1$ имеет только малые множители. В этом случае для эффективного вычисления дискретных логарифмов можно использовать алгоритм Полига — Хеллмана в конечном поле $\mathbb {F} _{\mathit {q}}$ ^[12]
На практике рекомендуемый размер параметров: $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}}$ )^[13]
Шифрование — очень быстрая операция. Расшифровка выполняется намного медленнее, узким местом является вычисление $u(x)$ на шаге 2 " алгоритма дешифрования ". Корни $s(x)$ на шаге 4 можно найти, просто попробовав все возможности в $\mathbb {Z} _{\mathit {p}}$ ^[14]
Основным недостатком схемы Шор-Ривеста является то, что открытый ключ довольно велик, а именно бит $(ph.\lg p)$ . Для параметров $p=197$ и $h=24$ это около 36000 бит^[15]
Расширение сообщения происходит в $\lg {p^{h}}/\lg {\binom {p}{h}}$ . Для $p=197$ и $h=24$ , это $1.797$ ^[16]

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

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

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

элемент $t\in \mathbb {F} _{q}$ с степенью $h$
генератор $g$
целое число $d\in \mathbb {Z} _{q-1}$
перестановка $\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}

^[17]

Атака с раскрытием части $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^[19]. Мы можем ожидать, что $|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}}

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

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

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

См. также править

Примечания править

↑ A. Queiruga Dios, L. Hernández Encinas, and J. Espinosa García. a case study of chor-rivest cryptosystem in maple. — С. 2.
↑ Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. handbool of applied cryptography. — С. 302. Архивировано 15 декабря 2017 года.
↑ Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. handbool of applied cryptography. — С. 300. Архивировано 15 декабря 2017 года.
↑ ¹ ² ³ Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. handbool of applied cryptography. — С. 303. Архивировано 15 декабря 2017 года.
↑ Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. handbool of applied cryptography. — С. 156. Архивировано 15 декабря 2017 года.
↑ Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. handbool of applied cryptography. — 2.229 Fact. — С. 84. Архивировано 15 декабря 2017 года.
↑ Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. handbool of applied cryptography. — С. 163. Архивировано 15 декабря 2017 года.
↑ Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. handbool of applied cryptography. — С. 304. Архивировано 15 декабря 2017 года.
↑ Dr. Nguyen Binh, Dr. Ngo Duc Thien. giáo trình cơ sở mật mã học. — С. 118—120. Архивировано 23 ноября 2015 года. Архивная копия от 23 ноября 2015 на Wayback Machine
↑ Dr. Nguyen Binh, Dr. Ngo Duc Thien. giáo trình cơ sở mật mã học. — Note 1. — С. 120. Архивировано 23 ноября 2015 года. Архивная копия от 23 ноября 2015 на Wayback Machine
↑ Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. handbool of applied cryptography. — 8.45 Note (i). — С. 305. Архивировано 15 декабря 2017 года.
↑ Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. handbool of applied cryptography. — 8.45 Note (ii). — С. 305. Архивировано 15 декабря 2017 года.
↑ Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. handbool of applied cryptography. — 8.45 Note (iii). — С. 305. Архивировано 15 декабря 2017 года.
↑ Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. handbool of applied cryptography. — 8.45 Note (iv). — С. 305. Архивировано 15 декабря 2017 года.
↑ Dr. Nguyen Binh, Dr. Ngo Duc Thien. giáo trình cơ sở mật mã học. — Note 5. — С. 120. Архивировано 23 ноября 2015 года. Архивная копия от 23 ноября 2015 на Wayback Machine
↑ Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. handbool of applied cryptography. — 8.45 Note (vi). — С. 306. Архивировано 15 декабря 2017 года.
↑ ¹ ² ³ B. Chor, R.L. Rivest. A knapsack-type public key cryptosystem based on arithmetic in finite fields. IEEE Transactions on Information Theory. — С. 901—909. Архивировано 21 декабря 2016 года.
↑ Serge Vaudenay. Cryptanalysis of the Chor-Rivest Cryptosystem. Архивировано 23 декабря 2017 года.
↑ A.K. Lenstra, H.W. Lenstra Jr., L. Lov´asz. Factoring polynomials with rational coeﬃcients. — С. 515—534.

[1] A. Queiruga Dios, L. Hernández Encinas, and J. Espinosa García. a case study of chor-rivest cryptosystem in maple. — С. 2.

[2] Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. handbool of applied cryptography. — С. 302. Архивировано 15 декабря 2017 года.

[:1-3] Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. handbool of applied cryptography. — С. 300. Архивировано 15 декабря 2017 года.

[:0-4] ¹ ² ³ Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. handbool of applied cryptography. — С. 303. Архивировано 15 декабря 2017 года.

[5] Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. handbool of applied cryptography. — С. 156. Архивировано 15 декабря 2017 года.

[6] Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. handbool of applied cryptography. — 2.229 Fact. — С. 84. Архивировано 15 декабря 2017 года.

[7] Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. handbool of applied cryptography. — С. 163. Архивировано 15 декабря 2017 года.

[8] Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. handbool of applied cryptography. — С. 304. Архивировано 15 декабря 2017 года.

[9] Dr. Nguyen Binh, Dr. Ngo Duc Thien. giáo trình cơ sở mật mã học. — С. 118—120. Архивировано 23 ноября 2015 года. Архивная копия от 23 ноября 2015 на Wayback Machine

[10] Dr. Nguyen Binh, Dr. Ngo Duc Thien. giáo trình cơ sở mật mã học. — Note 1. — С. 120. Архивировано 23 ноября 2015 года. Архивная копия от 23 ноября 2015 на Wayback Machine

[11] Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. handbool of applied cryptography. — 8.45 Note (i). — С. 305. Архивировано 15 декабря 2017 года.

[12] Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. handbool of applied cryptography. — 8.45 Note (ii). — С. 305. Архивировано 15 декабря 2017 года.

[13] Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. handbool of applied cryptography. — 8.45 Note (iii). — С. 305. Архивировано 15 декабря 2017 года.

[14] Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. handbool of applied cryptography. — 8.45 Note (iv). — С. 305. Архивировано 15 декабря 2017 года.

[15] Dr. Nguyen Binh, Dr. Ngo Duc Thien. giáo trình cơ sở mật mã học. — Note 5. — С. 120. Архивировано 23 ноября 2015 года. Архивная копия от 23 ноября 2015 на Wayback Machine

[16] Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. handbool of applied cryptography. — 8.45 Note (vi). — С. 306. Архивировано 15 декабря 2017 года.

[:2-17] ¹ ² ³ B. Chor, R.L. Rivest. A knapsack-type public key cryptosystem based on arithmetic in finite fields. IEEE Transactions on Information Theory. — С. 901—909. Архивировано 21 декабря 2016 года.

[18] Serge Vaudenay. Cryptanalysis of the Chor-Rivest Cryptosystem. Архивировано 23 декабря 2017 года.

[19] A.K. Lenstra, H.W. Lenstra Jr., L. Lov´asz. Factoring polynomials with rational coeﬃcients. — С. 515—534.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]