Rabin cryptosystem

The Rabin cryptosystem is within the cryptology an asymmetric cryptosystem , whose security provable on the factoring based and with RSA is used. It can also be used for a signature . In practice, however, the process is rarely used. The decryption is not unambiguous, as there are several, usually four, solutions for x of the equation . ${\displaystyle y=x^{2}{\bmod {n}}}$

history

The procedure was published in January 1979 by Michael O. Rabin . The Rabin cryptosystem was the first asymmetric cryptosystem , in which it could be proved mathematically that it is at least as difficult to solve as the factorization problem (which is assumed to be not efficiently solvable).

Key generation

Like all asymmetric cryptosystems , the Rabin cryptosystem also uses a public key and a secret key (private key). The public key is used for encryption and can be published without hesitation, while the secret key is used for decryption and may only be known to the recipients of the message.

A detailed mathematical description of the key generation follows:

Let two prime numbers that are as large as possible , often short as written, for which a certain congruence condition must apply. The public key is generated by multiplying the two numbers, so . The secret key is the couple . In other words: if you only know, you can encrypt but not decrypt; if you, on the other hand , know and can decrypt with it. If and were not prime numbers, the procedure would not be applicable. ${\displaystyle p,q}$ ${\displaystyle p,q\in \mathbb {P} }$ ${\displaystyle n}$ ${\displaystyle n=p\cdot q}$ ${\displaystyle (p,q)}$ ${\displaystyle n}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle p}$ ${\displaystyle q}$

Example:

If you accept and , then this results in the public key . and are valid numbers because they are prime numbers and the congruence condition applies to them. ${\displaystyle p=7}$ ${\displaystyle q=11}$ ${\displaystyle n=p\cdot q=77}$ ${\displaystyle 7}$ ${\displaystyle 11}$

In reality, much larger numbers are used to make third party decryption difficult (prime numbers on the order of and larger). ${\displaystyle 10^{200}}$

Congruence condition

In the Rabin cryptosystem, the prime numbers and are usually chosen so that the congruence condition applies. ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle p\equiv q\equiv 3{\pmod {4}}}$

This condition simplifies and speeds up the decryption. In general, the following applies: Let be a prime number with and with , then one finds a square root of with ${\displaystyle r}$ ${\displaystyle r\equiv 3{\pmod {4}}}$ ${\displaystyle a\in \mathbb {Z} }$ ${\displaystyle a\equiv b^{2}{\pmod {r}}}$ ${\displaystyle s}$ ${\displaystyle a}$

${\displaystyle s\equiv a^{\frac {r+1}{4}}{\pmod {r}}}$.

So it applies

${\displaystyle s^{2}\equiv a^{\frac {r+1}{2}}\equiv b^{r+1}\equiv b^{2}\equiv a{\pmod {r}}}$

because of the little Fermat's theorem . ${\displaystyle b^{r-1}\equiv 1{\pmod {r}}}$

Since is a prime number, either or is also true . ${\displaystyle r}$ ${\displaystyle s\equiv b{\pmod {r}}}$ ${\displaystyle s\equiv -b{\pmod {r}}}$

Because of this , the congruence condition is already fulfilled in the example. ${\displaystyle 7\equiv 11\equiv 3{\pmod {4}}}$

Encryption

With the Rabin method any plain text from the set can be encrypted. Alice, who wants to encrypt such plain text, only needs to know the public key of the recipient Bob. It then calculates the ciphertext using the formula ${\displaystyle m}$ ${\displaystyle \{0,\ldots ,n-1\}}$ ${\displaystyle n}$ ${\displaystyle c}$

${\displaystyle c\equiv m^{2}{\pmod {n}}}$

In practical use, the use of block ciphers is recommended .

In our example, let the plaintext dream be the plaintext. The ciphertext is here now . ${\displaystyle P=\{0,...,76\}}$ ${\displaystyle m=20}$ ${\displaystyle c\equiv m^{2}{\pmod {n}}\equiv 15{\pmod {n}}}$

You have to note that for exactly four different that has the value 15, namely for . Every quadratic remainder has exactly four different square roots modulo . ${\displaystyle m}$ ${\displaystyle c}$ ${\displaystyle m\in \{13,20,57,64\}}$ ${\displaystyle c}$ ${\displaystyle n=pq}$

Decryption

Decryption

During the decryption , the plain text is calculated again from the ciphertext using the secret key .

The exact mathematical procedure is now described:

Be general and known, search with . For compound (e.g. ours ) there is no efficient way to determine . With a prime number (in our case and ), however, the Chinese remainder can be used. ${\displaystyle c}$ ${\displaystyle r}$ ${\displaystyle m\in \{0,...,n-1\}}$ ${\displaystyle m^{2}\equiv c\,{\pmod {r}}}$ ${\displaystyle r}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle r\in \mathbb {P} }$ ${\displaystyle p}$ ${\displaystyle q}$

