# Pioneering Public Key: Public Exchange of Secret Keys

• Print
• + Share This
Like this article? We recommend

## Developing an Innovative Secret Key Delivery Solution

While a graduate student at Berkeley in the early 1970s, Ralph Merkle devised a system that enabled people like Alice and Bob to exchange secret keys over a public line, marking the beginning of public key cryptography. Even though BlackHat is assumed to be listening to Alice and Bob's communications, Merkle envisioned a way to create a difficult, time-consuming problem for BlackHat. At the same time, Merkle's approach makes it easier for Alice and Bob to establish their shared secret key.

The goal was to create a problem that would take BlackHat a long time to solve even with the aid of a computer. Here's what Merkle devised.

### First Attempt: A Database of Key/Serial Number Pairs

Suppose that Alice makes 1,000,000 new secret keys and stamps a unique serial number on each one (see Figure 9-1). Note that there's no reason to order the serial numbers. Alice keeps a database of each secret key and serial number.

If Alice then sends Bob a plaintext electronic copy of that database, he can easily pick a serial number (say, serial number 500,121) and its paired secret key (1yt8a42x35); then he calls Alice to tell her to use the secret key associated with serial number 500,121. But as Figure 9-2 shows, what's easy for Alice is also easy for the eavesdropping BlackHat. BlackHat has copied the database Alice sent to Bob-remember that it was sent over public lines-and quickly figures out the secret key. So this secret key exchange doesn't work for Alice and Bob.

Figure 9-1 Alice makes 1,000,000 secret keys.

Figure 9-2 Alice sends Bob a file of secret keys and serial numbers, but BlackHat copies it and learns their secrets.

### Second Attempt: An Encrypted Database of Key/Serial Number Pairs

 Alice encrypts the entire database of serial number/secret key pairs.

Now suppose that Alice encrypts her serial number/secret key database and then ships the encrypted database to Bob. Alice tells Bob the encryption method she used but not the encryption key. Because Bob doesn't know Alice's encryption key, he must try all possible keys. Say it takes Bob about one hour, using his desktop computer, to find Alice's encryption key.1 After decrypting the entire database, Bob selects a secret key and tells Alice the matching serial number-say, serial number 500,121. As before, Alice knows to use secret key 1yt8a42x35 (see Figure 9-3). But, like Bob, BlackHat can also spend about an hour decrypting Alice's database, so BlackHat can also figure out that serial number 500,121 matches secret key 1yt8a42x35. We still need a method that will make BlackHat's job much tougher than Alice and Bob's job.

Figure 9-3 Alice sends an encrypted database of secret key and key pairs, but BlackHat isn't intimidated.

### Merkle's Insight: Individually Encrypted Key/Serial Number Pairs

This brings us to Merkle's creative insight. As the result of this innovation, Bob's work doesn't change, but BlackHat's work increases dramatically. Let's see how.

 Third approach. Encrypt each individual serial number/secret key pair.

Previously, Alice encrypted the entire database with one secret key. But that didn't make BlackHat work longer than Bob. Now Alice sends 1,000,000 encrypted secret key/serial number pairs (see Figure 9-4).

Figure 9-4 Alice sends Bob 1,000,000 encrypted secret key/serial number pairs. BlackHat eavesdrops and copies the key pairs sent to Bob.

 Each secret key/serial number pair is encrypted with a different secret key.

Each secret key/serial number pair (second column, Table 9-1) is encrypted with a unique secret key (third column, Table 9-1) to make the encrypted pair (final column, Table 9-1). Alice uses a million different secret keys to encrypt the 1,000,000 individual secret key/serial number pairs. Table 9-1 shows each secret key/serial number pair encrypted with a separate key.

Bob gets 1,000,000 encrypted secret key/serial number pairs and picks one encrypted pair-say, Pair3. He spends an hour deciphering it and learns that Pair3 means secret key 1yt8a42x35 and serial number 500,121 (see Figure 9-5). As before, he tells Alice that he will encrypt with the secret key matching the serial number 500,121. Alice quickly matches the serial number to the corresponding secret key in her database.

