Skip to content

RSA algorithm↑

RSA is among the most widely used public key cryptographic primitives for encryption, digital signatures, as well as a basis for key encapsulation and key agreement protocols.

Using small RSA keys can lead to a complete security breach, compromising confidentiality, authentication, or both, depending on the application. This can also pose a compliance threat. Moreover, RSA is vulnerable to quantum attacks. As a result, RSA is quantum-vulnerable and must be replaced with quantum-resistant alternatives to maintain security against quantum adversaries.

Despite being a well-studied cryptosystem, RSA requires careful implementation to ensure security. To minimize the risk of faulty implementation, use well-established cryptographic libraries, which are developed and maintained by qualified cryptographic engineers.

Detailed description↑

General introduction↑

RSA is a public-key cryptosystem that enables secure data encryption and digital signatures, relying on the mathematical difficulty of factoring large composite numbers. It works by generating a pair of keys: a public key for encryption or signature verification and a private key for decryption or signature generation, ensuring that only the intended recipient or signer can perform the corresponding cryptographic operation. During key generation, two large primes are chosen independently and with enough randomness. Their product is taken as the RSA modulus. The cryptographic primitives are designed such that the participating entities perform modular exponentiation, raising a number to an exponent modulo the chosen exponent. This modular exponentiation can be computed efficiently. An eavesdropper attempting to decrypt an encryption or forge a signature is faced with a hard computational problem, which is inverse to modular exponentiation.
Next, we provide an example focussing on encryption to provide intuition to the reader. It is followed by a description of the signature modes.

Key Generation example: RSA key generation starts with two distinct odd prime numbers, p and q, generated at random. The RSA modulus is their product, n=pq. The RSA encryption exponent e\<(p-1)(q-1) with certain mathematical properties is then chosen. A popular choice in practice is 65537=216+1, for efficiency. The decryption exponent d is then computed as an integer such that ed equals 1 modulo the least common multiple of p-1 and q-1. The secret private key is (p,q,d) and the public key is (n,e).

Encryption scheme example: Consider Bob wanting to encrypt and send a message m to Alice. Alice generates a key pair as above, sends Bob the public key (n,e) and keeps the private key (p,q,d) secret. Bob encodes the message into a positive integer encode(m)<n and sends Alice the encrypted message c= encode(m)e modulo n. Here, encode(m) is a possibly randomized cryptographically secure encoding function. The arithmetic of RSA is such that Alice can recover encode(m) as cd modulo n.

In the original RSA proposal, the encoding function is deterministic. The resulting encryption and decryption primitives are referred to as RSAEP and RSADP, respectively, by IETF PKCS1. It is a deterministic encryption scheme, meaning that, given a chosen public key, the encryption is a deterministic function of the message. Therefore, it is not semantically secure and vulnerable to chosen-plaintext attacks. Furthermore, it is malleable and insecure under chosen cipher-text attacks.

To mitigate these issues, the message has to be randomly “padded” appropriately while being encoded as an integer. Two encryption modes resulting from the choice of padding are RSAES-PKCS1-v1_5 and RSAES-OAEP. The RSAES-PKCS1-v1_5 padding scheme predates RSAES-OAEP and is deprecated by IETF due to vulnerability to the Bleichenbacher attack.

RSAES-OAEP. The Optimal Asymmetric Encryption Padding (OAEP) is a padding scheme to mitigate aforementioned security issues arising from plain RSA being a deterministic encryption scheme (see, for instance NIST SP 800-56B Rev. 2, section 7.2.2). It consists of encryption/decryption primitives RSAEP/RSADP, a cryptographic hash function H, a possibly different cryptographic hash function to serve as a mask generating function (MGF) and a random number bit generator (RBF). RSAES-OAEP is IND-CCA2 secure, meaning it ensures security even against chosen-ciphertext attacks such as the Bleichenbacher attack.

RSA Signature: There are two signature modes, namely RSASSA-PSS and RSASSA-PKCS1-v1_5 (see for instance, IETS #1: RSA Cryptography Specifications Version 2.2.) Unlike the encryption case, no attacks are known against the signature scheme RSASSA-PKCS1-v1_5 using the PKCS1-v1_5 padding. Yet, as a precautionary measure, IETF requires RSASSA-PSS in new applications. RSASSA-PKCS1-v1_5 schemes may still persist, for compatibility with existing applications.

RSA Key Agreement: NIST SP 800-56B Rev. 2 describes two families (KAS1 and KAS2) of RSA based key agreement schemes and a family KTS-OAEP of key transfer mechanisms. Both the agreement schemes employ RSA secret value encapsulation RSASVE as a primitive. The main distinction between KAS1 and KAS2 is that in the former, only one of the party’s key-establishment keys is used. In the latter, both the party’s key-establishment keys are used. As a consequence, KAS1 only comes with two confirmation modes KAS1-basic (with no confirmation) and KAS1-party_V-confirmation. Whereas KAS2 accommodates KAS2-basic, KAS2-party_V-confirmation, KAS2-party_U-confirmation and KAS2- bilateral-confirmation. See NIST SP 800-56B Rev. 2 section 10 for contexts in which KAS1, KAS2 or KTS-OAEP are recommended.

Security recommendations↑

The best known classical cryptanalytic algorithm to break RSA is the Number Field Sieve integer factorization algorithm. Recent examples illustrate the vulnerability of small keys:

  • In 2024, an 829-bit key was broken (factored) using 2700 core years of computation, costing an estimated $120,000—affordable to organized threat actors.
  • By comparison, factoring RSA-512 in 2015 cost just $75 in 4 hours, making it accessible to individual attackers.

As a consequence, to guarantee bit security on the order of hundreds, RSA key lengths need to be in the thousands of bits. For instance, NIST SP 800-57 PART 1 REV. 5 recommends RSA key lengths of 3072 bits for 128-bit security and 7682 bits for 256-bit security. A shorter key length risks an attacker recovering the secret key, with consequences including forged signatures, disclosure of plaintext from encrypted data, etc. For instance, a conservative stance is to consider big organizations and nation-states as possessing the resources to break RSA with key length 1024.

Shor’s algorithm can factor integers efficiently with access to fault tolerant quantum computers, thereby breaking RSA in the advent of fault tolerant quantum computers. Therefore, RSA is not considered to be post-quantum secure.

RSA cryptographic primitives should be implemented using well-established cryptographic libraries, adhering to the list of validations for RSA keys is in NIST SP 800-89 5.3.3 and FIPS 186-3. For guidance on proper RSA implementation, refer to established standards and guidelines, including:

  • NIST SP 800-56B REV. 2
  • NIST SP 800-89
  • NIST SP 800-57 PART 1 REV. 5
  • IETF PKCS #1: RSA Cryptography Specifications Version 2.2

Sources↑