Public key cryptography is a technology used for information security. It can be utilized to implement authorization schemes to protect access to data, guarantee data or code provenance and integrity, or be part of more complex key establishment algorithms.
Authorization Scheme
Let’s focus on the authorization scheme. We can imagine a network data storage appliance, managed by an IT administrator, and guarded by a program named the “access control agent”. The goal is to verify the identity of computers requesting access to the data storage before granting access. It can be compared to a real-world scenario where the network storage is a like building containing valuable goods, the IT administrator is the building tenant, and the access control agent is a door with a keyed lock.
To access the data on the network storage, a remote computer must first prove its identity to the access control agent. To that end, the requesting computer needs a self-generated, long-lived pair of keys (a public and a private key).
- The private key is a perfect random number, kept secret, never shared, and securely stored in that computer. This private key can be used by the computer to prove its identity because it is permanently attached to that computer. A correct proof of identity cannot be generated without knowledge of the private key, therefore the computer cannot be impersonated.
- The public key is directly derived from the private key using a straightforward but one-way calculation, such that it is impossible to figure out the private key value from the public. The public key is publicly shared and can be used by anyone to verify proof of identity. If the verification is a success, it means the proof was generated using the matching private key (remember: one computer -> one private key -> one public key); therefore, we can be assured that the requester knows the right private key. Note that the verification process never exposes the value of the private key.
The above remote computer can be compared to an individual trying to enter a building through a locked door. To that end, the individual must possess a door lock key with a unique random shape, that works with the matching door lock mechanism.
- The door lock’s key is equivalent to the computer’s private key: it is owned by only one individual, and kept secret, never shared, therefore it uniquely identifies the holder, because it is permanently attached to the holder.
- The door lock is equivalent to the computer’s public key. First, it uniquely matches a key, and second, if we suppose that the door lock mechanism cannot be torn down, then it is impossible to figure out the shape of the key that can open it. In a way, the door lock is used to verify the identity of the key holder without revealing secret information. When the door lock opens, it proves that the person used the matching key. Exactly like in public key cryptography!
In both cases, it could be verified that the requester owns the correct secret information without ever revealing it to anyone, even the verifying party ( a public key or a door lock that both reveal nothing about the related secret).
The Catch
Now there is a catch. As we explained, computers requesting access create their own arbitrarily chosen key pair.
Let’s assume the verification process works as follows:
|
Access control agent |
|
Computer 1 with key pair Kpub1, Kpriv1 |
|---|---|---|
|
Who are you? |
--> |
|
|
|
<-- |
I’m computer #1234 |
|
What is your public key? |
--> |
|
|
|
<-- |
Here you go: 1489758125891748957 (Kupb1) |
|
Please calculate the signature of this random message: “1892374897189” with your private key |
--> |
|
|
|
|
OK Please wait… Calculate R=Sign(1892374897189 with Kpriv1) |
|
|
<-- |
Here you go: R=8925689082905869082 |
|
I’m checking R with your public key now… Verify (8925689082905869082 with KPub1)… OK! |
|
|
|
OK, you can access! |
--> |
|
The above verification scheme only proves that the requester knows the value of the private key that matches the public key used when verifying the identity, but it doesn’t confirm the identity at all.
Demonstration:
|
Access control agent |
|
Computer 2 with key pair Kpub2, Kpriv2 |
|---|---|---|
|
Who are you? |
--> |
|
|
|
<-- |
I’m computer #1234 (Computer 2 impersonates computer 1!!!) |
|
What is your public key? |
--> |
|
|
|
<-- |
Here you go: 902586812780778907890 (Kupb2) |
|
Please calculate the signature of this random message: “12541252345245” with your private key |
--> |
|
|
|
|
OK Please wait… Calculate R=Sign (12541252345245with Kpriv2) |
|
|
<-- |
Here you go: R=2356736736572356235623 |
|
I’m checking R with your public key now… Verify (2356736736572356235623 with KPub2) … OK! |
|
|
|
OK, you can access! |
--> |
|
The access control agent cannot figure out the real identity of the requesting computer. The above protocol is similar to letting anyone come and install their own door lock on the building’s door. When they’re entering the building, you know that they have the right key, but you cannot know who they are.
Conclusion
We have just discovered how the Rivest, and Shamir (RSA) and Elliptic Curve Digital Signature Algorithm (ECDSA) public-key signature algorithms work, and their caveats!
In Part 2, we will learn how to correctly attach an identity and a public key, which is like putting a trustworthy label on a door lock.
