Page 1 of 15Free preview · 1–5

About this document

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

Tags

Doxxly editorial guide

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.

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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.

  6. 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.

  7. 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.

  8. 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.

Visit people.csail.mit.edu

How to read and use this document

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.

Explore more Technology & Security resources

Frequently asked questions about A Method for Obtaining Digital Signatures and Public-Key Cryptosystems

Practical answers about reading, downloading and understanding this document on Doxxly.

More in Technology & Security