ACE Encrypt

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

\Z — The set of integers.

F_2[T] — The set of univariate polynomials with coefficients in the finite field F_2 of cardinality 2.

A \operatorname{rem} n — integer r \in \left{0,\dots,n-1\right} such that A\equiv r\pmod n for integer n0 and A \in \Z.

A \operatorname{rem} f — polynomial r \in F_2[T] with \deg(r) such that A\equiv r\pmod f with A,f \in F_2[T],f \ne 0.

Basic string notation

A^{\ast} — The set of all strings.

A^{n} — The set of all strings with length n.

For x \in A^{\ast} L(x) — length of string x. The string of length zero is denoted \lambda_A.

For x,y \in A^{\ast} x|y — the result of x and y concatenation.

Bits, Bytes, Words

b\overset{\text{def}}\left{0,1\right} — The set of bits. Let us take all sets of form b, b^{n_1}, (b^{n_1})^{n_2},.... For such a set A we define the "zero element": {=}0 \in b; 0_{A^n}\stackrel{\mathrm{def}}{=}(0_A,...,0_A) \in A^n for n0.}}

We define B\stackrel{\mathrm{def}}b^8 as a set of bytes, and W\stackrel{\mathrm{def}}b^{32} as a set of words.

For x \in A^{\ast} with A \in \left{b,B,W\right} and l0 we define a padding operator: pad_l(x) \stackrel{\mathrm{def}}{=} \begin{cases} x, & L(x) \ge l \ x||0_{A^{l-L(x)}}, & L(x) \end{cases}.}}

Conversion operator

Conversion operator I_{src}^{dst}: src \to dst makes a conversion between elements Z,F_2[T],b^{\ast},B^{\ast},W^{\ast}.

Encryption Scheme

Encryption Key Pair

The encryption scheme employs two key types:

ACE public key: (P,q,g_1,g_2,c,d,h_1,h_2,k_1,k_2).

ACE private key: (w,x,y,z_1,z_2).

For a given size parameter m, such that 1024 \le m \le 16384, key components are defined as:

q — a 256-bit prime number.

P — a m-bit prime number, such that P\equiv 1\pmod q.

g_1,g_2,c,d,h_1,h_2 — elements \left{1,\dots,P-1\right} (whose multiplicative order modulo P divides q).

w,x,y,z_1,z_2 — elements \left{0,\dots,q-1\right}.

k_1,k_2 — elements B^\ast with L(k_1)=20l'+64 and L(k_2)=32\left\lceil l/16 \right\rceil+40, where l=\left\lceil m/8 \right\rceil and l'=L_b(\left\lceil (2\left\lceil l/4 \right\rceil +4)/16 \right\rceil).

Key Generation

Algorithm. Key Generation for ACE encryption scheme.

Input: a size parameter m, such that 1024 \le m \le 16384.

Output: a public/private key pair.

1. Generate a random prime q, such that 2^{255} .
2. Generate a random prime P, 2^{m-1} , such that P\equiv1(mod q).
3. Generate a random integer g_1 \in \left{ 2,...,P-1 \right}, such that g_1^q\equiv1(mod P).
4. Generate random integers w \in \left{ 1,...,q-1 \right} and x,y,z_1,z_2 \in \left{ 0,...,q-1 \right}
5. Compute the following integers in \left{ 1,...,P-1 \right}:
6. Generate random byte strings k_1 \in B^{20l'+64} and k_2 \in B^{2\left\lceil l/16 \right\rceil+40}, where l=L_B(P) and l' = L_B(\left\lceil (2\left\lceil l/4 \right\rceil +4)/16 \right\rceil).
7. Return the public key/private key pair

Ciphertext Representation

A ciphertext of the ACE encryption scheme has the form

where the components are defined as:

u_1,u_2,v — integers from \left{ 1,...,P-1 \right} (whose multiplicative order modulo P divides q).

s — element W^4.

e — element B^{\ast}.

s,u_1,u_2,v we call the preamble, and e — the cryptogram. If a cleartext is a string consisting of l байт, then the length of e is equal to l+16\left\lceil l/1024 \right\rceil.

We need to introduce the function CEncode, which maps a ciphertext to its byte-string representation, and the corresponding inverse function CDecode. For the integer l0, word string s \in W^4, integers 0 \le u_1,u_2,v, and byte string e \in B^{\ast}, {=}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}.}}

For integer l0, byte string \psi \in B^{\ast}, such that L(\psi) \ge 3l+16, {=}(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}.}}

Encryption Process

Algorithm. ACE asymmetric encryption operation.

input: public key (P,q,g_1,g_2,c,d,h_1,h_2,k_1,k_2) and byte string M \in B^{\ast}.

Output: byte string — ciphertext \psi\ of M.

