Cramer-Shoup cryptosystem

The Cramer-Shoup cryptosystem is an asymmetric cryptosystem developed by Ronald Cramer and Victor Shoup , which can be viewed as an extension of the Elgamal encryption method . It was the first practicable encryption method that was secure against adaptive chosen ciphertext attacks in the standard model (without a random oracle ). The security of the method is based on the difficulty of the Decisional Diffie-Hellman problem .

The procedure

Like all asymmetric encryption, the Cramer-Shoup method also consists of three algorithms.

Key generation

• First one chooses a cyclic group of prime order (here written multiplicatively) and in this two generators . In addition, a cryptological hash function must be specified. These values ​​are public parameters and can be used by several users at the same time. ${\displaystyle G}$ ${\displaystyle q}$ ${\displaystyle g_{1},g_{2}}$ ${\displaystyle H}$
• Then random keys are chosen as the secret key . ${\displaystyle x_{1},x_{2},y_{1},y_{2},z\in \mathbb {Z} _{q}}$
• The public key is calculated from these . ${\displaystyle c=g_{1}^{x_{1}}g_{2}^{x_{2}},d=g_{1}^{y_{1}}g_{2}^{y_{2}},h=g_{1}^{z}}$

Encryption

To encrypt a message with the public key , proceed as follows: ${\displaystyle m\in G}$ ${\displaystyle (c,d,h)}$

• A random one is chosen. ${\displaystyle r\in \mathbb {Z} _{q}}$
• ${\displaystyle u_{1}=g_{1}^{r},u_{2}=g_{2}^{r}}$
• ${\displaystyle e=h^{r}m}$ This is the encryption of the message as with ElGamal.
• ${\displaystyle \alpha =H(u_{1},u_{2},e)}$, where is a universal one-way hash function or a collision-resistant hash function. ${\displaystyle H}$
• ${\displaystyle v=c^{r}d^{r\alpha }}$. This element ensures that an attacker cannot use parts of the cipher to generate further ciphers and thus ensures the non-deformability required for security

The cipher then consists of . ${\displaystyle (u_{1},u_{2},e,v)}$

Decryption

There are two steps to decrypt a cipher with the secret key . ${\displaystyle (u_{1},u_{2},e,v)}$ ${\displaystyle (x_{1},x_{2},y_{1},y_{2},z)}$

• First you calculate and check if . If this is not the case, the decryption is aborted and an error message is output. ${\displaystyle \alpha =H(u_{1},u_{2},e)}$ ${\displaystyle u_{1}^{x_{1}}u_{2}^{x_{2}}(u_{1}^{y_{1}}u_{2}^{y_{2}})^{\alpha }=v}$
• If not, the plaintext is calculated . ${\displaystyle m=e/(u_{1}^{z})}$

correctness

The correctness of the procedure follows

${\displaystyle u_{1}^{z}=g_{1}^{rz}=h^{r}}$and . ${\displaystyle m=e/h^{r}}$

Instantiation

We choose the standard length for generic applications of 128 bit as the security level. This results in an output length of 256 bits for the hash function. SHA-256 can be assumed to be collision-resistant.

One needs a group in which the Decisional Diffie-Hellman problem is difficult to compute, such as . To do this, one chooses a prime number with a length of 3248 bits, so that the group has a multiplicative subgroup of prime order , whereby a length of 256 bits should be. That means that must apply. The choice of parameters results in a length of bit for the secret key and bit for the public key. A cipher is bit long. ${\displaystyle \mathbb {Z} _{p}^{*}}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle q}$ ${\displaystyle q|(p-1)}$ ${\displaystyle 5\cdot 256=1280}$ ${\displaystyle 3\cdot 3248=9744}$ ${\displaystyle 4\cdot 3248=12992}$

Individual evidence

1. ↑ Ronald Cramer and Victor Shoup: A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack . In: Proceedings of Crypto 1998 . 1998, p. 13--25 ( cwi.nl ).
2. ↑ ^{a b c} European Network of Excellence in Cryptology II (Ed.): ECRYPT II Yearly Report on Algorithms and Keysizes (2009-2010) . 2010, p. 30-32 ( PDF 2.4MB ). PDF 2.4MB ( Memento of the original from August 21, 2010 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice.  
3. ↑ European Network of Excellence in Cryptology II (Ed.): ECRYPT II Yearly Report on Algorithms and Keysizes (2009-2010) . 2010, p. 52 ( PDF 2.4MB ). PDF 2.4MB ( Memento of the original from August 21, 2010 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice.