Keys and Locks — Why a Public Key Is Safe to Publish

The Small Padlock in the Address Bar

A small padlock icon floats in your browser's address bar. Whether you are logging into your bank, opening your email, or paying for goods, that picture is there. Yet, not many people truly understand what this picture means. Out of 1,880 people who responded to an online survey, 89% misunderstood what this icon meant (DOI: 10.1109/spw54247.2022.9833869).

When the same survey asked people to judge whether a site could be trusted, only 23 to 44% mentioned this icon. Yet, this small minority who paid close attention to the icon answered that they would stop purchases in a simulated shopping scenario if the icon were missing (DOI: 10.1109/spw54247.2022.9833869).

The researchers' conclusion is this: The padlock icon guarantees the security of the connection, but many people read it as a sign that the entire site is secure and trustworthy (DOI: 10.1109/spw54247.2022.9833869). The security of the connection means preventing anyone in the middle from eavesdropping on, altering, or faking and inserting the content traveling back and forth between your browser and that site (DOI: 10.17487/rfc8446, standard document). The padlock is a sign that the road is safe, not a sign that the shop at the end of the road is honest. Many people use the mechanism behind the icon several times a day without ever having had the opportunity to learn what that mechanism promises.

This article follows three questions. How is it safe even when the locking tool is handed out to everyone? What does that security rely on? Where does it actually break down? We will use no formulas, only going as far as the arithmetic of multiplying two large numbers.

The Problem of Having to Send the Key First

Let us say you put a letter in a box and send it locked with a padlock. Since the recipient needs the same key to open the box, the key must arrive before the letter. Symmetric encryption is a cipher where the locking key and the opening key are the same. This method only works if the sender and the recipient share the same secret key (DOI: 10.1017/cbo9780511780448.011, book chapter).

Locking and unlocking things is very old. However, the method of making the locking key entirely public only appeared in literature in the late 1970s (DOI: 10.1017/cbo9780511780448.011, book chapter).

In symmetric encryption, keys must be shared in advance, so the path used to hand over the key must also be secure. A paper published in 1976 targeted precisely this burden. That paper argued that a new type of cipher achieving two things was needed. Minimizing the need for a secure channel to hand over keys, and creating the equivalent of a handwritten signature. The paper proposed a way to solve these yet-unsolved problems (DOI: 10.1109/tit.1976.1055638).

The answer was to make the locking tool and the unlocking tool two different things. A public key is an open padlock put out for anyone to take and use. A private key is a key that only the owner keeps and never sends anywhere. A key pair is a set of a public key and a private key created together to match only each other.

Let us say you put a basket of open padlocks in front of your front door with a sign telling people to take one. A person who wants to send me a letter picks up one of the padlocks and locks a box. Anyone can do the locking, and only I, who have the key, can do the unlocking. The padlocks in the basket are public keys, and the key that only I have is a private key.

In 1978, a method that made this idea actually work came out. The core property of that method is this. Even if the key that locks the cipher, namely the public key, is made public, its paired key that unlocks the cipher, namely the private key, is not revealed (DOI: 10.1145/359340.359342). Therefore, there is no need for someone to carry the key over. The sender locks with the key made public by the recipient, and only the recipient, who knows the paired key, unlocks it (DOI: 10.1145/359340.359342).

If you separate the locking tool and the unlocking tool, you can exchange secrets without handing over keys in advance.

Why No Key Comes Out Even If You Take the Padlock Apart

Sixty-one times 53 takes a single sheet of paper. It is 3,233. Conversely, if you receive only the value 3,233 and try to find which two numbers were multiplied to produce it, trying each division one by one starting from small numbers is the simplest method. With four-digit numbers, it finishes quickly. However, when the numbers become very large, this backtracking becomes hopelessly difficult.

