DEV Community: Alberto Boffi

Asymmetric Encryption & PKI: Digital Signatures, RSA, and Future Security

Alberto Boffi — Sun, 16 Aug 2026 12:09:45 +0000

Asymmetric Ciphers: Why Do We Need Something Different?

An asymmetric cipher (or public key cipher) is a cipher where the encryption and decryption keys are different.

Asymmetric ciphers were born to solve two main problems related to symmetric ciphers:

Symmetric ciphers cannot provide authenticity;
The security of a symmetric cipher is based on the precondition that the key has been previously exchanged in a secure way. But there is no way to do it, other than encrypting the key itself, which would recursively raise the same problem of exchanging another key.

The trade-off? Efficiency. Asymmetric ciphers are from 10x to 1000x slower than symmetric encryption.

In an asymmetric cipher, each one of the two endpoints has two keys, called public key and private key (or secret key), where the public key is built starting from the private key: $k_{p u b} = f (k_{p r i})$ .
As the name suggests, the public key can be visible to everyone, while the private key is only known by the respective endpoint. The cipher is based on three main features:

If the message has been encrypted with the private (public) key of a certain endpoint, it can be only decrypted with public (private) key of the same endpoint;
If the message has been encrypted with the public key, decrypt it without knowing the private key must be computationally hard;
Compute the private key given the public key (i.e. compute $f^{- 1} (k_{p u b})$ ) must be computationally hard.

To give a concrete example, a private key can be the set of two large prime numbers $p$ and $q$ , while the public key the product $p \cdot q$ . At this point, finding the prime factors that make up the public key means solving a famous NP problem known as prime factorization.

As for symmetric ciphers and cryptographic hash functions, since we cannot prove the exponential lower bound complexity of an algorithm, asymmetric ciphers are the outcome of public contests.

Confidentiality & Key Encapsulation

Asymmetric encryption can be used to provide confidentiality against a ciphertext-only attack as follows:

Bob (receiver) generates a keypair $(k_{p r i}, k_{p u b})$ . He sends $k_{p u b}$ to Alice;
Alice (sender) encrypts the plaintext with Bob's public key: $c t x = E (pt x, k_{p u b})$ . She sends it to Bob;
Bob decrypts the ciphertext using his private key: $pt x = D (c t x, k_{p r})$ .

Symmetrically, if Alice in turn generates another pair of private and public key, Bob can send messages to Alice too, producing a secure bi-directional communication.
However, since asymmetric encryption is so much slower than symmetric encryption, in practice an asymmetric cipher is never used to entirely manage a communication. Instead, it is used to do what is called key encapsulation, i.e. to securely exchange the key to use from there on with a symmetric cipher. Since the key is the only message being exchanged, just a pair $(k_{p r i}, k_{p u b})$ for only one of the two endpoints is enough. Moreover, for this reason we don't really need to consider known-plaintext attacks for asymmetric ciphers.

The standard cryptosystem used to provide confidentiality through asymmetric encryption is the Rivest-Shamir-Adleman, commonly known as RSA, which is actually based on the prime factorization problem.

Maintaining Integrity

For the property of integrity, nothing changes with respect to a symmetric cipher: we can still use a MAC tag in the same way.

Solving Authenticity: Digital Signatures

With an asymmetric cipher, we can actually provide authenticity. In this scenario, we are not interested anymore in hiding the content of the message, but in guaranteeing the identity of the sender. The way we can do it is by adopting the digital equivalent of a handwritten signature:

Alice (sender) generates a keypair $(k_{p r i}, k_{p u b})$ . She sends $k_{p u b}$ to Bob;
Alice sends the message $m s g_{A}$ in clear text to Bob;
Alice encrypts the message with her private key: $d s = E (m s g_{A}, k_{p r i})$ , where $d s$ is called digital signature. She sends the digital signature to Bob;
Bob (receiver) decrypts the digital signature with Alice's public key: $m s g_{B} = D (d s, k_{p u b})$
Bob compares $m s g_{B}$ with the message $m s g_{A}$ previously sent in clear text by Alice: if they are equal authenticity is guaranteed.

The role of the digital signature is therefore to guarantee that the endpoint who sent the message is the same one that originally transmitted the public key. This mechanism works in theory, but there's a practical problem: usually we want to provide authenticity in exchanging big documents, and when the message is particularly long the encryption is slow.
We can solve the problem by exploiting the cryptographic hash functions: Alice also sends the hash $h (m s g_{A})$ of the message, and produces the digital signature by encrypting $h (m s g_{A})$ instead of $m s g_{A}$ . At this point Bob can decrypt it and compare the result with the hash sent in clear by Alice.
Since the hash has a fixed length regardless of the size of $m s g_{A}$ , we are gaining in efficiency.

