RSA Encryption and Signatures

RSA defines trapdoor operations on integers modulo a composite number. Secure systems use those operations only through standardized encryption or signature schemes because textbook RSA is deterministic, malleable, and structurally unsafe.

Key Generation #

An RSA key generator obtains distinct, independently generated probable primes p and q, then calculates:

n      = p * q
phi(n) = (p - 1) * (q - 1)
lambda = lcm(p - 1, q - 1)

The modulus n determines the key size. Generation standards impose additional conditions on prime size, difference, primality testing, and random-bit generation; selecting two values that merely pass a small-prime trial division is insufficient. Applications should call an approved library key generator rather than generate primes themselves.

Choose a public exponent e such that gcd(e, lambda) = 1. The conventional choice is 65537. The private exponent is its modular inverse:

e * d = 1 (mod lambda)

Using phi(n) instead of the Carmichael value lambda can also produce a correct inverse under the PKCS #1 conditions. A public key contains (n, e). A private key normally retains p, q, d, and Chinese remainder theorem (CRT) values.

Private Operations and CRT #

The public representative m and ciphertext representative c are related by the RSA primitives:

c = m^e mod n
m = c^d mod n

Private operations can compute modulo p and q separately, then recombine the results with CRT. That optimization is substantially faster, but a fault in one branch can expose a factor of n. Cryptographic libraries therefore combine CRT protections with implementation countermeasures such as RSA blinding and result verification.

Timing, cache, power, and fault behavior belong to the threat model whenever an attacker can submit chosen ciphertexts or signatures to the device. Constant time and side-channel resistance are implementation properties, not consequences of the RSA equations.

Security Assumptions and Key Sizes #

Knowing p and q makes recovery of the private operation straightforward, so factoring the modulus is a sufficient break. No proof establishes that breaking every RSA-based scheme is exactly equivalent to factoring. Security arguments also depend on the RSA problem, the encoding scheme, the hash function, randomness, and the attack model.

Current NIST transition guidance accepts RSA moduli of at least 2,048 bits for 112-bit classical security strength. A 3,072-bit modulus corresponds to about 128-bit strength. Protocol or compliance requirements can demand a larger size or prohibit RSA for new uses. Larger keys increase CPU, bandwidth, and certificate size; they do not repair a weak padding scheme or compromised implementation.

RSA does not provide forward secrecy by itself. TLS 1.3 removed RSA key transport and establishes traffic secrets with ephemeral (EC)DHE. An RSA certificate can still authenticate a TLS 1.3 endpoint with an allowed RSA-PSS signature.

OAEP Encryption #

RSAES-OAEP encodes a message with a hash, a mask-generation function, a label, and a random seed before applying the public RSA operation. For a modulus represented by k octets and a hash output of hLen octets, the plaintext limit is:

mLen <= k - 2*hLen - 2

OAEP is therefore intended for short values such as randomly generated symmetric keys, not bulk data. A hybrid protocol encapsulates or transports a content-encryption key and protects the actual payload with authenticated encryption. The complete hybrid construction must come from a protocol standard; RSAES-OAEP alone does not authenticate application data.

The OAEP parameters are part of the algorithm identifier. Both endpoints must agree on the hash, mask-generation hash, and label. A library default from one API may not match another API’s default, so protocols must specify them.

PSS Signatures #

RSASSA-PSS hashes the message, incorporates a salt, applies a mask-generation function, and encodes the result to the modulus width before the private RSA operation. Verification reverses the public operation and validates every field. The salt length, message hash, and mask-generation hash are explicit parameters.

New protocols should use PSS when RSA signatures are required. PKCS #1 v1.5 encryption and signature encodings remain necessary in some legacy protocols, but compatibility is not a reason to select them for a new design. A verifier must implement the exact scheme identified by the protocol and reject malformed or out-of-range representatives.

Integer, ASN.1, and PEM Encodings #

PKCS #1 defines I2OSP and OS2IP to convert between nonnegative integers and fixed-length, big-endian octet strings. Leading zero octets are significant when a scheme requires exactly k octets. ASN.1 DER INTEGER values are signed, so a positive RSA integer whose high bit is set receives a leading 00 octet. Confusing those rules causes truncated, negative, or wrong-width values.

Common containers have different structures:

PEM adds a textual label and Base64 armor around a DER value. A label such as PUBLIC KEY and RSA PUBLIC KEY therefore identifies different ASN.1 structures. Parse the expected container with a maintained library instead of extracting integers with ad hoc Base64 and byte slicing.

Reject Textbook RSA and Padding Oracles #

Textbook RSA applies the modular exponentiation directly. It leaks plaintext equality, permits algebraic modification, and has no integrity check. Never use it for encryption or signatures, including examples promoted as “signing by encrypting a hash with the private key.”

Decryption must not reveal whether failure came from ciphertext range, OAEP structure, label hash, delimiter, or downstream plaintext parsing. Distinct errors, response times, retry behavior, or logs visible to an attacker can form a padding oracle. Use a library with oracle-resistant decoding, keep externally observable failure behavior uniform, and authenticate the enclosing protocol. Do not return partially decoded plaintext after any failure.

References #

• RFC 8017: PKCS #1 v2.2
• FIPS 186-5: Digital Signature Standard
• NIST SP 800-56B Rev. 2: Pair-Wise Key-Establishment Schemes Using Integer Factorization Cryptography
• NIST SP 800-131A Rev. 2: Transitioning the Use of Cryptographic Algorithms and Key Lengths
• RFC 8446: TLS 1.3
• RFC 7468: Textual Encodings of PKIX, PKCS, and CMS Structures