As before, Alice and Bob assume that BlackHat is listening, has copied all 1,000,000 encrypted pairs Alice sent to Bob, and has heard Bob tell Alice to use the secret key associated with serial number 500,121.

### Black Hat's Frustrating Problem

 BlackHat must decrypt many more serial number/secret key pairs than does Bob.

How does BlackHat figure out the secret key Alice and Bob agreed to share? BlackHat doesn't know that Bob selected Pair 3; he knows only that one of the encrypted pairs Alice sent to Bob contains serial number 500,121. But here's the rub: BlackHat doesn't know which pair. It must be one of the million pairs, but he has no clue which one (see Figure 9-6).

Table 9-1 Alice's database of secret keys and serial numbers, encryption key, and encryption message sent to Bob (and snooped by BlackHat).

Figure 9-5 Bob picks one encrypted pair and decrypts it to learn the secret key and serial number.

Recall that Bob tells Alice only the serial number he learned. BlackHat has a much bigger problem than Bob: He must decrypt about half the encrypted pairs Alice sent to Bob until he stumbles onto the one pair that decrypts to 1yt8a42x35 / 500,121.

With this twist, Merkle turned a relatively simple problem for Bob into a time-consuming problem for BlackHat. If deciphering one encrypted pair takes about one hour and if BlackHat must try, on average, about 500,000 of them, BlackHat has a 500,000-hour problem. Bob has only a one-hour problem.

As a result, Alice and Bob can communicate confidentially with their shared secret key while BlackHat is busy trying to figure out which secret key they are using.

### The Key to Public Key Technology

 Easy and difficult puzzles.

All public key cryptography works in the same way. You and your confidant share a quickly solved problem. Let's call it an easy puzzle. But if you withhold a critical puzzle piece from your adversary, the easy puzzle is transformed into a difficult, time-consuming puzzle. In Merkle's innovative implementation, Bob solves one encrypted pair and finds a secret key to share with Alice. BlackHat doesn't know and isn't told which encrypted pair Bob solved. That critically withheld puzzle information forces BlackHat to solve, on average, 500,000 encrypted pairs-a much more time-consuming puzzle.

Figure 9-6 BlackHat has a big problem. He knows that one of the 1,000,000 pairs he copied contains the pair Alice and Bob are using; but because he doesn't know which one, he must try them one by one. According to probability theory, he'll have to try about half of them before he stumbles onto Bob's choice.

 Technology reduces the perceived advantage.

A ratio of 500,000 to 1 may seem impressive, and certainly after 500,000 hours (or about 50 years) Alice and Bob's secrets have much less value. A delay of 50 years may seem sufficient to protect secrets, but more powerful computer hardware and more efficient software can dramatically reduce that number.

Bob may use a \$1,000 computer to solve a puzzle sent to him by Alice, but an adversary-wanting to learn about, let's say, the next major West Coast land deal, might use a \$10,000,000 computer. A computer 10,000 times more expensive and 10,000 times faster than Bob's desktop might solve the 50-year problem in 50 hours. With better software, it might take even less time.

Cryptographic history is replete with stories of technological advances eliminating cryptographic advantages. As a result, cryptographers prefer a much larger advantage: at least 500,000,000 to 1, which is about 1,000 years compared with 1 minute. One way to accomplish that is to give BlackHat a much bigger search space. For example, Alice could send a greater number of encrypted pairs, but that's an inefficient use of bandwidth. Only one of the 1,000,000 encrypted pairs is used; the other encrypted 999,999 pairs just cloak the selected one and are thrown away.

Hiding in Plain Sight

Just as Merkle designed a way to keep an electronic adversary busy looking through a maze of possibilities, so, too, did spies design real-world mazes to hide the locations of dead drops: prearranged hidden places for leaving and retrieving messages and money. A good location was one that let you hide your message in plain sight, a hiding place that was hard to recognize unless you had secret information.

One of the more elaborate hiding places in the history of espionage helped the U.S. Central Intelligence Agency (CIA) retrieve valuable information about the Cuban missile crisis of the 1960s from an insider in Soviet military intelligence. The informant gave the CIA specific instructions about how to find the information hidden in a Moscow building-a task that would be hard for someone without the instructions or who had never directly observed the exact location.