Another problem is due to the difference between digital signatures and paper signatures. In the physical world, to sign means to sign the output, while in the digital world it means to sign the code.
To understand this concept, let's imagine that we are signing a digital document. In reality, we are not signing what is written in the document at that specific moment, since the document can contain dynamic content, such as a date that changes according to the current day: when the date updates, the signature remains the same, and this is not the desired behavior.
Actually, there is no real way to solve this problem, other than signing only the types of document that can't change.

As last observation, let's imagine we want to provide confidentiality together with authenticity. In this case, we can combine the mechanisms seen for both properties, in a "matrioska" structure.
We are not going to see this in an explicit way, but in general both Alice and Bob will generate their own $(k_{p r i}, k_{p u b})$ pair. Then, Alice will first encrypt the message using her private key, and then she will encrypt the result another time with Bob's public key. Bob will decrypt the ciphertext received with his private key first, and then with Alice's public key.

The RSA standard, other than confidentiality, is built to provide authenticity as well.

How Secure Are They Compared to Symmetric Ciphers?

We have seen that the only possible attack to a secure symmetric cipher is brute-forcing the key, which has a cost of $T (λ) = O (2^{λ})$ .
Asymmetric ciphers, instead, rely on hard problems for which brute-forcing is not the best attack. This implies that break a secure asymmetric cipher requires little less than $O (2^{λ})$ operations, depending on the particular algorithm employed. Thus:

It's not possible to rely on the length of the key to compare the security of an asymmetric cipher with the security of a symmetric cipher.

We can only use the length of the key to compare two symmetric ciphers. If, instead, we want to compare the security of an asymmetric cipher, we need to know the computational complexity needed to break it.

Public Key Infrastructure

We're not done yet. For the moment, we cannot yet guarantee the full security of an asymmetric cipher. In fact, the asymmetric cipher architecture presented so far is sensitive to another kind of attack, called Man In The Middle (MITM) attack. In a MITM attack, the attacker can intercept any message exchanged between Alice and Bob, and send messages in turn. For this reason, he can be (logically) seen as a "man in the middle" of the communication.
A MITM attack can pose a threat to the communication since we have not yet seen a way to "bind" the public key to the endpoint that produced it. To understand this, let us suppose that Alice wants to send her public key $k_{p u b (A)}$ to Bob. If the attacker generates his keypair $(k_{p r i (E)}, k_{p u b (E)})$ , he can intercept $k_{p u b (A)}$ and send $k_{p u b (E)}$ to Bob instead. At this point, Bob will treat $k_{p u b (E)}$ believing it to be Alice's key. The attacker can now use his private key $k_{p r i (E)}$ to decrypt the messages sent by Bob, violating the confidentiality constraint, and to sign messages towards Bob, violating the authenticity constraint. He can furthermore carry on the communication in both directions, talking to Alice pretending to be Bob, and to Bob pretending to be Alice.

To prevent a MITM attack, we need to apply the same mechanism we just saw for providing authenticity on the message, but now providing authenticity on the public key that Alice sends to Bob. To do that, we introduce a new endpoint, called Certificate Authority (CA).
The communication consists of two phases. In the first phase, Alice communicates with the Certificate Authority:

Alice generates a keypair $(k_{p r i (A)}, k_{p u b (A)})$ . She sends $k_{p u b (A)}$ to the CA;
The CA generates a keypair $(k_{p r i (C)}, k_{p u b (C)})$ . It signs Alice's public key: $d s = E (k_{p u b (A)}, k_{p r i (C)})$ ;
The CA sends to Alice a collection of data containing: the digital signature $d s$ , the subject's public key $k_{p u b (A)}$ , the CA public key $k_{p u b (C)}$ and other details, as the signature algorithm or information about Alice. This collection is called digital certificate;

The second phase involves the communication between Alice and Bob. Now, we assume that Bob has a list of public keys owned by CAs he trust:

Alice sends the digital certificate to Bob;
Bob verifies that $k_{p u b (C)}$ is in his list of trusted public keys. If not, he discards the digital certificate;
If $k_{p u b (C)}$ is trusted, Bob decrypts the digital signature $d s$ with $k_{p u b (C)}$ : $k = D (d s, k_{p u b (C)})$ ;
Bob compares $k$ with $k_{p u b (A)}$ : if they are equal, authenticity on Alice's public key is guaranteed.

