A method for obtaining digital signatures and public-key cryptosystems

1978/02/01 by Ronald L. Rivest, R. L. Rivest, Adi Shamir +3 · 13,160 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Chaos-based Image/Signal Encryption #Computer science #Computer security #Cryptography and Data Security #Cryptosystem #DECIPHER #DNA and Biological Computing #Digital signature #Encryption #Hash function #Key (lock) #Mathematics #Public-key cryptography #Signature (topology) #Theoretical computer science

paper · pdf · doi:10.1145/359340.359342

published in Communications of the ACM 21(2), 120-126 (Association for Computing Machinery)

openalex publication_date 1978/02/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

An encryption method is presented with the novel property that publicly revealing an encryption key does not thereby reveal the corresponding decryption key. This has two important consequences: (1) Couriers or other secure means are not needed to transmit keys, since a message can be enciphered using an encryption key publicly revealed by the intented recipient. Only he can decipher the message, since only he knows the corresponding decryption key. (2) A message can be “signed” using a privately held decryption key. Anyone can verify this signature using the corresponding publicly revealed encryption key. Signatures cannot be forged, and a signer cannot later deny the validity of his signature. This has obvious applications in “electronic mail” and “electronic funds transfer” systems. A message is encrypted by representing it as a number M, raising M to a publicly specified power e, and then taking the remainder when the result is divided by the publicly specified product, n , of two large secret primer numbers p and q. Decryption is similar; only a different, secret, power d is used, where e * d ≡ 1(mod (p - 1) * (q - 1)). The security of the system rests in part on the difficulty of factoring the published divisor, n .

Cited by