His instructions were to go to a particular foyer near the number 28 telephone. Across the hallway was a dark green radiator held to the wall by a single metal hook. Between the wall and the radiator was a space 2 to 3 centimeters wide that was to be used as the drop. The selected hiding place made it easy for both parties to deposit and retrieve materials while in a standing position. In this way, someone observing the scene would be less likely to notice the drop.

Merkle envisioned his public distribution of secret keys in a similar way: Make it hard for BlackHat to find your secret key by giving him a much bigger search space than Bob's.

1. Obviously, Alice does not choose a "strong" cryptographic method to encrypt her database. Recall from Chapter 4 that a strong encryption method is one in which the most practical attack is to try each possible key and there are so many possible keys that it's infeasible to try even half of them.
• + Share This
• 🔖 Save To Your Account

### InformIT Promotional Mailings & Special Offers

I would like to receive exclusive offers and hear about products from InformIT and its family of brands. I can unsubscribe at any time.

## Overview

Pearson Education, Inc., 221 River Street, Hoboken, New Jersey 07030, (Pearson) presents this site to provide information about products and services that can be purchased through this site.

This privacy notice provides an overview of our commitment to privacy and describes how we collect, protect, use and share personal information collected through this site. Please note that other Pearson websites and online products and services have their own separate privacy policies.

## Collection and Use of Information

To conduct business and deliver products and services, Pearson collects and uses personal information in several ways in connection with this site, including:

### Questions and Inquiries

For inquiries and questions, we collect the inquiry or question, together with name, contact details (email address, phone number and mailing address) and any other additional information voluntarily submitted to us through a Contact Us form or an email. We use this information to address the inquiry and respond to the question.

### Online Store

For orders and purchases placed through our online store on this site, we collect order details, name, institution name and address (if applicable), email address, phone number, shipping and billing addresses, credit/debit card information, shipping options and any instructions. We use this information to complete transactions, fulfill orders, communicate with individuals placing orders or visiting the online store, and for related purposes.

### Surveys

Pearson may offer opportunities to provide feedback or participate in surveys, including surveys evaluating Pearson products, services or sites. Participation is voluntary. Pearson collects information requested in the survey questions and uses the information to evaluate, support, maintain and improve products, services or sites, develop new products and services, conduct educational research and for other purposes specified in the survey.

### Contests and Drawings

Occasionally, we may sponsor a contest or drawing. Participation is optional. Pearson collects name, contact information and other information specified on the entry form for the contest or drawing to conduct the contest or drawing. Pearson may collect additional personal information from the winners of a contest or drawing in order to award the prize and for tax reporting purposes, as required by law.

### Newsletters

If you have elected to receive email newsletters or promotional mailings and special offers but want to unsubscribe, simply email information@informit.com.

### Service Announcements

On rare occasions it is necessary to send out a strictly service related announcement. For instance, if our service is temporarily suspended for maintenance we might send users an email. Generally, users may not opt-out of these communications, though they can deactivate their account information. However, these communications are not promotional in nature.

### Customer Service

We communicate with users on a regular basis to provide requested services and in regard to issues relating to their account we reply via email or phone in accordance with the users' wishes when a user submits their information through our Contact Us form.

## Other Collection and Use of Information

### Application and System Logs

Pearson automatically collects log data to help ensure the delivery, availability and security of this site. Log data may include technical information about how a user or visitor connected to this site, such as browser type, type of computer/device, operating system, internet service provider and IP address. We use this information for support purposes and to monitor the health of the site, identify problems, improve service, detect unauthorized access and fraudulent activity, prevent and respond to security incidents and appropriately scale computing resources.

### Web Analytics

Pearson may use third party web trend analytical services, including Google Analytics, to collect visitor information, such as IP addresses, browser types, referring pages, pages visited and time spent on a particular site. While these analytical services collect and report information on an anonymous basis, they may use cookies to gather web trend information. The information gathered may enable Pearson (but not the third party web trend services) to link information with application and system log data. Pearson uses this information for system administration and to identify problems, improve service, detect unauthorized access and fraudulent activity, prevent and respond to security incidents, appropriately scale computing resources and otherwise support and deliver this site and its services.