This communication scheme as it stands works in theory, but in practice there exists a large number of Certificate Authorities, and Bob can only have a small number of them in his list of trusted public keys. So, whenever he receives a public key from a new legitimate CA, he will discard the digital certificate. We therefore need to reduce the number of CAs to trust.
To do this, the key $k_{p u b (C)}$ of the CA is in turn authenticated by another higher-level CA, responsible for signing multiple low-level CA's public keys. For the same reason, the public keys of the high-level CAs are signed by other CAs on a higher level, and so on. The top-level CAs are called Root CAs: they are the only CAs that self-sign their certificates, and therefore the only CAs we need to trust.

All this mechanism of creation and distribution of digital certificates is known as Public Key Infrastructure (PKI).

What's Still Unsolved?

Despite everything we've covered, there are still some open problems in cryptography. Among these we can mention:

Homomorphic encryption: Homomorphic encryption is a form on encryption that allows users to perform computation over encrypted data without decrypting it. It's pretty useful when the user wants to give this data to a third-party as a public cloud infrastructure. We are already able to do it, but in the state-of-the-art the process it's quite slow. The challenge is to find more efficient ways to do it;
Quantum computing: Several NP problems underlying cryptographic algorithms, such as the prime numbers factorization, can be actually quickly solved by quantum computers. Nowadays there exists a research field, called post-quantum cryptography, that studies algorithms that are difficult to solve even for a quantum computer;
Side-channel information: Another, different kind of attack that can compromise a secure communication, is the side-channel attack. In a side-channel attack, instead of exploiting vulnerabilities in the cipher, the attacker exploits extra information derived from the implementation of the cipher, as power consumption or electromagnetic radiations emitted by the encryption device. The prevention of side-channel attacks is still a much debated and studied topic.

If you've made it this far, you now have a solid foundation to understand how modern cryptography works under the hood: from perfect ciphers that are beautiful in theory but impractical, to the block ciphers and hash functions that actually protect your data every single day. Which of these topics are you most curious to explore further?

Beyond Secrecy: Data Integrity, Cryptographic Hashes, and HMAC

Alberto Boffi — Sun, 16 Aug 2026 12:09:16 +0000

Beyond Secrecy: How We Guarantee Data Integrity in Symmetric Ciphers

We move now from confidentiality to the constraint of integrity. This might seem counterintuitive when talking about cryptography, but now we are not interested anymore in hiding the message to transmit, but just in guaranteeing that the content of the message can't be manipulated along the channel.
As we did for confidentiality, we need to model the attack framework that we assume is in place. In this case, we consider a bit-flipping attack (or active attack), in which the attacker can intercept and tamper with the data.
To understand the danger of this kind of attack, try to imagine a bank transaction: by simply changing some bits in the ciphertext, once decrypted, the message can contain a different amount of money with respect to what was originally sent.

Basic Idea: To provide integrity, we can append to the message a tag that the attacker is not able to forge, which can guarantee that the message has not been tampered with. This tag is also called Message Authentication Code (MAC) (and by the way, please note that the name is misleading: the Message Authentication Code provides integrity, not authenticity).
From a high level perspective, we can see this idea as a set of two functions, the first one used by the sender, and the second one by the receiver:

$co m p u t e_{M A C} (s t r in g, k ey) = t a g$
$v er i f y_{M A C} (s t r in g, t a g, k ey) = {t r u e ∣ f a l se}$

In practice, we can implement this concept using different approaches. CBC-MAC The idea behind a CBC-MAC basically consists in using as tag an encrypted version of the message. But since now, as we will see, the tag will not be decrypted by the receiver, we can use the block ciphers in a different way with respect to the CTR mode, in order to produce a shorter output string.
In particular, the block ciphers are connected in cascade in such a way that the input of each one is the output of the previous block XORed with the corresponding section of the message (the first section can be simply XORed with a 0).
In case the message has a fixed prefix, the tag has to be encrypted one more time for the technique to be secure.

At this point, we can describe the communication flow as follows:

Alice, given the message $m s g$ and the key $k$ , calculates the CBC-MAC tag and sends it to Bob together with $m s g$ ;
Bob, using the message received by Alice and the key $k$ , calculates the CBC-MAC from his side;
Bob compares his CBC-MAC with the one sent by Alice. If they are the same, the message has not been tampered with.

This method works since any attempt from the attacker to forge the message would cause a change even in the CBC-MAC calculated by Bob. To forge the message, the attacker should also change the CBC-MAC accordingly, but he cannot do it without the key.

The problem with this technique is the efficiency: calculating the CBC-MAC tag every time a message is sent is expensive and slow. This is where things get interesting: enter the next method. Cryptographic Hash Functions

A Cryptographic Hash is a function $H : Σ^{*} \to Σ^{n}$ for which the following problems are computationally hard:

