ACE (Advanced Cryptographic Engine) — 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.
Contents
- Authors
- Security
- Basic Terminology and Notation
- Basic mathematical notation
- Basic string notation
- Bits Bytes Words
- Conversion operator
- Encryption Key Pair
- Key Generation
- Ciphertext Representation
- Encryption Process
- Decryption process
- Signature Scheme
- Signature Representation
- Signature Generation Process
- Implementation Utilization and Performance
- References
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:
Basic Terminology and Notation
Here we introduce some notations, being used in this article.
Basic mathematical notation
Basic string notation
For
For
Bits, Bytes, Words
Let us take all sets of form
We define
For
Conversion operator
Conversion operator
Encryption Key Pair
The encryption scheme employs two key types:
ACE public key:
ACE private key:
For a given size parameter m
Key Generation
Algorithm. Key Generation for ACE encryption scheme.
Input: a size parameter m
Output: a public/private key pair.
- Generate a random prime
q , such that 2 255 < q < 2 256 . - Generate a random prime
P , 2 m − 1 < P < 2 m , such that P ≡ 1 ( m o d q ) . - Generate a random integer
g 1 ∈ { 2 , . . . , P − 1 } , such thatg 1 q ≡ 1 ( m o d P ) . - Generate random integers
w ∈ { 1 , . . . , q − 1 } andx , y , z 1 , z 2 ∈ { 0 , . . . , q − 1 } - Compute the following integers in
{ 1 , . . . , P − 1 } :g 2 ← g 1 w r e m P ,
c ← g 1 x r e m P ,
d ← g 1 y r e m P ,
h 1 ← g 1 z 1 r e m P ,
h 2 ← g 1 z 2 r e m P . - Generate random byte strings
k 1 ∈ B 20 l ′ + 64 k 2 ∈ B 2 ⌈ l / 16 ⌉ + 40 l = L B ( P ) and l ′ = L B ( ⌈ ( 2 ⌈ l / 4 ⌉ + 4 ) / 16 ⌉ ) . - 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 ) )
Ciphertext Representation
A ciphertext of the ACE encryption scheme has the form
where the components are defined as:
We need to introduce the function
representation, and the corresponding inverse function
For integer
Encryption Process
Algorithm. ACE asymmetric encryption operation.
input: public key
Output: byte string — ciphertext
- Generate
r ∈ { 0 , . . . , q − 1 } at random. - Generate the ciphertext preamble:
- Generate
s ∈ W 4 at random. - Compute
u 1 ← g 1 r r e m P ,u 2 ← g 2 r r e m P . - Compute
α ← U O W H a s h ′ ( k 1 , L B ( P ) , s , u 1 , u 2 ) ∈ Z ; note that 0 < α < 2 160 . - Compute
v ← c r d α r r e m P .
- Generate
- Compute the key for the symmetric encryption operation:
-
h 1 ~ ← h 1 r r e m P ,h 2 ~ ← h 2 r r e m P . - Compute
k ← E S H a s h ( k , L B ( P ) , s , u 1 , u 2 , h 1 ~ , h 2 ~ ) ∈ W 8 .
-
- Compute cryptogram
e ← S E n c ( k , s , 1024 , M ) . - Encode the ciphertext:
ψ ← C E n c o d e ( L B ( P ) , s , u 1 , u 2 , v , e ) . - Return
ψ
Before starting off the symmetric encryption process, the input message
Note that if
Algorithm. ACE asymmetric encryption process.
Input:
Output:
- If
M = λ B , then return λ 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 - Generate the key
k A X U A X U H a s h : ( 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 ) . . -
e ← λ B , i ← 0 . - While
i < L ( M ) , do the following: -
r ← m i n ( 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 ) . -
( 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 ) .
-
- Encrypt the plaintext:
e n c ← [ M ] i i + r ⊕ m a s k e - Generate the message authentication code:
- If
i + r = L ( M ) , then l a s t B l o c k ← 1 ; elsel a s t B l o c k ← 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
- If
- Update the ciphertext:
e ← e | | e n c | | I W ∗ B ∗ ( m a c ⊕ m a s k m ) . -
i ← i + r .
-
- Return
e .
Decryption process
Algorithm. ACE decryption process.
Input: public key
Output: Decrypted message
- Decrypt the ciphertext:
- If
L ( ψ ) < 3 L B ( P ) + 16 , then return R e j e c t . - Compute:
( s , u 1 , u 2 , v , e ) ← C D e c o d e ( L B ( P ) , ψ ) ∈ W 4 × Z × Z × Z × B ∗
note that0 ≤ u 1 , u 2 , v < 256 l l = L B ( P ) .
- If
- Verify the ciphertext preamble:
- If
u 1 ≥ P oru 2 ≥ P orv ≥ P , then returnR e j e c t . - If
u 1 q ≠ 1 r e m P , then returnR e j e c t . -
r e j e c t ← 0 . - If
u 2 ≠ u 1 w r e m P , thenr e j e c t ← 1 . - Compute
α ← U O W H a s h ′ ( k 1 , L B ( P ) , s , u 1 , u 2 ) ∈ Z ; note that0 ≤ α ≤ 2 160 - If
v ≠ u 1 x + α y r e m P , thenr e j e c t ← 1 . - If
r e j e c t = 1 , then return R e j e c t .
- If
- Compute the key for the symmetric decryption operation:
-
h 1 ~ ← u 1 z 1 r e m P ,h 2 ~ ← u 1 z 2 r e m P . - Compute
k ← E S H a s h ( k 2 , L B ( P ) , s , u 1 , h 1 ~ , h 2 ~ ) ∈ W 8
-
- Compute
M ← S D e c ( k , s , 1024 , e ) ;note thatS D e c can return R e j e c t . - Return
M .
Algorithm. Decryption operation
Input:
Output: Decrypted message
- If
e = λ B , then return λ 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 - Generate the key
k A X U A X U H a s h : ( 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 ) . . -
M ← λ B , i ← 0 . - While
i < L ( e ) , do the following: -
r ← m i n ( L ( e ) − i , m + 16 ) − 16 . - If
r ≤ 0 , then returnR e j e c t . - 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 ) . -
( 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 ) .
-
- Verify the message authentication code:
- If
i + r + 16 = L ( M ) , then l a s t b l o c k ← 1 ; elsel a s t b l o c k ← 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 - If
[ e ] r i + r i + r + 16 ≠ I W ∗ B ∗ ( m a c ⊕ m a s k m ) , then returnR e j e c t .
- If
- Update the plaintext:
M ← M | | ( [ e ] i i + r ) ⊕ m a s k e ) . -
i ← i + r + 16 .
-
- Return
M .
Signature Scheme
The signature scheme employs two key types:
ACE Signature public key:
ACE Signature private key:
For the given size parameter
Key Generation
Algorithm. Key generation for the ACE public-key signature scheme.
Input: size parameter
Output: public/private key pair.
- Generate random prime numbers
p , q , such that ( p − 1 ) / 2 and ( q − 1 ) / 2 — is also a prime number, and 2 m 1 − 1 < p < 2 m 1 2 m 2 − 1 < q < 2 m 2 p ≠ q ,
wherem 1 = ⌊ m / 2 ⌋ andm 1 = ⌈ m / 2 ⌉ . - Set
N ← p q . - Generate random prime number
e ′ , где 2 160 ≤ e ′ ≤ 2 161 - Generate random
h ′ ∈ { 1 , . . . , N − 1 } , taking into accountg c d ( h ′ , N ) = 1 andg c d ( h ′ ± 1 , N ) = 1 , and computeh ← ( h ′ ) − 2 r e m N . - Generate random
a ∈ { 0 , . . . , ( p − 1 ) ( q − 1 ) / 4 − 1 } and computex ← h a r e m N . - Generate random byte strings
k ′ ∈ B 184 , and s ∈ B 32 . - Return public key/private key pair
( ( N , h , x , e ′ , k ′ , s ) , ( p , q , a ) ) .
Signature Representation
The signature in the ACE signature scheme has the form
We need to introduce the
For integer
Signature Generation Process
Algorithm. ACE Signature Generation Process.
Input: public key
Output: byte string — digital signature
- Perform the following steps to hash the input data:
- Generate a hash key
k ~ ∈ B 20 m + 64 m = L b ( ⌈ ( L ( M ) + 8 ) / 64 ⌉ ) . - Compute
m h ← I W ∗ Z ( U O W H a s h ′ ′ ( k ~ , M ) ) .
- Generate a hash key
- Select
y ~ ∈ { 1 , . . . , N − 1 } at random, and computey ′ ← y ~ 2 r e m N . - Compute
x ′ ← ( y ′ ) r ′ h m h r e m N . - Generate a random prime
e , 2 160 ≤ e ≤ 2 161 ( w , d ) : ( e , w , d ) ← G e n C e r t P r i m e ( s ) . Repeat this step until e ≠ e ′ . - Set
r ← U O W H a s h ′ ′ ′ ( k ′ , L B ( N ) , x ′ , k ~ ) ∈ Z ; note that0 ≤ r < 2 160 - Compute
y ← h b r e m N , whereb ← e − 1 ( a − r ) r e m ( p ′ q ′ ) ,
and wherep ′ = ( p − 1 ) / 2 andq ′ = ( q − 1 ) / 2 . - Encode the signature:
σ ← S E n c o d e ( L B ( N ) , d , w , y , y ′ , k ~ ) . - Return
σ
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:
Table 1. Time costs on basic operations.
Table 2. Performance of encryption scheme and signature scheme.