This is a calculation where one-way calculation is easily done by anyone in one direction, while reversing it in the opposite direction is absurdly hard (DOI: 10.1126/science.1074376). Multiplying the two numbers is the easy direction, and recovering the two numbers from the product alone is the hard direction. Modern cryptography stands on top of such calculations.

Public keys and private keys are placed separately in these two directions. In the 1978 method, the owner picks two large numbers, keeps them secret, and makes a key unlocked by those two numbers. The key that is made public contains not the two numbers themselves, but the value obtained by multiplying the two numbers (DOI: 10.1145/359340.359342). If you recover the original two numbers from the product, you can recreate the key, but that recovery is precisely the hard direction. This is the reason why you can hold the padlock in your hand and take it apart without being able to carve the key.

The task of turning a product back into its original two numbers by dividing it is called "factoring." The paper that introduced the method described its own security like this: the security of this system partly relies on the difficulty of factoring that published product (DOI: 10.1145/359340.359342).

The authors wrote "partly." This means it relies on other things as well, but what that remainder is is not written in the abstract. Furthermore, the difficulty of factoring a product itself is not a proven fact. Commonly used one-way calculations rely on unproven conjectures or possess already known weaknesses (DOI: 10.1126/science.1074376).

This padlock is merely made so expensive to open that no one can afford the cost yet, and it has not been proven impossible to open. When that cost becomes cheap, the lock weakens along with it.

Using the Same Device in Reverse Becomes a Signature

At the bottom of a paper contract goes a handwritten signature. The second thing the 1976 proposal wanted to create was the electronic equivalent of this signature (DOI: 10.1109/tit.1976.1055638).

This time, we reverse the order of holding the key and the lock. The owner attaches a mark to a message using their own key. Anyone tries the lock of the basket to confirm that the mark came from the matching key. At this point, nothing is hidden, and who attached it is revealed. A digital signature is a mark that only the person holding the private key can create, and anyone can verify using its matching public key. The 1978 method wrote down these uses together from the start. When you sign a message with the unlocking key kept secret—that is, the private key—anyone can verify that signature using the public matching key (DOI: 10.1145/359340.359342).

The digital signature standard published by the U.S. standards body lists three uses. First, it catches whether data has been changed without permission. Second, it verifies who signed. Third, it allows the recipient to present that signature to a third party as evidence that "that person truly signed" (DOI: 10.6028/nist.fips.186-4, standard document).

The third use has a name. Non-repudiation is the property that the person who signed cannot easily deny that signature later. The word used by the standard is "easily," and this word stops at the denial being difficult. The 1978 paper wrote the same point more strongly. The signature cannot be forged, and the person who signed cannot later deny the signature (DOI: 10.1145/359340.359342). However, even that assertion stands on the condition from the same paper that its security partly relies on the fact that multiplication is hard to factor.

Signatures also stand on the same math as locks. They are secure only as long as the cost of faking them remains too high.

Is That Padlock Really Theirs?

Let us imagine someone secretly slipping their own padlock into a basket. From the outside, they look identical. The box locked with that padlock opens for the person who slipped it in. They read the letter, lock it back up with the true owner's padlock, and send it on. Neither side notices.

A man-in-the-middle attack is an attack where someone stuck in the middle pretends to be the other party to both sides. The person who slipped the padlock in is this very person stuck in the middle. The man-in-the-middle attack is one of the best-known attacks in computer security. This attack targets the data itself flowing between both ends, aiming at the secrecy and integrity of that data—namely, that others cannot see it and it has not been altered in the middle (DOI: 10.1109/comst.2016.2548426, survey).

What the public key removed is the burden of handing over keys in advance. The burden of verifying whether the other person is truly who they claim to be remains and has simply moved elsewhere. Since you cannot tell whose a padlock is just by looking at it, you attach a name tag to the padlock, and a trustworthy third party signs that name tag.

A certificate is a document where a third party signs that this public key belongs to this person. A certificate authority is an organization that signs a certificate with its own private key to guarantee the owner of that public key. Whether the signature on the name tag is genuine is verified, in turn, using that certificate authority's public key.

