Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
ACE Encrypt
open-in-new
<h2 id="authors">Authors</h2> <p>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. </p><p>Ronald Cramer currently stays in the university of Aarhus, <a href="/facts/Denmark/KVtykzsw">Denmark</a>. He worked on the project of ACE Encrypt while his staying in ETH in <a href="/facts/Z%25C3%25BCrich/dXpgq7df">Zürich</a>, <a href="/facts/Switzerland/LcGuxeTe">Switzerland</a>. </p><p>Mehdi Nassehi and Thomas Schweinberger worked on ACE project in the IBM research lab in <a href="/facts/Z%25C3%25BCrich/dXpgq7df">Zürich</a>, <a href="/facts/Switzerland/LcGuxeTe">Switzerland</a>. Victor Shoup works in the IBM research lab in <a href="/facts/Z%25C3%25BCrich/dXpgq7df">Zürich</a>, <a href="/facts/Switzerland/LcGuxeTe">Switzerland</a>. </p> <h2 id="security">Security</h2> <p>The encryption scheme in ACE can be proven secure under reasonable and natural intractability assumptions. These four assumptions are: </p> <ul><li>The Decisional Diffie-Hellman (DDH) assumption</li> <li>Strong RSA assumption</li> <li>SHA-1 second preimage collision resistance</li> <li>MARS sum/counter mode pseudo-randomness</li></ul> <h2 id="basic-terminology-and-notation">Basic Terminology and Notation</h2> <p>Here we introduce some notations, being used in this article. </p> <h3>Basic mathematical notation</h3> <p> Z {\displaystyle \mathbb {Z} } — The set of integers. F 2 [ T ] {\displaystyle F_{2}[T]} — The set of univariate polynomials with coefficients in the finite field F 2 {\displaystyle F_{2}} of cardinality 2. A rem n {\displaystyle A\operatorname {rem} n} — integer r ∈ { 0 , … , n − 1 } {\displaystyle r\in \left\{0,\dots ,n-1\right\}} such that A ≡ r ( mod n ) {\displaystyle A\equiv r{\pmod {n}}} for integer n > 0 {\displaystyle n>0} and A ∈ Z {\displaystyle A\in \mathbb {Z} } . A rem f {\displaystyle A\operatorname {rem} f} — polynomial r ∈ F 2 [ T ] {\displaystyle r\in F_{2}[T]} with deg ( r ) < deg ( f ) {\displaystyle \deg(r)<\deg(f)} such that A ≡ r ( mod f ) {\displaystyle A\equiv r{\pmod {f}}} with A , f ∈ F 2 [ T ] , f ≠ 0 {\displaystyle A,f\in F_{2}[T],f\neq 0} . </p> <h3>Basic string notation</h3> <p> A ∗ {\displaystyle A^{\ast }} — The set of all strings. A n {\displaystyle A^{n}} — The set of all strings with length n. For x ∈ A ∗ L ( x ) {\displaystyle x\in A^{\ast }L(x)} — length of string x {\displaystyle x} . The string of length zero is denoted λ A {\displaystyle \lambda _{A}} . For x , y ∈ A ∗ {\displaystyle x,y\in A^{\ast }} x ‖ y {\displaystyle x\|y} — the result of x {\displaystyle x} and y {\displaystyle y} concatenation. </p> <h3>Bits, Bytes, Words</h3> <p> b = def { 0 , 1 } {\displaystyle 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 , . . . {\displaystyle b,b^{n_{1}},(b^{n_{1}})^{n_{2}},...} . For such a set A we define the "zero element": </p> 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} . <p>We define B = d e f b 8 {\displaystyle B{\stackrel {\mathrm {def} }{{}={}}}b^{8}} as a set of bytes, and W = d e f b 32 {\displaystyle W{\stackrel {\mathrm {def} }{{}={}}}b^{32}} as a set of words. </p><p>For x ∈ A ∗ {\displaystyle x\in A^{\ast }} with A ∈ { b , B , W } {\displaystyle A\in \left\{b,B,W\right\}} and l > 0 {\displaystyle l>0} we define a padding operator: </p> 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}}} . <h3>Conversion operator</h3> <p>Conversion operator I s r c d s t : s r c → d s t {\displaystyle I_{src}^{dst}:src\to dst} makes a conversion between elements Z , F 2 [ T ] , b ∗ , B ∗ , W ∗ {\displaystyle Z,F_{2}[T],b^{\ast },B^{\ast },W^{\ast }} . </p> <h2 id="encryption-scheme">Encryption Scheme</h2> <h3>Encryption Key Pair</h3> <p>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 ) {\displaystyle (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 ) {\displaystyle (w,x,y,z_{1},z_{2})} . For a given size parameter m {\displaystyle m} , such that 1024 ≤ m ≤ 16384 {\displaystyle 1024\leq m\leq 16384} , key components are defined as: q {\displaystyle q} — a 256-bit prime number. P {\displaystyle P} — a m-bit prime number, such that 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}} — elements { 1 , … , P − 1 } {\displaystyle \left\{1,\dots ,P-1\right\}} (whose multiplicative order modulo P {\displaystyle P} divides q {\displaystyle q} ). w , x , y , z 1 , z 2 {\displaystyle w,x,y,z_{1},z_{2}} — elements { 0 , … , q − 1 } {\displaystyle \left\{0,\dots ,q-1\right\}} . k 1 , k 2 {\displaystyle k_{1},k_{2}} — elements B ∗ {\displaystyle B^{\ast }} with L ( k 1 ) = 20 l ′ + 64 {\displaystyle L(k_{1})=20l'+64} and L ( k 2 ) = 32 ⌈ l / 16 ⌉ + 40 {\displaystyle L(k_{2})=32\left\lceil l/16\right\rceil +40} , where l = ⌈ m / 8 ⌉ {\displaystyle l=\left\lceil m/8\right\rceil } and 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 )} . </p> <h3>Key Generation</h3> <p>Algorithm. Key Generation for ACE encryption scheme. Input: a size parameter m {\displaystyle m} , such that 1024 ≤ m ≤ 16384 {\displaystyle 1024\leq m\leq 16384} . Output: a public/private key pair. </p> <ol><li>Generate a random prime q {\displaystyle q} , such that 2 255 < q < 2 256 {\displaystyle 2^{255}<q<2^{256}} .</li> <li>Generate a random prime P {\displaystyle P} , 2 m − 1 < P < 2 m {\displaystyle 2^{m-1}<P<2^{m}} , such that P ≡ 1 ( m o d q ) {\displaystyle P\equiv 1(modq)} .</li> <li>Generate a random integer g 1 ∈ { 2 , . . . , P − 1 } {\displaystyle g_{1}\in \left\{2,...,P-1\right\}} , such that g 1 q ≡ 1 ( m o d P ) {\displaystyle g_{1}^{q}\equiv 1(modP)} .</li> <li>Generate random integers w ∈ { 1 , . . . , q − 1 } {\displaystyle w\in \left\{1,...,q-1\right\}} and x , y , z 1 , z 2 ∈ { 0 , . . . , q − 1 } {\displaystyle x,y,z_{1},z_{2}\in \left\{0,...,q-1\right\}} </li> <li>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} .</li> <li>Generate random byte strings k 1 ∈ B 20 l ′ + 64 {\displaystyle k_{1}\in B^{20l'+64}} and k 2 ∈ B 2 ⌈ l / 16 ⌉ + 40 {\displaystyle k_{2}\in B^{2\left\lceil l/16\right\rceil +40}} , where l = L B ( P ) {\displaystyle l=L_{B}(P)} and 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 )} .</li> <li>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}))} </li></ol> <h3>Ciphertext Representation</h3> <p>A ciphertext of the ACE encryption scheme has the form </p> ( s , u 1 , u 2 , v , e ) {\displaystyle (s,u_{1},u_{2},v,e)} ,<p>where the components are defined as: u 1 , u 2 , v {\displaystyle u_{1},u_{2},v} — integers from { 1 , . . . , P − 1 } {\displaystyle \left\{1,...,P-1\right\}} (whose multiplicative order modulo P {\displaystyle P} divides q {\displaystyle q} ). s {\displaystyle s} — element W 4 {\displaystyle W^{4}} . e {\displaystyle e} — element B ∗ {\displaystyle B^{\ast }} . s , u 1 , u 2 , v {\displaystyle s,u_{1},u_{2},v} we call the <i>preamble</i>, and e {\displaystyle e} — the <i>cryptogram</i>. If a cleartext is a string consisting of l {\displaystyle l} байт, then the length of e {\displaystyle e} is equal to l + 16 ⌈ l / 1024 ⌉ {\displaystyle l+16\left\lceil l/1024\right\rceil } . We need to introduce the function C E n c o d e {\displaystyle CEncode} , which maps a ciphertext to its byte-string </p><p> representation, and the corresponding inverse function C D e c o d e {\displaystyle CDecode} . For the integer l > 0 {\displaystyle l>0} , word string s ∈ W 4 {\displaystyle s\in W^{4}} , integers 0 ≤ u 1 , u 2 , v < 256 l {\displaystyle 0\leq u_{1},u_{2},v<256^{l}} , and byte string e ∈ B ∗ {\displaystyle e\in B^{\ast }} , </p> 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 }} .<p> For integer l > 0 {\displaystyle l>0} , byte string ψ ∈ B ∗ {\displaystyle \psi \in B^{\ast }} , such that L ( ψ ) ≥ 3 l + 16 {\displaystyle L(\psi )\geq 3l+16} , </p> 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 }} . <h3>Encryption Process</h3> <p>Algorithm. ACE asymmetric encryption operation. input: public key ( 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})} and byte string M ∈ B ∗ {\displaystyle M\in B^{\ast }} . Output: byte string — ciphertext ψ {\displaystyle \psi \ } of M {\displaystyle M} . </p> <ol><li>Generate r ∈ { 0 , . . . , q − 1 } {\displaystyle r\in \left\{0,...,q-1\right\}} at random.</li> <li>Generate the ciphertext preamble: <ol><li>Generate s ∈ W 4 {\displaystyle s\in W^{4}} at random.</li> <li>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} .</li> <li>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} ; note that 0 < α < 2 160 {\displaystyle 0<\alpha \ <2^{160}} .</li> <li>Compute v ← c r d α r r e m P {\displaystyle v\leftarrow c^{r}d^{\alpha \ r}remP} .</li></ol></li> <li>Compute the key for the symmetric encryption operation: <ol><li> 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} .</li> <li>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}} .</li></ol></li> <li>Compute cryptogram e ← S E n c ( k , s , 1024 , M ) {\displaystyle e\leftarrow SEnc(k,s,1024,M)} .</li> <li>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)} .</li> <li>Return ψ {\displaystyle \psi \ } .</li></ol><p> Before starting off the symmetric encryption process, the input message M ∈ B ∗ {\displaystyle M\in B^{\ast }} is divided into blocks M 1 , . . . , M t {\displaystyle 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 {\displaystyle E_{i}} 16-byte message authentication code is computed. We get the cryptogram </p> 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 } .<p> Note that if L ( M ) = 0 {\displaystyle L(M)=0} , then L ( e ) = 0 {\displaystyle L(e)=0} . </p><p>Algorithm. ACE asymmetric encryption process. Input: ( 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} Output: 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 } . </p> <ol><li>If M = λ B {\displaystyle M=\lambda _{B}} , then return λ B {\displaystyle \lambda _{B}} .</li> <li>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} </li> <li>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).} .</li> <li> e ← λ B , i ← 0 {\displaystyle e\leftarrow \lambda _{B},i\leftarrow 0} .</li> <li>While i < L ( M ) {\displaystyle i<L(M)} , do the following: <ol><li> r ← m i n ( L ( M ) − i , m ) {\displaystyle r\leftarrow min(L(M)-i,m)} .</li> <li>Generate mask values for the encryption and MAC: <ol><li> ( 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)} .</li> <li> ( 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)} .</li></ol></li> <li>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}} .</li> <li>Generate the message authentication code: <ol><li>If i + r = L ( M ) {\displaystyle i+r=L(M)} , then l a s t B l o c k ← 1 {\displaystyle lastBlock\leftarrow 1} ; else l a s t B l o c k ← 0 {\displaystyle lastBlock\leftarrow 0} .</li> <li> 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}} .</li></ol></li> <li>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})} .</li> <li> i ← i + r {\displaystyle i\leftarrow i+r} .</li></ol></li> <li>Return e {\displaystyle e} .</li></ol> <h3>Decryption process</h3> <p>Algorithm. ACE decryption process. Input: public key ( 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})} and corresponding private key ( w , x , y , z 1 , z 2 ) {\displaystyle (w,x,y,z_{1},z_{2})} , byt e string ψ ∈ B ∗ {\displaystyle \psi \in B^{\ast }} . Output: Decrypted message M ∈ B ∗ ∪ R e j e c t {\displaystyle M\in B^{\ast }\cup {Reject}} . </p> <ol><li>Decrypt the ciphertext: <ol><li>If L ( ψ ) < 3 L B ( P ) + 16 {\displaystyle L(\psi )<3L_{B}(P)+16} , then return R e j e c t {\displaystyle Reject} .</li> <li>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 }} ;note that 0 ≤ u 1 , u 2 , v < 256 l {\displaystyle 0\leq u_{1},u_{2},v<256^{l}} , where l = L B ( P ) {\displaystyle l=L_{B}(P)} .</li></ol></li> <li>Verify the ciphertext preamble: <ol><li>If u 1 ≥ P {\displaystyle u_{1}\geq P} or u 2 ≥ P {\displaystyle u_{2}\geq P} or v ≥ P {\displaystyle v\geq P} , then return R e j e c t {\displaystyle Reject} .</li> <li>If u 1 q ≠ 1 r e m P {\displaystyle u_{1}^{q}\neq 1remP} , then return R e j e c t {\displaystyle Reject} .</li> <li> r e j e c t ← 0 {\displaystyle reject\leftarrow 0} .</li> <li>If u 2 ≠ u 1 w r e m P {\displaystyle u_{2}\neq u_{1}^{w}remP} , then r e j e c t ← 1 {\displaystyle reject\leftarrow 1} .</li> <li>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} ; note that 0 ≤ α ≤ 2 160 {\displaystyle 0\leq \alpha \leq 2^{160}} .</li> <li>If v ≠ u 1 x + α y r e m P {\displaystyle v\neq u_{1}^{x+{\alpha }y}remP} , then r e j e c t ← 1 {\displaystyle reject\leftarrow 1} .</li> <li>If r e j e c t = 1 {\displaystyle reject=1} , then return R e j e c t {\displaystyle Reject} .</li></ol></li> <li>Compute the key for the symmetric decryption operation: <ol><li> 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} .</li> <li>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}} .</li></ol></li> <li>Compute M ← S D e c ( k , s , 1024 , e ) {\displaystyle M\leftarrow SDec(k,s,1024,e)} ;note that S D e c {\displaystyle SDec} can return R e j e c t {\displaystyle Reject} .</li> <li>Return M {\displaystyle M} .</li></ol> <p>Algorithm. Decryption operation S D e c {\displaystyle SDec} . Input: ( 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} Output: Decrypted message M ∈ B ∗ ∪ R e j e c t {\displaystyle M\in B^{\ast }\cup {Reject}} . </p> <ol><li>If e = λ B {\displaystyle e=\lambda _{B}} , then return λ B {\displaystyle \lambda _{B}} .</li> <li>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} </li> <li>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).} .</li> <li> M ← λ B , i ← 0 {\displaystyle M\leftarrow \lambda _{B},i\leftarrow 0} .</li> <li>While i < L ( e ) {\displaystyle i<L(e)} , do the following: <ol><li> r ← m i n ( L ( e ) − i , m + 16 ) − 16 {\displaystyle r\leftarrow min(L(e)-i,m+16)-16} .</li> <li>If r ≤ 0 {\displaystyle r\leq 0} , then return R e j e c t {\displaystyle Reject} .</li> <li>Generate mask values for the encryption and MAC: <ol><li> ( 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)} .</li> <li> ( 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)} .</li></ol></li> <li>Verify the message authentication code: <ol><li>If i + r + 16 = L ( M ) {\displaystyle i+r+16=L(M)} , then l a s t b l o c k ← 1 {\displaystyle lastblock\leftarrow 1} ; else l a s t b l o c k ← 0 {\displaystyle lastblock\leftarrow 0} .</li> <li> 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}} .</li> <li>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})} , then return R e j e c t {\displaystyle Reject} .</li></ol></li> <li>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})} .</li> <li> i ← i + r + 16 {\displaystyle i\leftarrow i+r+16} .</li></ol></li> <li>Return M {\displaystyle M} .</li></ol> <h2 id="signature-scheme">Signature Scheme</h2> <p>The signature scheme employs two key types: ACE Signature public key: ( N , h , x , e ′ , k ′ , s ) {\displaystyle (N,h,x,e',k',s)} . ACE Signature private key: ( p , q , a ) {\displaystyle (p,q,a)} . For the given size parameter m {\displaystyle m} , such that 1024 ≤ m ≤ 16384 {\displaystyle 1024\leq m\leq 16384} , key components are defined the following way: p {\displaystyle p} — ⌊ m / 2 ⌋ {\displaystyle \left\lfloor m/2\right\rfloor } -bit prime number with ( p − 1 ) / 2 {\displaystyle (p-1)/2} — is also a prime number. q {\displaystyle q} — ⌊ m / 2 ⌋ {\displaystyle \left\lfloor m/2\right\rfloor } -bit prime number with ( q − 1 ) / 2 {\displaystyle (q-1)/2} — is also a prime number. N {\displaystyle N} — N = p q {\displaystyle N=pq} and has either m {\displaystyle m} or m − 1 {\displaystyle m-1} бит. h , x {\displaystyle h,x} — elements { 1 , . . . , N − 1 } {\displaystyle \left\{1,...,N-1\right\}} (quadratic residues modulo N {\displaystyle N} ). e ′ {\displaystyle e'} — 161-bit prime number. a {\displaystyle a} — element { 0 , . . . , ( p − 1 ) ( q − 1 ) / 4 − 1 } {\displaystyle \left\{0,...,(p-1)(q-1)/4-1\right\}} k ′ {\displaystyle k'} — elements B 184 {\displaystyle B^{184}} . s {\displaystyle s} — elements B 32 {\displaystyle B^{32}} . </p> <h3>Key Generation</h3> <p>Algorithm. Key generation for the ACE public-key signature scheme. Input: size parameter m {\displaystyle m} , such that 1024 ≤ m ≤ 16384 {\displaystyle 1024\leq m\leq 16384} . Output: public/private key pair. </p> <ol><li>Generate random prime numbers p , q {\displaystyle p,q} , such that ( p − 1 ) / 2 {\displaystyle (p-1)/2} and ( q − 1 ) / 2 {\displaystyle (q-1)/2} — is also a prime number, and 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 } and m 1 = ⌈ m / 2 ⌉ {\displaystyle m_{1}=\left\lceil m/2\right\rceil } .</li> <li>Set N ← p q {\displaystyle N\leftarrow pq} .</li> <li>Generate random prime number e ′ {\displaystyle e'} , где 2 160 ≤ e ′ ≤ 2 161 {\displaystyle 2^{160}\leq e'\leq 2^{161}} .</li> <li>Generate random h ′ ∈ { 1 , . . . , N − 1 } {\displaystyle h'\in \left\{1,...,N-1\right\}} , taking into account g c d ( h ′ , N ) = 1 {\displaystyle gcd(h',N)=1} and g c d ( h ′ ± 1 , N ) = 1 {\displaystyle gcd(h'\pm 1,N)=1} , and compute h ← ( h ′ ) − 2 r e m N {\displaystyle h\leftarrow (h')^{-2}remN} .</li> <li>Generate random a ∈ { 0 , . . . , ( p − 1 ) ( q − 1 ) / 4 − 1 } {\displaystyle a\in \left\{0,...,(p-1)(q-1)/4-1\right\}} and compute x ← h a r e m N {\displaystyle x\leftarrow h^{a}remN} .</li> <li>Generate random byte strings k ′ ∈ B 184 {\displaystyle k'\in B^{184}} , and s ∈ B 32 {\displaystyle s\in B^{32}} .</li> <li>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))} .</li></ol> <h3>Signature Representation</h3> <p>The signature in the ACE signature scheme has the form ( d , w , y , y ′ , k ~ ) {\displaystyle (d,w,y,y',{\tilde {k}})} , where the components are defined the following way: d {\displaystyle d} — element B 64 {\displaystyle B^{64}} . w {\displaystyle w} — integer, such that 2 160 ≤ w ≤ 2 161 {\displaystyle 2^{160}\leq w\leq 2^{161}} . y , y ′ {\displaystyle y,y'} — elements { 1 , . . . , N − 1 } {\displaystyle \left\{1,...,N-1\right\}} . k ~ {\displaystyle {\tilde {k}}} — element B ∗ {\displaystyle B^{\ast }} ;note that 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 )} , where M {\displaystyle M} — message being signed. </p><p> We need to introduce the S E n c o d e {\displaystyle SEncode} function, which maps a signature into its byte string representation, and the corresponding inverse function S D e c o d e {\displaystyle SDecode} . For integer l > 0 {\displaystyle l>0} , byte string d ∈ B 64 {\displaystyle d\in B^{64}} , integers 0 ≤ w ≤ 256 21 {\displaystyle 0\leq w\leq 256^{21}} and 0 ≤ y , y ′ < 256 l {\displaystyle 0\leq y,y'<256^{l}} , and byte string k ~ ∈ B ∗ {\displaystyle {\tilde {k}}\in B^{\ast }} ,</p> 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 }} .<p> For integer l > 0 {\displaystyle l>0} , byte string σ ∈ B ∗ {\displaystyle \sigma \in B^{\ast }} , where L ( σ ) ≥ 2 l + 53 {\displaystyle L(\sigma )\geq 2l+53} , </p> 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 }} . <h3>Signature Generation Process</h3> <p>Algorithm. ACE Signature Generation Process. Input: public key ( N , h , x , e ′ , k ′ , s ) {\displaystyle (N,h,x,e',k',s)} and corresponding private key ( p , q , a ) {\displaystyle (p,q,a)} and byte string M ∈ B ∗ {\displaystyle M\in B^{\ast }} , 0 ≤ L ( M ) ≤ 2 64 {\displaystyle 0\leq L(M)\leq 2^{64}} . Output: byte string — digital signature σ ∈ B ∗ {\displaystyle \sigma \in B^{\ast }} . </p> <ol><li>Perform the following steps to hash the input data: <ol><li>Generate a hash key k ~ ∈ B 20 m + 64 {\displaystyle {\tilde {k}}\in B^{20m+64}} at random, such that m = L b ( ⌈ ( L ( M ) + 8 ) / 64 ⌉ ) {\displaystyle m=L_{b}(\left\lceil (L(M)+8)/64\right\rceil )} .</li> <li>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))} .</li></ol></li> <li>Select y ~ ∈ { 1 , . . . , N − 1 } {\displaystyle {\tilde {y}}\in \left\{1,...,N-1\right\}} at random, and compute y ′ ← y ~ 2 r e m N {\displaystyle y'\leftarrow {\tilde {y}}^{2}remN} .</li> <li>Compute x ′ ← ( y ′ ) r ′ h m h r e m N {\displaystyle x'\leftarrow (y')^{r'}h^{m_{h}}remN} .</li> <li>Generate a random prime e {\displaystyle e} , 2 160 ≤ e ≤ 2 161 {\displaystyle 2^{160}\leq e\leq 2^{161}} , and its certificate of correctness ( 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)} . Repeat this step until e ≠ e ′ {\displaystyle e\neq e'} .</li> <li>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} ; note that 0 ≤ r < 2 160 {\displaystyle 0\leq r<2^{160}} .</li> <li>Compute y ← h b r e m N {\displaystyle y\leftarrow h^{b}remN} , where b ← e − 1 ( a − r ) r e m ( p ′ q ′ ) {\displaystyle b\leftarrow e^{-1}(a-r)rem(p'q')} ,and where p ′ = ( p − 1 ) / 2 {\displaystyle p'=(p-1)/2} and q ′ = ( q − 1 ) / 2 {\displaystyle q'=(q-1)/2} .</li> <li>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}})} .</li> <li>Return σ {\displaystyle \sigma } </li></ol> <h2 id="notes">Notes</h2> <p>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 в.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a> </p> <h2 id="implementation-utilization-and-performance">Implementation, Utilization and Performance</h2> <p>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. </p><p>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: </p> Time costs on basic operations<table><tbody><tr><td></td><td colspan="2">Power PC</td><td colspan="2">Pentium</td></tr><tr><td></td><td colspan="2">Operand size(byte)</td><td colspan="2">Operand size(byte)</td></tr><tr><td></td><td>512</td><td>1024</td><td>512</td><td>1024</td></tr><tr><td>Multiplication</td><td>3.5×10−5 s</td><td>1.0×10−4 s</td><td>4.5×10−5 s</td><td>1.4×10−4 s</td></tr><tr><td>Squaring</td><td>3.3×10−5 s</td><td>1.0×10−4 s</td><td>4.4×10−5 s</td><td>1.4×10−4 s</td></tr><tr><td>Exponentiation</td><td>1.9×10−2 s</td><td>1.2×10−1 s</td><td>2.6×10−2 s</td><td>1.7×10−1 s</td></tr></tbody></table> Performance of encryption scheme and signature scheme<table><tbody><tr><td></td><td colspan="2">Power PC</td><td colspan="2">Pentium</td></tr><tr><td></td><td>Fixed costs (ms)</td><td>MBit/sec</td><td>Fixed costs (ms)</td><td>MBit/sec</td></tr><tr><td>Encrypt</td><td>160</td><td>18</td><td>230</td><td>16</td></tr><tr><td>Decrypt</td><td>68</td><td>18</td><td>97</td><td>14</td></tr><tr><td>Sign</td><td>48</td><td>64</td><td>62</td><td>52</td></tr><tr><td>Sign set-up</td><td>29</td><td></td><td>41</td><td></td></tr><tr><td>Verify</td><td>52</td><td>65</td><td>73</td><td>53</td></tr></tbody></table> <h2 id="literature">Literature</h2> <h2 id="external-links">External links</h2> <ul><li><a href="http://www.alphaworks.ibm.com/tech/ace">http://www.alphaworks.ibm.com/tech/ace</a></li> <li><a href="http://www.zurich.ibm.com/security/ace/">http://www.zurich.ibm.com/security/ace/</a></li> <li><a href="https://www.cosic.esat.kuleuven.be/nessie/deliverables/decision-final.pdf">NESSIE Portfolio of recommended cryptographic primitives</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>ACE: The Advanced Cryptographic Engine, T. Schweinberger and V. Shoup, manuscript 2000 <a href="http://www.zurich.ibm.com/security/ace/ace_spec.pdf" target="_blank">http://www.zurich.ibm.com/security/ace/ace_spec.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> </ol>