1. Generate r \in \left{ 0,...,q-1 \right} at random.
2. Generate the ciphertext preamble:
3. Generate s \in W^4 at random.
4. Compute u_1 \leftarrow g_1^r rem P, u_2 \leftarrow g_2^r rem P.
5. Compute \alpha\ \leftarrow UOWHash^\prime (k_1,L_B(P),s,u_1,u_2) \in Z; note that 0 .
6. Compute v \leftarrow c^r d^{\alpha\ r} rem P.
7. Compute the key for the symmetric encryption operation:
8. \tilde{h_1} \leftarrow h_1^r rem P, \tilde{h_2} \leftarrow h_2^r rem P.
9. Compute k \leftarrow ESHash(k,L_B(P),s,u_1,u_2,\tilde{h_1},\tilde{h_2}) \in W^8.
10. Compute cryptogram e \leftarrow SEnc(k,s,1024,M).
11. Encode the ciphertext:
12. Return \psi\ . Before starting off the symmetric encryption process, the input message M \in B^{\ast} is divided into blocks M_1,...,M_t, 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 E_i 16-byte message authentication code is computed. We get the cryptogram Note that if L(M)=0, then L(e)=0. Algorithm. ACE asymmetric encryption process.

Input: (k,s,M,m) \in W^8 \times W^4 \times Z \times B^{\ast} m0

Output: e \in B^l, l=L(M)+16 \left\lceil L(N)/m \right\rceil.

1. If M=\lambda_B , then return \lambda_B .
2. Initialize a pseudo-random generator state:
3. Generate the key k_{AXU} AXUHash :
4. e \leftarrow \lambda_B, i \leftarrow 0.
5. While i, do the following:
6. r \leftarrow min(L(M)-i,m).
7. Generate mask values for the encryption and MAC: 1. (mask_m,genState) \leftarrow GenWords(4,genState). 1. (mask_e,genState) \leftarrow GenWords(r,genState).
8. Encrypt the plaintext: enc \leftarrow \Bigl[M\Bigr]_i^{i+r} \oplus mask_e.
9. Generate the message authentication code: 1. If i+r=L(M), then lastBlock \leftarrow 1; else lastBlock \leftarrow 0. 1. mac \leftarrow AXUHash(k_{AXU},lastBlock,enc) \in W^4.
10. Update the ciphertext: e \leftarrow e||enc||I_{W^{\ast}}^{B^{\ast}}(mac \oplus mask_m).
11. i \leftarrow i+r.
12. Return e .

Decryption process

Algorithm. ACE decryption process.

Input: public key (P,q,g_1,g_2,c,d,h_1,h_2,k_1,k_2) and corresponding private key (w,x,y,z_1,z_2), byt e string \psi \in B^{\ast}.

Output: Decrypted message M \in B^{\ast} \cup {Reject}.

1. Decrypt the ciphertext:
2. If L(\psi) , then return Reject .
3. Compute: note that 0 \le u_1,u_2,v, where l=L_B(P).
4. Verify the ciphertext preamble:
5. If u_1 \ge P or u_2 \ge P or v \ge P, then return Reject .
6. If u_1^q \ne 1 rem P, then return Reject .
7. reject \leftarrow 0 .
8. If u_2 \ne u_1^w rem P, then reject \leftarrow 1 .
9. Compute \alpha \leftarrow UOWHash^{\prime}(k_1,L_B(P),s,u_1,u_2) \in Z; note that 0 \le \alpha \le 2^{160}.
10. If v \ne u_1^{x+{\alpha}y} rem P, then reject \leftarrow 1 .
11. If reject=1 , then return Reject .
12. Compute the key for the symmetric decryption operation:
13. \tilde{h_1} \leftarrow u_1^{z_1} rem P, \tilde{h_2} \leftarrow u_1^{z_2} rem P.
14. Compute k \leftarrow ESHash(k_2,L_B(P),s,u_1,\tilde{h_1},\tilde{h_2}) \in W^8.
15. Compute M \leftarrow SDec(k,s,1024,e);note that SDec can return Reject .
16. Return M. Algorithm. Decryption operation SDec.

Input: (k,s,m,e) \in W^8 \times W^4 \times Z \times B^{\ast} m0

Output: Decrypted message M \in B^{\ast} \cup {Reject}.