Resistance to first preimage attack: Given $d = H (s)$ , find $s$ (i.e., invert $H$ ).
In the ideal case, the computation required is $T (n) = O (2^{n})$ ;
Resistance to second preimage attack: Given $s$ and $d = H (s)$ , find $r \neq = s$ such that $H (r) = d$ .
In the ideal case, the computation required is $T (n) = O (2^{n})$ ;
Resistance to collision: Find $r, s$ with $r \neq = s$ such that $H (s) = H (r)$ .
In the ideal case, the computation required is $T (n) = O (2^{\frac{n}{2}})$ .

The output of the function is called hash or digest.

Working with bits, in our case a cryptographic hash function can be more explicitly defined as $H : {0, 1}^{*} \to {0, 1}^{n}$ . So what it does is taking an arbitrary-length-input and convert it into a fixed-length-output. This means that the function is not injective: there will necessarily be multiple input being mapped into the same output. It's however not possible to compress the input indefinitely, as there always exists a minimum number of bits, called entropy, that can be used to represent a certain information. But not every function of this kind is a cryptographic hash function, as they must respect the three requirements. For example, a simple function that just takes the first $n$ bits of the input string is not resistant to both second preimage attack and collision.

The second preimage attack can be reduced to the first preimage attack, and this means that if $H$ does not satisfy the first property, it will necessarily not satisfy the second too. The opposite is, in general, not true. This also explains why, in the ideal case, the time complexity of the two attacks is the same. The ideal complexity required to find a collision is less because the computation can be speeded up by exploiting the math behind the probabilistic birthday paradox.

Worth noting: the first two properties are what, commonly speaking, distinguishes a cryptographic hash function from a simple hash function, which just tries to avoid conflicts.

As discussed talking about block ciphers, we cannot prove in theory that a function is a cryptographic hash function, since we cannot prove the exponential lower bound complexity of an algorithm. So, even in this case, these functions are the result of public contests.
Old cryptographic hash functions as SHA-1 and MD5 has proven to be broken. Nowadays, we can confidently use SHA-2 and SHA-3, that can produce digests of 256, 384 or 512 bits. SHA-3 has been produced because SHA-2 actually shares some mechanism with functions that have been proven to be broken, but both SHA-2 and SHA-3 are currently unbroken and widely standardized. Cryptographic hash functions are highly employed in computer security, for example to avoid storing passwords and other important data in clear text, or in digital forensics to obtain a "fingerprint" of the acquired disk. For our purposes, we need cryptographic hash functions to compute a MAC tag that is easy to build and verify.
Contrary to what we have done for the CBC-MAC, now Alice cannot simply use $h (m s g)$ as MAC tag to send with the message $m s g$ , since it would be completely useless. In fact, given that the hash is produced without using a key, the attacker can simply forge the message and change the tag accordingly.
So, given the key $k$ that Alice and Bob are using, the problem can be solved by using $h (m s g + k)$ as a tag.
We can therefore provide a tag that can guarantee integrity, and that can be computed much more efficiently with respect to the CBC-MAC.

It's worth pointing out that this is just the general idea behind how cryptographic hash functions are used to ensure integrity. In reality, the mechanism is more complex and sophisticated, and goes by the name of HMAC.

The Authenticity Constraint: Why Symmetric Ciphers Are Not Enough

Before moving on to the next part, let's briefly consider the scenario where we want to provide authenticity. This means that the attacker is communicating with the receiver by pretending to be someone else. Differently from confidentiality and integrity, there is actually no ongoing attack to model here: we're just considering standard communication, with the only difference being that the receiver was expecting a message from another sender.

Unfortunately, a symmetric cipher cannot be used to provide authenticity, so we can't discuss this property. To break through, we need a fundamentally different idea, called asymmetric cryptography, that will be discussed in the next article.

Symmetric Encryption: From One-Time Pad to AES and Block Ciphers

Alberto Boffi — Sun, 16 Aug 2026 12:08:55 +0000

Symmetric Ciphers: The Fight for Confidentiality

Let's start with the simpler of the two families. As previously discussed, a symmetric cipher is a cipher in which the required encryption and decryption keys are the same.

The first constraint we will analyze is also the most popular and discussed when talking about cryptography: confidentiality.
To be able to correctly judge the level of confidentiality of our cipher, the first thing to do is to put ourselves inside a framework where we assume to be under some kind of attack. In particular, we'll consider the most basic model of an attack, called ciphertext-only attack. In a ciphertext-only attack, the attacker can simply intercept and read the ciphertext transmitted over the channel.

The Perfect Cipher

Let $c t x_{se n t}$ be the ciphertext transmitted over the channel, and $pt x_{se n t}$ the corresponding plaintext. A cipher is said to be perfect iff $\forall pt x \in P$ and $\forall c t x \in C$ we have $P (pt x_{se n t} = pt x) = P (pt x_{se n t} = pt x ∣ c t x_{se n t} = c t x)$ .

