Ранцевая криптосистема Шора-Ривеста была предложена в 1985 году (Chor, 1985; Chor and Rivest, 1988)[1] . В настоящее время она является единственной известной схемой шифрования, основанной на задаче о ранце, которая не использует модульного умножения для маскировки простой задачи о ранце [2] На данный момент создано множество рюкзачных криптосистем, например ранцевая криптосистема Меркла — Хеллмана . Однако практически все существующие на сегодняшний день взломаны или признаны потенциально небезопасными, примечательным исключением является схема Шор-Ривеста. Криптосистема Шора-Ривеста является одной из немногих не взломанных систем[3] .
Пусть пользователь B хочет отправить зашифрованное сообщение A. Для этого:
Для генерации открытого и закрытого ключей нужно [4] :
Выбрать конечное поле
F
q
{\displaystyle \mathbb {F} _{\mathit {q}}}
характеристики
p
{\displaystyle {\mathit {p}}}
, где
q
=
p
h
{\displaystyle {\mathit {q}}={\mathit {p}}^{\mathit {h}}}
,
p
≥
h
{\displaystyle {\mathit {p}}\geq {\mathit {h}}}
, и для которого возможно эффективно решать задачу дискретного логарифмирования (см. Особенности криптосистемы 3)
Выбрать случайный монотонный неприводимый многочлен
f
(
x
)
{\displaystyle {\mathit {f}}{\bigl (}x{\bigr )}}
степени
h
{\displaystyle {\mathit {h}}}
над
Z
p
{\displaystyle \mathbb {Z} _{\mathit {p}}}
. Элементы
F
q
{\displaystyle \mathbb {F} _{\mathit {q}}}
будут представлены как многочлены от
Z
p
[
x
]
{\displaystyle \mathbb {Z} _{\mathit {p}}[{\mathit {x}}]}
степени меньше
h
{\displaystyle {\mathit {h}}}
, причем умножение можно выполняться по модулю
f
(
x
)
{\displaystyle {\mathit {f}}{\bigl (}x{\bigr )}}
.
Выбрать случайный примитивный многочлен
g
(
x
)
{\displaystyle {\mathit {g}}{\bigl (}x{\bigr )}}
поля
F
q
{\displaystyle \mathbb {F} _{\mathit {q}}}
.
Вычислить дискретный логарифм
a
i
=
log
g
(
x
)
(
x
+
i
)
{\displaystyle {\mathit {a}}_{\mathit {i}}=\log _{\mathit {g(x)}}({\mathit {x}}+{\mathit {i}})}
элемента поля
(
x
+
i
)
{\displaystyle ({\mathit {x}}+{\mathit {i}})}
.
Выбрать случайную перестановку
π
{\displaystyle \pi }
на множестве целых чисел
{
0
,
1
,
2
,
.
.
.
,
p
−
1
}
{\displaystyle \{0,1,2,...,p-1\}}
Выбрать случайное целое число
d
{\displaystyle d}
,
0
≤
d
≤
p
h
−
2
{\displaystyle 0\leq d\leq p^{h}-2}
Вычислить
c
i
=
(
a
π
(
i
)
+
d
)
mod
(
p
h
−
1
)
{\displaystyle c_{i}=(a_{\pi (i)}+d){\bmod {(}}p^{h}-1)}
,
0
≤
i
≤
p
−
1
{\displaystyle 0\leq i\leq p-1}
Открытым ключом
A
{\displaystyle {\mathsf {A}}}
является
(
(
c
0
,
c
1
,
.
.
.
,
c
p
−
1
)
,
p
,
h
)
{\displaystyle ((c_{0},c_{1},...,c_{p-1}),p,h)}
; закрытым ключом
A
{\displaystyle {\mathsf {A}}}
является
(
f
(
x
)
,
g
(
x
)
,
π
,
d
)
{\displaystyle (f(x),g(x),\pi ,d)}
Для генерации случайного мононического неприводимого многочлена можно использовать следующий алгоритм:[5]
ВХОД: простое
p
{\displaystyle p}
и положительное целое число
m
{\displaystyle m}
.
ВЫХОД: монотонный неприводимый многочлен
f
(
x
)
{\displaystyle {\mathit {f}}{\bigl (}x{\bigr )}}
степени
m
{\displaystyle m}
в
Z
p
[
x
]
{\displaystyle \mathbb {Z} _{\mathit {p}}[{\mathit {x}}]}
.
Полученный многочлен будет неприводимым, ввиду следующей теоремы:
Случайно выбрать целые числа
a
0
,
a
1
,
a
2
,
.
.
.
,
a
m
−
1
{\displaystyle a_{0},a_{1},a_{2},...,a_{m-1}}
между
0
{\displaystyle 0}
и
p
−
1
{\displaystyle p-1}
с
a
0
≠
0
{\displaystyle a_{0}\neq 0}
. Представить многочлен
f
(
x
)
{\displaystyle {\mathit {f}}{\bigl (}x{\bigr )}}
в виде"
f
(
x
)
=
x
m
+
a
m
−
1
x
m
−
1
+
.
.
.
+
a
2
x
2
+
a
1
x
+
a
0
{\displaystyle f(x)=x^{m}+a_{m-1}x^{m-1}+...+a_{2}x^{2}+a_{1}x+a_{0}}
Выбрать
u
(
x
)
=
x
{\displaystyle u(x)=x}
Для
i
{\displaystyle i}
от
1
{\displaystyle 1}
до
⌊
m
2
⌋
{\displaystyle \lfloor {\frac {m}{2}}\rfloor }
сделать следующие действия:
Вычислить
u
(
x
)
=
u
(
x
)
p
mod
f
(
x
)
{\displaystyle u(x)=u(x)^{p}{\bmod {f}}(x)}
. (Заметить, что
u
(
x
)
{\displaystyle u(x)}
является многочленом от
Z
p
[
x
]
{\displaystyle \mathbb {Z} _{\mathit {p}}[{\mathit {x}}]}
степени меньше
m
{\displaystyle m}
)
Вычислить
d
(
x
)
=
gcd
(
f
(
x
)
,
u
(
x
)
−
x
)
{\displaystyle d(x)=\gcd(f(x),u(x)-x)}
Если
d
(
x
)
≠
1
{\displaystyle d(x)\neq 1}
вернуть
f
(
x
)
{\displaystyle {\mathit {f}}{\bigl (}x{\bigr )}}
«приводимый».
Для генерации случайного мононического примитивного многочлена можно использовать следующий алгоритм: [7]
ВХОД: простое
p
{\displaystyle p}
, целое число
m
{\displaystyle m}
≥ 1 и различные простые множители
r
1
,
r
2
,
.
.
.
,
r
t
{\displaystyle r_{1},r_{2},...,r_{t}}
из
p
m
−
1
{\displaystyle p^{m}-1}
.
ВЫХОД: монотонный примитивный многочлен
f
(
x
)
{\displaystyle {\mathit {f}}{\bigl (}x{\bigr )}}
степени
m
{\displaystyle m}
в
Z
p
[
x
]
{\displaystyle \mathbb {Z} _{\mathit {p}}[{\mathit {x}}]}
.
Генерировать случайный монотонный неприводимый многочлен над
Z
p
{\displaystyle \mathbb {Z} _{\mathit {p}}}
.
Для
i
{\displaystyle i}
от
1
{\displaystyle 1}
до
t
{\displaystyle t}
сделать следующие действия:
Вычислить
l
(
x
)
=
x
(
p
m
−
1
)
/
r
i
mod
f
(
x
)
{\displaystyle l(x)=x^{{(p^{m}-1)}/r_{i}}{\bmod {f}}(x)}
Если
l
(
x
)
=
1
{\displaystyle l(x)=1}
вернуть
f
(
x
)
{\displaystyle {\mathit {f}}{\bigl (}x{\bigr )}}
«не примитивный».
Если
f
(
x
)
{\displaystyle {\mathit {f}}{\bigl (}x{\bigr )}}
примитивный — повторить шаги алгоритма. Иначе вернуть
f
(
x
)
{\displaystyle {\mathit {f}}{\bigl (}x{\bigr )}}
Для шифрования с открытым ключом
B
{\displaystyle {\mathsf {B}}}
нужно сделать следующее[4] :
Получить открытый ключ
A
{\displaystyle {\mathsf {A}}}
(
(
c
0
,
c
1
,
.
.
.
,
c
p
−
1
)
,
p
,
h
)
{\displaystyle ((c_{0},c_{1},...,c_{p-1}),p,h)}
Представить сообщение
m
{\displaystyle m}
как двоичную строку длины
⌊
lg
(
p
h
)
⌋
{\displaystyle \lfloor \lg {\binom {p}{h}}\rfloor }
, где
(
p
h
)
{\displaystyle {\binom {p}{h}}}
является биномиальным коэффициентом
(
p
h
)
=
p
!
h
!
(
p
−
h
)
!
{\displaystyle {\binom {p}{h}}={\frac {p!}{h!(p-h)!}}}
Рассмотреть
m
{\displaystyle m}
как двоичное представление целого числа. Преобразовать это целое число в двоичный вектор
M
=
(
M
0
,
M
1
,
.
.
.
,
M
p
−
1
)
{\displaystyle M=(M_{0},M_{1},...,M_{p-1})}
длины
p
{\displaystyle p}
, имеющий ровно
h
{\displaystyle h}
единиц следующим образом:
Выбрать
l
=
h
{\displaystyle l=h}
Для
i
{\displaystyle i}
от
1
{\displaystyle 1}
до
p
{\displaystyle p}
выполнить следующие действия: Если
m
≥
(
p
−
i
l
)
{\displaystyle m\geq {\binom {p-i}{l}}}
то выбрать
M
i
−
1
=
1
{\displaystyle M_{i-1}=1}
,
m
=
m
−
(
p
−
i
l
)
{\displaystyle m=m-{\binom {p-i}{l}}}
,
l
=
l
−
1
{\displaystyle l=l-1}
. В противном случае выбрать
M
i
−
1
=
0
{\displaystyle M_{i-1}=0}
. (Примечание:
(
n
0
)
=
1
{\displaystyle {\binom {n}{0}}=1}
для
n
≥
0
{\displaystyle n\geq 0}
;
(
0
l
)
=
0
{\displaystyle {\binom {0}{l}}=0}
для
l
≥
1
{\displaystyle l\geq 1}
)
Вычислить
c
=
∑
i
=
o
p
−
1
(
M
i
c
i
)
mod
(
p
h
−
1
)
{\displaystyle c=\sum _{i=o}^{p-1}(M_{i}c_{i}){\bmod {(}}p^{h}-1)}
Отправить зашифрованный текст
c
{\displaystyle c}
в
A
{\displaystyle {\mathsf {A}}}
Для дешифрования с открытым ключом
A
{\displaystyle {\mathsf {A}}}
нужно сделать следующее[4] :
Вычислить
r
=
(
c
−
h
d
)
mod
(
p
h
−
1
)
{\displaystyle r=(c-hd){\bmod {(}}p^{h}-1)}
Вычислить
u
(
x
)
=
g
(
x
)
r
mod
f
(
x
)
{\displaystyle u(x)={g(x)}^{r}{\bmod {f}}(x)}
Вычислить
s
(
x
)
=
u
(
x
)
+
f
(
x
)
{\displaystyle s(x)=u(x)+f(x)}
, монотонный многочлен степени
h
{\displaystyle {\mathit {h}}}
над
Z
p
{\displaystyle \mathbb {Z} _{\mathit {p}}}
Разложить
s
(
x
)
{\displaystyle s(x)}
на произведение линейных множителей над
Z
p
{\displaystyle \mathbb {Z} _{\mathit {p}}}
:
s
(
x
)
=
∏
j
=
1
h
(
x
+
t
j
)
{\displaystyle s(x)=\prod _{j=1}^{h}(x+t_{j})}
, где
t
j
∈
Z
p
{\displaystyle t_{j}\in \mathbb {Z} _{p}}
(см. Особенности криптосистемы 5)
Вычислить двоичный вектор
M
=
(
M
0
,
M
1
,
.
.
.
,
M
p
−
1
)
{\displaystyle M=(M_{0},M_{1},...,M_{p-1})}
следующим образом. Компоненты
M
{\displaystyle M}
, которые равны
1
{\displaystyle 1}
, имеют индексы
π
−
1
(
t
j
)
,
1
≤
j
≤
h
{\displaystyle \pi ^{-1}(t_{j}),1\leq j\leq h}
. Остальные компоненты равны
0
{\displaystyle 0}
.
Сообщение
m
{\displaystyle m}
восстанавливается из
M
{\displaystyle M}
следующим образом:
Выбрать
m
=
0
{\displaystyle m=0}
,
l
=
h
{\displaystyle l=h}
Для
i
{\displaystyle i}
от
1
{\displaystyle 1}
до
p
{\displaystyle p}
выполнить следующие действия: Если
M
i
−
1
=
1
{\displaystyle M_{i-1}=1}
, то выбрать
m
=
m
+
(
p
−
i
l
)
{\displaystyle m=m+{\binom {p-i}{l}}}
и
l
=
l
−
1
{\displaystyle l=l-1}
Для доказательства работы схемы можно заметить, что[8]
u
(
x
)
=
g
(
x
)
r
mod
f
(
x
)
≡
g
(
x
)
c
−
h
d
≡
g
(
x
)
(
∑
i
=
0
p
−
1
M
i
c
i
)
−
h
d
(
mod
f
(
x
)
)
≡
g
(
x
)
(
∑
i
=
0
p
−
1
M
i
(
a
π
(
i
)
+
d
)
)
−
h
d
≡
g
(
x
)
∑
i
=
0
p
−
1
M
i
a
π
(
i
)
(
mod
f
(
x
)
)
≡
∏
i
=
0
p
−
1
[
g
(
x
)
a
π
(
i
)
]
M
i
≡
∏
i
=
0
p
−
1
(
x
+
π
(
i
)
)
M
i
(
mod
f
(
x
)
)
{\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}}}
Так как
∏
i
=
0
p
−
1
(
x
+
π
(
i
)
)
M
i
{\displaystyle \textstyle \prod _{i=0}^{p-1}(x+\pi (i))^{M_{i}}\displaystyle }
и
s
(
x
)
{\displaystyle s(x)}
— монические многочлены степени
h
{\displaystyle {\mathit {h}}}
и конгруэнтны по модулю
f
(
x
)
{\displaystyle f(x)}
, то:
s
(
x
)
=
u
(
x
)
+
f
(
x
)
=
∏
i
=
0
p
−
1
(
x
+
π
(
i
)
)
M
i
{\displaystyle s(x)=u(x)+f(x)=\textstyle \prod _{i=0}^{p-1}(x+\pi (i))^{M_{i}}\displaystyle }
Следовательно,
h
{\displaystyle {\mathit {h}}}
корней
s
(
x
)
{\displaystyle s(x)}
все лежат в
Z
p
{\displaystyle \mathbb {Z} _{\mathit {p}}}
, и применение
π
−
1
{\displaystyle \pi ^{-1}}
к этим корням дает координаты
M
{\displaystyle M}
, которые равны
1
{\displaystyle 1}
.
В качестве примера можно рассмотреть работу схемы в случае, когда параметры относительно малы[9]
Для генерации ключей A выполняет следующее:
Выбирает
p
=
7
{\displaystyle p=7}
и
h
=
4
{\displaystyle h=4}
Выбирает неприводимый многочлен
f
(
x
)
=
x
4
+
3
x
3
+
5
x
2
+
6
x
+
2
{\displaystyle f(x)=x^{4}+3x^{3}+5x^{2}+6x+2}
степени
4
{\displaystyle 4}
над
Z
7
{\displaystyle \mathbb {Z} _{7}}
. Элементы конечного поля
F
7
4
{\displaystyle \mathbb {F} _{7^{4}}}
представлены как многочлены от
Z
7
[
x
]
{\displaystyle \mathbb {Z} _{7}[{\mathit {x}}]}
степени меньше
4
{\displaystyle 4}
, причем умножение выполняется по модулю
f
(
x
)
{\displaystyle f(x)}
.
Выбирает случайный примитивный элемент
g
(
x
)
=
3
x
3
+
3
x
2
+
6
{\displaystyle g(x)=3x^{3}+3x^{2}+6}
Вычисляет следующие дискретные логарифмы
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
{\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 }
на
{
0
,
1
,
2
,
3
,
4
,
5
,
6
}
{\displaystyle \{0,1,2,3,4,5,6\}}
, определяемой
π
(
0
)
=
6
,
π
(
1
)
=
4
,
π
(
2
)
=
0
,
π
(
3
)
=
2
,
π
(
4
)
=
1
,
π
(
5
)
=
5
,
π
(
6
)
=
3
{\displaystyle \pi (0)=6,\pi (1)=4,\pi (2)=0,\pi (3)=2,\pi (4)=1,\pi (5)=5,\pi (6)=3}
Выбирает случайное целое число
d
=
1702
{\displaystyle d=1702}
Вычисляет
c
o
=
(
a
6
+
d
)
mod
2
400
=
1925
c
1
=
(
a
4
+
d
)
mod
2
400
=
2081
c
2
=
(
a
0
+
d
)
mod
2
400
=
330
c
3
=
(
a
2
+
d
)
mod
2
400
=
1356
c
4
=
(
a
1
+
d
)
mod
2
400
=
1237
c
5
=
(
a
5
+
d
)
mod
2
400
=
1082
c
6
=
(
a
3
+
d
)
mod
2
400
=
310
{\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}}}
Открытым ключом
A
{\displaystyle {\mathsf {A}}}
является
(
(
c
o
,
c
1
,
c
2
,
c
3
,
c
4
,
c
5
,
c
6
)
,
p
=
7
,
h
=
4
)
{\displaystyle ((c_{o},c_{1},c_{2},c_{3},c_{4},c_{5},c_{6}),p=7,h=4)}
, а закрытый ключ
A
=
(
f
(
x
)
,
g
(
x
)
,
π
,
d
)
{\displaystyle {\mathsf {A}}=(f(x),g(x),\pi ,d)}
Чтобы зашифровать сообщение
m
=
22
{\displaystyle m=22}
для
A
{\displaystyle {\mathsf {A}}}
,
B
{\displaystyle {\mathsf {B}}}
делает следующее:
Получает открытый ключ
A
{\displaystyle {\mathsf {A}}}
открытого ключа
Представляет
m
{\displaystyle m}
как двоичную строку длиной
5
{\displaystyle 5}
:
m
=
10110
{\displaystyle m=10110}
. (так как
⌊
lg
(
7
4
)
=
5
⌋
{\displaystyle \lfloor \lg {\binom {7}{4}}=5\rfloor }
)
Использует метод, описанный на шаге 3 " алгоритма Шифрования ", для преобразования
m
{\displaystyle m}
в бинарный вектор
M
=
(
1
,
0
,
1
,
1
,
0
,
0
,
1
)
{\displaystyle M=(1,0,1,1,0,0,1)}
длины
7
{\displaystyle 7}
.
Вычисляет
c
=
(
c
0
+
c
2
+
c
3
+
c
6
)
mod
2
400
=
1521
{\displaystyle c=(c_{0}+c_{2}+c_{3}+c_{6}){\bmod {2}}400=1521}
Отправляет
c
=
1521
{\displaystyle c=1521}
в
A
{\displaystyle {\mathsf {A}}}
Чтобы расшифровать зашифрованный текст
c
=
1521
{\displaystyle c=1521}
,
A
{\displaystyle {\mathsf {A}}}
делает следующие действия:
Вычисляет
r
=
(
c
−
h
d
)
mod
(
2400
)
=
1913
{\displaystyle r=(c-hd){\bmod {(}}2400)=1913}
Вычисляет
u
(
x
)
=
g
(
x
)
1913
mod
f
(
x
)
=
x
3
+
3
x
2
+
2
x
+
5
{\displaystyle u(x)={g(x)}^{1913}{\bmod {f}}(x)=x^{3}+3x^{2}+2x+5}
Вычисляет
s
(
x
)
=
u
(
x
)
+
f
(
x
)
=
x
4
+
4
x
3
+
x
2
+
x
{\displaystyle s(x)=u(x)+f(x)=x^{4}+4x^{3}+x^{2}+x}
Факторизует
s
(
x
)
=
x
(
x
+
2
)
(
x
+
3
)
(
x
+
6
)
{\displaystyle s(x)=x(x+2)(x+3)(x+6)}
(так
t
1
=
0
{\displaystyle t_{1}=0}
,
t
2
=
2
{\displaystyle t_{2}=2}
,
t
3
=
3
{\displaystyle t_{3}=3}
,
t
4
=
6
{\displaystyle t_{4}=6}
)
Компоненты
M
{\displaystyle M}
, которые равны
1
{\displaystyle 1}
, имеют индексы
π
−
1
(
0
)
=
2
{\displaystyle \pi ^{-1}(0)=2}
,
π
−
1
(
2
)
=
3
{\displaystyle \pi ^{-1}(2)=3}
,
π
−
1
(
3
)
=
6
{\displaystyle \pi ^{-1}(3)=6}
и
π
−
1
(
6
)
=
0
{\displaystyle \pi ^{-1}(6)=0}
. Следовательно,
M
=
(
1
,
0
,
1
,
1
,
0
,
0
,
1
)
{\displaystyle M=(1,0,1,1,0,0,1)}
Использует метод, описанный на шаге 6 " алгоритма дешифрования ", чтобы преобразовать
M
{\displaystyle M}
в целое число
m
=
22
{\displaystyle m=22}
, тем самым восстанавливая исходный текст.
Известно, что система небезопасна, если раскрыты части секретного ключа, например, если известны
g
(
x
)
{\displaystyle g(x)}
и
d
{\displaystyle d}
в некотором представлении
F
q
{\displaystyle \mathbb {F} _{\mathit {q}}}
или если
f
(
x
)
{\displaystyle f(x)}
известно, или если
π
{\displaystyle \pi }
известен[10]
Хотя схема Шор-Ривеста была описана только для случая
p
{\displaystyle p}
простой, она распространяется на случай, когда базовое поле
Z
p
{\displaystyle \mathbb {Z} _{\mathit {p}}}
заменяется полем первичного степенного порядка[11]
Чтобы сделать задачу дискретного логарифма выполнимой на шаге 1 алгоритма " Генерация ключей ", параметры
p
{\displaystyle p}
и
h
{\displaystyle h}
могут быть выбраны так, что
q
=
p
h
−
1
{\displaystyle q=p^{h}-1}
имеет только малые множители. В этом случае для эффективного вычисления дискретных логарифмов можно использовать алгоритм Полига — Хеллмана в конечном поле
F
q
{\displaystyle \mathbb {F} _{\mathit {q}}}
[12]
На практике рекомендуемый размер параметров:
p
≈
200
{\displaystyle p\approx 200}
и
h
≈
25
{\displaystyle h\approx 25}
. Один конкретный выбор первоначально предложенных параметров:
p
=
197
{\displaystyle p=197}
и
h
=
24
{\displaystyle h=24}
; в этом случае наибольший простой коэффициент
197
24
−
1
{\displaystyle 197^{24}-1}
составляет
10316017
{\displaystyle 10316017}
, а плотность набора ранца составляет около
1.077
{\displaystyle 1.077}
. Другие первоначально заданные параметры:
{
p
=
211
,
h
=
24
}
{\displaystyle \{p=211,h=24\}}
,
{
p
=
3
5
,
h
=
24
}
{\displaystyle \{p=3^{5},h=24\}}
(базовое поле
F
3
5
{\displaystyle \mathbb {F} _{3^{5}}}
) и
{
p
=
2
8
,
h
=
25
}
{\displaystyle \{p=2^{8},h=25\}}
(базовое поле
F
2
8
{\displaystyle \mathbb {F} _{2^{8}}}
)[13]
Шифрование — очень быстрая операция. Расшифровка выполняется намного медленнее, узким местом является вычисление
u
(
x
)
{\displaystyle u(x)}
на шаге 2 " алгоритма дешифрования ". Корни
s
(
x
)
{\displaystyle s(x)}
на шаге 4 можно найти, просто попробовав все возможности в
Z
p
{\displaystyle \mathbb {Z} _{\mathit {p}}}
[14]
Основным недостатком схемы Шор-Ривеста является то, что открытый ключ довольно велик, а именно бит
(
p
h
.
lg
p
)
{\displaystyle (ph.\lg p)}
. Для параметров
p
=
197
{\displaystyle p=197}
и
h
=
24
{\displaystyle h=24}
это около 36000 бит[15]
Расширение сообщения происходит в
lg
p
h
/
lg
(
p
h
)
{\displaystyle \lg {p^{h}}/\lg {\binom {p}{h}}}
. Для
p
=
197
{\displaystyle p=197}
и
h
=
24
{\displaystyle h=24}
, это
1.797
{\displaystyle 1.797}
[16]
В этом разделе Serge Vaudenay [англ.] показывает, что он может монтировать атаку, когда раскрывается какая-либо часть секретного ключа. Несколько таких атак уже опубликованы в документе[17] и некоторые из них были улучшены ниже.[18]
Секретные ключи состоят из:
элемент
t
∈
F
q
{\displaystyle t\in \mathbb {F} _{q}}
с степенью
h
{\displaystyle h}
генератор
g
{\displaystyle g}
целое число
d
∈
Z
q
−
1
{\displaystyle d\in \mathbb {Z} _{q-1}}
перестановка
π
{\displaystyle \pi }
на множестве целых чисел
{
0
,
1
,
2
,
.
.
.
,
p
−
1
}
{\displaystyle \{0,1,2,...,p-1\}}
Атака с раскрытием части
t
{\displaystyle t}
Если предположим, что
π
(
0
)
=
i
{\displaystyle \pi (0)=i}
и
π
(
1
)
=
j
{\displaystyle \pi (1)=j}
(из-за симметрии в секретном ключе мы знаем, что будет выполняться произвольный выбор
(
i
,
j
)
{\displaystyle (i,j)}
), мы можем вычислить
log
(
t
+
α
i
)
{\displaystyle \log(t+\alpha _{i})}
и
log
(
t
+
α
j
)
{\displaystyle \log(t+\alpha _{j})}
, то решим систему уравнения:
c
0
=
d
+
log
(
t
+
α
i
)
log
g
{\displaystyle c_{0}=d+{\frac {\log(t+\alpha _{i})}{\log g}}}
c
1
=
d
+
log
(
t
+
α
j
)
log
g
{\displaystyle c_{1}=d+{\frac {\log(t+\alpha _{j})}{\log g}}}
с неизвестными
d
{\displaystyle d}
и
log
g
{\displaystyle \log {g}}
[17]
Атака с раскрытием части
g
{\displaystyle g}
Если предположим, что
π
(
0
)
=
i
{\displaystyle \pi (0)=i}
и
π
(
1
)
=
j
{\displaystyle \pi (1)=j}
(из-за симметрии в секретном ключе мы знаем, что будет выполняться произвольный выбор
(
i
,
j
)
{\displaystyle (i,j)}
), мы можем вычислить:
g
c
0
−
c
1
=
t
+
α
i
t
+
α
j
{\displaystyle g^{c_{0}-c_{1}}={\frac {t+\alpha _{i}}{t+\alpha _{j}}}}
затем разрешить
t
{\displaystyle t}
Атака с раскрытием части
π
{\displaystyle \pi }
Найдем линейную комбинацию с формой
∑
i
=
1
p
−
1
x
i
(
c
i
−
c
0
)
=
0
{\displaystyle \textstyle \sum _{i=1}^{p-1}\displaystyle x_{i}(c_{i}-c_{0})=0}
с относительно небольшими интегральными коэффициентами
x
i
{\displaystyle x_{i}}
. Это можно выполнить с помощью алгоритма Lenstra-Lenstra-Lovász [19] . Мы можем ожидать, что
|
x
i
|
≤
B
{\displaystyle |x_{i}|\leq B}
с
B
≈
p
h
p
−
1
{\displaystyle B\approx p^{\tfrac {h}{p-1}}}
. Обозначая это, получаем некоторое уравнение:
∏
i
∈
I
(
t
+
α
π
(
i
)
)
x
i
=
∏
i
∈
J
(
t
+
α
π
(
j
)
)
−
x
j
{\displaystyle \prod _{i\in I}(t+\alpha _{\pi (i)})^{x_{i}}=\prod _{i\in J}(t+\alpha _{\pi (j)})^{-x_{j}}}
с неотрицательными малыми степенями, который является полиномиальным уравнением с малой степенью, которое может быть эффективно разрешено.[17]
Атака с раскрытием части
π
{\displaystyle \pi }
и
g
p
r
{\displaystyle g_{p^{r}}}
Мы можем интерполировать полином
Q
(
x
)
{\displaystyle Q(x)}
с
h
/
r
+
1
{\displaystyle h/r+1}
парами
(
α
π
(
i
)
,
g
p
r
c
i
)
{\displaystyle (\alpha _{\pi (i)},{g_{p^{r}}}^{c_{i}})}
. Таким образом, мы получаем многочлен
h
/
r
{\displaystyle h/r}
— степени, корни которого являются сопряженными
−
t
{\displaystyle -t}
. Потом мы можем решить его, чтобы получить
t
{\displaystyle t}
и выполнить атаку с раскрытием части
t
{\displaystyle 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 года.
↑ 1 2 3 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 года.
↑ 1 2 3 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 coefficients . — С. 515—534.
Приложения Криптосистемы на основе задачи о ранце Дополнительно
Алгоритмы
Теория Стандарты Темы