RSA

RSA#

The RSA class implements the Rivest-Shamir-Adleman public-key encryption algorithm, whose security is based upon the Integer Factorization problem.

class RSA#

Creates a new RSA instance.

Parameters:

  • bits (int) – Number of bits for the modulus. Primes are generated having half the bits. Default is 2048.

  • force (bool) – Argument to force computations with higher orders of numbers, irrespective of resultant performance.

Note

The implementation of RSA in this module follows the standards set by NIST in FIPS 186-5. Refer the Standards to see the full list of NIST Standards and Guidelines considered.

Introduction#

The Rivest-Shamir-Adleman (RSA) algorithm is a widely used public-key encryption algorithm that provides secure data transmission. It is based on the principles of asymmetric cryptography, where a pair of keys is used to encrypt and decrypt data. The security of RSA relies on the difficulty of factoring large composite numbers, which makes it computationally infeasible to determine the private key from the public key.

Mathematical Details#

RSA Key Generation#

The RSA key generation process involves the following steps:

  1. Choose two large prime numbers: Two large prime numbers, \(p\) and \(q\), are chosen randomly.

  2. Compute the modulus: The modulus, \(n\), is computed as:

\[n = p \cdot q\]

  1. Compute the totient: The Euler’s totient, \(\phi(n)\), is computed as:

\[\phi(n) = (p-1) \cdot (q-1)\]

  1. Choose the public exponent: A small prime number, \(e\), is chosen as the public exponent. In the implementation, the standard value of 65537 is used.

  2. Compute the private exponent: The private exponent, \(d\), is computed as:

\[d = e^{-1} \mod \phi(n)\]

The public key is then the pair \((n, e)\), and the private key is \((n, d)\).

RSA Encryption/Decryption Process#

  • Encryption: The plaintext message, \(m\), is encrypted using the public key \((n, e)\) as follows:

\[c = m^e \mod n\]

  • Decryption: The ciphertext message, \(c\), is decrypted using the private key \((n, d)\) as follows:

\[m = c^d \mod n\]

RSA Signature/Verification Process#

  • Signature: The hash of the plaintext message, \(m_h\), is signed using the private key \((n, d)\) as follows:

\[s = m_h^d \mod n\]

  • Verification: The signature, \(s\), for a message \(m\) with hash \(m_h\), is verified using the public key \((n, e)\) as follows:

\[m_h' = s^e \mod n\]

The result of the verification is given by:

\[m_h' \stackrel{?}{=} m_h\]

Usage#

# Example usage of RSA to encrypt, decrypt, sign and verify a message
from cryptosystems import RSA
cipher = RSA()
public_key, private_key = cipher.generate_keys()  # Generate RSA keys
ciphertext = cipher.encrypt("Hello World", public_key)
print(ciphertext) # 123456
plaintext = cipher.decrypt(ciphertext, 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 RSA key pair, in the form \(((n, e), (n, d))\).

Returns:

A tuple containing the public key and private key.

Return type:

tuple

encrypt(plaintext: int | str | bytes, public_key: tuple) → int#

Encrypts the given plaintext using the RSA algorithm and returns the ciphertext.

Parameters:

  • plaintext (int | str | bytes) – The plaintext message to be encrypted.

  • public_key (tuple) – The public key used for encryption, in the form \((n, e)\).

Returns:

The encrypted ciphertext.

Return type:

int

decrypt(ciphertext: int | str | bytes, private_key: tuple, return_type: str)#

Decrypts the given ciphertext using the RSA algorithm and returns the deciphered plaintext.

Parameters:

  • ciphertext (int | str | bytes) – The ciphertext message to be decrypted.

  • private_key (tuple) – The private key used for decryption, the form \((n, d)\).

  • return_type (str) – The type in which plaintext is to be returned. It should be either ‘int’, ‘str’, or ‘bytes’. Default is ‘int’

Returns:

The decrypted plaintext.

Return type:

int | str | bytes

sign(message: int | str | bytes, private_key: tuple) → tuple#

Signs the given message using the RSA Algorithm and returns the signature and SHA256 hash.

Parameters:

  • message (int | str | bytes) – The plaintext message to be signed.

  • private_key (tuple) – The private key used for signature, the form \((n, d)\).

Returns:

The tuple of signature (int) and the SHA256 hash (bytes) of the message.

Return type:

tuple

verify(signature: int | str | bytes, message_hash: bytes, public_key: tuple) → bool#

Verifies the given signature using the RSA Algorithm and returns True or False.

Parameters:

  • signature (int | str | bytes) – The signature to be verified.

  • message_hash (bytes) – The SHA256 hash for the message.

  • public_key (tuple) – The public key used for verification, the form \((n, e)\).

Returns:

True or False, the result of whether the message is verified.

Return type:

bool

References#