In other terms, after eavesdropping the communication, the attacker has not any additional information with respect to what he previously knew. But this definition is not constructive. If a perfect cipher actually exists, how we can build one? Let's first look at a characteristic feature of a perfect cipher:

If a cipher with $∣ P ∣ = ∣ C ∣$ is perfect, then $∣ K ∣ \geq ∣ P ∣$ .

Let me walk through the intuition behind this theorem.
We are considering the case where the number of plaintexts is the same as the number of ciphertexts: for instance, suppose $P = {pt x_{1}, pt x_{2}, pt x_{3}}$ and $C = {c t x_{1}, c t x_{2}, c t x_{3}}$ .
If the number of keys is enough, we can theoretically map every plaintext in each possible ciphertext, depending on the key used. If instead the number of keys is not enough, some ciphertexts will not be mapped by every possible plaintext. This means that every time one of these ciphertexts is transmitted, the attacker will get more information than he had before. To understand it better, let's continue with the same example, and suppose that the key space has only two keys: $K = {k_{1}, k_{2}}$ . We can define a possible encryption function as follow: $E (pt x_{1}, k_{1}) = c t x_{1}$ , $E (pt x_{1}, k_{2}) = c t x_{2}$ , $E (pt x_{2}, k_{1}) = c t x_{2}$ , $E (pt x_{2}, k_{2}) = c t x_{3}$ , $E (pt x_{3}, k_{1}) = c t x_{2}$ , $E (pt x_{3}, k_{2}) = c t x_{3}$ .

Remember that this mapping is known to the attacker: as we discussed earlier, the cryptosystem is fully known to him.
For the sake of simplicity, let's just focus on $pt x_{1}$ , but the same reasoning can be applied to each plaintext: before the transmission the attacker can state that $P (pt x_{se n t} = pt x_{1}) = P (pt x_{se n t} = pt x_{2}) = P (pt x_{se n t} = pt x_{3}) = \frac{1}{3}$ , as he has no idea which message will be transmitted. Let's now suppose that $c t x_{3}$ is transmitted other the channel. At this point, since there is no key mapping $pt x_{1}$ to $c t x_{3}$ , the attacker knows that $pt x_{se n t} \neq = pt x_{1}$ . He can consequently tell that $P (pt x_{se n t} = pt x_{1} ∣ c t x_{se n t} = c t x_{3}) = 0 \neq = P (pt x_{se n t} = pt x_{1})$ . Therefore, we can state that the cipher is not perfect. Moreover, we can observe that the hypothesis of the theorem about $∣ P ∣ = ∣ C ∣$ is not so far-fetched: intuitively, in the encryption, to be sure that the same key does not map multiple plaintexts in the same ciphertext, we need at least as many ciphertexts as the number of plaintexts, i.e. $∣ P ∣ \leq ∣ C ∣$ . In the decryption we can apply the opposite reasoning: to be sure that the same decryption key does not map multiple ciphertexts in the same plaintext we need $∣ P ∣ \geq ∣ C ∣$ . So at the end we obtain $∣ P ∣ = ∣ C ∣$ . The only real example of secure cipher we have today is the Vernam cipher, also called one-time pad (OTP). In its most popular form, it considers $P = C = {0, 1}^{l}, K = {0, 1}^{λ}$ . The encryption function $E$ performs a bitwise XOR between the plaintext and the key to obtain the ciphertext. The decryption function $D$ is exactly the same function as $E$ : by performing a bitwise XOR between the ciphertext and the key, it returns the original plaintext. The key is called "pad". More formally:

E (pt x, k) = pt x \oplus k, D (c t x, k) = c t x \oplus k

However, keep in mind that this is not the only possible implementation of a OTP cipher. Another, conceptually equivalent variant, is the one in which the encryption function performs a modulo

l

addition between each character of the plaintext and the corresponding character of the key. In other terms, it works on the additive group

Z_{l}

. The robustness of OTP is due to some strict assumptions:

The pad must have at least the same length $l$ as the plaintext;
The pad must be chosen randomly, i.e. it must be uniformly distributed in the set of all possible keys;
The pad must never be reused (hence the name one-time pad).

About point 3, the best way to understand the danger of key-reusing is by seeing it in action. Suppose we want to use the OTP cipher on images, and we encrypt the dog image with a certain key:

Let's now encrypt another image (the cat image) with the same key:

The two results, taken individually, appear pretty random. But when we XOR them together, we get the XOR of the two original plaintexts, and this is what it looks like:

