Overview
RSA works over integers modulo a product of two large primes. Public and private exponents are chosen so that modular exponentiation with one key can be inverted only with the matching key.
FoundationSource checked
RSA
Uses modular arithmetic with a public key and private key for encryption or signatures.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Cryptography
- Difficulty
- Advanced
- Family
- Public-Key Cryptography
- Tier
- Foundation
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 1
- Relationships
- 8
- Code example
- Not ready
- Visualization
- Ready
Core Concepts
public keyprivate keymodular exponentiationpadding scheme
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(k^2)
Average
O(k^3)
Worst
O(k^3)
Space
O(k)
When to Use
- Use vetted cryptographic libraries rather than implementing RSA directly.
- Use it when interoperability requires RSA signatures or encryption.
- Use modern padding schemes such as OAEP or PSS as appropriate.
When Not to Use
- Avoid textbook RSA without padding.
- Avoid implementing key generation or padding yourself in production.
- Avoid RSA for new key agreement designs when modern elliptic-curve options are available.
What It Does
- Computes public-key cryptography within Public-Key Cryptography workloads (O(k^3) time, O(k) space).
- Works by Public and private exponents are chosen so that modular exponentiation with one key can be inverted only with the matching key.
- Maintains key invariants across public key, private key, modular exponentiation.
Use Cases
- Digital signatures
- Key transport in legacy protocols
- Teaching public-key cryptography
Inputs
- Public or private key
- Message or digest
Outputs
- Ciphertext
- Signature
- Verification result
Key Formulas (1)
RSA transform
ciphertext = messagee mod n
ciphertext = message^e mod nApplies modular exponentiation with the public exponent and modulus.
Pseudocode
- 1.Generate two large prime numbers
- 2.Build a modulus from their product
- 3.Choose matching public and private exponents
- 4.Apply modular exponentiation to encrypt or sign
- 5.Apply the matching key operation to decrypt or verify
Canonical Example
- Input
- message digest, RSA private key, and PSS padding
- Output
- digital signature
- Explanation
- The signer applies padded RSA with the private key; verifiers check the signature with the public key.
Implementation Notes
- Use constant-time, audited cryptographic libraries.
- Validate key sizes, padding modes, and randomness requirements.
- Keep encryption and signature APIs separate.
Common Pitfalls
- Using raw RSA without padding.
- Choosing weak key sizes or nonstandard public exponents.
- Leaking timing information during private-key operations.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow public and private keys being used for encryption or signatures.
Step 1 of 5: Generate two large prime numbers
key-pair-flowNotes
Textbook RSA is a mathematical primitive; secure systems rely on padding, validation, and side-channel-resistant implementations.
Sources (2)
What each reference supports for this entry.
RFC 8017
DocumentationIETF PKCS #1 reference for RSA cryptographic primitives and schemes.
Open sourceNIST FIPS 186-5
DocumentationNIST Digital Signature Standard covering RSA, ECDSA, and EdDSA signature algorithms.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Alternative toElliptic Curve Digital Signature Algorithm
Cryptography · Specialized
RSA and ECDSA can both support digital signatures with different mathematics.
Compare with thisUsesExponentiation by Squaring
Numerical Methods · Foundation
RSA public and private operations are modular exponentiations.
Compare with thisUsesModular Exponentiation
Cryptography · Foundation
RSA encryption, decryption, signing, and verification are modular exponentiation operations.
Compare with thisConceptual neighborDiffie-Hellman Key Exchange
Cryptography · Foundation
Both are public-key cryptographic primitives.
Compare with thisRelationships
View full relationship pageConceptual neighborDiffie-Hellman Key Exchange
Both are public-key cryptographic primitives.
Alternative toElliptic Curve Digital Signature Algorithm
RSA and ECDSA can both support digital signatures with different mathematics.
Related Algorithms
Tags
CryptographyPublic KeySecurity