In our case we are looking for square roots : ${\displaystyle m_{p},m_{q}}$

${\displaystyle m_{p}^{2}\equiv c{\pmod {p}}}$

and

${\displaystyle m_{q}^{2}\equiv c{\pmod {q}}}$

Because of the above congruence condition we can choose:

${\displaystyle m_{p}\equiv c^{\frac {p+1}{4}}{\pmod {p}}}$

and

${\displaystyle m_{q}\equiv c^{\frac {q+1}{4}}{\pmod {q}}}$.

In our example we get and . ${\displaystyle m_{p}=1}$ ${\displaystyle m_{q}=9}$

Using the extended Euclidean algorithm are now having determined. In our example we get . ${\displaystyle y_{p},y_{q}}$ ${\displaystyle y_{p}\cdot p+y_{q}\cdot q=1}$ ${\displaystyle y_{p}=-3,y_{q}=2}$

Now, taking advantage of the Chinese remainder theorem , the four square roots , , and of calculated ( stands as usual for the amount of residue classes modulo ; the four square roots lie in the set ): ${\displaystyle +r}$ ${\displaystyle -r}$ ${\displaystyle +s}$ ${\displaystyle -s}$ ${\displaystyle c+n\mathbb {Z} \in \mathbb {Z} /n\mathbb {Z} }$ ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ ${\displaystyle n}$ ${\displaystyle \{0,...,n-1\}}$

${\displaystyle {\begin{aligned}r&=(y_{p}\cdot p\cdot m_{q}+y_{q}\cdot q\cdot m_{p}){\pmod {n}}\\-r&=n-r\\s&=(y_{p}\cdot p\cdot m_{q}-y_{q}\cdot q\cdot m_{p}){\pmod {n}}\\-s&=n-s\end{aligned}}}$

One of these square roots is again the initial plaintext . The following applies in the example . ${\displaystyle \mod \,n}$ ${\displaystyle m}$ ${\displaystyle m\in \{64,\mathbf {20} ,13,57\}}$

rating

effectiveness

The decryption provides three more results in addition to the plain text, so the correct result must be guessed. This is the major disadvantage of the Rabin cryptosystem.

But you can choose plain texts with a special structure. As a result, however, the equivalence to the factorization problem is lost, as can be shown. The system is thus weakened.

Efficiency

A squaring must be carried out during encryption . This is more efficient than RSA with the exponent 3. ${\displaystyle \mod \,n}$

The decryption requires the use of the Chinese remainder of the law and a modular exponentiation and . The efficiency of the decryption is comparable to RSA . ${\displaystyle \mod \,p}$ ${\displaystyle \mod \,q}$

safety

The great advantage of the Rabin cryptosystem is that you can only break it if you can efficiently solve the factorization problem described .

In contrast to RSA , for example, it can be shown that the Rabin cryptosystem is just as difficult to break as the factorization problem on which it is based. It is therefore safer. So whoever can break the Rabin method can also solve the factorization problem and vice versa. It is therefore considered a safe practice as long as the factorization problem remains unsolved. As already described, it is a prerequisite that the plain texts do not have a specific structure.

Since efforts are also made to solve factoring problems outside of cryptology, a solution would quickly spread among experts. But that has not happened so far. One can therefore assume that the underlying factorization problem is currently unsolvable. An attacker who just eavesdropping will therefore not currently be able to break the system.

An active attacker, however, can break the system with an attack with a freely selectable ciphertext attack (English chosen-ciphertext attack ), as can be shown mathematically. For this reason, the Rabin cryptosystem is rarely used in practice.

By adding redundancy, e.g. B. Repeating the last 64 bits, the root becomes unique. This thwarted the attack (because the decryptor only returns the root that the attacker already knows). As a result, the equivalence of security to the Rabin cryptosystem can no longer be proven. However, according to the Handbook of Applied Cryptography by Menezes, Oorschot and Vanstone, the equivalence holds under the assumption that the root extraction is a two-part process (1. extract root and root and 2. apply the Chinese remainder algorithm). ${\displaystyle \mod \ p}$ ${\displaystyle \mod \ q}$

Since only the square remainders are used in the coding (in the example these are only 23 of the 76 possible states), the method can also be attacked. ${\displaystyle n=77}$

literature

• Johannes Buchmann: Introduction to Cryptography , 2nd, extended edition. Springer, Berlin et al. 2001 ISBN 3-540-41283-2 (p. 125 ff.)
• Michael O. Rabin: Digitalized Signatures and Public-Key Functions as Intractable as Factorization . MIT-LCS-TR 212, MIT Laboratory for Computer Science, January 1979 (original English article)

Individual evidence

1. ↑ Handbook of Applied Cryptography. Retrieved May 23, 2006 .