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.
Authors
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.
Victor Shoup works in the IBM research lab in Zürich, Switzerland.
Security
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
Here we introduce some notations, being used in this article.
Basic mathematical notation
— The set of integers.
— The set of univariate polynomials with coefficients in the finite field
of cardinality 2.
— integer
such that
for integer
and
.
— polynomial
with
such that
with
.
Basic string notation
— The set of all strings.
— The set of all strings with length n.
For
— length of string
. The string of length zero is denoted
.
For
— the result of
and
concatenation.
Bits, Bytes, Words
— The set of bits.
Let us take all sets of form
. For such a set A we define the "zero element":
![{\displaystyle 0_{b}{\stackrel {\mathrm {def} }{=}}0\in b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9dfeb070159037637ae55dff87ef39184ab09d77)
;
![{\displaystyle 0_{A^{n}}{\stackrel {\mathrm {def} }{=}}(0_{A},...,0_{A})\in A^{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/10ac863dd4f3c15e1ada137235f37f3a35058bc9)
for
![{\displaystyle n>0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/27a6a5d982d54202a14f111cb8a49210501b2c96)
.
We define
as a set of bytes, and
as a set of words.
For
with
and
we define a padding operator:
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/361b69079e649320c10cba874f67f6ea24e7521d)
.
Conversion operator
Conversion operator
makes a conversion between elements
.
Encryption Scheme
Encryption Key Pair
The encryption scheme employs two key types:
ACE public key:
.
ACE private key:
.
For a given size parameter
, such that
, key components are defined as:
— a 256-bit prime number.
— a m-bit prime number, such that
.
— elements
(whose multiplicative order modulo
divides
).
— elements
.
— elements
with
and
, where
and
.
Key Generation
Algorithm. Key Generation for ACE encryption scheme.
Input: a size parameter
, such that
.
Output: a public/private key pair.
- Generate a random prime
, such that
. - Generate a random prime
,
, such that
. - Generate a random integer
, such that
. - Generate random integers
and ![{\displaystyle x,y,z_{1},z_{2}\in \left\{0,...,q-1\right\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5a6144e93551d0fb8a321a62c9ca1984470e3f7e)
- Compute the following integers in
:![{\displaystyle g_{2}\leftarrow g_{1}^{w}remP}](https://wikimedia.org/api/rest_v1/media/math/render/svg/15371f5c047ba8d1851219f37dec467a1ef230c5)
,
![{\displaystyle c\leftarrow g_{1}^{x}remP}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b45bb7e15dce66285e08a47db4008665b1030bf4)
,
![{\displaystyle d\leftarrow g_{1}^{y}remP}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8ee442709fd35f3d42d37e3ffd807c1c73741cb0)
,
![{\displaystyle h_{1}\leftarrow g_{1}^{z_{1}}remP}](https://wikimedia.org/api/rest_v1/media/math/render/svg/abd9b17a839368e49c2a5d1b1008225f3082a9a2)
,
![{\displaystyle h_{2}\leftarrow g_{1}^{z_{2}}remP}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9b5119bcecd9fcdefe1ea8efdc4739d9bd721307)
.
- Generate random byte strings
and
, where
and
. - Return the public key/private key pair
![{\displaystyle ((P,q,g_{1},g_{2},c,d,h_{1},h_{2},k_{1},k_{2}),(w,x,y,z_{1},z_{2}))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fc3085b7585e5ba6dc67f90d00ea5361437dfda4)
Ciphertext Representation
A ciphertext of the ACE encryption scheme has the form
![{\displaystyle (s,u_{1},u_{2},v,e)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/57d67fc4593c4b82ef8c084fd0dc7c76b0dd7f40)
,
where the components are defined as:
— integers from
(whose multiplicative order modulo
divides
).
— element
.
— element
.
we call the preamble, and
— the cryptogram. If a cleartext is a string consisting of
байт, then the length of
is equal to
.
We need to introduce the function
, which maps a ciphertext to its byte-string
representation, and the corresponding inverse function
. For the integer
, word string
, integers
, and byte string
,
![{\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 }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b8fd1b203ca78d877ba53de2bcd44f4b45029341)
.
For integer
, byte string
, such that
,
![{\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)
.
Encryption Process
Algorithm. ACE asymmetric encryption operation.
input: public key
and byte string
.
Output: byte string — ciphertext
of
.
- Generate
at random. - Generate the ciphertext preamble:
- Generate
at random. - Compute
,
. - Compute
; note that
. - Compute
.
- Compute the key for the symmetric encryption operation:
,
. - Compute
.
- Compute cryptogram
. - Encode the ciphertext:
![{\displaystyle \psi \ \leftarrow CEncode(L_{B}(P),s,u_{1},u_{2},v,e)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2f51971949c0e57b83ff6178355097bfb0f256ad)
.
- Return
.
Before starting off the symmetric encryption process, the input message
is divided into blocks
, where each of the block, possibly except the last one, is of 1024 bytes. Each block is encrypted by the stream cipher. For each encrypted block
16-byte message authentication code is computed. We get the cryptogram
![{\displaystyle e=E_{1}||C_{1}||...||E_{t}||C_{t}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/349dec7a8c983e560bf49514461b5286bf1099be)
.
![{\displaystyle L(e)=L(M)+16\left\lceil L(M)/m\right\rceil }](https://wikimedia.org/api/rest_v1/media/math/render/svg/a622f238f16fabeb20a1fd1525117a9269cf1f77)
.
Note that if
, then
.
Algorithm. ACE asymmetric encryption process.
Input:
![{\displaystyle m>0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/501173910e6da8425b4e9d44a4e8643620bc2464)
Output:
,
.
- If
, then return
. - Initialize a pseudo-random generator state:
![{\displaystyle genState\leftarrow InitGen(k,s)\in GenState}](https://wikimedia.org/api/rest_v1/media/math/render/svg/02b50aa7b7cb54e4fdbfdbc4504988279ca76f25)
- Generate the key
: ![{\displaystyle (k_{AXU},genState)\leftarrow GenWords((5L_{b}(\left\lceil m/64\right\rceil )+24),genState).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0d3fbc1f42a4d5614429babf1ff1315a45926853)
.
. - While
, do the following:
. - Generate mask values for the encryption and MAC:
.
.
- Encrypt the plaintext:
. - Generate the message authentication code:
- If
, then
; else
.
.
- Update the ciphertext:
.
.
- Return
.
Decryption process
Algorithm. ACE decryption process.
Input: public key
and corresponding private key
, byt e string
.
Output: Decrypted message
.
- Decrypt the ciphertext:
- If
, then return
. - Compute:
![{\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 }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e8c64015792b73088c40923e0f44211ed8ca68b4)
;
note that
, where
.
- Verify the ciphertext preamble:
- If
or
or
, then return
. - If
, then return
.
. - If
, then
. - Compute
; note that
. - If
, then
. - If
, then return
.
- Compute the key for the symmetric decryption operation:
,
. - Compute
.
- Compute
;note that
can return
. - Return
.
Algorithm. Decryption operation
.
Input:
![{\displaystyle m>0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/501173910e6da8425b4e9d44a4e8643620bc2464)
Output: Decrypted message
.
- If
, then return
. - Initialize a pseudo-random generator state:
![{\displaystyle genState\leftarrow InitGen(k,s)\in GenState}](https://wikimedia.org/api/rest_v1/media/math/render/svg/02b50aa7b7cb54e4fdbfdbc4504988279ca76f25)
- Generate the key
: ![{\displaystyle (k_{AXU},genState^{\prime })\leftarrow GenWords((5L_{b}(\left\lceil m/64\right\rceil )+24),genState).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/35244127d5ce86f41f1afdc25040c78c9304d49d)
.
. - While
, do the following:
. - If
, then return
. - Generate mask values for the encryption and MAC:
.
.
- Verify the message authentication code:
- If
, then
; else
.
. - If
, then return
.
- Update the plaintext:
.
.
- Return
.
Signature Scheme
The signature scheme employs two key types:
ACE Signature public key:
.
ACE Signature private key:
.
For the given size parameter
, such that
, key components are defined the following way:
—
-bit prime number with
— is also a prime number.
—
-bit prime number with
— is also a prime number.
—
and has either
or
бит.
— elements
(quadratic residues modulo
).
— 161-bit prime number.
— element ![{\displaystyle \left\{0,...,(p-1)(q-1)/4-1\right\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e5a8e161e1e1a298ab8d1fc1ef35063fd8c13f)
— elements
.
— elements
.
Key Generation
Algorithm. Key generation for the ACE public-key signature scheme.
Input: size parameter
, such that
.
Output: public/private key pair.
- Generate random prime numbers
, such that
and
— is also a prime number, and ![{\displaystyle 2^{m_{1}-1}<p<2^{m_{1}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eee000ed9edc14c74188b613dc9f0c81b2381426)
,
![{\displaystyle 2^{m_{2}-1}<q<2^{m_{2}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/66fc2c2b96b56bcea5d3ff9345ed8c9d7e43839f)
, и
![{\displaystyle p\neq q}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ac1f5fae3451ae6d0b52465cb06703bb11681b64)
,
where
and
. - Set
. - Generate random prime number
, где
. - Generate random
, taking into account
and
, and compute
. - Generate random
and compute
. - Generate random byte strings
, and
. - Return public key/private key pair
![{\displaystyle ((N,h,x,e',k',s),(p,q,a))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5a4ed9dd86b7d05ea879dcde0664884f27bf085f)
.
Signature Representation
The signature in the ACE signature scheme has the form
, where the components are defined the following way:
— element
.
— integer, such that
.
— elements
.
— element
;note that
, where
— message being signed.
We need to introduce the
function, which maps a signature into its byte string representation, and the corresponding inverse function
. For integer
, byte string
, integers
and
, and byte string
,
![{\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 }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/50ef9c01641262d516f19b833fad421b5ed52b4b)
.
For integer
, byte string
, where
,
![{\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)
.
Signature Generation Process
Algorithm. ACE Signature Generation Process.
Input: public key
and corresponding private key
and byte string
,
.
Output: byte string — digital signature
.
- Perform the following steps to hash the input data:
- Generate a hash key
at random, such that
. - Compute
.
- Select
at random, and compute
. - Compute
. - Generate a random prime
,
, and its certificate of correctness
:
. Repeat this step until
. - Set
; note that
. - Compute
, where ![{\displaystyle b\leftarrow e^{-1}(a-r)rem(p'q')}](https://wikimedia.org/api/rest_v1/media/math/render/svg/839ea3e70f51a0a9ace4edc148319369d1b7d4d1)
,
and where
and
. - Encode the signature:
![{\displaystyle \sigma \leftarrow SEncode(L_{B}(N),d,w,y,y',{\tilde {k}})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/05670b262f7c1cdfe14e04b87f1a95cc18ca1b11)
.
- Return
![{\displaystyle \sigma }](https://wikimedia.org/api/rest_v1/media/math/render/svg/59f59b7c3e6fdb1d0365a494b81fb9a696138c36)
Notes
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 | 3.5×10−5 s | 1.0×10−4 s | 4.5×10−5 s | 1.4×10−4 s |
Squaring | 3.3×10−5 s | 1.0×10−4 s | 4.4×10−5 s | 1.4×10−4 s |
Exponentiation | 1.9×10−2 s | 1.2×10−1 s | 2.6×10−2 s | 1.7×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 |
Literature
- ^ ACE: The Advanced Cryptographic Engine, T. Schweinberger and V. Shoup, manuscript 2000
External links
- http://www.alphaworks.ibm.com/tech/ace
- http://www.zurich.ibm.com/security/ace/
- NESSIE Portfolio of recommended cryptographic primitives