A method for obtaining digital signatures and public-key cryptosystems
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: 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 intended recipient. Only he can decipher the message, since only he knows the corresponding decryption key. 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 prime 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 .
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The RSA function E(x,y)=x^y mod η underlies the assumption that given E(x,y), y, and η, x cannot be computed in polynomial time.
“Consider that the RSA function E( x , y ) = x y mod η underlies the assumption that given E( x , y ) , y , and η , where E is an encryption function; x cannot be computed in polynomial time.”
From IoT Expunge: Implementing Verifiable Retention of IoT Data (2020) · cites this paper as [34]
One-way accumulators were proposed by Benaloh and Mare and are based on the RSA assumption.
“One-way accumulators were proposed by Benaloh and Mare [11] and are based on RSA assumption [34].”
From IoT Expunge: Implementing Verifiable Retention of IoT Data (2020) · cites this paper as [34]
Cites
Secure communications over insecure channels
Merkle, R. C. (1978) · Communications of the ACM · doi:10.1145/359460.359473 · Cited by 757 · see citing works
Special Feature Exhaustive Cryptanalysis of the NBS Data Encryption Standard
Diffie, W., & Hellman, M. E. (1977) · Computer · doi:10.1109/c-m.1977.217750 · Cited by 567 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Shamir, A. (1979) · Communications of the ACM · doi:10.1145/359168.359176 · Cited by 13,756 · see citing works
Algorithms for quantum computation: discrete logarithms and factoring
Shor, P. W. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365700 · Cited by 8,713 · see citing works
A public key cryptosystem and a signature scheme based on discrete logarithms
Elgamal, T. (1985) · IEEE Transactions on Information Theory · doi:10.1109/tit.1985.1057074 · Cited by 8,059 · see citing works
Public-Key Cryptosystems Based on Composite Degree Residuosity Classes
Paillier, P. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-48910-x_16 · Cited by 7,250 · see citing works
Fully homomorphic encryption using ideal lattices
Gentry, C. (2009) · Proceedings of the forty-first annual ACM symposium on Theory of computing · doi:10.1145/1536414.1536440 · Cited by 6,806 · see citing works
The Byzantine generals problem
Lamport, L., Shostak, R., & Pease, M. (1982) · ACM Transactions on Programming Languages and Systems · doi:10.1145/357172.357176 · Cited by 6,023 · see citing works
Secure spread spectrum watermarking for multimedia
Cox, I. J., Kilian, J., Leighton, F. T., & Shamoon, T. (1997) · IEEE Transactions on Image Processing · doi:10.1109/83.650120 · Cited by 5,299 · see citing works
The Arithmetic of Elliptic Curves
Silverman, J. H. (1986) · Graduate Texts in Mathematics · doi:10.1007/978-1-4757-1920-8 · Cited by 4,044 · see citing works
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1999) · SIAM Review · doi:10.1137/s0036144598347011 · Cited by 3,904 · see citing works
IoT security: Review, blockchain solutions, and open challenges
Khan, M. A., & Salah, K. (2018) · Future Generation Computer Systems · doi:10.1016/j.future.2017.11.022 · Cited by 2,488 · see citing works
A Digital Signature Based on a Conventional Encryption Function
Merkle, R. C. (1988) · Lecture Notes in Computer Science · doi:10.1007/3-540-48184-2_32 · Cited by 1,998 · see citing works
NTRU: A ring-based public key cryptosystem
Hoffstein, J., Pipher, J., & Silverman, J. H. (1998) · Lecture Notes in Computer Science · doi:10.1007/bfb0054868 · Cited by 1,947 · see citing works
Security without identification: transaction systems to make big brother obsolete
Chaum, D. (1985) · Communications of the ACM · doi:10.1145/4372.4373 · Cited by 1,666 · see citing works
Rivest, R. L., Shamir, A., & Tauman, Y. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-45682-1_32 · Cited by 1,619 · see citing works
Self-citationProtocols for Public Key Cryptosystems
Merkle, R. C. (1980) · 1980 IEEE Symposium on Security and Privacy · doi:10.1109/sp.1980.10006 · Cited by 1,418 · see citing works
A Survey on Homomorphic Encryption Schemes: Theory and Implementation
Acar, A., Aksu, H., Uluagac, A. S., & Conti, M. (2019) · ACM Computing Surveys · doi:10.1145/3214303 · Cited by 1,397 · see citing works
Bernstein, D. J., & Lange, T. (2017) · Nature · doi:10.1038/nature23461 · Cited by 1,242 · see citing works
Huang, L., Joseph, A. D., Nelson, B., Rubinstein, B. I. P., & Tygar, J. D. (2011) · Proceedings of the 4th ACM workshop on Security and artificial intelligence · doi:10.1145/2046684.2046692 · Cited by 1,194 · see citing works
A Review on the Use of Blockchain for the Internet of Things
Fernandez-Carames, T. M., & Fraga-Lamas, P. (2018) · IEEE Access · doi:10.1109/access.2018.2842685 · Cited by 1,078 · see citing works
Quantum algorithms: an overview
Montanaro, A. (2016) · npj Quantum Information · doi:10.1038/npjqi.2015.23 · Cited by 1,071 · see citing works
A Simple Unpredictable Pseudo-Random Number Generator
Blum, L., Blum, M., & Shub, M. (1986) · SIAM Journal on Computing · doi:10.1137/0215025 · Cited by 1,036 · see citing works
Secure communications over insecure channels
Merkle, R. C. (1978) · Communications of the ACM · doi:10.1145/359460.359473 · Cited by 757 · see citing works
A Survey on quantum computing technology
Gyongyosi, L., & Imre, S. (2019) · Computer Science Review · doi:10.1016/j.cosrev.2018.11.002 · Cited by 646 · see citing works
Fernandez-Carames, T. M., & Fraga-Lamas, P. (2020) · IEEE Access · doi:10.1109/access.2020.2968985 · Cited by 607 · see citing works
Data security and privacy-preserving in edge computing paradigm: survey and open issues
Zhang, J., Chen, B., Zhao, Y., Cheng, X., & Hu, F. (2018) · IEEE Access · doi:10.1109/access.2018.2820162 · Cited by 514 · see citing works
Security services using blockchains: a state of the art survey
Salman, T., Zolanvari, M., Erbad, A., Jain, R., & Samaka, M. (2019) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2018.2863956 · Cited by 502 · see citing works
Privacy and Robustness in Federated Learning: Attacks and Defenses
Lyu, L., Yu, H., Ma, X., Chen, C., Sun, L., Zhao, J., Yang, Q., & Yu, P. S. (2024) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2022.3216981 · Cited by 548 · see citing works
Secure audit logs to support computer forensics
Schneier, B., & Kelsey, J. (1999) · ACM Transactions on Information and System Security · doi:10.1145/317087.317089 · Cited by 443 · see citing works
Fog Computing for Sustainable Smart Cities: A Survey
Perera, C., Qin, Y., Estrella, J. C., Reiff-Marganiec, S., & Vasilakos, A. V. (2018) · ACM Computing Surveys · doi:10.1145/3057266 · Cited by 459 · see citing works
Micali, S. (2000) · SIAM Journal on Computing · doi:10.1137/s0097539795284959 · Cited by 424 · see citing works
Factorization of a 768-Bit RSA Modulus
Kleinjung, T., Aoki, K., Franke, J., Lenstra, A. K., Thomé, E., Bos, J. W., Gaudry, P., Kruppa, A., Montgomery, P. L., Osvik, D. A., et al. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-14623-7_18 · Cited by 423 · see citing works
Security for Industrial Communication Systems
Dzung, D., Naedele, M., Von Hoff, T. P., & Crevatin, M. (2005) · Proceedings of the IEEE · doi:10.1109/jproc.2005.849714 · Cited by 386 · see citing works
Quantum algorithms for algebraic problems
Childs, A. M., & van Dam, W. (2010) · Reviews of Modern Physics · doi:10.1103/revmodphys.82.1 · Cited by 344 · see citing works
Amin, R., & Biswas, G. P. (2016) · Ad Hoc Networks · doi:10.1016/j.adhoc.2015.05.020 · Cited by 320 · see citing works
A Survey on SCADA Systems: Secure Protocols, Incidents, Threats and Tactics
Pliatsios, D., Sarigiannidis, P., Lagkas, T., & Sarigiannidis, A. G. (2020) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2020.2987688 · Cited by 320 · see citing works
A Systematic Review of Homomorphic Encryption and Its Contributions in Healthcare Industry
Munjal, K., & Bhatia, R. (2023) · Complex & Intelligent Systems · doi:10.1007/s40747-022-00756-z · Cited by 269 · see citing works
Towards Fair and Privacy-Preserving Federated Deep Models
Lyu, L., Yu, J., Nandakumar, K., Li, Y., Ma, X., Jin, J., Yu, H., & Ng, K. S. (2020) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2020.2996273 · Cited by 250 · see citing works
Electronic Patient-Physician Communication: Problems and Promise
Mandl, K. D., Kohane, I. S., & Brandt, A. M. (1998) · Annals of Internal Medicine · doi:10.7326/0003-4819-129-6-199809150-00012 · Cited by 222 · see citing works
CacheBleed: a timing attack on OpenSSL constant-time RSA
Yarom, Y., Genkin, D., & Heninger, N. (2017) · Journal of Cryptographic Engineering · doi:10.1007/s13389-017-0152-y · Cited by 210 · see citing works
Authentication theory and hypothesis testing
Maurer, U. M. (2000) · IEEE Transactions on Information Theory · doi:10.1109/18.850674 · Cited by 200 · see citing works
DNA origami cryptography for secure communication
Zhang, Y., Wang, F., Chao, J., Xie, M., Liu, H., Pan, M., Kopperger, E., Liu, X., Li, Q., Shi, J., et al. (2019) · Nature Communications · doi:10.1038/s41467-019-13517-3 · Cited by 163 · see citing works
Quantum Search Algorithms for Wireless Communications
Botsinis, P., Alanis, D., Babar, Z., Nguyen, H. V., Chandra, D., Ng, S. X., & Hanzo, L. (2019) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2018.2882385 · Cited by 149 · see citing works
Design and Implementation of a Secure Modbus Protocol
Fovino, I. N., Carcano, A., Masera, M., & Trombetta, A. (2009) · IFIP Advances in Information and Communication Technology · doi:10.1007/978-3-642-04798-5_6 · Cited by 138 · see citing works
Quantum resistant public key cryptography: a survey
Perlner, R. A., & Cooper, D. A. (2009) · Proceedings of the 8th Symposium on Identity and Trust on the Internet · doi:10.1145/1527017.1527028 · Cited by 137 · see citing works
Security Aspects of Blockchain Technology Intended for Industrial Applications
Idrees, S. M., Nowostawski, M., Jameel, R., & Mourya, A. K. (2021) · Electronics · doi:10.3390/electronics10080951 · Cited by 127 · see citing works
Privacy-preserving neural networks with Homomorphic encryption: Challenges and opportunities
Pulido-Gaytan, B., Tchernykh, A., Cortés-Mendoza, J. M., Babenko, M., Radchenko, G., Avetisyan, A., & Drozdov, A. Y. (2021) · Peer-to-Peer Networking and Applications · doi:10.1007/s12083-021-01076-8 · Cited by 126 · see citing works
Quantum reversible circuit of AES-128
Almazrooie, M., Samsudin, A., Abdullah, R., & Mutter, K. N. (2018) · Quantum Information Processing · doi:10.1007/s11128-018-1864-3 · Cited by 75 · see citing works
Energy-efficient mechanisms in security of the internet of things: A survey
Hellaoui, H., Koudil, M., & Bouabdallah, A. (2017) · Computer Networks · doi:10.1016/j.comnet.2017.08.006 · Cited by 61 · see citing works
On Security in Publish/Subscribe Services: A Survey
Esposito, C., & Ciampi, M. (2015) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2014.2364616 · Cited by 55 · see citing works
Drive-By Key-Extraction Cache Attacks from Portable Code
Genkin, D., Pachmanov, L., Tromer, E., & Yarom, Y. (2018) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-93387-0_5 · Cited by 57 · see citing works
Neural Networks-Based Cryptography: A Survey
Meraouche, I., Dutta, S., Tan, H., & Sakurai, K. (2021) · IEEE Access · doi:10.1109/access.2021.3109635 · Cited by 52 · see citing works
Gong, S., Tcydenova, E., Jo, J., Lee, Y., & Park, J. H. (2019) · Sustainability · doi:10.3390/su11143889 · Cited by 47 · see citing works
Secure Data Aggregation with Fully Homomorphic Encryption in Large-Scale Wireless Sensor Networks
Li, X., Chen, D., Li, C., & Wang, L. (2015) · Sensors · doi:10.3390/s150715952 · Cited by 41 · see citing works
RUASN: A Robust User Authentication Framework for Wireless Sensor Networks
Kumar, P., Choudhury, A. J., Sain, M., Lee, S.-G., & Lee, H.-J. (2011) · Sensors · doi:10.3390/s110505020 · Cited by 40 · see citing works
Elhoseny, M., Haseeb, K., Shah, A. A., Ahmad, I., Jan, Z., & Alghamdi, M. I. (2021) · Energies · doi:10.3390/en14175364 · Cited by 41 · see citing works
A new chaos-based secure image encryption scheme using multiple substitution boxes
Khan, J. S., ur Rehman, A., Ahmad, J., & Habib, Z. (2015) · 2015 Conference on Information Assurance and Cyber Security (CIACS) · doi:10.1109/ciacs.2015.7395561 · Cited by 31 · see citing works
Reaction Attack on Outsourced Computing with Fully Homomorphic Encryption Schemes
Zhang, Z., Plantard, T., & Susilo, W. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-31912-9_28 · Cited by 27 · see citing works
From Algorithm to Hardware: A Survey on Efficient and Safe Deployment of Deep Neural Networks
Geng, X., Wang, Z., Chen, C., Xu, Q., Xu, K., Jin, C., Gupta, M., Yang, X., Chen, Z., Sabry Aly, M. M., et al. (2025) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2024.3394494 · Cited by 26 · see citing works
A Survey on Secure Computation Based on Homomorphic Encryption in Vehicular Ad Hoc Networks
Sun, X., Yu, F. R., Zhang, P., Xie, W., & Peng, X. (2020) · Sensors · doi:10.3390/s20154253 · Cited by 23 · see citing works
Parallel approaches to improve the speed of chaotic-maps-based encryption using GPU
Elrefaey, A., Sarhan, A., & El-Shennawy, N. M. (2021) · Journal of Real-Time Image Processing · doi:10.1007/s11554-020-01064-w · Cited by 21 · see citing works
A Practical Cryptanalysis of the Algebraic Eraser
Ben-Zvi, A., Blackburn, S. R., & Tsaban, B. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-662-53018-4_7 · Cited by 15 · see citing works
Hybrid cryptosystem for image file using elgamal and double playfair cipher algorithm
Hardi, S. M., Tarigan, J. T., & Safrina, N. (2018) · Journal of Physics: Conference Series · doi:10.1088/1742-6596/978/1/012068 · Cited by 9 · see citing works
Protection of data confidentiality and patient privacy in medical sensor networks
Sankar, R., Le, X. H., Lee, S., & Wang, D. (2013) · Implantable Sensor Systems for Medical Applications · doi:10.1533/9780857096289.2.279 · Cited by 7 · see citing works
IoT Expunge: Implementing Verifiable Retention of IoT Data
Panwar, N., Sharma, S., Gupta, P., Ghosh, D., Mehrotra, S., & Venkatasubramanian, N. (2020) · Proceedings of the Tenth ACM Conference on Data and Application Security and Privacy · doi:10.1145/3374664.3375737 · Cited by 6 · see citing works
A public key cryptosystem and signature scheme based on numerical series
Nagaty, K. A. (2020) · SN Applied Sciences · doi:10.1007/s42452-019-1928-8 · Cited by 5 · see citing works
Welz, T., & Herbst, K. (2008) · Sexually Transmitted Diseases · doi:10.1097/olq.0b013e31815fd3fc · Cited by 5 · see citing works
Cipher image damage and decisions in real time
Silva-García, V. M., Flores-Carapia, R., Rentería-Márquez, C., Luna-Benoso, B., Jiménez-Vázquez, C. A., & González-Ramírez, M. D. (2015) · Journal of Electronic Imaging · doi:10.1117/1.jei.24.1.013012 · Cited by 5 · see citing works
Cipher Image Damage: An Application of Filters
Flores-Carapia, R., Silva-García, V. M., Luna-Benoso, B., & Rentería-Márquez, C. (2015) · Polibits · doi:10.17562/pb-52-7 · Cited by 1 · see citing works
- Authors
- Rivest, R. L., Shamir, A., & Adleman, L.
- Affiliations
- Massachusetts Institute of Technology (US)
- MIT Lab for Computer Science and Department of Mathematics, Cambridge, MA
- ORCID
- Rivest, R. L.
- Venue
- Communications of the ACM
- Published
- 1983-01
- Volume
- 26
- Issue
- 1
- Pages
- 96-99
- ISSN
- 0001-0782 (ISSN-L)
- 1557-7317
- OpenAlex
- W1996360405
- Cited by
- 13,012
- References
- 2
- Citations by year
- 2026: 15 · 2025: 67 · 2024: 115 · 2023: 112 · 2022: 106 · 2021: 445 · 2020: 549 · 2019: 493 · 2018: 498 · 2017: 456 · 2016: 522 · 2015: 557 · 2014: 669 · 2013: 600 · 2012: 600
- FWCI
- 69.91
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- Communications of the ACM (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Cryptography and Data Security
- Physical Sciences › Computer Science › Information Systems › Cryptography and Residue Arithmetic
- Physical Sciences › Computer Science › Artificial Intelligence › Computer Science and Engineering
- Keywords
- public-key cryptography, digital signatures, RSA encryption, encryption keys, decryption keys, modular exponentiation, integer factorization, email, electronic funds transfer, key distribution
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