The name tag does not end with its issuance. If a key is lost or stolen, that name tag must not remain active. Revocation is the act of invalidating an issued certificate before its expiration.

Weak points have also emerged in this framework. The number of certificate authorities trusted by browsers has multiplied, and when the browser trusts them, users effectively end up trusting them too. Yet the basic checks performed when issuing certificates have actually decreased (DOI: 10.1109/sp.2013.41, 2013 review). Because certificate authorities trusted by browsers can generally sign any site's name tag, the more trusted places there are, the more a flaw in a single place becomes a crack in the whole system. Attacks targeting secure web connections and their certificate trust framework have been proposed in number, executed in practice, and have evolved. Proposals to reinforce this framework have also emerged and been evaluated against one another (DOI: 10.1109/sp.2013.41).

The task of verifying whose padlock it is shifted to name tags and the entities signing those name tags, and attacks have targeted that very framework.

Where It Breaks Outside of Math

The first failure is a leaking key. A key leak is when a private key that was never supposed to be sent anywhere ends up in the hands of someone who is not the owner. For someone holding the key, the strength of the padlock does not matter. The math has no flaws, yet the box opens.

Keys leak more often than people think. Developers upload code to public repositories that anyone can see to fix it together. It is common to upload code with private key files or secret values (API keys) used to connect to services left inside (DOI: 10.14722/ndss.2019.23418). Looking for private key files and API keys for 11 services, secrets like these were leaking in over 100,000 repositories combined. New secrets were leaking by the thousands every day as well (DOI: 10.14722/ndss.2019.23418). This is the result of scanning incoming code in real time for nearly six months and scouring a public dataset containing 13% of open-source repositories. The authors conclude that such leaks are widespread and far from a solved problem.

Signatures are no different. Companies that make programs attach digital signatures to them, which is called code signing. Signed malware can bypass the protection mechanism that only installs and runs programs with a valid signature. Antivirus software also frequently skips checks for signed programs (DOI: 10.1145/3133956.3133958). The researchers divided the weaknesses of the code signing system into three types and gave two examples of threats. One is stealing the private key attached to a legitimate certificate to sign malware. Another is impersonating an actual company that does not make software and therefore lacks a signing certificate. The researchers also propose concrete steps to fix this ecosystem.

Keys reside in computer memory while they are in use. The main memory used by most computers retains its contents for several seconds even after the power is cut off. This went against widely held assumptions, and it happened even at room temperature and after being pulled out of the board (DOI: 10.1145/1506409.1506429, 2009 experiment). If you dump the contents of the memory entirely during that window, you can find the keys inside (DOI: 10.1145/1506409.1506429). Therefore, in front of someone who gets their hands on the machine, there are limits to how well the operating system can protect the keys. The researchers actually demonstrated that several full-disk encryption products that lock the entire storage device could be cracked without special equipment. While discussing several ways to reduce the risk, they wrote that as far as they knew, there was no simple solution to eliminate this risk.

Developers who translate cryptography into code usually borrow pre-made cryptographic toolkits. Making the tools simple helps, but that alone is not enough (DOI: 10.1109/sp.2017.52). Simple tools reduced the choices, making people less likely to pick unsafe configurations. However, when documentation was poor, examples were missing, and the ability to securely store keys was absent, participants given simple tools still struggled. This was true both in writing working code and in writing secure code. These are the results of a controlled experiment where 256 Python developers gathered from GitHub were given one of five toolkits and asked to perform common cryptographic tasks.

Documentation and examples only bridged the gap on the working side. Faithful documentation and easy examples appeared to compensate for the disadvantages of complex tools in terms of functionality, but not in terms of safety. Regardless of the toolkit, in about 20% of the tasks written correctly for functionality, participants believed their code was secure when it was not. This is a point the authors note as particularly concerning. Making code work and making code secure are different things, and even the people who wrote it failed to spot the difference. The authors' prescription is twofold: provide simple and convenient usage, and perhaps more importantly, provide documentation with safe and easy-to-use examples that broadly support common tasks (DOI: 10.1109/sp.2017.52).