1. If e=\lambda_B , then return \lambda_B .
2. Initialize a pseudo-random generator state:
3. Generate the key k_{AXU} AXUHash :
4. M \leftarrow \lambda_B, i \leftarrow 0.
5. While i, do the following:
6. r \leftarrow min(L(e)-i,m+16)-16.
7. If r \le 0, then return Reject .
8. Generate mask values for the encryption and MAC: 1. (mask_m,genState) \leftarrow GenWords(4,genState). 1. (mask_e,genState) \leftarrow GenWords(r,genState).
9. Verify the message authentication code: 1. If i+r+16=L(M), then lastblock \leftarrow 1; else lastblock \leftarrow 0. 1. mac \leftarrow AXUHash(k_{AXU},lastBlock,\Bigl[e\Bigr]i^{i+r}) \in W^4. 1. If \Bigl[e\Big]r{i+r}^{i+r+16} \ne I_{W^{\ast}}^{B^{\ast}}(mac \oplus mask_m), then return Reject .
10. Update the plaintext: M \leftarrow M||(\Bigl[e\Bigr]_i^{i+r}) \oplus mask_e).
11. i \leftarrow i+r+16.
12. Return M .

Signature Scheme

The signature scheme employs two key types:

ACE Signature public key: (N,h,x,e',k',s).

ACE Signature private key: (p,q,a).

For the given size parameter m, such that 1024 \le m \le 16384, key components are defined the following way:

p — \left\lfloor m/2 \right\rfloor-bit prime number with (p-1)/2 — is also a prime number.

q — \left\lfloor m/2 \right\rfloor-bit prime number with (q-1)/2 — is also a prime number.

N — N=pqand has either m or m-1 бит.

h,x — elements \left{1,...,N-1\right} (quadratic residues modulo N).

e' — 161-bit prime number.

a — element \left{0,...,(p-1)(q-1)/4-1\right}

k' — elements B^{184}.

s — elements B^{32}.

Key Generation

Algorithm. Key generation for the ACE public-key signature scheme.

Input: size parameter m, such that 1024 \le m \le 16384.

Output: public/private key pair.

1. Generate random prime numbersp,q, such that (p-1)/2 and (q-1)/2 — is also a prime number, and m_1=\left\lfloor m/2 \right\rfloor and m_1=\left\lceil m/2 \right\rceil.
2. Set N \leftarrow pq.
3. Generate random prime number e', где 2^{160} \le e' \le 2^{161}.
4. Generate random h' \in \left{1,...,N-1\right}, taking into account gcd(h',N)=1 and gcd(h' \pm 1,N)=1, and compute h \leftarrow (h')^{-2} rem N.
5. Generate random a \in \left{0,...,(p-1)(q-1)/4-1\right}and compute x \leftarrow h^a rem N.
6. Generate random byte strings k' \in B^{184}, and s \in B^{32}.
7. Return public key/private key pair

Signature Representation

The signature in the ACE signature scheme has the form (d,w,y,y',\tilde{k}), where the components are defined the following way:

d — element B^{64}.

w — integer, such that 2^{160} \le w \le 2^{161}.

y,y' — elements \left{1,...,N-1\right}.

\tilde{k} — element B^{\ast};note that L(\tilde{k})=64+20L_B(\left\lceil (L(M)+8)/64 \right\rceil), where M — message being signed.

We need to introduce the SEncode function, which maps a signature into its byte string representation, and the corresponding inverse function SDecode. For integer l0, byte string d \in B^{64}, integers 0 \le w \le 256^{21} and 0 \le y,y', and byte string \tilde{k} \in B^{\ast},{=}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}.}}

For integer l0, byte string \sigma \in B^{\ast}, where L(\sigma) \ge 2l+53, {=}(\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

Algorithm. ACE Signature Generation Process.

Input: public key (N,h,x,e',k',s) and corresponding private key (p,q,a) and byte string M \in B^{\ast}, 0 \le L(M) \le 2^{64}.

Output: byte string — digital signature \sigma \in B^{\ast}.

1. Perform the following steps to hash the input data:
2. Generate a hash key \tilde{k} \in B^{20m+64} at random, such that m=L_b(\left\lceil (L(M)+8)/64 \right\rceil).
3. Compute m_h \leftarrow I_{W^{\ast}}^{Z}(UOWHash^{\prime\prime}(\tilde{k},M)).
4. Select \tilde{y} \in \left{1,...,N-1\right} at random, and compute y' \leftarrow \tilde{y}^2 rem N.
5. Compute x' \leftarrow (y')^{r'}h^{m_h} rem N.
6. Generate a random prime e, 2^{160} \le e \le 2^{161}, and its certificate of correctness (w,d): (e,w,d) \leftarrow GenCertPrime(s). Repeat this step until e \ne e'.
7. Set r \leftarrow UOWHash^{\prime\prime\prime}(k',L_B(N),x',\tilde{k}) \in Z; note that 0 \le r .
8. Compute y \leftarrow h^b rem N, where and where p'=(p-1)/2 and q'=(q-1)/2.
9. Encode the signature:
10. Return \sigma

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 в.

Implementation, Utilization and Performance

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:

Literature

References

1. [http://www.zurich.ibm.com/security/ace/ace_spec.pdf ACE: The Advanced Cryptographic Engine, T. Schweinberger and V. Shoup, manuscript 2000]