ACE (advanced cryptographic engine) is the collection of units, implementing both a public key encryption scheme and a digital signature scheme. Corresponding names for these schemes — «ACE Encrypt» and «ACE Sign». Schemes are based on Cramer-Shoup public key encryption scheme and Cramer-Shoup signature scheme. Introduced variants of these schemes are intended to achieve a good balance between performance and security of the whole encryption system.
All the algorithms, implemented in ACE are based on algorithms developed by Victor Shoup and Ronald Cramer. The full algorithms specification is written by Victor Shoup. Implementation of algorithms is done by Thomas Schweinberger and Mehdi Nassehi, its supporting and maintaining is done by Victor Shoup. Thomas Schweinberger participated in construction of ACE specification document and also wrote a user manual.
Ronald Cramer currently stays in the university of Aarhus, Denmark . He worked on the project of ACE Encrypt while his staying in ETH in Zürich , Switzerland .
Mehdi Nassehi and Thomas Schweinberger worked on ACE project in the IBM research lab in Zürich , Switzerland .Zürich , Switzerland .
The encryption scheme in ACE can be proven secure under reasonable and natural
intractability assumptions.
These four assumptions are:
The Decisional Diffie-Hellman (DDH) assumption
Strong RSA assumption
SHA-1 second preimage collision resistance
MARS sum/counter mode pseudo-randomness Basic Terminology and Notation
edit
Here we introduce some notations, being used in this article.
Basic mathematical notation
edit
Z
{\displaystyle \mathbb {Z} }
F
2
[
T
]
{\displaystyle F_{2}[T]}
F
2
{\displaystyle F_{2}}
A
rem
n
{\displaystyle A\operatorname {rem} n}
r
∈
{
0
,
…
,
n
−
1
}
{\displaystyle r\in \left\{0,\dots ,n-1\right\}}
A
≡
r
(
mod
n
)
{\displaystyle A\equiv r{\pmod {n}}}
n
>
0
{\displaystyle n>0}
A
∈
Z
{\displaystyle A\in \mathbb {Z} }
A
rem
f
{\displaystyle A\operatorname {rem} f}
r
∈
F
2
[
T
]
{\displaystyle r\in F_{2}[T]}
deg
(
r
)
<
deg
(
f
)
{\displaystyle \deg(r)<\deg(f)}
A
≡
r
(
mod
f
)
{\displaystyle A\equiv r{\pmod {f}}}
A
,
f
∈
F
2
[
T
]
,
f
≠
0
{\displaystyle A,f\in F_{2}[T],f\neq 0}
Basic string notation
edit
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
=
def
{
0
,
1
}
{\displaystyle b{\overset {\text{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}}
for
n
>
0
{\displaystyle n>0}
.
We define
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}}
For
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}}}
.
Conversion operator
I
s
r
c
d
s
t
:
s
r
c
→
d
s
t
{\displaystyle I_{src}^{dst}:src\to dst}
Z
,
F
2
[
T
]
,
b
∗
,
B
∗
,
W
∗
{\displaystyle Z,F_{2}[T],b^{\ast },B^{\ast },W^{\ast }}
The encryption scheme employs two key types:
(
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
(
mod
q
)
{\displaystyle P\equiv 1{\pmod {q}}}
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,\dots ,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,\dots ,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'+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'=L_{b}(\left\lceil (2\left\lceil l/4\right\rceil +4)/16\right\rceil )}
Algorithm. Key Generation for ACE encryption scheme.
m
{\displaystyle m}
1024
≤
m
≤
16384
{\displaystyle 1024\leq m\leq 16384}
Generate a random prime
q
{\displaystyle q}
2
255
<
q
<
2
256
{\displaystyle 2^{255}<q<2^{256}}
Generate a random prime
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)}
Generate a random integer
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)}
Generate random integers
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\}}
Compute the following integers in
{
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}
.
Generate random byte strings
k
1
∈
B
20
l
′
+
64
{\displaystyle k_{1}\in B^{20l'+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'=L_{B}(\left\lceil (2\left\lceil l/4\right\rceil +4)/16\right\rceil )}
Return the public key/private key pair
(
(
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}))}
Ciphertext Representation
edit
A ciphertext of the ACE encryption scheme has the form
(
s
,
u
1
,
u
2
,
v
,
e
)
{\displaystyle (s,u_{1},u_{2},v,e)}
,
where the components are defined as:
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}
preamble , and
e
{\displaystyle e}
cryptogram . If a cleartext is a string consisting of
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}
representation, and the corresponding inverse function
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 }}
.
Algorithm. ACE asymmetric encryption operation.
(
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}
Generate
r
∈
{
0
,
.
.
.
,
q
−
1
}
{\displaystyle r\in \left\{0,...,q-1\right\}}
Generate the ciphertext preamble:
Generate
s
∈
W
4
{\displaystyle s\in W^{4}}
Compute
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}
Compute
α
←
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}}
Compute
v
←
c
r
d
α
r
r
e
m
P
{\displaystyle v\leftarrow c^{r}d^{\alpha \ r}remP}
Compute the key for the symmetric encryption operation:
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}
Compute
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}}
Compute cryptogram
e
←
S
E
n
c
(
k
,
s
,
1024
,
M
)
{\displaystyle e\leftarrow SEnc(k,s,1024,M)}
Encode the ciphertext:
ψ
←
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)}
.
Return
ψ
{\displaystyle \psi \ }
Before starting off the symmetric encryption process, the input message
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 }
.
Note that if
L
(
M
)
=
0
{\displaystyle L(M)=0}
L
(
e
)
=
0
{\displaystyle L(e)=0}
Algorithm. ACE asymmetric encryption process.
(
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 }
If
M
=
λ
B
{\displaystyle M=\lambda _{B}}
λ
B
{\displaystyle \lambda _{B}}
Initialize a pseudo-random generator state:
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}
Generate the key
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}
While
i
<
L
(
M
)
{\displaystyle i<L(M)}
r
←
m
i
n
(
L
(
M
)
−
i
,
m
)
{\displaystyle r\leftarrow min(L(M)-i,m)}
Generate mask values for the encryption and 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)}
Encrypt the plaintext:
e
n
c
←
[
M
]
i
i
+
r
⊕
m
a
s
k
e
{\displaystyle enc\leftarrow {\Bigl [}M{\Bigr ]}_{i}^{i+r}\oplus mask_{e}}
Generate the message authentication code:
If
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}}
Update the ciphertext:
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}
Return
e
{\displaystyle e}
Algorithm. ACE decryption process.
(
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}}
Decrypt the ciphertext:
If
L
(
ψ
)
<
3
L
B
(
P
)
+
16
{\displaystyle L(\psi )<3L_{B}(P)+16}
R
e
j
e
c
t
{\displaystyle Reject}
Compute:
(
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)}
Verify the ciphertext preamble:
If
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}
If
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}
If
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}
Compute
α
←
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}}
If
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}
If
r
e
j
e
c
t
=
1
{\displaystyle reject=1}
R
e
j
e
c
t
{\displaystyle Reject}
Compute the key for the symmetric decryption operation:
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}
Compute
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}}
Compute
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}
Return
M
{\displaystyle M}
Algorithm. Decryption operation
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}}
If
e
=
λ
B
{\displaystyle e=\lambda _{B}}
λ
B
{\displaystyle \lambda _{B}}
Initialize a pseudo-random generator state:
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}
Generate the key
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}
While
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}
If
r
≤
0
{\displaystyle r\leq 0}
R
e
j
e
c
t
{\displaystyle Reject}
Generate mask values for the encryption and 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)}
Verify the message authentication code:
If
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}}
If
[
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}
Update the plaintext:
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}
Return
M
{\displaystyle M}
The signature scheme employs two key types:
(
N
,
h
,
x
,
e
′
,
k
′
,
s
)
{\displaystyle (N,h,x,e',k',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'}
a
{\displaystyle a}
{
0
,
.
.
.
,
(
p
−
1
)
(
q
−
1
)
/
4
−
1
}
{\displaystyle \left\{0,...,(p-1)(q-1)/4-1\right\}}
k
′
{\displaystyle k'}
B
184
{\displaystyle B^{184}}
s
{\displaystyle s}
B
32
{\displaystyle B^{32}}
Algorithm. Key generation for the ACE public-key signature scheme.
m
{\displaystyle m}
1024
≤
m
≤
16384
{\displaystyle 1024\leq m\leq 16384}
Generate random prime numbers
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}
,
where
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 }
Set
N
←
p
q
{\displaystyle N\leftarrow pq}
Generate random prime number
e
′
{\displaystyle e'}
2
160
≤
e
′
≤
2
161
{\displaystyle 2^{160}\leq e'\leq 2^{161}}
Generate random
h
′
∈
{
1
,
.
.
.
,
N
−
1
}
{\displaystyle h'\in \left\{1,...,N-1\right\}}
g
c
d
(
h
′
,
N
)
=
1
{\displaystyle gcd(h',N)=1}
g
c
d
(
h
′
±
1
,
N
)
=
1
{\displaystyle gcd(h'\pm 1,N)=1}
h
←
(
h
′
)
−
2
r
e
m
N
{\displaystyle h\leftarrow (h')^{-2}remN}
Generate random
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}
Generate random byte strings
k
′
∈
B
184
{\displaystyle k'\in B^{184}}
s
∈
B
32
{\displaystyle s\in B^{32}}
Return public key/private key pair
(
(
N
,
h
,
x
,
e
′
,
k
′
,
s
)
,
(
p
,
q
,
a
)
)
{\displaystyle ((N,h,x,e',k',s),(p,q,a))}
.
Signature Representation
edit
The signature in the ACE signature scheme has the form
(
d
,
w
,
y
,
y
′
,
k
~
)
{\displaystyle (d,w,y,y',{\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'}
{
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}
We need to introduce the
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'<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',{\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'))||{\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 }}
.
Signature Generation Process
edit
Algorithm. ACE Signature Generation Process.
(
N
,
h
,
x
,
e
′
,
k
′
,
s
)
{\displaystyle (N,h,x,e',k',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 }}
Perform the following steps to hash the input data:
Generate a hash key
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 )}
Compute
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))}
Select
y
~
∈
{
1
,
.
.
.
,
N
−
1
}
{\displaystyle {\tilde {y}}\in \left\{1,...,N-1\right\}}
y
′
←
y
~
2
r
e
m
N
{\displaystyle y'\leftarrow {\tilde {y}}^{2}remN}
Compute
x
′
←
(
y
′
)
r
′
h
m
h
r
e
m
N
{\displaystyle x'\leftarrow (y')^{r'}h^{m_{h}}remN}
Generate a random prime
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'}
Set
r
←
U
O
W
H
a
s
h
′
′
′
(
k
′
,
L
B
(
N
)
,
x
′
,
k
~
)
∈
Z
{\displaystyle r\leftarrow UOWHash^{\prime \prime \prime }(k',L_{B}(N),x',{\tilde {k}})\in Z}
0
≤
r
<
2
160
{\displaystyle 0\leq r<2^{160}}
Compute
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'q')}
,
p
′
=
(
p
−
1
)
/
2
{\displaystyle p'=(p-1)/2}
q
′
=
(
q
−
1
)
/
2
{\displaystyle q'=(q-1)/2}
Encode the signature:
σ
←
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',{\tilde {k}})}
.
Return
σ
{\displaystyle \sigma }
In the definition of ACE Encryption process and ACE Signature process some auxiliary function (e.g. UOWHash, ESHash and some other) are being used, definition of which goes beyond this article. More details about it can be found in в.[ 1]
ACE Encryption scheme is recommended by NESSIE (New European Schemes for Signatures, Integrity and Encryption) as asymmetric encryption scheme. Press-release is dated by February 2003.
Both schemes were implemented in ANSI C, with the use of GNU GMP library. Tests were done on two platforms: Power PC 604 model 43P under AIX system and 266 MHz Pentium under Windows NT system. Result tables:
Time costs on basic operations
Power PC
Pentium
Operand size(byte)
Operand size(byte)
512
1024
512
1024
Multiplication
× 10−5 s× 10−4 s× 10−5 s× 10−4 s
Squaring
× 10−5 s× 10−4 s× 10−5 s× 10−4 s
Exponentiation
× 10−2 s× 10−1 s× 10−2 s× 10−1 s
Performance of encryption scheme and signature scheme
Power PC
Pentium
Fixed costs (ms)
MBit/sec
Fixed costs (ms)
MBit/sec
Encrypt
160
18
230
16
Decrypt
68
18
97
14
Sign
48
64
62
52
Sign set-up
29
41
Verify
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)