The last is the person in front of the screen. If a browser cannot verify a site's identity, it displays a warning that the certificate is not valid. These warnings often appear in harmless situations, but they can also be a sign of a man-in-the-middle attack (DOI: 10.1184/r1/6621806). Even with better-designed warnings, far too many people chose the dangerous option. Two newly designed warnings were significantly better than those of three widely used browsers, but under all warning conditions, too many participants engaged in risky behavior (DOI: 10.1184/r1/6621806). This is the result of designing new warnings based on a user survey of over 400 people and comparing them in a lab experiment with 100 participants. The researchers believe that while warnings can be improved, it may be better to block unsafe connections entirely and eliminate harmless warnings to reduce warnings altogether.

The failures gathered here happened at the place where the key is stored, the way signatures and nameplates are trusted, the person writing the code, and the person in front of the warning. Failures due to flawed math are not on this list. However, this list is a selected set of examples and is not the result of counting accidents. On the math side as well, as seen earlier, there are unproven conjectures and known vulnerabilities (DOI: 10.1126/science.1074376). And quantum computers are cited as machines that can make reversing products cheap.

The Day It Gets Cheap, and Today

Quantum computers are a new kind of computer that use the physical laws of very small particles for calculation. If a large-scale quantum computer is built, it will become possible to solve the problem of factoring products and problems of the same family. They solve them in a way where the amount of computation does not spiral out of control even as numbers grow (DOI: 10.14722/ndss.2020.24203). This means that the difficult direction we saw earlier becomes easy. Then, all public-key methods in use today are considered unsafe in a post-quantum computer environment (DOI: 10.14722/ndss.2020.24203). Such a computer is still a possibility, and that possibility has become a worry for security researchers.

The work to fill that gap is already in motion. As of 2020, the U.S. standards body had begun the process of setting ciphers that withstand quantum computers as standards (DOI: 10.14722/ndss.2020.24203). A 2020 performance study that measured candidate signature schemes under real network conditions concluded that at least two are worth adopting with almost no extra burden compared to the signature methods used today (DOI: 10.14722/ndss.2020.24203).

And this apparatus is working right now. The method from 1978 is one of the most widely used public-key encryption methods (DOI: 10.1109/access.2021.3129224). SSL is a protocol that protects the connection between a browser and a site with encryption, and handles the security of the connection indicated by the padlock icon in the address bar. The successor protocol used today is called TLS. In 2012, SSL was the de facto standard for secure internet communication, and its safety against an intervening attacker relied on correctly verifying public-key certificates (DOI: 10.1145/2382196.2382204).

This apparatus is widely used today as well, its safety relies on a computational value that no one can afford yet, and it has not been proven that this value will remain expensive. That it is widely used and that it is unproven are both true.

A Few Seconds Opening a Bank Website

Now let us follow the few seconds it takes to type a bank address into the address bar and enter.

When the browser begins establishing a connection with the bank server, the bank presents a certificate. Inside it is the padlock the bank has placed in the basket, which is the bank's public key. There is also a name tag stating that this padlock belongs to this bank, alongside a signature on that name tag made by a certificate authority. The browser verifies that signature using the certificate authority's public key.

The security of this connection against an intervening attacker depends entirely on correctly verifying the certificate presented at this exact moment (DOI: 10.1145/2382196.2382204). If the verification is skipped or incorrect, someone else's padlock mixed into the basket will be accepted as the bank's. If it cannot be verified, a warning appears (DOI: 10.1184/r1/6621806). In the laboratory experiment mentioned earlier, including the condition where they received a newly designed warning, too many participants chose the dangerous option across all conditions. And such warnings frequently appear even in harmless situations.