It's therefore evident that the attacker can get information about every plaintext that has been encrypted with the same key.
To test it yourself: https://t.ly/7YJX.

If these three assumptions are met, there is no way an attacker can get information about the plaintext by observing the ciphertext. The only information he could infer is the length of the plaintext (since it is the same of the length of the ciphertext), but this is already a public information of the cryptosystem. We can therefore state:

OTP is not vulnerable to brute force attacks.

In fact, by brute forcing all the possible keys, an attacker would get all the possible plaintexts, but the plaintext space is an information he already had before. This cipher is still used in government scope, but, unfortunately, for our everyday purposes is impractical. The reasons why actually lie in the assumptions stated before:

The first problem is to communicate the key to the receiver in a secure way, and in the case of OTP this means to communicate a message at least as long as the plaintext. The advantage in communicating the key, instead of directly communicate the plaintext, is that in this way we can send a unique long bitstream that can be used to extract multiple keys, until the sum of the length of the messages to sent reaches the length of the bitstream. But this process makes the data to communicate even bigger. Nowadays, where OTP is used, the key is communicated in person, even if this is still a method sensitive to corruption or theft. But this is obviously not an option for our daily purposes;
Generating a key that is completely random is not an easy task at all. True-random generators exist, but they are harder to implement and slower than pseudorandom generators;
We need as many keys as the possible messages that can be sent from here on, theoretically forever. In practical applications, some key reuse problems have arisen.

Since building a OTP cipher is not practical, we have to leave the ambition of a perfectly secure cipher. The idea is to go towards something more feasible to implement, that, even if not perfect in theory, is unbreakable in practice. And honestly, that's good enough.

Computationally-Secure Cipher: Good Enough Is Good Enough

We have seen that, in a perfect cipher, the attacker cannot know the plaintext associated to a ciphertext without knowing the key. But what if the plaintext can be actually obtained, yet the process of doing this is extremely computationally difficult?

A secure cipher is a cipher that is computational hard to break.

The statement refers to NP problems and it is telling that, in order for a cipher to be secure, decrypting the message without knowing the key should be reduced to solving a NP problem.
Note that this concept is based on the non-proved assumption that $P \neq = NP$ . If one day it will be proved that $P = NP$ , every concept described from now on will immediately collapse, and modern cryptography will have to be entirely thrown away. Let that sink in for a moment.
But how we can use this definition to our advantage?
We have seen that the problems with the implementation of a perfect cipher derive from the generation and distribution of long keys. We can therefore think to manage a communication as follows:
Basic Idea: Alice and Bob exchange a key that is shorter than the plaintext. At this point, both Alice and Bob use the same deterministic function to extend the length of key, in order to reach the length of the plaintext. With the same key, Alice and Bob can now communicate using a OTP protocol.
The function used to stretch the key goes under a particular name in the literature:

A Pseudorandom Number Generator (PRNG) is a deterministic function $PRNG : {0, 1}^{λ} \to {0, 1}^{λ + n}$ , where $n$ is called PRNG stretch.

The problem now is that, since the exchanged key is shorter than the plaintext, the cipher isn't perfect anymore. However, if the PRNG is hard to break, using Proposition 2 we can say that the cipher is by definition secure. In particular, still denoting with $λ$ the length of the original exchanged key, and assuming that the attacker can only do computations with polynomial complexity with respect to $λ$ :

A Cryptographically Safe Pseudorandom Number Generator (CSPRNG) is a PRNG whose output cannot be distinguished from an uniform random sampling of ${0, 1}^{λ + n}$ in $O (p o l y (λ))$ .

Although possible, building and testing a CSPRNG from scratch is neither efficient nor practical. So the real question becomes: how do we practically implement it? Actually, a CSPRNG is built by means of a particular building block, called block cipher. Let's first define and analyze a block cipher, then we'll move to describing how it is used to build a CSPRNG.

A block cipher is an encryption algorithm that takes as input a key $k$ and a string $pt x$ of a fixed length $b$ (called block), and returns an output of the same length. Given $k$ , the encryption function $E (pt x, k)$ corresponds to one of the possible permutations over the set of the $2^{b}$ possible input blocks.

When dealing with cryptography through a theoretical lens, a block cipher usually goes under the name of Pseudorandom Permutation (PRP), but both terms mean exactly the same thing.

A block cipher that accepts keys of length $λ$ is said to be broken if, without knowing the key, the plaintext can be derived from the ciphertext with less than $2^{λ}$ operations.

