ACE (Advanced Cryptographic Engine ) — набор программных средств, реализующих шифрование в режиме схемы шифрования с открытым ключом, а также в режиме цифровой подписи. Соответствующие названия этих режимов — «ACE Encrypt» и «ACE Sign». Схемы являются вариантами реализации схем Крамера-Шоупа. Внесённые изменения нацелены на достижение наилучшего баланса между производительностью и безопасностью всей системы шифрования.
Все алгоритмы , написанные в ACE, основаны на алгоритмах, разработанных Виктором Шоупом (Victor Shoup) и Рональдом Крамером (Ronald Cramer). Полная спецификация алгоритмов написана Виктором Шоупом. Реализация алгоритмов выполнена Томасом Швейнбергером(Thomas Schweinberger) и Медди Нассей (Mehdi Nassehi), их поддержкой и развитием занимается Виктор Шоуп. Томас Швейнберг принимал участие в составлении документа спецификаций ACE, а также написал руководство пользователя.Дания . Он принимал участие в работе, относящейся к ACE Encrypt пока находился в ETH в Цюрихе , Швейцария .
Доказательство безопасности схемы шифрования и схемы цифровой подписи в ACE проводится с использованием обоснованных и естественных допущений.
Четырьмя основными допущениями являются:
Допущение Диффи-Хеллмана
Сильное допущение RSA
Стойкость к коллизиям на второй прообраз в SHA-1
Псевдо-случайность режима сумматора/счётчика MARS
править
Приведём определения некоторых обозначений и терминов, используемых в данной статье.
править
Z
{\displaystyle Z}
F
2
[
T
]
{\displaystyle F_{2}[T]}
F
2
{\displaystyle F_{2}}
A
r
e
m
n
{\displaystyle Aremn}
r
∈
{
0
,
.
.
.
,
n
−
1
}
{\displaystyle r\in \left\{0,...,n-1\right\}}
A
≡
r
(
m
o
d
n
)
{\displaystyle A\equiv r(modn)}
n
>
0
{\displaystyle n>0}
A
∈
Z
{\displaystyle A\in Z}
A
r
e
m
f
{\displaystyle Aremf}
r
∈
F
2
[
T
]
{\displaystyle r\in F_{2}[T]}
d
e
g
(
r
)
<
d
e
g
(
f
)
{\displaystyle deg(r)<deg(f)}
A
≡
r
(
m
o
d
f
)
{\displaystyle A\equiv r(modf)}
A
,
f
∈
F
2
[
T
]
,
f
≠
0
{\displaystyle A,f\in F_{2}[T],f\neq 0}
править
A
∗
{\displaystyle A^{\ast }}
A
n
{\displaystyle A^{n}}
x
∈
A
∗
L
(
x
)
{\displaystyle x\in A^{\ast }L(x)}
x
{\displaystyle x}
λ
A
{\displaystyle \lambda _{A}}
x
,
y
∈
A
∗
{\displaystyle x,y\in A^{\ast }}
x
|
|
y
{\displaystyle x||y}
x
{\displaystyle x}
y
{\displaystyle y}
b
=
d
e
f
{
0
,
1
}
{\displaystyle b{\stackrel {\mathrm {def} }{=}}\left\{0,1\right\}}
b
,
b
n
1
,
(
b
n
1
)
n
2
,
.
.
.
{\displaystyle b,b^{n_{1}},(b^{n_{1}})^{n_{2}},...}
0
b
=
d
e
f
0
∈
b
{\displaystyle 0_{b}{\stackrel {\mathrm {def} }{=}}0\in b}
0
A
n
=
d
e
f
(
0
A
,
.
.
.
,
0
A
)
∈
A
n
{\displaystyle 0_{A^{n}}{\stackrel {\mathrm {def} }{=}}(0_{A},...,0_{A})\in A^{n}}
n
>
0
{\displaystyle n>0}
Определим
B
=
d
e
f
b
8
{\displaystyle B{\stackrel {\mathrm {def} }{=}}b^{8}}
W
=
d
e
f
b
32
{\displaystyle W{\stackrel {\mathrm {def} }{=}}b^{32}}
Для
x
∈
A
∗
{\displaystyle x\in A^{\ast }}
A
∈
{
b
,
B
,
W
}
{\displaystyle A\in \left\{b,B,W\right\}}
l
>
0
{\displaystyle l>0}
p
a
d
l
(
x
)
=
d
e
f
{
x
,
L
(
x
)
≥
l
x
|
|
0
A
l
−
L
(
x
)
,
L
(
x
)
<
l
{\displaystyle pad_{l}(x){\stackrel {\mathrm {def} }{=}}{\begin{cases}x,&L(x)\geq l\\x||0_{A^{l-L(x)}},&L(x)<l\end{cases}}}
Оператор преобразования
I
s
r
c
d
s
t
:
s
r
c
→
d
s
t
{\displaystyle I_{src}^{dst}:src\rightarrow dst}
Z
,
F
2
[
T
]
,
b
∗
,
B
∗
,
W
∗
{\displaystyle Z,F_{2}[T],b^{\ast },B^{\ast },W^{\ast }}
В схеме шифрования ACE задействованы два типа ключей:
(
P
,
q
,
g
1
,
g
2
,
c
,
d
,
h
1
,
h
2
,
k
1
,
k
2
)
{\displaystyle (P,q,g_{1},g_{2},c,d,h_{1},h_{2},k_{1},k_{2})}
(
w
,
x
,
y
,
z
1
,
z
2
)
{\displaystyle (w,x,y,z_{1},z_{2})}
m
{\displaystyle m}
1024
≤
m
≤
16384
{\displaystyle 1024\leq m\leq 16384}
q
{\displaystyle q}
P
{\displaystyle P}
P
≡
1
(
m
o
d
q
)
{\displaystyle P\equiv 1(modq)}
g
1
,
g
2
,
c
,
d
,
h
1
,
h
2
{\displaystyle g_{1},g_{2},c,d,h_{1},h_{2}}
{
1
,
.
.
.
,
P
−
1
}
{\displaystyle \left\{1,...,P-1\right\}}
P
{\displaystyle P}
q
{\displaystyle q}
w
,
x
,
y
,
z
1
,
z
2
{\displaystyle w,x,y,z_{1},z_{2}}
{
0
,
.
.
.
,
q
−
1
}
{\displaystyle \left\{0,...,q-1\right\}}
k
1
,
k
2
{\displaystyle k_{1},k_{2}}
B
∗
{\displaystyle B^{\ast }}
L
(
k
1
)
=
20
l
′
+
64
{\displaystyle L(k_{1})=20l^{\prime }+64}
L
(
k
2
)
=
32
⌈
l
/
16
⌉
+
40
{\displaystyle L(k_{2})=32\left\lceil l/16\right\rceil +40}
l
=
⌈
m
/
8
⌉
{\displaystyle l=\left\lceil m/8\right\rceil }
l
′
=
L
b
(
⌈
(
2
⌈
l
/
4
⌉
+
4
)
/
16
⌉
)
{\displaystyle l^{\prime }=L_{b}(\left\lceil (2\left\lceil l/4\right\rceil +4)/16\right\rceil )}
Алгоритм. Генерация ключа для схемы шифрования ACE.
m
{\displaystyle m}
1024
≤
m
≤
16384
{\displaystyle 1024\leq m\leq 16384}
Сгенерировать случайное простое число
q
{\displaystyle q}
2
255
<
q
<
2
256
{\displaystyle 2^{255}<q<2^{256}}
Сгенерировать случайное простое число
P
{\displaystyle P}
2
m
−
1
<
P
<
2
m
{\displaystyle 2^{m-1}<P<2^{m}}
P
≡
1
(
m
o
d
q
)
{\displaystyle P\equiv 1(modq)}
Сгенерировать случайное целое число
g
1
∈
{
2
,
.
.
.
,
P
−
1
}
{\displaystyle g_{1}\in \left\{2,...,P-1\right\}}
g
1
q
≡
1
(
m
o
d
P
)
{\displaystyle g_{1}^{q}\equiv 1(modP)}
Сгенерировать случайные целые числа
w
∈
{
1
,
.
.
.
,
q
−
1
}
{\displaystyle w\in \left\{1,...,q-1\right\}}
x
,
y
,
z
1
,
z
2
∈
{
0
,
.
.
.
,
q
−
1
}
{\displaystyle x,y,z_{1},z_{2}\in \left\{0,...,q-1\right\}}
Вычислить следующие целые числа в
{
1
,
.
.
.
,
P
−
1
}
{\displaystyle \left\{1,...,P-1\right\}}
g
2
←
g
1
w
r
e
m
P
{\displaystyle g_{2}\leftarrow g_{1}^{w}remP}
c
←
g
1
x
r
e
m
P
{\displaystyle c\leftarrow g_{1}^{x}remP}
d
←
g
1
y
r
e
m
P
{\displaystyle d\leftarrow g_{1}^{y}remP}
h
1
←
g
1
z
1
r
e
m
P
{\displaystyle h_{1}\leftarrow g_{1}^{z_{1}}remP}
h
2
←
g
1
z
2
r
e
m
P
{\displaystyle h_{2}\leftarrow g_{1}^{z_{2}}remP}
Сгенерировать случайные байтовые строки
k
1
∈
B
20
l
′
+
64
{\displaystyle k_{1}\in B^{20l^{\prime }+64}}
k
2
∈
B
2
⌈
l
/
16
⌉
+
40
{\displaystyle k_{2}\in B^{2\left\lceil l/16\right\rceil +40}}
l
=
L
B
(
P
)
{\displaystyle l=L_{B}(P)}
l
′
=
L
B
(
⌈
(
2
⌈
l
/
4
⌉
+
4
)
/
16
⌉
)
{\displaystyle l^{\prime }=L_{B}(\left\lceil (2\left\lceil l/4\right\rceil +4)/16\right\rceil )}
Вернуть пару открытый/закрытый ключ
(
(
P
,
q
,
g
1
,
g
2
,
c
,
d
,
h
1
,
h
2
,
k
1
,
k
2
)
,
(
w
,
x
,
y
,
z
1
,
z
2
)
)
{\displaystyle ((P,q,g_{1},g_{2},c,d,h_{1},h_{2},k_{1},k_{2}),(w,x,y,z_{1},z_{2}))}
Шифротекст в схеме шифрования ACE имеет вид
(
s
,
u
1
,
u
2
,
v
,
e
)
{\displaystyle (s,u_{1},u_{2},v,e)}
где компоненты определяются следующим образом:
u
1
,
u
2
,
v
{\displaystyle u_{1},u_{2},v}
{
1
,
.
.
.
,
P
−
1
}
{\displaystyle \left\{1,...,P-1\right\}}
P
{\displaystyle P}
q
{\displaystyle q}
s
{\displaystyle s}
W
4
{\displaystyle W^{4}}
e
{\displaystyle e}
B
∗
{\displaystyle B^{\ast }}
s
,
u
1
,
u
2
,
v
{\displaystyle s,u_{1},u_{2},v}
преамбулой , а
e
{\displaystyle e}
криптограммой . Если текст — строка из
l
{\displaystyle l}
e
{\displaystyle e}
l
+
16
⌈
l
/
1024
⌉
{\displaystyle l+16\left\lceil l/1024\right\rceil }
Необходимо ввести функцию
C
E
n
c
o
d
e
{\displaystyle CEncode}
C
D
e
c
o
d
e
{\displaystyle CDecode}
l
>
0
{\displaystyle l>0}
s
∈
W
4
{\displaystyle s\in W^{4}}
0
≤
u
1
,
u
2
,
v
<
256
l
{\displaystyle 0\leq u_{1},u_{2},v<256^{l}}
e
∈
B
∗
{\displaystyle e\in B^{\ast }}
C
E
n
c
o
d
e
(
l
,
s
,
u
1
,
u
2
,
v
,
e
)
=
d
e
f
I
W
∗
B
∗
(
s
)
|
|
p
a
d
l
(
I
Z
B
∗
(
u
1
)
)
|
|
p
a
d
l
(
I
Z
B
∗
(
u
2
)
)
|
|
p
a
d
l
(
I
Z
B
∗
(
v
)
)
|
|
e
∈
B
∗
{\displaystyle CEncode(l,s,u_{1},u_{2},v,e){\stackrel {\mathrm {def} }{=}}I_{W^{\ast }}^{B^{\ast }}(s)||pad_{l}(I_{Z}^{B^{\ast }}(u_{1}))||pad_{l}(I_{Z}^{B^{\ast }}(u_{2}))||pad_{l}(I_{Z}^{B^{\ast }}(v))||e\in B^{\ast }}
l
>
0
{\displaystyle l>0}
ψ
∈
B
∗
{\displaystyle \psi \in B^{\ast }}
L
(
ψ
)
≥
3
l
+
16
{\displaystyle L(\psi )\geq 3l+16}
C
D
e
c
o
d
e
(
l
,
ψ
)
=
d
e
f
(
I
B
∗
W
∗
(
[
ψ
]
0
16
)
,
I
B
∗
Z
(
[
ψ
]
16
16
+
l
)
,
I
B
∗
Z
(
[
ψ
]
16
+
l
16
+
2
l
)
,
I
B
∗
Z
(
[
ψ
]
16
+
2
l
16
+
3
l
)
,
[
ψ
]
16
+
3
l
L
(
ψ
)
)
∈
W
4
×
Z
×
Z
×
Z
×
B
∗
{\displaystyle CDecode(l,\psi ){\stackrel {\mathrm {def} }{=}}(I_{B^{\ast }}^{W^{\ast }}({\Bigl [}\psi {\Bigr ]}_{0}^{16}),I_{B^{\ast }}^{Z}({\Bigl [}\psi {\Bigr ]}_{16}^{16+l}),I_{B^{\ast }}^{Z}({\Bigl [}\psi {\Bigr ]}_{16+l}^{16+2l}),I_{B^{\ast }}^{Z}({\Bigl [}\psi {\Bigr ]}_{16+2l}^{16+3l}),{\Bigl [}\psi {\Bigr ]}_{16+3l}^{L(\psi )})\in W^{4}\times Z\times Z\times Z\times B^{\ast }}
Алгоритм. Асимметричный процесс шифрования ACE.
(
P
,
q
,
g
1
,
g
2
,
c
,
d
,
h
1
,
h
2
,
k
1
,
k
2
)
{\displaystyle (P,q,g_{1},g_{2},c,d,h_{1},h_{2},k_{1},k_{2})}
M
∈
B
∗
{\displaystyle M\in B^{\ast }}
ψ
{\displaystyle \psi \ }
M
{\displaystyle M}
Сгенерировать случайное
r
∈
{
0
,
.
.
.
,
q
−
1
}
{\displaystyle r\in \left\{0,...,q-1\right\}}
Сгенерировать преамбулу шифротекста:
Сгенерировать
s
∈
W
4
{\displaystyle s\in W^{4}}
Вычислить
u
1
←
g
1
r
r
e
m
P
{\displaystyle u_{1}\leftarrow g_{1}^{r}remP}
u
2
←
g
2
r
r
e
m
P
{\displaystyle u_{2}\leftarrow g_{2}^{r}remP}
Вычислить
α
←
U
O
W
H
a
s
h
′
(
k
1
,
L
B
(
P
)
,
s
,
u
1
,
u
2
)
∈
Z
{\displaystyle \alpha \ \leftarrow UOWHash^{\prime }(k_{1},L_{B}(P),s,u_{1},u_{2})\in Z}
0
<
α
<
2
160
{\displaystyle 0<\alpha \ <2^{160}}
Вычислить
v
←
c
r
d
α
r
r
e
m
P
{\displaystyle v\leftarrow c^{r}d^{\alpha \ r}remP}
Вычислить ключ для операции симметричного шифрования:
h
1
~
←
h
1
r
r
e
m
P
{\displaystyle {\tilde {h_{1}}}\leftarrow h_{1}^{r}remP}
h
2
~
←
h
2
r
r
e
m
P
{\displaystyle {\tilde {h_{2}}}\leftarrow h_{2}^{r}remP}
Вычислить
k
←
E
S
H
a
s
h
(
k
,
L
B
(
P
)
,
s
,
u
1
,
u
2
,
h
1
~
,
h
2
~
)
∈
W
8
{\displaystyle k\leftarrow ESHash(k,L_{B}(P),s,u_{1},u_{2},{\tilde {h_{1}}},{\tilde {h_{2}}})\in W^{8}}
Вычислить криптограмму
e
←
S
E
n
c
(
k
,
s
,
1024
,
M
)
{\displaystyle e\leftarrow SEnc(k,s,1024,M)}
Закодировать шифротекст:
ψ
←
C
E
n
c
o
d
e
(
L
B
(
P
)
,
s
,
u
1
,
u
2
,
v
,
e
)
{\displaystyle \psi \ \leftarrow CEncode(L_{B}(P),s,u_{1},u_{2},v,e)}
Вернуть
ψ
{\displaystyle \psi \ }
Перед запуском процесса симметричного шифрования входное сообщение
M
∈
B
∗
{\displaystyle M\in B^{\ast }}
M
1
,
.
.
.
,
M
t
{\displaystyle M_{1},...,M_{t}}
E
i
{\displaystyle E_{i}}
e
=
E
1
|
|
C
1
|
|
.
.
.
|
|
E
t
|
|
C
t
{\displaystyle e=E_{1}||C_{1}||...||E_{t}||C_{t}}
L
(
e
)
=
L
(
M
)
+
16
⌈
L
(
M
)
/
m
⌉
{\displaystyle L(e)=L(M)+16\left\lceil L(M)/m\right\rceil }
L
(
M
)
=
0
{\displaystyle L(M)=0}
L
(
e
)
=
0
{\displaystyle L(e)=0}
Алгоритм. Симметричный процесс шифрования ACE.
(
k
,
s
,
M
,
m
)
∈
W
8
×
W
4
×
Z
×
B
∗
{\displaystyle (k,s,M,m)\in W^{8}\times W^{4}\times Z\times B^{\ast }}
m
>
0
{\displaystyle m>0}
e
∈
B
l
{\displaystyle e\in B^{l}}
l
=
L
(
M
)
+
16
⌈
L
(
N
)
/
m
⌉
{\displaystyle l=L(M)+16\left\lceil L(N)/m\right\rceil }
Если
M
=
λ
B
{\displaystyle M=\lambda _{B}}
λ
B
{\displaystyle \lambda _{B}}
Проинициализировать генератор псевдо-случайных чисел:
g
e
n
S
t
a
t
e
←
I
n
i
t
G
e
n
(
k
,
s
)
∈
G
e
n
S
t
a
t
e
{\displaystyle genState\leftarrow InitGen(k,s)\in GenState}
Сгенерировать ключ
k
A
X
U
A
X
U
H
a
s
h
{\displaystyle k_{AXU}AXUHash}
(
k
A
X
U
,
g
e
n
S
t
a
t
e
)
←
G
e
n
W
o
r
d
s
(
(
5
L
b
(
⌈
m
/
64
⌉
)
+
24
)
,
g
e
n
S
t
a
t
e
)
.
{\displaystyle (k_{AXU},genState)\leftarrow GenWords((5L_{b}(\left\lceil m/64\right\rceil )+24),genState).}
e
←
λ
B
,
i
←
0
{\displaystyle e\leftarrow \lambda _{B},i\leftarrow 0}
Пока
i
<
L
(
M
)
{\displaystyle i<L(M)}
r
←
m
i
n
(
L
(
M
)
−
i
,
m
)
{\displaystyle r\leftarrow min(L(M)-i,m)}
Сгенерировать значения масок для шифрования и MAC:
(
m
a
s
k
m
,
g
e
n
S
t
a
t
e
)
←
G
e
n
W
o
r
d
s
(
4
,
g
e
n
S
t
a
t
e
)
{\displaystyle (mask_{m},genState)\leftarrow GenWords(4,genState)}
(
m
a
s
k
e
,
g
e
n
S
t
a
t
e
)
←
G
e
n
W
o
r
d
s
(
r
,
g
e
n
S
t
a
t
e
)
{\displaystyle (mask_{e},genState)\leftarrow GenWords(r,genState)}
Зашифровать текст:
e
n
c
←
[
M
]
i
i
+
r
⊕
m
a
s
k
e
{\displaystyle enc\leftarrow {\Bigl [}M{\Bigr ]}_{i}^{i+r}\oplus mask_{e}}
Сгенерировать аутентификационный код сообщения:
Если
i
+
r
=
L
(
M
)
{\displaystyle i+r=L(M)}
l
a
s
t
B
l
o
c
k
←
1
{\displaystyle lastBlock\leftarrow 1}
l
a
s
t
B
l
o
c
k
←
0
{\displaystyle lastBlock\leftarrow 0}
m
a
c
←
A
X
U
H
a
s
h
(
k
A
X
U
,
l
a
s
t
B
l
o
c
k
,
e
n
c
)
∈
W
4
{\displaystyle mac\leftarrow AXUHash(k_{AXU},lastBlock,enc)\in W^{4}}
Обновить шифротекст:
e
←
e
|
|
e
n
c
|
|
I
W
∗
B
∗
(
m
a
c
⊕
m
a
s
k
m
)
{\displaystyle e\leftarrow e||enc||I_{W^{\ast }}^{B^{\ast }}(mac\oplus mask_{m})}
i
←
i
+
r
{\displaystyle i\leftarrow i+r}
Вернуть
e
{\displaystyle e}
Алгоритм. Процесс дешифрования ACE.
(
P
,
q
,
g
1
,
g
2
,
c
,
d
,
h
1
,
h
2
,
k
1
,
k
2
)
{\displaystyle (P,q,g_{1},g_{2},c,d,h_{1},h_{2},k_{1},k_{2})}
(
w
,
x
,
y
,
z
1
,
z
2
)
{\displaystyle (w,x,y,z_{1},z_{2})}
ψ
∈
B
∗
{\displaystyle \psi \in B^{\ast }}
M
∈
B
∗
∪
R
e
j
e
c
t
{\displaystyle M\in B^{\ast }\cup {Reject}}
Дешифровать шифротекст:
Если
L
(
ψ
)
<
3
L
B
(
P
)
+
16
{\displaystyle L(\psi )<3L_{B}(P)+16}
R
e
j
e
c
t
{\displaystyle Reject}
Вычислить:
(
s
,
u
1
,
u
2
,
v
,
e
)
←
C
D
e
c
o
d
e
(
L
B
(
P
)
,
ψ
)
∈
W
4
×
Z
×
Z
×
Z
×
B
∗
{\displaystyle (s,u_{1},u_{2},v,e)\leftarrow CDecode(L_{B}(P),\psi )\in W^{4}\times Z\times Z\times Z\times B^{\ast }}
0
≤
u
1
,
u
2
,
v
<
256
l
{\displaystyle 0\leq u_{1},u_{2},v<256^{l}}
l
=
L
B
(
P
)
{\displaystyle l=L_{B}(P)}
Подтвердить преамбулу шифротекста:
Если
u
1
≥
P
{\displaystyle u_{1}\geq P}
u
2
≥
P
{\displaystyle u_{2}\geq P}
v
≥
P
{\displaystyle v\geq P}
R
e
j
e
c
t
{\displaystyle Reject}
Если
u
1
q
≠
1
r
e
m
P
{\displaystyle u_{1}^{q}\neq 1remP}
R
e
j
e
c
t
{\displaystyle Reject}
r
e
j
e
c
t
←
0
{\displaystyle reject\leftarrow 0}
Если
u
2
≠
u
1
w
r
e
m
P
{\displaystyle u_{2}\neq u_{1}^{w}remP}
r
e
j
e
c
t
←
1
{\displaystyle reject\leftarrow 1}
Вычислить
α
←
U
O
W
H
a
s
h
′
(
k
1
,
L
B
(
P
)
,
s
,
u
1
,
u
2
)
∈
Z
{\displaystyle \alpha \leftarrow UOWHash^{\prime }(k_{1},L_{B}(P),s,u_{1},u_{2})\in Z}
0
≤
α
≤
2
160
{\displaystyle 0\leq \alpha \leq 2^{160}}
Если
v
≠
u
1
x
+
α
y
r
e
m
P
{\displaystyle v\neq u_{1}^{x+{\alpha }y}remP}
r
e
j
e
c
t
←
1
{\displaystyle reject\leftarrow 1}
Если
r
e
j
e
c
t
=
1
{\displaystyle reject=1}
R
e
j
e
c
t
{\displaystyle Reject}
Вычислить ключ для процесс симметричного дешифрования:
h
1
~
←
u
1
z
1
r
e
m
P
{\displaystyle {\tilde {h_{1}}}\leftarrow u_{1}^{z_{1}}remP}
h
2
~
←
u
1
z
2
r
e
m
P
{\displaystyle {\tilde {h_{2}}}\leftarrow u_{1}^{z_{2}}remP}
Вычислить
k
←
E
S
H
a
s
h
(
k
2
,
L
B
(
P
)
,
s
,
u
1
,
h
1
~
,
h
2
~
)
∈
W
8
{\displaystyle k\leftarrow ESHash(k_{2},L_{B}(P),s,u_{1},{\tilde {h_{1}}},{\tilde {h_{2}}})\in W^{8}}
Вычислить
M
←
S
D
e
c
(
k
,
s
,
1024
,
e
)
{\displaystyle M\leftarrow SDec(k,s,1024,e)}
S
D
e
c
{\displaystyle SDec}
R
e
j
e
c
t
{\displaystyle Reject}
Вернуть
M
{\displaystyle M}
Алгоритм. Операция дешифрования
S
D
e
c
{\displaystyle SDec}
(
k
,
s
,
m
,
e
)
∈
W
8
×
W
4
×
Z
×
B
∗
{\displaystyle (k,s,m,e)\in W^{8}\times W^{4}\times Z\times B^{\ast }}
m
>
0
{\displaystyle m>0}
M
∈
B
∗
∪
R
e
j
e
c
t
{\displaystyle M\in B^{\ast }\cup {Reject}}
Если
e
=
λ
B
{\displaystyle e=\lambda _{B}}
λ
B
{\displaystyle \lambda _{B}}
Проинициализировать генератор псевдо-случайных чисел:
g
e
n
S
t
a
t
e
←
I
n
i
t
G
e
n
(
k
,
s
)
∈
G
e
n
S
t
a
t
e
{\displaystyle genState\leftarrow InitGen(k,s)\in GenState}
Сгенерировать ключ
k
A
X
U
A
X
U
H
a
s
h
{\displaystyle k_{AXU}AXUHash}
(
k
A
X
U
,
g
e
n
S
t
a
t
e
′
)
←
G
e
n
W
o
r
d
s
(
(
5
L
b
(
⌈
m
/
64
⌉
)
+
24
)
,
g
e
n
S
t
a
t
e
)
.
{\displaystyle (k_{AXU},genState^{\prime })\leftarrow GenWords((5L_{b}(\left\lceil m/64\right\rceil )+24),genState).}
M
←
λ
B
,
i
←
0
{\displaystyle M\leftarrow \lambda _{B},i\leftarrow 0}
Пока
i
<
L
(
e
)
{\displaystyle i<L(e)}
r
←
m
i
n
(
L
(
e
)
−
i
,
m
+
16
)
−
16
{\displaystyle r\leftarrow min(L(e)-i,m+16)-16}
Если
r
≤
0
{\displaystyle r\leq 0}
R
e
j
e
c
t
{\displaystyle Reject}
Сгенерировать значения масок для шифрования и MAC:
(
m
a
s
k
m
,
g
e
n
S
t
a
t
e
)
←
G
e
n
W
o
r
d
s
(
4
,
g
e
n
S
t
a
t
e
)
{\displaystyle (mask_{m},genState)\leftarrow GenWords(4,genState)}
(
m
a
s
k
e
,
g
e
n
S
t
a
t
e
)
←
G
e
n
W
o
r
d
s
(
r
,
g
e
n
S
t
a
t
e
)
{\displaystyle (mask_{e},genState)\leftarrow GenWords(r,genState)}
Подтвердить аутентификационный код сообщения:
Если
i
+
r
+
16
=
L
(
M
)
{\displaystyle i+r+16=L(M)}
l
a
s
t
b
l
o
c
k
←
1
{\displaystyle lastblock\leftarrow 1}
l
a
s
t
b
l
o
c
k
←
0
{\displaystyle lastblock\leftarrow 0}
m
a
c
←
A
X
U
H
a
s
h
(
k
A
X
U
,
l
a
s
t
B
l
o
c
k
,
[
e
]
i
i
+
r
)
∈
W
4
{\displaystyle mac\leftarrow AXUHash(k_{AXU},lastBlock,{\Bigl [}e{\Bigr ]}_{i}^{i+r})\in W^{4}}
Если
[
e
]
r
i
+
r
i
+
r
+
16
≠
I
W
∗
B
∗
(
m
a
c
⊕
m
a
s
k
m
)
{\displaystyle {\Bigl [}e{\Big ]}r_{i+r}^{i+r+16}\neq I_{W^{\ast }}^{B^{\ast }}(mac\oplus mask_{m})}
R
e
j
e
c
t
{\displaystyle Reject}
Обновить текст:
M
←
M
|
|
(
[
e
]
i
i
+
r
)
⊕
m
a
s
k
e
)
{\displaystyle M\leftarrow M||({\Bigl [}e{\Bigr ]}_{i}^{i+r})\oplus mask_{e})}
i
←
i
+
r
+
16
{\displaystyle i\leftarrow i+r+16}
Вернуть
M
{\displaystyle M}
В схеме цифровой подписи ACE задействованы два типа ключей:
(
N
,
h
,
x
,
e
′
,
k
′
,
s
)
{\displaystyle (N,h,x,e^{\prime },k^{\prime },s)}
(
p
,
q
,
a
)
{\displaystyle (p,q,a)}
m
{\displaystyle m}
1024
≤
m
≤
16384
{\displaystyle 1024\leq m\leq 16384}
p
{\displaystyle p}
⌊
m
/
2
⌋
{\displaystyle \left\lfloor m/2\right\rfloor }
(
p
−
1
)
/
2
{\displaystyle (p-1)/2}
q
{\displaystyle q}
⌊
m
/
2
⌋
{\displaystyle \left\lfloor m/2\right\rfloor }
(
q
−
1
)
/
2
{\displaystyle (q-1)/2}
N
{\displaystyle N}
N
=
p
q
{\displaystyle N=pq}
m
{\displaystyle m}
m
−
1
{\displaystyle m-1}
h
,
x
{\displaystyle h,x}
{
1
,
.
.
.
,
N
−
1
}
{\displaystyle \left\{1,...,N-1\right\}}
N
{\displaystyle N}
e
′
{\displaystyle e^{\prime }}
a
{\displaystyle a}
{
0
,
.
.
.
,
(
p
−
1
)
(
q
−
1
)
/
4
−
1
}
{\displaystyle \left\{0,...,(p-1)(q-1)/4-1\right\}}
k
′
{\displaystyle k^{\prime }}
B
184
{\displaystyle B^{184}}
s
{\displaystyle s}
B
32
{\displaystyle B^{32}}
Алгоритм. Генерация ключа для схемы цифровой подписи ACE.
m
{\displaystyle m}
1024
≤
m
≤
16384
{\displaystyle 1024\leq m\leq 16384}
Сгенерировать случайные простые числа
p
,
q
{\displaystyle p,q}
(
p
−
1
)
/
2
{\displaystyle (p-1)/2}
(
q
−
1
)
/
2
{\displaystyle (q-1)/2}
2
m
1
−
1
<
p
<
2
m
1
{\displaystyle 2^{m_{1}-1}<p<2^{m_{1}}}
2
m
2
−
1
<
q
<
2
m
2
{\displaystyle 2^{m_{2}-1}<q<2^{m_{2}}}
p
≠
q
{\displaystyle p\neq q}
m
1
=
⌊
m
/
2
⌋
{\displaystyle m_{1}=\left\lfloor m/2\right\rfloor }
m
1
=
⌈
m
/
2
⌉
{\displaystyle m_{1}=\left\lceil m/2\right\rceil }
Положить
N
←
p
q
{\displaystyle N\leftarrow pq}
Сгенерировать случайное простое число
e
′
{\displaystyle e^{\prime }}
2
160
≤
e
′
≤
2
161
{\displaystyle 2^{160}\leq e^{\prime }\leq 2^{161}}
Сгенерировать случайное
h
′
∈
{
1
,
.
.
.
,
N
−
1
}
{\displaystyle h^{\prime }\in \left\{1,...,N-1\right\}}
g
c
d
(
h
′
,
N
)
=
1
{\displaystyle gcd(h^{\prime },N)=1}
g
c
d
(
h
′
±
1
,
N
)
=
1
{\displaystyle gcd(h^{\prime }\pm 1,N)=1}
h
←
(
h
′
)
−
2
r
e
m
N
{\displaystyle h\leftarrow (h^{\prime })^{-2}remN}
Сгенерировать случайное
a
∈
{
0
,
.
.
.
,
(
p
−
1
)
(
q
−
1
)
/
4
−
1
}
{\displaystyle a\in \left\{0,...,(p-1)(q-1)/4-1\right\}}
x
←
h
a
r
e
m
N
{\displaystyle x\leftarrow h^{a}remN}
Сгенерировать случайные байтовые строки
k
′
∈
B
184
{\displaystyle k^{\prime }\in B^{184}}
s
∈
B
32
{\displaystyle s\in B^{32}}
Вернуть пару открытый ключ/закрытый ключ
(
(
N
,
h
,
x
,
e
′
,
k
′
,
s
)
,
(
p
,
q
,
a
)
)
{\displaystyle ((N,h,x,e^{\prime },k^{\prime },s),(p,q,a))}
Подпись в схеме цифровой подписи ACE имеет вид
(
d
,
w
,
y
,
y
′
,
k
~
)
{\displaystyle (d,w,y,y^{\prime },{\tilde {k}})}
d
{\displaystyle d}
B
64
{\displaystyle B^{64}}
w
{\displaystyle w}
2
160
≤
w
≤
2
161
{\displaystyle 2^{160}\leq w\leq 2^{161}}
y
,
y
′
{\displaystyle y,y^{\prime }}
{
1
,
.
.
.
,
N
−
1
}
{\displaystyle \left\{1,...,N-1\right\}}
k
~
{\displaystyle {\tilde {k}}}
B
∗
{\displaystyle B^{\ast }}
L
(
k
~
)
=
64
+
20
L
B
(
⌈
(
L
(
M
)
+
8
)
/
64
⌉
)
{\displaystyle L({\tilde {k}})=64+20L_{B}(\left\lceil (L(M)+8)/64\right\rceil )}
M
{\displaystyle M}
Необходимо ввести функцию
S
E
n
c
o
d
e
{\displaystyle SEncode}
S
D
e
c
o
d
e
{\displaystyle SDecode}
l
>
0
{\displaystyle l>0}
d
∈
B
64
{\displaystyle d\in B^{64}}
0
≤
w
≤
256
21
{\displaystyle 0\leq w\leq 256^{21}}
0
≤
y
,
y
′
<
256
l
{\displaystyle 0\leq y,y^{\prime }<256^{l}}
k
~
∈
B
∗
{\displaystyle {\tilde {k}}\in B^{\ast }}
S
E
n
c
o
d
e
(
l
,
d
,
w
,
y
,
y
′
,
k
~
)
=
d
e
f
d
|
|
p
a
d
21
(
I
Z
B
∗
(
w
)
)
|
|
p
a
d
l
(
I
Z
B
∗
(
y
)
)
|
|
p
a
d
l
(
I
Z
B
∗
(
y
′
)
)
|
|
k
~
∈
B
∗
{\displaystyle SEncode(l,d,w,y,y^{\prime },{\tilde {k}}){\stackrel {\mathrm {def} }{=}}d||pad_{21}(I_{Z}^{B^{\ast }}(w))||pad_{l}(I_{Z}^{B^{\ast }}(y))||pad_{l}(I_{Z}^{B^{\ast }}(y^{\prime }))||{\tilde {k}}\in B^{\ast }}
l
>
0
{\displaystyle l>0}
σ
∈
B
∗
{\displaystyle \sigma \in B^{\ast }}
L
(
σ
)
≥
2
l
+
53
{\displaystyle L(\sigma )\geq 2l+53}
C
S
e
c
o
d
e
(
l
,
σ
)
=
d
e
f
(
[
σ
]
0
64
,
I
B
∗
Z
(
[
σ
]
64
85
)
,
I
B
∗
Z
(
[
σ
]
85
85
+
l
)
,
I
B
∗
Z
(
[
σ
]
85
+
l
85
+
2
l
)
,
[
σ
]
85
+
2
l
L
(
σ
)
)
∈
B
64
×
Z
×
Z
×
Z
×
B
∗
{\displaystyle CSecode(l,\sigma ){\stackrel {\mathrm {def} }{=}}({\Bigl [}\sigma {\Bigr ]}_{0}^{64},I_{B^{\ast }}^{Z}({\Bigl [}\sigma {\Bigr ]}_{64}^{85}),I_{B^{\ast }}^{Z}({\Bigl [}\sigma {\Bigr ]}_{85}^{85+l}),I_{B^{\ast }}^{Z}({\Bigl [}\sigma {\Bigr ]}_{85+l}^{85+2l}),{\Bigl [}\sigma {\Bigr ]}_{85+2l}^{L(\sigma )})\in B^{64}\times Z\times Z\times Z\times B^{\ast }}
править
Алгоритм. Генерирование цифровой подписи ACE.
(
N
,
h
,
x
,
e
′
,
k
′
,
s
)
{\displaystyle (N,h,x,e^{\prime },k^{\prime },s)}
(
p
,
q
,
a
)
{\displaystyle (p,q,a)}
M
∈
B
∗
{\displaystyle M\in B^{\ast }}
0
≤
L
(
M
)
≤
2
64
{\displaystyle 0\leq L(M)\leq 2^{64}}
σ
∈
B
∗
{\displaystyle \sigma \in B^{\ast }}
Произвести следующие действия для хеширования входных данных:
Сгенерировать случайно ключ хеша
k
~
∈
B
20
m
+
64
{\displaystyle {\tilde {k}}\in B^{20m+64}}
m
=
L
b
(
⌈
(
L
(
M
)
+
8
)
/
64
⌉
)
{\displaystyle m=L_{b}(\left\lceil (L(M)+8)/64\right\rceil )}
Вычислить
m
h
←
I
W
∗
Z
(
U
O
W
H
a
s
h
′
′
(
k
~
,
M
)
)
{\displaystyle m_{h}\leftarrow I_{W^{\ast }}^{Z}(UOWHash^{\prime \prime }({\tilde {k}},M))}
Выбрать случайное
y
~
∈
{
1
,
.
.
.
,
N
−
1
}
{\displaystyle {\tilde {y}}\in \left\{1,...,N-1\right\}}
y
′
←
y
~
2
r
e
m
N
{\displaystyle y^{\prime }\leftarrow {\tilde {y}}^{2}remN}
Вычислить
x
′
←
(
y
′
)
r
′
h
m
h
r
e
m
N
{\displaystyle x^{\prime }\leftarrow (y^{\prime })^{r^{\prime }}h^{m_{h}}remN}
Сгенерировать случайное простое число
e
{\displaystyle e}
2
160
≤
e
≤
2
161
{\displaystyle 2^{160}\leq e\leq 2^{161}}
(
w
,
d
)
{\displaystyle (w,d)}
(
e
,
w
,
d
)
←
G
e
n
C
e
r
t
P
r
i
m
e
(
s
)
{\displaystyle (e,w,d)\leftarrow GenCertPrime(s)}
e
≠
e
′
{\displaystyle e\neq e^{\prime }}
Положить
r
←
U
O
W
H
a
s
h
′
′
′
(
k
′
,
L
B
(
N
)
,
x
′
,
k
~
)
∈
Z
{\displaystyle r\leftarrow UOWHash^{\prime \prime \prime }(k^{\prime },L_{B}(N),x^{\prime },{\tilde {k}})\in Z}
0
≤
r
<
2
160
{\displaystyle 0\leq r<2^{160}}
Вычислить
y
←
h
b
r
e
m
N
{\displaystyle y\leftarrow h^{b}remN}
b
←
e
−
1
(
a
−
r
)
r
e
m
(
p
′
q
′
)
{\displaystyle b\leftarrow e^{-1}(a-r)rem(p^{\prime }q^{\prime })}
p
′
=
(
p
−
1
)
/
2
{\displaystyle p^{\prime }=(p-1)/2}
q
′
=
(
q
−
1
)
/
2
{\displaystyle q^{\prime }=(q-1)/2}
Закодировать подпись:
σ
←
S
E
n
c
o
d
e
(
L
B
(
N
)
,
d
,
w
,
y
,
y
′
,
k
~
)
{\displaystyle \sigma \leftarrow SEncode(L_{B}(N),d,w,y,y^{\prime },{\tilde {k}})}
В схемах шифрования и цифровой подписи ACE используются некоторые вспомогательные функции(такие как, например, UOWHash,ESHash и другие), описание которых выходит за рамки данной статьи. Подробнее о данных функциях можно найти в[ 1]
править
Схема шифрования ACE рекомендована проектом NESSIE (New European Schemes for Signatures, Integrity and Encryption) как асимметричная схема шифрования. Пресс-релиз датирован февралем 2003.
Power PC
Pentium
Размер операнда(байт)
Размер операнда(байт)
512
1024
512
1024
Умножение
3.5 * 10^(-5) сек
1.0 * 10^(-4) сек
4.5 * 10^(-5) сек
1.4 * 10^(-4) сек
Возведение в квадрат
3.3 * 10^(-5) сек
1.0 * 10^(-4) сек
4.4 * 10^(-5) сек
1.4 * 10^(-4) сек
Потенцирование
1.9 * 10^(-2) сек
1.2 * 10^(-1) сек
2.6 * 10^(-2) сек
1.7 * 10^(-1) сек
Power PC
Pentium
Постоянные затраты (мсек)
МБит/сек
Постоянные затраты (мсек)
МБит/сек
Шифрование
160
18
230
16
Дешифрование
68
18
97
14
Подпись
48
64
62
52
Подпись (начальная установка)
29
41
Верификация
52
65
73
53
![{\displaystyle F_{2}[T]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/76e452838ced0113f025e5c31774ba0f26eae308)
![{\displaystyle r\in F_{2}[T]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9565964d1c289ec8d2201a9a85fca215c02ac29d)
![{\displaystyle A,f\in F_{2}[T],f\neq 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a55214ef544515c9ed65fc428d1587697f3219d8)
![{\displaystyle Z,F_{2}[T],b^{\ast },B^{\ast },W^{\ast }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c35e25f92de94c93e61028f1d0853c129cdf3f0c)
![{\displaystyle CDecode(l,\psi ){\stackrel {\mathrm {def} }{=}}(I_{B^{\ast }}^{W^{\ast }}({\Bigl [}\psi {\Bigr ]}_{0}^{16}),I_{B^{\ast }}^{Z}({\Bigl [}\psi {\Bigr ]}_{16}^{16+l}),I_{B^{\ast }}^{Z}({\Bigl [}\psi {\Bigr ]}_{16+l}^{16+2l}),I_{B^{\ast }}^{Z}({\Bigl [}\psi {\Bigr ]}_{16+2l}^{16+3l}),{\Bigl [}\psi {\Bigr ]}_{16+3l}^{L(\psi )})\in W^{4}\times Z\times Z\times Z\times B^{\ast }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/03a79f952531c75a4cb655c8659a6aa5ec1f7ac6)
![{\displaystyle enc\leftarrow {\Bigl [}M{\Bigr ]}_{i}^{i+r}\oplus mask_{e}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0f8f3fabcf461aa26d078b0c8480718c08490a10)
![{\displaystyle mac\leftarrow AXUHash(k_{AXU},lastBlock,{\Bigl [}e{\Bigr ]}_{i}^{i+r})\in W^{4}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5f65db2fa6d5f8e52723299070e4a3eff5ded3ee)
![{\displaystyle {\Bigl [}e{\Big ]}r_{i+r}^{i+r+16}\neq I_{W^{\ast }}^{B^{\ast }}(mac\oplus mask_{m})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a18e19082c760c22a5e0800b19a6b8d9d2c96156)
![{\displaystyle M\leftarrow M||({\Bigl [}e{\Bigr ]}_{i}^{i+r})\oplus mask_{e})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dab1f7145b998610f7100e6a94fcdf988554ee59)
![{\displaystyle CSecode(l,\sigma ){\stackrel {\mathrm {def} }{=}}({\Bigl [}\sigma {\Bigr ]}_{0}^{64},I_{B^{\ast }}^{Z}({\Bigl [}\sigma {\Bigr ]}_{64}^{85}),I_{B^{\ast }}^{Z}({\Bigl [}\sigma {\Bigr ]}_{85}^{85+l}),I_{B^{\ast }}^{Z}({\Bigl [}\sigma {\Bigr ]}_{85+l}^{85+2l}),{\Bigl [}\sigma {\Bigr ]}_{85+2l}^{L(\sigma )})\in B^{64}\times Z\times Z\times Z\times B^{\ast }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7b9da10ec5c5017b9db158078fbe0f7d55cfdef3)