The padlock icon in the address bar indicates that this connection is a secure connection (DOI: 10.1109/spw54247.2022.9833869). TLS, the protocol that establishes and maintains this connection, is designed to prevent the eavesdropping, tampering, and forgery we saw earlier—namely wiretapping, modification, and spoofing (DOI: 10.17487/rfc8446, standard document). The minority of respondents who paid close attention to the padlock when judging trust felt reassured after reading more details about the connection's security in the auxiliary screen that opens when clicking the padlock. The researchers suggest that communicating the connection's security accurately and clearly is more effective through such auxiliary screens than through a small icon (DOI: 10.1109/spw54247.2022.9833869).

Three things are not verified during these few seconds: whether the bank's private key remains solely with the bank, whether the certificate authority that signed the name tag checked properly at the time of issuance, and whether the value of tracing back from the padlock to the key remains computationally expensive. The connection security indicated by the padlock icon stands on top of these three things. If a key leaks, the box opens even if the mathematics is completely fine. The name tag of a stolen key can only be revoked once someone notices it has been stolen. As noted in 2013, the checks performed when issuing certificates have been decreasing, and it has not been proven that tracing back will permanently remain expensive. Furthermore, the icon never tells you from the start whether that site is an honest place (DOI: 10.1109/spw54247.2022.9833869).

That leaves one question: Who guards the issuer of the name tag? There is no single answer to this question. Several proposals have emerged to reinforce the certificate trust framework (DOI: 10.1109/sp.2013.41). The path of recording every issuance in a public ledger that anyone can see is covered in "What Does the Padlock in Your Address Bar Actually Guarantee? — Instead of Picking a Trustworthy Authority, the Web Decided to Write Every Issuance Down", and the next part of this series, "What Is a Blockchain", covers another idea: records guarded collectively by many participants.

Where to Look Next

One way to guard the issuer of a name tag is covered in "What Does the Padlock in Your Address Bar Actually Guarantee? — Instead of Picking a Trustworthy Authority, the Web Decided to Write Every Issuance Down" (/articles/certificate-transparency). It is the decision to write every issuance into a record that anyone can see.

If you are curious about the side where the checked value does not become cheap, go to "Will Quantum Computers Really Break All Encryption? — Two Misconceptions: "All" and "Later"" (/articles/post-quantum-crypto-debate). That side takes over the place this article merely passed by after noting that "if that value becomes cheap, the lock weakens along with it."

A device that shows the fact of knowing a secret without handing over the secret itself is in "Zero-Knowledge Proofs: Proving the Truth Without Revealing the Data" (/articles/zero-knowledge-proofs-basics).

This article only looked at verification between two people. The problem of many people agreeing on a single record is handled by "Consensus Without Trust — How Mutually Distrusting Participants Agree on One Ledger" (/articles/consensus-without-trust-basics).

Source Papers

