Public-Key Cryptosystems and Digital Signatures
Introduction
Sometimes I would get some interesting questions from my friends about internet security, such as whether it is possible to leak the bank account password when logging to the online bank via an untrusted network, whether it is possible that the message you received from someone via an untrusted network got modified maliciously, and whether it is possible that someone pretends to be you and send messages in your name. My answers to those questions are as long as your computer and cell phone are uncontaminated they are almost impossible thanks to our modern public-key crytosystems and digital signatures.
There are a couple of introductions to the public-key crystosystems and digital signature available online. However, I think most of them are incomplete or hard to understand. In this blog post, I am going to describe the public-key crystosystems and digital signatures using extremely simple math, so that there would be no ambiguity at all.
Usages
The modern cryptosystems are public-key encryption systems in which everyone has a public-key for encryption and a private key for decryption. The public-key is seen by everyone, but the private is only accessible by the owner. The public-key encryption systems could also generate digital signatures which could be used to verify whether the message you received is unmodified and truly sent from the sender.
RSA (Rivest–Shamir–Adleman) is a typical algorithm for the public-key cryptosystems used by modern computers to encrypt and decrypt messages. However, we are not going to introduce the RSA algorithm in this blog post. Instead, we would describe the public-key cryptosystems and digital signatures at a high level.
Essential Features
Each user has their own encryption and decryption functions, $E$ and $D$, using public-key and private key respectively. We use $M$ to represent the message to be encrypted and sent. There are four features that are essential to a public-key cryptosystem.
- Decrypting an encrypted message gives you the original message (Of course!). Specifically,
$$
D(E(M)) = M
$$
- Encrypting a decrypted message gives you the original message (Hmm…). Specifically,
$$
E(D(M)) = M
$$
$E$ and $D$ are easy to compute. This means the encryption and decryption process should be fast.
The publicity of $E$ does not compromise the secrecy of $D$. This means you could hardly find a way to decrypt the encrypted message, even if you know how to encrypt the message.
We would ignore how to satisfy the four features in this blog post.
Message Encryption and Decryption
Suppose we have two people, Alice and Bob. Both of them are using the same public-key cryptosystems. This means Alice and Bob both have their private keys stored secretly and have their public key published to some authorities. From the authorities, we could find the public keys of Alice and Bob unambiguously. We denote encrypting the message using Alice and Bob’s public keys to be $E_A$ and $E_B$ respectively, and decrypting the message using Alice and Bob’s private keys to be $D_A$ and $D_B$ respectively.
One day, Alice wanted to send a private message $M$ to Bob. Alice found the public key of Bob, encrypted the message $M$ using Bob’s public key. The encrypted message for Bob is denoted as $C$.
$$
E_B(M) = C
$$
Once Bob received the encrypted message $C$, he could decrypt $C$ using his private key.
$$
D_B(C) = D_B(E_B(M)) = M
$$
Even if the network was compromised and someone intercepted $C$, it is still almost impossible to decrypt $C$ because of that $D_B$ is unknown and the feature “the publicity of $E$ does not compromise the secrecy of $D$” for public-key cryptosystems.
The message content is safe because of the public-key encryption systems. However, it does not provide any assurance about the sender. For example, James could send Bob a message $M^\prime$ which specifically says the message is from Alice, encrypt it using $E_B$, and send it to Bob. If there is no author verification procedure and Bob is not careful enough, Bob might actually think the message is sent from Alice. In some other scenarios, James might have intercepted the encrypted message $C$ sent out from Alice to Bob, prevented the message transmission to Bob, replaced the original message to $M^\prime$ which specifically says the message is from Alice, encrypt it using $E_B$, and send it to Bob. Bob might also be convinced that the message content $M^\prime$ was actually the original message Alice has sent. Specifically,
$$
E_B(M^\prime) = C^\prime \\
D_B(C^\prime) = D_B(E_B(M^\prime)) = M^\prime
$$
Digital signatures, derived from the public-key cryptosystems, are designed to solve these authentication problems.
Digital Signatures
In addition to the encrypted message $C$ that Alice sent to Bob, Alice would also have to send her digital signature $S$ to Bob. Namely,
$$
E_B(D_A(M)) = S
$$
Alice could find $E_B$ using Bob’s public key and $D_A$ using her private key.
Once Bob received both $S$ and $C$, he could decrypt both $S$ and $C$ using his private key and Alice’s public key. Specially,
$$
D_B(C) = D_B(E_B(M)) = M \\
E_A(D_B(S)) = E_A(D_B(E_B(D_A(M)))) = E_A((D_A(M))) = M
$$
We found actually the two decrypted messages from $S$ and $C$ are exactly the same. This is expected if the message was sent from Alice and the content of the message was not modified. Let’s further see what will happen if someone pretends to be Alice to send a message to Bob, or the content of the message has been modified.
James, again, wanted to send Bob a message $M^\prime$ which specifically says the message is from Alice, or had intercepted an encrypted message $C$ from Alice, blocked it and created a message $M^\prime$ which specifically says the message is from Alice. To make the message readable by Bob, James encrypted $M^\prime$ using $E_B$, send the encrypted message $C^\prime$ to Bob.
$$
E_B(M^\prime) = C^\prime
$$
Because Bob does not accept any message without a signature, James had to make up a signature. However, because James knew nothing about Alice’s private key, he used a decryption function $D_J$ which is different from Alice’s secrete $D_A$. The signature James generated would be
$$
E_B(D_J(M^\prime)) = S^\prime
$$
Once Bob received both $S^\prime$ and $C^\prime$, he could decrypt both $S$ and $C$ using his private key and Alice’s public key as usual. Specially,
$$
D_B(C^\prime) = D_B(E_B(M^\prime)) = M^\prime \\
E_A(D_B(S^\prime)) = E_A(D_B(E_B(D_J(M^\prime)))) = E_A((D_J(M^\prime))) = M^{\prime\prime}
$$
In this case, Bob would see the two decrypted messages are not the same. Bob would then realize that there is something unusual happened and he should not trust anything about the message.
Hacking the Public-Key Cryptosystems
As long as the four features of the public-key cryptosystems hold, cracking it is almost impossible. If somedayy, when the almighty quantum computer is available, the feature “the publicity of $E$ does not compromise the secrecy of $D$” would be compromised, therefore the modern public-key cryptosystems would no longer be reliable. I may talk about this topic in the future.
There is another way to send fake messages to Bob in name of Alice, without using a quantum computer. If James could somehow crack the account name and password of Alice on the web application, replace the Alice’s public encryption function from $E_A$ to $E_J$, when Bob tried to retrieve Alice’s encryption function, he would get $E_J$ instead of $E_A$. The decryption of signature $S^\prime$ would become $M^\prime$ instead of $M^{\prime\prime}$ then. Concretely,
$$
E_J(D_B(S^\prime)) = E_J(D_B(E_B(D_J(M^\prime)))) = E_J((D_J(M^\prime))) = M^{\prime}
$$
In this case the two decrypted messages match. Bob would be convinced that the message is from Alice and it has not been modified.
It should be noted that James was replacing Alice’s public encryption function from $E_A$ to $E_J$, instead of replacing his private decryption function from $D_J$ to $D_A$. In principle, $D_A$ would only be kept on Alice local computer and not anywhere else. Even if James has Alice’s account name and password on the web application, he would not get a copy of $D_A$ unless he specifically hacked Alice’s physical computer.
Final Remarks
This reminds us that actually keeping our password safe is the most important.
References
Public-Key Cryptosystems and Digital Signatures
https://leimao.github.io/blog/Public-Key-Cryptosystem-and-Digital-Signature/