• Untraceable electronic mail, return addresses, and digital pseudonyms
• Security without identification: transaction systems to make big brother obsolete
• Complex architecture of primes and natural numbers
• Factoring 2048-bit RSA Integers in 177 Days with 13436 Qubits and a Multimode Memory
• Reaching Agreement in the Presence of Faults
• Communication Security via Temporal Dependency
• On the security of public key protocols
• A Smart Contract-Based Access Control Framework For Smart Healthcare Systems
• Probabilistic encryption
• Structured Design of Substitution-Permutation Encryption Networks
• (Adversarial) Electromagnetic Disturbance in the Industry
• Systolic modular multiplication
• A cubic analogue of the RSA cryptosystem
• Gaussian quantum information
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum algorithms for scientific computing
• Evaluating DV/CV-QKD Architectures for SAFE Long-Term Secure Storage: A Risk Model and ILP-Based Cost Optimization Approach
• Avoiding Obfuscation with Prover-Estimator Debate
• Quantum-Resilient Banking Transaction Security using DW-HKEM: A Hybrid RSA/ML-KEM Cryptographic Gateway with Real-Time Monitoring
• GHZ-Equivalent State Distribution in Quantum Networks: Reducing Decoherence and Quantum Resource Consumption
• Dynamic Logic with Parallel Operator for Verifying Communication Protocols
• Efficient routing and spectrum allocation in arbitrary flex-grid entanglement networks
• How to factor 2048 bit RSA integers with less than a million noisy qubits
• A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Authenticated Algorithms for Byzantine Agreement
• The effect of publicly co-funded industry-science collaboration on scientific production
• The Socio-Technological Lives of Bitcoin
• When RSA Fails: Exploiting Prime Selection Vulnerabilities in Public Key Cryptography
• Partially coherent optical chip enables physical-layer public-key encryption
• Permutation Polynomials of the form L(X)+γTr_q^q3(h(X)) over finite fields with even characteristic
• Post-Quantum Cryptography in the 5G Core
• Methods and Tools for Secure Quantum Clouds with a specific Case Study on Homomorphic Encryption
• Scalable Multiterminal Key Agreement via Error-Correcting Codes
• Enhancing the Practical Reliability of Shor's Quantum Algorithm via Generalized Period Decomposition: Theory and Large-Scale Empirical Validation
• Primitive Vector Cipher(PVC): A Hybrid Encryption Scheme based on the Vector Computational Diffie-Hellman (V-CDH) Problem
• Quantum Encrypted Control of Networked Systems
• Privacy-preserving formal concept analysis: A homomorphic encryption-based concept construction
• On Solving Structured SAT on Ising Machines: A Semiprime Factorization Study
• A knapsack McEliece-based public key cryptosystem
• Enhanced Digitized Adiabatic Quantum Factorization Algorithm Using Null-Space Encoding
• Random Permutations in Computational Complexity
• LSEG: A Lightweight and Secure Key Exchange Protocol for Smart Grid Communication
• Generalized State Discrimination for Tunable Quantum Key Distribution
• LaMoS: Enabling Efficient Large Number Modular Multiplication through SRAM-based CiM Acceleration
• New permutation polynomials over \mathbbF_q²
• GPoS: Geospatially-aware Proof of Stake
• Elementary closed-forms for non-trivial divisors
• How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
• IoT security: Review, blockchain solutions, and open challenges
• CFB-Then-ECB Mode-Based Image Encryption for an Efficient Correction of Noisy Encrypted Images
• Off-the-record communication, or, why not to use PGP
• On the History of the Square and Multiply Algorithm
• Quantum-Resistant Networks Using Post-Quantum Cryptography
• Provably efficient machine learning for quantum many-body problems
• Design and analysis of authenticated key agreement scheme in cloud-assisted cyber–physical systems
• Collaborative penetration testing suite for emerging generative AI algorithms
• A Probabilistic Computing Approach to the Closest Vector Problem for Lattice-Based Factoring
• A Congruence for Sums of Integer Powers Modulo Products of Distinct Primes
• Efficient Power-Analysis-Resistant Dual-Field Elliptic Curve Cryptographic Processor Using Heterogeneous Dual-Processing-Element Architecture
• A Meta-Complexity Characterization of Minimal Quantum Cryptography
• Integer Factoring with Unoperations
• AI-Driven Post-Quantum Cryptography for Cyber-Resilient V2X Communication in Transportation Cyber-Physical Systems
• Reproducible Builds for Quantum Computing
• RSA+: an RSA variant
• Fast adaptive optics for high-dimensional quantum communications in turbulent channels
• Quashing Quishing Attacks Using Self-Authenticating Dual-Modulated QR Codes
• A Near-Cache Architectural Framework for Cryptographic Computing
• Quantum Technology and the Military-Revolution or Hype?: The Impact of Emerging Quantum Technologies on Future Warfare
• Red Teaming Quantum-Resistant Cryptographic Standards: A Penetration Testing Framework Integrating AI and Quantum Security
• PMark: Towards Robust and Distortion-free Semantic-level Watermarking with Channel Constraints
• Towards Adapting Federated & Quantum Machine Learning for Network Intrusion Detection: A Survey
• Intro2QC: An Approachable Introduction to Quantum Computing for STEM Education in High Schools
• An efficient practical alternative to ECC by Pell curve cryptography with a new vision
• Towards Safeguarding LLM Fine-tuning APIs against Cipher Attacks
• Defining Security in Quantum Key Distribution
• Multi-channel secure communication framework for wireless IoT (MCSC-WoT): enhancing security in Internet of Things
• SilentLedger: Privacy-Preserving Auditing for Blockchains with Complete Non-Interactivity
• Power and limitations of distributed quantum state purification
• A Hybrid Encryption Framework Combining Classical, Post-Quantum, and QKD Methods
• Efficient QKD in Non-Ideal Scenarios with User-Defined Output Length Requirements
• Supporting Socially Constrained Private Communications with SecureWhispers
• The Role of Quantum Computing in Advancing Scientific High-Performance Computing: A perspective from the ADAC Institute
• Hybrid Fiber-Free-Space Entanglement Distribution Using Off-the-Shelf Quantum Devices
• New Authentication Scheme for Wireless Body Area Networks Using the Bilinear Pairing
• Periodicity and Dynamical Systems of Dickson Polynomials in Finite Fields
• Quantum Prime Factorization: A Novel Approach Based on Fermat Method
• Iteration Sums of The Euler Totient Function Regarding Powers of Fermat Primes
• Flexible In-NAND Cryptographic Processing for Secure Flash Storage
• A Survey on Privacy-Preserving Computing in the Automotive Domain
• Performance and Storage Analysis of CRYSTALS Kyber as a Post Quantum Replacement for RSA and ECC
• Determination of Some Types of Permutations over \mathbbF_q² with Low-Degree
• An Unconditionally Secure Encryption Scheme for IoBT Networks
• Quantum Key-Recovery Attacks on FBC Algorithm
• Malleability-Resistant Encrypted Control System with Disturbance Compensation and Real-Time Attack Detection
• Prime Factorization Equation from a Tensor Network Perspective
• Characterizing the Sensitivity to Individual Bit Flips in Client-Side Operations of the CKKS Scheme
• Product-Congruence Games: A Unified Impartial-Game Framework for RSA (φ-MuM) and AES (poly-MuM)
• Hidden shift problem for complex functions
• Secure One-Sided Device-Independent Quantum Key Distribution Under Collective Attacks with Enhanced Robustness
• Partially homomorphic framework for secure privacy-preserving ID creation
• Scalability of Shor’s algorithm with a limited set of rotation gates
• How not to secure wireless sensor networks: A plethora of insecure\n polynomial-based key pre-distribution schemes
• AICrypto: Evaluating Cryptography Capabilities of Large Language Models
• Shuffling for Semantic Secrecy
• On the Impossibility of Separating Intelligence from Judgment: The Computational Intractability of Filtering for AI Alignment
• Approximating Euler Totient Function using Linear Regression on RSA moduli
• Two Variations of Quantum Phase Estimation for Reducing Circuit Error Rates: Application to the Harrow--Hassidim--Lloyd Algorithm
• README: Robust Error-Aware Digital Signature Framework via Deep Watermarking Model
• Bridging the Gap Between PHE and FHE: A Performance and Trade-off Analysis of The Somewhat Homomorphic BGN Cryptosystem
• Energy-Based Transformers are Scalable Learners and Thinkers
• Deterministic Cryptographic Seed Generation via Cyclic Modular Inversion over ℤ/3^pℤ
• HexaMorphHash HMH- Homomorphic Hashing for Secure and Efficient Cryptographic Operations in Data Integrity Verification
• Permutation polynomials of the form x+γTr(H(x))
• Some Mathematical Problems Behind Lattice-Based Cryptography
• Learning Modular Exponentiation with Transformers
• Some more constructions of n-cycle permutation polynomials
• Public-Key Quantum Authentication and Digital Signature Schemes Based on the QMA-Complete Problem
• Quantum prime factorization algorithms using binary carry propagation
• Privacy-Preserving Chest X-ray Classification in Latent Space with Homomorphically Encrypted Neural Inference
• Secure Distributed Learning for CAVs: Defending Against Gradient Leakage with Leveled Homomorphic Encryption
• An Efficient Hardware Implementation of Elliptic Curve Point Multiplication over GF(2^m) on FPGA
• Primender Sequence: A Novel Mathematical Construct for Testing Symbolic Inference and AI Reasoning
• A Comparative Study of Classical and Post-Quantum Cryptographic Algorithms in the Era of Quantum Computing
• Private key and password protection by steganographic image encryption
• The Byzantine Generals Problem
• A Geometric Square-Based Approach to RSA Integer Factorization
• randextract: a Reference Library to Test and Validate Privacy Amplification Implementations
• Realistic quantum network simulation for experimental BBM92 key distribution
• Bi-SamplerZ: A Hardware-Efficient Gaussian Sampler Architecture for Quantum-Resistant Falcon Signatures
• The Cambridge Handbook of Discourse Studies
• Towards Generalized Proactive Defense against Face Swapping with Contour-Hybrid Watermark
• Joint Encryption and Error Correction for Secure Quantum Communication
• Measuring Post-Quantum TLS Deployment Across UK Internet Sectors
• Energy Consumption Framework and Analysis of Post-Quantum Key-Generation on Embedded Devices
• Advances in Quantum Cryptography
• Integer Reasoning Modulo Different Constants in SMT
• Efficient and Anonymous Authentication Scheme for Wireless Body Area Networks
• Outsourced Privacy-Preserving Feature Selection Based on Fully Homomorphic Encryption
• Network-wide Quantum Key Distribution with Onion Routing Relay (Conference Version)
• Network-wide Quantum Key Distribution with Onion Routing Relay
• SP2UBI: Secure and Privacy-Preserving Usage-Based Insurance
• Cyber Security and Data Ownership
• Multipartite Hardy paradox unlocks device-independent key sharing
• Exact Spin Elimination in Ising Hamiltonians and Energy-Based Machine Learning
• FedTDP: A Privacy-Preserving and Unified Framework for Trajectory Data Preparation via Federated Learning
• BloQBench: A Blockchain Benchmarking Framework for Quantum Supremacy
• Four new classes of permutation trinomials and their compositional inverses
• Robust algorithms for restricted domains
• Space-Efficient Quantum Algorithm for Elliptic Curve Discrete Logarithms with Resource Estimation
• Quantum algorithms: an overview
• Another Look at "Provable Security"
• Unknown Key-Share Attacks on the Station-to-Station (STS) Protocol
• Open problems in number theoretic complexity, II
• How to Leak a Secret
• Collision-Free Accumulators and Fail-Stop Signature Schemes Without Trees
• The Many Faces of End-to-End Encryption and Their Security Analysis
• Information and computation: Classical and quantum aspects
• Quantum cryptography
• Totally secure classical communication utilizing Johnson (-like) noise and Kirchoff's law
• Security of public-key cryptosystems based on Chebyshev polynomials
• A Directly Modulated Laser Platform for High-Dimensional Quantum Key Distribution
• Cryptanalysis of a fast cryptographic checksum algorithm
• A bibliometric retrospective of Computers & Security
• A Practical Cryptanalysis of the Algebraic Eraser
• A Public-Key Cryptosystem Based on the Word Problem
• The Pathology of Cryptology—A Current Survey
• Number-theoretic expressions obtained through analogy between prime factorization and optical interferometry
• Applications of SAT Solvers to Cryptanalysis of Hash Functions
• On Cryptographic Assumptions and Challenges
• Cryptographic Assumptions: A Position Paper
• An overview of computational complexity
• Module Lattice Security (Part IV): Probabilistic Polynomial Quantum Attack on Module-LWE over 2-Power Cyclotomics
• Efficient Elliptic Curve Exponentiation Using Mixed Coordinates
• Leveraging the power of quantum computing for breaking RSA encryption
• Asymptotically Fast Factorization of Integers
• NSA and Dual EC_DRBG: Déjà Vu All Over Again?
• A probabilistic factorization algorithm with quadratic forms of negative discriminant
• Refined analysis and improvements on some factoring algorithms
• Kerberos: an authentication service for computer networks
• Covert Prompt Transmission for Secure Large Language Model Services
• VDDP: Verifiable Distributed Differential Privacy under the Client-Server-Verifier Setup
• Mersenne Factorization Factory
• Algorithms for quantum computation: discrete logarithms and factoring
• N Using RSA with Low Exponent in a Public Key Network
• Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities
• New Attacks on PKCS#1 v1.5 Encryption
• A Digital Signature Based on a Conventional Encryption Function
• The Nature of Computation
• Analysis and improvement of a multi-factor biometric authentication scheme
• Analyzing and comparing Montgomery multiplication algorithms
• Modular multiplication without trial division
• A robust and verifiable cryptographically secure election scheme
• LightDSA: A Python-Based Hybrid Digital Signature Library and Performance Analysis of RSA, DSA, ECDSA and EdDSA in Variable Configurations, Elliptic Curve Forms and Curves
• Quantum-safe IPsec in the banking industry
• Factorization of the tenth Fermat number
• Authentication and authenticated key exchanges
• Quantum key distribution system in standard telecommunications fiber using a short wavelength single photon source
• Universal Blind Quantum Computation
• A formal proof of countermeasures against fault injection attacks on CRT-RSA
• Cryptography in a Quantum World
• Exact Constructive Digit-by-Digit Algorithms for Integer e-th Root Extraction
• MOZAIK: A Privacy-Preserving Analytics Platform for IoT Data Using MPC and FHE
• Is the Data Encryption Standard a group? (Results of cycling experiments on DES)
• A complete classification of quantum public-key encryption protocols
• Some Remarks on Lucas-Based Cryptosystems
• Cloning and tampering threats in e-Passports
• Crypto-ncRNA: a bio-inspired post-quantum cryptographic primitive exploiting RNA folding complexity
• Quantum cryptographic network based on quantum memories
• Backdoor Attacks on Black-Box Ciphers Exploiting Low-Entropy Plaintexts
• A Pseudorandom Generator from any One-way Function
• The NP-completeness column
• The first ten years of public-key cryptography
• Structured light under turbulence
• Finite-size security of QKD: comparison of three proof techniques
• Secure exchange of information by synchronization of neural networks
• QCaMP: A 4-Week Summer Camp Introducing High School Students to Quantum Information Science and Technology
• Quantum information and relativity theory
• Extending the ElGamal Cryptosystem to the Third Group of Units of \Z_n
• Experimental demonstration of quantum digital signatures using phase-encoded coherent states of light
• Key Distillation and the Secret-Bit Fraction
• An improved Monte Carlo factorization algorithm
• Deep learning for video classification and captioning
• Security Services Using Blockchains: A State of the Art Survey
• Secure quantum key distribution with realistic devices
• A Scalable Framework for Post-Quantum Authentication in Public Key Infrastructures
• Nanomaterials for Quantum Information Science and Engineering
• SoK: Can Fully Homomorphic Encryption Support General AI Computation? A Functional and Cost Analysis
• PQ-CAN: A Framework for Simulating Post-Quantum Cryptography in Embedded Systems
• Public Quadratic Polynomial-Tuples for Efficient Signature-Verification and Message-Encryption
• Towards Combinatorial Interpretability of Neural Computation
• The future of secure communications: device independence in quantum key distribution
• Secure Text Mail Encryption with Generative Adversarial Networks
• Vulnerability of blockchain technologies to quantum attacks
• Quantum Covert Communication under Extreme Adversarial Control
• Three-electron spin qubits
• Public-key cryptography [wikipedia]
• RSA cryptosystem [wikipedia]
• A region-based lossless watermarking scheme for enhancing security of medical data. [europepmc]
• Security protection of DICOM medical images using dual-layer reversible watermarking with tamper detection capability. [europepmc]
• An enhanced biometric-based authentication scheme for telecare medicine information systems using elliptic curve cryptosystem. [europepmc]
• Secure Authentication for Remote Patient Monitoring with Wireless Medical Sensor Networks. [europepmc]
• Encryption key distribution via chaos synchronization. [europepmc]
• A genome-wide CRISPR screen reconciles the role of N-linked glycosylation in galectin-3 transport to the cell surface. [europepmc]
• Experimental measurement-device-independent quantum digital signatures. [europepmc]
• IoT Elements, Layered Architectures and Security Issues: A Comprehensive Survey. [europepmc]
• Implementation and security analysis of practical quantum secure direct communication. [europepmc]
• DNA origami cryptography for secure communication. [europepmc]
• Quantum cryptography beyond quantum key distribution. [europepmc]
• An Architecture and Management Platform for Blockchain-Based Personal Health Record Exchange: Development and Usability Study. [europepmc]
• Suggested Integral Analysis for Chaos-Based Image Cryptosystems. [europepmc]
• Green IoT and Edge AI as Key Technological Enablers for a Sustainable Digital Transition towards a Smart Circular Economy: An Industry 5.0 Use Case. [europepmc]
• A Comprehensive Survey on Security and Privacy for Electronic Health Data. [europepmc]
• Realization of quantum secure direct communication over 100 km fiber with time-bin and phase quantum states. [europepmc]
• Jamming a terahertz wireless link. [europepmc]
• The Rise of Cloud Computing: Data Protection, Privacy, and Open Research Challenges-A Systematic Literature Review (SLR). [europepmc]
• Biology and medicine in the landscape of quantum advantages. [europepmc]
• Fast single-photon detectors and real-time key distillation enable high secret-key-rate quantum key distribution systems. [europepmc]
• TreeViewer: Flexible, modular software to visualise and manipulate phylogenetic trees. [europepmc]
• Practical high-dimensional quantum key distribution protocol over deployed multicore fiber. [europepmc]
• All-silicon multidimensionally-encoded optical physical unclonable functions for integrated circuit anti-counterfeiting. [europepmc]
• A primer for quantum computing and its applications to healthcare and biomedical research. [europepmc]
• High-rate intercity quantum key distribution with a semiconductor single-photon source. [europepmc]

Related

• Cryptography and Encryption
• Untraceable electronic mail, return addresses, and digital pseudonyms
• Efficient Authenticated Encryption Schemes with Public Verifiability
• New directions in cryptography
• Digital signature schemes using non-square matrices or scrap automorphisms