• ""It builds trust with the customers" - Exploring User Perceptions of the Padlock Icon in Browser UI" (2022) — DOI: 10.1109/spw54247.2022.9833869 — Online survey of 1,880 people. 89% misunderstood the meaning of the padlock. While 23–44% mentioned the padlock when judging trustworthiness, they stated they would stop a hypothetical purchase if it were absent. The icon guarantees connection security, but is read as overall site reliability. A detailed secondary screen would likely be more effective.
• "Boolean Functions for Cryptography and Error-Correcting Codes" (2010, book chapter) — DOI: 10.1017/cbo9780511780448.011 — If the encryption key is secret, it is symmetric cryptography (relying on the sender and receiver sharing a secret key); if public, it is public-key cryptography. Public-key cryptography appeared in literature in the late 1970s.
• "New directions in cryptography" (1976) — DOI: 10.1109/tit.1976.1055638 — Proposed a new cryptographic system that minimizes the need for secure key delivery channels and provides the equivalent of handwritten signatures.
• "A method for obtaining digital signatures and public-key cryptosystems" (1978) — DOI: 10.1145/359340.359342 — Even when the encryption key is made public, the decryption key is not revealed. Claims no delivery needed, signature and public-key verification, and unforgeability and non-repudiation. Security relies "in part" on the difficulty of factoring public products.
• "Physical One-Way Functions" (2002) — DOI: 10.1126/science.1074376 — Modern cryptography stands on one-way functions, but commonly used ones rely on unproven conjectures or have known weaknesses. Physical one-way functions are offered as an alternative.
• "Digital signature standard (DSS)" (2013, standard document) — DOI: 10.6028/nist.fips.186-4 — Uses of signatures (tamper detection, signer identity verification, third-party evidence) and non-repudiation. A signer cannot "easily" repudiate later.
• "A Survey of Man In The Middle Attacks" (2016, survey) — DOI: 10.1109/comst.2016.2548426 — Man-in-the-middle attacks are one of the best-known attacks, targeting the confidentiality and integrity of data flowing between endpoints. Outlines classification and prevention mechanisms.
• "SoK: SSL and HTTPS: Revisiting Past Challenges and Evaluating Certificate Trust Model Enhancements" (2013) — DOI: 10.1109/sp.2013.41 — The number of certificate authorities trusted by browsers has grown while baseline issuance due diligence has dropped. Comparative evaluation of certificate trust model improvements.
• "How Bad Can It Git? Characterizing Secret Leakage in Public GitHub Repositories" (2019) — DOI: 10.14722/ndss.2019.23418 — Real-time scan for roughly 6 months + snapshots of 13% of repositories. Over 100,000 repositories affected, with thousands of new secrets leaked daily. A widespread and unresolved problem.
• "Certified Malware" (2017) — DOI: 10.1145/3133956.3133958 — Signed malware bypasses protection mechanisms and antivirus software. Three types of code-signing system weaknesses (private key theft, company impersonation, etc.). Proposes improvement steps.
• "Lest we remember" (2009) — DOI: 10.1145/1506409.1506429 — Main memory retains its contents for several seconds even after power is cut. Limits the ability to protect keys from physical access attackers, and several disk encryption products were breached. There is no simple fix to eliminate this.
• "Comparing the Usability of Cryptographic APIs" (2017) — DOI: 10.1109/sp.2017.52 — Controlled experiment with 256 developers and 5 libraries. Simplicity is beneficial but insufficient, and documentation supplements did not translate to security outcomes. About 20% of correctly written tasks were mistakenly thought to be secure. The prescription is a simple interface + broad support for common tasks + documentation with safe, easy-to-use examples.
• "Crying Wolf: An Empirical Study of SSL Warning Effectiveness" (2018) — DOI: 10.1184/r1/6621806 — Survey of 400 people + experiment with 100 people. New warnings were significantly better, but too many participants behaved dangerously under all conditions. Suggests reducing warnings themselves.
• "Post-Quantum Authentication in TLS 1.3: A Performance Study" (2020) — DOI: 10.14722/ndss.2020.24203 — If large-scale quantum computers emerge, all current public-key algorithms are considered unsafe. NIST standardization process initiated. At least two of the candidate signatures can be adopted with almost no added overhead.
• "Systematic and Critical Review of RSA Based Public Key Cryptographic Schemes: Past and Present Status" (2021) — DOI: 10.1109/access.2021.3129224 — RSA is one of the most widely used and applied algorithms in public-key cryptography ("one of the most"). Systematic review classifying them into 11 categories.
• "The most dangerous code in the world" (2012) — DOI: 10.1145/2382196.2382204 — SSL is the de facto standard for secure internet communication, and safety against active attackers depends on correctly verifying the public-key certificate presented during connection establishment.
• "The Transport Layer Security (TLS) Protocol Version 1.3" (2018, standard document) — DOI: 10.17487/rfc8446 — A protocol specification that enables communication designed to prevent eavesdropping, tampering, and forgery.