Rabin cryptosystem

The Rabin cryptosystem is within cryptology an asymmetric cryptosystem whose security is provable on the factorisation and which is related to RSA. It can in principle also be used for signature. In practice, the method is hardly applicable since the decryption is not unique, in addition there are certain opportunities for attack.

History

The method was published in January 1979 by Michael O. Rabin. The Rabin cryptosystem was the first asymmetric cryptosystem, in which could be proved by mathematical way that it is at least as difficult to solve as the factoring problem ( which is assumed to be solved efficiently ).

Key generation

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

There now follows a precise mathematical description of the key generation:

Be two large prime numbers as possible, often abbreviated as written, for a certain congruence must apply. The public key is generated by multiplying the two numbers, ie. The secret key is the pair. In other words: Who knows just can not decrypt ver - but, on the other hand who knows and can decrypt with it. Had and no primes, so the process would not apply.

Example:

If one accepts and then results from the public key. 7 and 11 are valid numbers because they are prime numbers and the coincidence constraint applies to this.

In reality, much larger numbers are used for decryption by third parties difficult to make ( primes on the order of and larger).

Congruence

In Rabin cryptosystem, the prime numbers p and q usually chosen so that the congruence is valid.

This condition simplifies and speeds up the decryption process. In general, namely: Let r be a prime number and then you will find a square root s of a with

It is therefore necessary.

Since r is a prime number, is also considered either or.

Because of the coincidence constraint is already satisfied in the example.

Encoding

With the Rabin method can be arbitrary plaintexts from the amount encrypt. Alice wants to encrypt a plaintext such, has to know only the public key of the receiver Bob. It then calculates the ciphertext according to the formula

In practical use, offers the use of block cipher.

In our example, let the plaintext space, the plaintext. The ciphertext is here now.

Here one must note that for exactly four different which has the value 15, ie for. Each square residual has exactly four square roots modulo.

Decryption

In the decryption of the plaintext from the ciphertext is calculated using the secret key again.

The exact mathematical procedure will now be described:

Be general and known, sought is with. For composite (eg, ours) is no efficient method for determining exists. Otherwise, if so take advantage ( in our case, and ), but then can the Chinese remainder theorem.

In our case, are now the square roots

And

Sought.

Because of the above congruence holds:

And

In our example, arise and.

With the extended Euclidean algorithm are now and, with determined. In our example, we obtain and.

Taking advantage of the Chinese Remainder Theorem are now the four square roots, and calculates ( as usual, stands for the amount of residue classes modulo, the four square roots are in volume):

One of these square roots is the initial plaintext. In the example considered.

Assessment

Effectiveness

In addition to plain text decryption provides three additional results, the correct result should therefore be guessed. This is the major drawback of the Rabin cryptosystem.

But you can choose plaintexts with special structure. This, however, is lost to the equivalence of factoring, as can be shown. The system is so weakened.

Efficiency

When encrypting a squaring must be performed. This is more efficient than RSA with exponent 3

Decryption requires the application of the Chinese remainder theorem and one modular exponentiation and. The efficiency of the decryption is similar to RSA.

Security

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

Unlike materials such as RSA can be shown that the Rabin cryptosystem as hard to break as the factoring problem on which it is based. It is thus safer. So if you can break the Rabin method, which can solve the factoring problem and vice versa. It is therefore considered as a safe method as long as the factoring problem is unsolved. Provided is as described, however, that the plain texts have no particular structure.

As one endeavors outside of cryptology to solve Faktorisierungsprobleme, a solution would spread rapidly in the professional world. But that has not happened. One can therefore assume that the underlying factorization problem is currently intractable. An attacker who only overheard, is therefore currently not be able to break the system.

However, an active attacker can attack the system with a with free choice of ciphertext ( chosen- ciphertext attack english ) break, as can be demonstrated mathematically. For this reason, the Rabin cryptosystem is in practice rarely used.

By adding redundancy, such as repeating the last 64, the root is unique. Thus the attack is thwarted (because the descrambler only returns the root that already knows the attacker ). Thus, the equivalence of security for Rabin cryptosystem is not provable. However, according to the Handbook of Applied Cryptography by Menezes, Oorschot and Vanstone, the equivalence holds under the assumption that the square root of two-tier process ( pull first root and root and apply 2 Chinese remainder theorem algorithm).

Since in the encoding, only the quadratic residues may be used ( in the example these are only 23 of the 76 possible states ), the process is also vulnerable.