This means that in an unbroken block cipher the only way to derive the plaintext is to brute force the key, which costs $T (λ) = O (2^{λ})$ .
There are some examples of widespread block ciphers. In the 1970s the standard was the Data Encryption Algorithm (DEA, aka DES), but the keys were only long 56 bits, and nowadays it can be broken in a reasonable amount of time. A variant is Triple DES, that we can superficially see as the same algorithm but with a three-times recursive encryption. Triple DES can still be found in some legacy systems, but it's officially deprecated. The standard algorithm is now Advanced Encryption Standard (AES). In AES, the block has a length of 128 bits, and the key can be 128, 192 or 256 bits long.
Keep in mind that the time required to brute-force a cipher that uses a 256-bits key is not even astronomically quantifiable, and also a 128-bits length can be considered more than enough. Obviously, it's rare that the message we want to encrypt is exactly of the same length of the block. In particular, the case where $l e n (pl ain t e x t) < l e n (b l oc k)$ doesn't cause any problem, since it's sufficient to extend the plaintext with a sequence of fixed bits ("padding"), until we reach the length of the block.
But what most of the time happens is that $l e n (pl ain t e x t) > l e n (b l oc k)$ , and so the block cipher is always used in conjunction with some mechanism to overcome this problem, that comes under different names:

Electronic CodeBook (ECB)

It's the most intuitive method, and it's based on the principle of split-and-encrypt: we split the plaintext in multiple segments and we encrypt each segment with the same key.

It's fast, easy to implement and even suitable for parallelization. The decryption is straight forward as well. The problem arises when in the original message there are repetitions, and two or more blocks come out to be the same: in this case, even the corresponding outputs will coincide. Therefore, even if the attacker does not know the corresponding plaintext, he knows that such parts are repeated, and that's a huge and really dangerous information. This is usually shown with the "ECB penguin" example: the one on the left is the original image, while on the right its encrypted version computed in ECB mode. Due to lot of repeated sections in the original image, the result it's pretty bad in terms of confidentiality:

Counter (CTR) Mode

To overcome the drawback of the Electronic CodeBook, this time we use a counter, made of numbers of fixed length, sequentially increased. We encrypt each value of the counter and then we XOR it with each segment of the plaintext. This process will return an output that it's always different.The starting number of the counter is indifferent, and we can also decide to use an increment different than 1, but 1 is secure enough and results in a more efficient computation.

We can also repeat the experiment of the encryption of the penguin image, using now the CTR mode. The difference in the result is pretty evident:

The CTR mode is actually the definitive implementation of our original idea about the construction of a computationally-secure cipher. In fact, in its schema we can actually spot a PRNG (highlighted in the figure below), that stretches the key received as input. If the block ciphers are not broken, the PRNG is also a CSPRNG. The concatenation of the outputs of each block cipher is the output string of the CSPRNG, which is then XORed with the plaintext in order to obtain the ciphertext, as in the OTP cipher.

How Block Ciphers Are Actually Built

I won't cover the algorithms behind the commonly used block ciphers here, but it is important to discuss the process that leads to their creation.
As we have seen, to prove that a PRNG is a CSPRNG we should prove that the block cipher employed is not broken, i.e. that deriving the plaintext or the key has at least a cost $T (λ) = O (2^{λ})$ . However, unfortunately, we are not (yet) able to do this. In fact, proving the exponential lower bound complexity of an algorithm would imply proving that $P \neq = NP$ . The only thing we can do is to prove that a PRNG is not a CSPRNG, in case we are able to derive the plaintext with less than $2^{λ}$ operations.
For this reason, the commonly used block ciphers are the result of public contests, where cryptographers propose their algorithms and other cryptographers try to break them.
At the beginning, introducing cryptography, we said that a public cryptosystem must not compromise security. We see now that a public cryptosystem actually improves security, since it means more revision, more testing and so more guarantees of robustness. This is something I find really elegant about the field.

What If the Attacker Already Knows Part of the Message?

So far we have analyzed confidentiality under the hypothesis of a ciphertext-only attack. But a ciphertext-only attack is not the only kind of attack that can compromise the constraint of confidentiality. Another possible threat is the so-called known-plaintext attack. In a known-plaintext attack, the attacker knows at least a sample of couples $(pt x, c t x)$ , where $c t x$ is the encryption of $pt x$ . A famous example of this kind of attacker was Alan Turing when, in the early 40s, he discovered repetitive messages in the Enigma code corresponding to the greeting to Adolf Hitler.
A limit case of a known-plaintext attack is the chosen-plaintext attack: in this case the attacker actually chooses the plaintext, and can consequently see the corresponding ciphertext. It's a rarer condition.
We can anyway just focus on general known-plaintext attacks, as chosen-plaintext attacks are just a proper subset.

