The paper presents a public-key encryption and digital signature method based on modular exponentiation using a modulus formed from two large secret primes. It explains private communication and signature verification, proves the correctness of encryption and decryption, and describes algorithms for key generation, primality testing, and efficient computation. A worked example illustrates the method. The security discussion examines factoring and related cryptanalytic approaches while acknowledging that the difficulty of breaking the system has not been proved.
Free preview text
The first 5 pages, shown as text so search engines and readers can find this document.
Page 1
A Method for Obtaining Digital
Signatures and Public-Key Cryptosystems
R.L. Rivest, A. Shamir, and L. Adleman∗
Abstract
An encryption method is presented with the novel property that publicly re-
vealing 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 intended 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 en-
cryption 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.
Key Words and Phrases: digital signatures, public-key cryptosystems, pri-
vacy, authentication, security, factorization, prime number, electronic mail,
message-passing, electronic funds transfer, cryptography.
CR Categories: 2.12, 3.15, 3.50, 3.81, 5.25
∗General permission to make fair use in teaching or research of all or part of this material is
granted to individual readers and to nonprofit libraries acting for them provided that ACM’s copy-
right notice is given and that reference is made to the publication, to its date of issue, and to the fact
that reprinting privileges were granted by permission of the Association for Computing Machinery.
To otherwise reprint a figure, table, other substantial excerpt, or the entire work requires specific
permission as does republication, or systematic or multiple reproduction.
This research was supported by National Science Foundation grant MCS76-14294, and the Office of
Naval Research grant number N00014-67-A-0204-0063.
Author’s Address: Laboratory for Computer Science, Massachusetts Institute of Technology, Cam-
bridge, MA 02139 E-mail addresses: rivest@theory.lcs.mit.edu
Page 2
I Introduction
The era of “electronic mail” [10] may soon be upon us; we must ensure that two
important properties of the current “paper mail” system are preserved: (a) messages
are private, and (b) messages can be signed . We demonstrate in this paper how to
build these capabilities into an electronic mail system.
At the heart of our proposal is a new encryption method. This method provides
an implementation of a “public-key cryptosystem,” an elegant concept invented by
Diffie and Hellman [1]. Their article motivated our research, since they presented
the concept but not any practical implementation of such a system. Readers familiar
with [1] may wish to skip directly to Section V for a description of our method.
II Public-Key Cryptosystems
In a “public key cryptosystem” each user places in a public file an encryption proce-
dure E. That is, the public file is a directory giving the encryption procedure of each
user. The user keeps secret the details of his corresponding decryption procedure D.
These procedures have the following four properties:
(a) Deciphering the enciphered form of a message M yields M . Formally,
D(E(M ) = M. (1)
(b) Both E and D are easy to compute.
(c) By publicly revealing E the user does not reveal an easy way to compute D.
This means that in practice only he can decrypt messages encrypted with E, or
compute D efficiently.
(d) If a message M is first deciphered and then enciphered, M is the result. For-
mally,
E(D(M ) = M. (2)
An encryption (or decryption) procedure typically consists of a general method
and an encryption key. The general method, under control of the key, enciphers a
message M to obtain the enciphered form of the message, called the ciphertext C.
Everyone can use the same general method; the security of a given procedure will rest
on the security of the key. Revealing an encryption algorithm then means revealing
the key.
When the user reveals E he reveals a very inefficient method of computing D(C):
testing all possible messages M until one such that E(M ) = C is found. If property
(c) is satisfied the number of such messages to test will be so large that this approach
is impractical.
A function E satisfying (a)-(c) is a “trap-door one-way function;” if it also satisfies
(d) it is a “trap-door one-way permutation.” Diffie and Hellman [1] introduced the
2
Page 3
concept of trap-door one-way functions but did not present any examples. These
functions are called “one-way” because they are easy to compute in one direction but
(apparently) very difficult to compute in the other direction. They are called “trap-
door” functions since the inverse functions are in fact easy to compute once certain
private “trap-door” information is known. A trap-door one-way function which also
satisfies (d) must be a permutation: every message is the cipertext for some other
message and every ciphertext is itself a permissible message. (The mapping is “one-
to-one” and “onto”). Property (d) is needed only to implement “signatures.”
The reader is encouraged to read Diffie and Hellman’s excellent article [1] for
further background, for elaboration of the concept of a public-key cryptosystem, and
for a discussion of other problems in the area of cryptography. The ways in which
a public-key cryptosystem can ensure privacy and enable “signatures” (described in
Sections III and IV below) are also due to Diffie and Hellman.
For our scenarios we suppose that A and B (also known as Alice and Bob) are
two users of a public-key cryptosystem. We will distinguish their encryption and
decryption procedures with subscripts: EA, DA, EB , DB .
III Privacy
Encryption is the standard means of rendering a communication private. The sender
enciphers each message before transmitting it to the receiver. The receiver (but no
unauthorized person) knows the appropriate deciphering function to apply to the
received message to obtain the original message. An eavesdropper who hears the
transmitted message hears only “garbage” (the ciphertext) which makes no sense to
him since he does not know how to decrypt it.
The large volume of personal and sensitive information currently held in comput-
erized data banks and transmitted over telephone lines makes encryption increasingly
important. In recognition of the fact that efficient, high-quality encryption techniques
are very much needed but are in short supply, the National Bureau of Standards has
recently adopted a “Data Encryption Standard” [13, 14], developed at IBM. The new
standard does not have property (c), needed to implement a public-key cryptosystem.
All classical encryption methods (including the NBS standard) suffer from the
“key distribution problem.” The problem is that before a private communication can
begin, another private transaction is necessary to distribute corresponding encryption
and decryption keys to the sender and receiver, respectively. Typically a private
courier is used to carry a key from the sender to the receiver. Such a practice is not
feasible if an electronic mail system is to be rapid and inexpensive. A public-key
cryptosystem needs no private couriers; the keys can be distributed over the insecure
communications channel.
How can Bob send a private message M to Alice in a public-key cryptosystem?
First, he retrieves EA from the public file. Then he sends her the enciphered message
EA(M ). Alice deciphers the message by computing DA(EA(M )) = M . By property
(c) of the public-key cryptosystem only she can decipher EA(M ). She can encipher a
3
Page 4
private response with EB , also available in the public file.
Observe that no private transactions between Alice and Bob are needed to estab-
lish private communication. The only “setup” required is that each user who wishes
to receive private communications must place his enciphering algorithm in the public
file.
Two users can also establish private communication over an insecure communi-
cations channel without consulting a public file. Each user sends his encryption key
to the other. Afterwards all messages are enciphered with the encryption key of the
recipient, as in the public-key system. An intruder listening in on the channel cannot
decipher any messages, since it is not possible to derive the decryption keys from the
encryption keys. (We assume that the intruder cannot modify or insert messages into
the channel.) Ralph Merkle has developed another solution [5] to this problem.
A public-key cryptosystem can be used to “bootstrap” into a standard encryption
scheme such as the NBS method. Once secure communications have been established,
the first message transmitted can be a key to use in the NBS scheme to encode all
following messages. This may be desirable if encryption with our method is slower
than with the standard scheme. (The NBS scheme is probably somewhat faster if
special-purpose hardware encryption devices are used; our scheme may be faster on
a general-purpose computer since multiprecision arithmetic operations are simpler to
implement than complicated bit manipulations.)
IV Signatures
If electronic mail systems are to replace the existing paper mail system for business
transactions, “signing” an electronic message must be possible. The recipient of a
signed message has proof that the message originated from the sender. This quality
is stronger than mere authentication (where the recipient can verify that the message
came from the sender); the recipient can convince a “judge” that the signer sent the
message. To do so, he must convince the judge that he did not forge the signed
message himself! In an authentication problem the recipient does not worry about
this possibility, since he only wants to satisfy himself that the message came from the
sender.
An electronic signature must be message-dependent, as well as signer-dependent.
Otherwise the recipient could modify the message before showing the message-signature
pair to a judge. Or he could attach the signature to any message whatsoever, since
it is impossible to detect electronic “cutting and pasting.”
To implement signatures the public-key cryptosystem must be implemented with
trap-door one-way permutations (i.e. have property (d)), since the decryption algo-
rithm will be applied to unenciphered messages.
How can user Bob send Alice a “signed” message M in a public-key cryptosystem?
He first computes his “signature” S for the message M using DB :
S = DB (M ) .
4
Page 5
(Deciphering an unenciphered message “makes sense” by property (d) of a public-
key cryptosystem: each message is the ciphertext for some other message.) He then
encrypts S using EA (for privacy), and sends the result EA(S) to Alice. He need not
send M as well; it can be computed from S.
Alice first decrypts the ciphertext with DA to obtain S. She knows who is the
presumed sender of the signature (in this case, Bob); this can be given if necessary in
plain text attached to S. She then extracts the message with the encryption procedure
of the sender, in this case EB (available on the public file):
M = EB (S) .
She now possesses a message-signature pair (M, S) with properties similar to those
of a signed paper document.
Bob cannot later deny having sent Alice this message, since no one else could have
created S = DB (M ). Alice can convince a “judge” that EB (S) = M , so she has proof
that Bob signed the document.
Clearly Alice cannot modify M to a different version M ′, since then she would
have to create the corresponding signature S′ = DB (M ′) as well.
Therefore Alice has received a message “signed” by Bob, which she can “prove”
that he sent, but which she cannot modify. (Nor can she forge his signature for any
other message.)
An electronic checking system could be based on a signature system such as the
above. It is easy to imagine an encryption device in your home terminal allowing
you to sign checks that get sent by electronic mail to the payee. It would only be
necessary to include a unique check number in each check so that even if the payee
copies the check the bank will only honor the first version it sees.
Another possibility arises if encryption devices can be made fast enough: it will
be possible to have a telephone conversation in which every word spoken is signed by
the encryption device before transmission.
When encryption is used for signatures as above, it is important that the en-
cryption device not be “wired in” between the terminal (or computer) and the com-
munications channel, since a message may have to be successively enciphered with
several keys. It is perhaps more natural to view the encryption device as a “hardware
subroutine” that can be executed as needed.
We have assumed above that each user can always access the public file reliably.
In a “computer network” this might be difficult; an “intruder” might forge messages
purporting to be from the public file. The user would like to be sure that he actually
obtains the encryption procedure of his desired correspondent and not, say, the en-
cryption procedure of the intruder. This danger disappears if the public file “signs”
each message it sends to a user. The user can check the signature with the public file’s
encryption algorithm EP F . The problem of “looking up” EP F itself in the public file
is avoided by giving each user a description of EP F when he first shows up (in person)
to join the public-key cryptosystem and to deposit his public encryption procedure.
He then stores this description rather than ever looking it up again. The need for a
5
A Method for Obtaining Digital Signatures and Public-Key Cryptosystems: summary, contents and background
This guide helps you understand the scope of A Method for Obtaining Digital Signatures and Public-Key Cryptosystems before or alongside reading the original document. It is based on the catalogue record, credited creator, source, classification and topics shown on this page. It does not replace the original work and does not invent claims about passages that Doxxly cannot verify.
Summary and overview
A Method for Obtaining Digital Signatures and Public-Key Cryptosystems is a 15-page documentcredited to Zora S. Underhill. The paper presents a public-key encryption and digital signature method based on modular exponentiation using a modulus formed from two large secret primes. It explains private communication and signature verification, proves the correctness of encryption and decryption, and describes algorithms for key generation, primality testing, and efficient computation. A worked example illustrates the method. The security discussion examines factoring and related cryptanalytic approaches while acknowledging that the difficulty of breaking the system has not been proved. It appears in the Technology & Security collection, which groups it with other material that readers may use for comparison and further study.
The item can be approached in several ways. A reader looking for a quick orientation can begin with the free five-page preview, inspect the page structure and use the metadata to judge relevance. Someone undertaking deeper research can work through the complete file, search its indexed text, record useful page references and compare its treatment of Cryptography, Public-key cryptosystems, Digital signatures, Privacy, Authentication, Number theory, Factorization, Primality testing with the related resources linked below.
Rather than reducing the work to a single claim, this page treats it as a source that should be read in context. The title, creator, publication source, licence and format all help explain what kind of evidence it may offer. Readers should distinguish the original author's statements from Doxxly's catalogue description, and should cite the original edition when using the material in academic, professional or published work.
Key topics and reader takeaways
The catalogue connects this document with Cryptography, Public-key cryptosystems, Digital signatures, Privacy, Authentication, Number theory, Factorization, Primality testing. These terms offer practical entry points rather than a substitute for close reading. Start by identifying the definitions, examples, arguments, tables or visual explanations attached to each topic. Then note where the creator draws connections, makes distinctions or moves from background material to a conclusion, recommendation, calculation or narrative development.
A useful reading method is to separate description from interpretation. First record what the item actually presents: names, headings, figures, formulas, quotations or stated propositions. Next consider why those details matter within the whole work. Finally compare them with another source from the same subject area. This process helps turn a long digital file into evidence that can be evaluated rather than merely skimmed.
Table of contents and reading guide
The following is an editorial content guide based on the verified catalogue topics. It is not represented as the original author's formal table of contents. Use it to organise notes while moving through the 15 pages in the player.
Part 1
Cryptography
Use this section of the reading guide to identify how Cryptography appears in A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, note important terms, and connect the subject to the wider purpose of the work.
Part 2
Public-key cryptosystems
Use this section of the reading guide to identify how Public-key cryptosystems appears in A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, note important terms, and connect the subject to the wider purpose of the work.
Part 3
Digital signatures
Use this section of the reading guide to identify how Digital signatures appears in A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, note important terms, and connect the subject to the wider purpose of the work.
Part 4
Privacy
Use this section of the reading guide to identify how Privacy appears in A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, note important terms, and connect the subject to the wider purpose of the work.
Part 5
Authentication
Use this section of the reading guide to identify how Authentication appears in A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, note important terms, and connect the subject to the wider purpose of the work.
Part 6
Number theory
Use this section of the reading guide to identify how Number theory appears in A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, note important terms, and connect the subject to the wider purpose of the work.
Part 7
Factorization
Use this section of the reading guide to identify how Factorization appears in A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, note important terms, and connect the subject to the wider purpose of the work.
Part 8
Primality testing
Use this section of the reading guide to identify how Primality testing appears in A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, note important terms, and connect the subject to the wider purpose of the work.
When a heading in the original differs from this guide, follow the original heading in your citation. Page numbers can also vary between editions. Doxxly's direct page field is useful for navigation, but formal references should include the title, creator, source and edition details available in the file itself.
About Zora S. Underhill
Doxxly credits Zora S. Underhill as the author or creator of A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. This page does not add an unverified biography, job title or institutional affiliation. The attribution is preserved so readers can distinguish the creator from the hosting library and follow the original record when an external author link is available.
Author context matters because a work reflects a particular purpose, audience and point of view. Before relying on the material, consider what the creator set out to explain, when the source was produced and whether later research or revised guidance should also be consulted. For literature and philosophy, compare translations and editions; for technical material, check whether a newer version has superseded the one shown here.
About the source organisation
The recorded source for this item is people.csail.mit.edu. Doxxly provides access and discovery tools but does not claim to be the original publisher unless explicitly stated. Source links, creator attribution and the recorded Publicly available file collected for editorial review licence are displayed to help readers assess provenance and permitted use.
Provenance is especially important for reports, standards, presentations and working spreadsheets. Check the original source for amendments, supporting files and current policy. A trustworthy research workflow keeps the source URL with any notes or downloaded copy, verifies important figures against the original, and avoids treating an archived document as automatically current.
Begin with the title and opening pages, then use the guide above to decide whether to read sequentially or move to a particular topic. The Doxxly player provides previous and next navigation, a direct page field, zoom steps, fit-to-width and fit-to-page modes, rotation and fullscreen. These controls are useful when a page contains small type, a wide table, an image, a scanned layout or a dense sequence of notes.
The first five pages are open to every visitor. A plan unlocks the complete item and full-document search. Search is best used for distinctive names, technical terms or short phrases; broad words can produce too many possible contexts. When you find a useful passage, read the surrounding pages so that a sentence, chart or formula is not separated from its explanation.
If downloading is enabled, members can obtain the original PDF file. Keep the original format when formulas, slide sequencing, pagination or layout carries meaning. Respect the Publicly available file collected for editorial review terms displayed on this page, and use the rights-report link if you believe the attribution or availability needs review.
Research questions to consider
As you read A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, ask which audience the creator addresses, what problem or idea organises the work, what evidence is presented, and which assumptions remain unstated. Note whether important terms are defined consistently and whether examples represent a broader pattern or a narrow case. For quantitative material, record units, time periods, formulas and data sources. For interpretive material, separate the creator's language from your own summary.
A second set of questions concerns relevance today. Which parts remain durable, which depend on their historical or institutional setting, and what would need confirmation from a newer source? Following the tags and the Technology & Security collection can reveal useful comparisons. Agreement between sources can strengthen confidence, while disagreement can point to changing definitions, methods, evidence or priorities.
Finally, decide what you need from the item: background knowledge, a quotation, a worked example, a model, a visual explanation or a starting bibliography. That purpose should guide the depth of reading and the notes you keep. Doxxly helps locate and navigate the source; careful interpretation remains the reader's responsibility.