### Cookies and Related Technologies

This site uses cookies and similar technologies to personalize content, measure traffic patterns, control security, track use and access of information on this site, and provide interest-based messages and advertising. Users can manage and block the use of cookies through their browser. Disabling or blocking certain cookies may limit the functionality of this site.

### Do Not Track

This site currently does not respond to Do Not Track signals.

## Security

Pearson uses appropriate physical, administrative and technical security measures to protect personal information from unauthorized access, use and disclosure.

## Children

This site is not directed to children under the age of 13.

## Marketing

Pearson may send or direct marketing communications to users, provided that

• Pearson will not use personal information collected or processed as a K-12 school service provider for the purpose of directed or targeted advertising.
• Such marketing is consistent with applicable law and Pearson's legal obligations.
• Pearson will not knowingly direct or send marketing communications to an individual who has expressed a preference not to receive marketing.
• Where required by applicable law, express or implied consent to marketing exists and has not been withdrawn.

Pearson may provide personal information to a third party service provider on a restricted basis to provide marketing solely on behalf of Pearson or an affiliate or customer for whom Pearson is a service provider. Marketing preferences may be changed at any time.

## Correcting/Updating Personal Information

If a user's personally identifiable information changes (such as your postal address or email address), we provide a way to correct or update that user's personal data provided to us. This can be done on the Account page. If a user no longer desires our service and desires to delete his or her account, please contact us at customer-service@informit.com and we will process the deletion of a user's account.

## Choice/Opt-out

Users can always make an informed choice as to whether they should proceed with certain services offered by InformIT. If you choose to remove yourself from our mailing list(s) simply visit the following page and uncheck any communication you no longer want to receive: www.informit.com/u.aspx.

## Sale of Personal Information

Pearson does not rent or sell personal information in exchange for any payment of money.

While Pearson does not sell personal information, as defined in Nevada law, Nevada residents may email a request for no sale of their personal information to NevadaDesignatedRequest@pearson.com.

## Supplemental Privacy Statement for California Residents

California residents should read our Supplemental privacy statement for California residents in conjunction with this Privacy Notice. The Supplemental privacy statement for California residents explains Pearson's commitment to comply with California law and applies to personal information of California residents collected in connection with this site and the Services.

## Sharing and Disclosure

Pearson may disclose personal information, as follows:

• As required by law.
• With the consent of the individual (or their parent, if the individual is a minor)
• In response to a subpoena, court order or legal process, to the extent permitted or required by law
• To protect the security and safety of individuals, data, assets and systems, consistent with applicable law
• In connection the sale, joint venture or other transfer of some or all of its company or assets, subject to the provisions of this Privacy Notice
• To investigate or address actual or suspected fraud or other illegal activities
• To exercise its legal rights, including enforcement of the Terms of Use for this site or another contract
• To affiliated Pearson companies and other companies and organizations who perform work for Pearson and are obligated to protect the privacy of personal information consistent with this Privacy Notice
• To a school, organization, company or government agency, where Pearson collects or processes the personal information in a school setting or on behalf of such organization, company or government agency.

## Links

This web site contains links to other sites. Please be aware that we are not responsible for the privacy practices of such other sites. We encourage our users to be aware when they leave our site and to read the privacy statements of each and every web site that collects Personal Information. This privacy statement applies solely to information collected by this web site.

## Requests and Contact

Please contact us about this Privacy Notice or if you have any requests or questions relating to the privacy of your personal information.

## Changes to this Privacy Notice

We may revise this Privacy Notice through an updated posting. We will identify the effective date of the revision in the posting. Often, updates are made to provide greater clarity or to comply with changes in regulatory requirements. If the updates involve material changes to the collection, protection, use or disclosure of Personal Information, Pearson will provide notice of the change through a conspicuous notice on this site or other appropriate way. Continued use of the site after the effective date of a posted revision evidences acceptance. Please contact us if you have questions or concerns about the Privacy Notice or any objection to any revisions.

Last Update: November 17, 2020