To analyze the situation, we consider the extreme case, where $P = {pt x_{1}, pt x_{2}}$ . At this point, if the encryption function is deterministic (as the ones seen so far), the cipher is not secure. In fact, even if the attacker knows only a pair $(pt x_{1}, c t x_{1})$ , he will be able to understand every message exchanged: if he reads $c t x_{1}$ , he knows that the original message is $pt x_{1}$ , vice versa $pt x_{2}$ .
This means that, in order for the cipher to be secure, the encryption function must be non-deterministic. Actually, there exists different paths we can follow to reach this goal:
A first, simple way is to manipulate the key every time it is used. Another common method is to choose each time a different number, called nonce, as starting point of the counter. But the most popular way to do it is probably the technique of rekeying, employed through what goes under the name of symmetric ratcheting. This method consists in producing a different key for every message through the use of a PRNG, that takes an input string of length $λ$ and stretches it into an output of length $2 λ$ : the first half of the output is used as a key, while the second half is used as input to the same function to produce another key, and so on. The initial input used to generate all the keys from there on is called seed.

The terms "ratcheting" derives from the fact that, as a ratchet can only turn on one side but cannot turn back, this mechanism ensures that, even finding a key, there's no way to know the previous ones.

What's Next?

We've locked down confidentiality, but what happens when the attacker can tamper with the ciphertext? Next up: integrity and hash functions.

Foundations of Cryptography: Information Theory & Security Models

Alberto Boffi — Sun, 16 Aug 2026 12:08:31 +0000

The Big Picture

Cryptography is the study of techniques to allow secure communication and data storage in the presence of attackers.

That's a good start, but it doesn't tell us much on its own. If we want to define cryptography in a more formal and precise way, we have to refer to the information theory, credited by Claude Shannon:

A communication is a flow of information over a channel that takes place between two endpoints: a sender, made of an information source and an encoder, and a receiver, made of an information destination and a decoder.

As convention, the two endpoints are usually called "Alice" and "Bob": you'll see these names everywhere in cryptography. The "information" can be modeled as strings of symbols belonging to a finite alphabet. Being in the computer science discipline, this alphabet is usually $Σ = {0, 1}$ . The ordinary readable string containing the information the sender wants to transmit is called message (or plaintext), while the encoded version of the message that is actually transmitted over the channel is the ciphertext.

A cryptosystem is a tuple $(P, C, K, E, D)$ , where:

The plaintext space $P = {0, 1}^{l}$ is the set of all possible plaintexts $pt x$ ;
The ciphertext space $C = {0, 1}^{l^{'}}$ is the set of all possible ciphertexts $c t x$ . Please note that, in general, $l \neq = l^{'}$ , i.e. the length of the plaintext does not necessarily have to coincide with that of the ciphertext;
The key space $K = {0, 1}^{λ}$ is the set of all possible keys $k$ ;
The encryption function $E$ is a function defined as $E : P \times K \to C$ ;
The decryption function $D$ is a function defined as $D : C \times K \to P$ .

A cipher is an implementation of the encryption function $E$ and decryption function $D$ such that, for every plaintext $pt x \in P$ , $\exists k, k^{'} \in K$ such that $D (E (pt x, k), k^{'}) = pt x$ . In case $k = k^{'}$ the cipher is called symmetric cipher, if instead $k \neq = k^{'}$ asymmetric cipher.

A cipher includes therefore an encryption algorithm that, given a key and a plaintext, produces a ciphertext, and a decryption algorithm that, given another key and any ciphertext produced during the encryption, returns the original plaintext. As we'll see, the functions $E$ and $D$ can also coincide.

How Do We Know If a Cipher Is Secure?

Before diving into the different kinds of ciphers, we should understand how to evaluate them, that is, what security requirements the ciphers must meet.

Here's the first thing that might surprise you:

An ideal attacker has complete knowledge of the cryptosystem in use.

This means that the attacker can access the plaintext, ciphertext and key space, and call the functions $E$ and $D$ as many times as he/she wants. Therefore, contrary to what some may think, hiding these elements cannot be considered a security requirement.
We will understand the importance of this assumption later on, and the reason why we can safely make it lies in Kerckhoff's second principle for a good cipher:

A cipher must be secure even if the cryptosystem is known to the enemy.

This means that the only thing that the attacker doesn't know is the specific plaintext the sender is communicating during a particular communication, or the specific keys in use. The main features a cipher can offer are the following (and depending on what you're building, some of these will matter more than others):

Confidentiality: The plaintext cannot be derived from the ciphertext without having the decryption key;
Integrity: The information transmitted cannot be tampered with along the channel;
Authenticity: The identity of the sender is guaranteed to the receiver.

Now that we've covered a high-level overview of ciphers, it's time to dive into how they actually work. We'll start with the most intuitive category: symmetric ciphers.