Rabin#
The Rabin class implements the Rabin public-key encryption algorithm, whose security is based on the Integer Factorization problem.
- class Rabin#
Creates a new Rabin instance.
Introduction#
The Rabin encryption algorithm is a public-key cryptosystem based on the mathematical problem of factoring large numbers. It is closely related to RSA but with a different approach to encryption. Like RSA, Rabin relies on the difficulty of factoring large composite numbers, but the encryption and decryption processes in Rabin use quadratic residues. The algorithm is probabilistically secure, meaning that the decryption process may result in multiple potential plaintext values, making it inherently different from RSA in certain applications.
Mathematical Details#
Rabin Key Generation#
The Rabin key generation process involves the following steps:
Choose two large prime numbers: Two large prime numbers, \(p\) and \(q\), are chosen randomly.
Compute the modulus: The modulus, \(n\), is computed as:
Public and private keys: The public key is the modulus \(n\), and the private key is the tuple of the two primes \((p, q)\).
Rabin Encryption/Decryption Process#
Encryption: The plaintext message, \(m\), is encrypted using the public key \(n\) as follows:
Decryption: The ciphertext \(c\) is decrypted using the private key \((p, q)\) as follows:
Using Lagrange’s simplification for primes \(\equiv 3 \mod 4\):
\begin{gather*} a = c^{(p+1)/4} \mod p, \quad x_q = p^{-1} \mod q\\ b = c^{(q+1)/4} \mod p, \quad y_p = q^{-1} \mod p \end{gather*}The potential plaintext values are then computed as:
\begin{gather*} m_1 = (a \cdot q \cdot y_p + b \cdot p \cdot x_q) \mod n\\ m_2 = -m_1 \mod n\\ m_3 = (a \cdot q \cdot y_p - b \cdot p \cdot x_q) \mod n\\ m_4 = -m_3 \mod n \end{gather*}
The correct message is then determined by comparing with the SHA256 hash of the plaintext.
Rabin Signature/Verification Process#
Signature: The hash of the plaintext message, \(m_h\), is signed using the private key \((p, q)\) as follows:
Compute:
\begin{gather*} a = c^{(p+1)/4} \mod p, \quad x_q = p^{-1} \mod q\\ b = c^{(q+1)/4} \mod p, \quad y_p = q^{-1} \mod p \end{gather*}Any one of the roots, as derived using the method described in decryption, can be used as the signature. Therefore:
\[s = (a \cdot q \cdot y_p + b \cdot p \cdot x_q) \mod n\]
Verification: The result of verification of the signature, \(s\), for a message \(m\) with hash \(m_h\), using the public key \(n\), is given by:
Usage#
# Example usage of Rabin to encrypt, decrypt, sign and verify a message
from cryptosystems import Rabin
cipher = Rabin()
public_key, private_key = cipher.generate_keys() # Generate Rabin keys
ciphertext, message_hash = cipher.encrypt("Hello World", public_key)
print(ciphertext) # 123456, b'\x12\x34\x56\x78\x90'
plaintext = cipher.decrypt(ciphertext, message_hash, private_key, "str")
print(plaintext) # 'Hello World'
signature, message_hash = cipher.sign("Hello World", private_key)
print(signature, message_hash, sep=", ") # 123456, b'\x12\x34\x56\x78\x90'
verification = cipher.verify(signature, message_hash, public_key)
print(verification) # True
Methods#
- generate_keypair() tuple#
Generates a new Rabin key pair, in the form \(n\) for the public key and \((p, q)\) for the private key.
- Returns:
A tuple containing the public key and private key.
- Return type:
- encrypt(plaintext: int | str | bytes, public_key: int) int#
Encrypts the given plaintext using the Rabin algorithm and returns the ciphertext.
- decrypt(ciphertext: int, private_key: tuple, return_type: str)#
Decrypts the given ciphertext using the Rabin algorithm and returns the deciphered plaintext.
- Parameters:
- Returns:
The decrypted plaintext.
- Return type:
- sign(message: int | str | bytes, private_key: tuple) tuple#
Signs the given message using the Rabin Algorithm and returns the signature and the SHA256 hash.