In cryptography, we often encrypt and sign messages that contain characters. However, asymmetric key cryptosystems (where Alice and Bob use different keys), such as RSA and ElGamal, are based on arithmetic operations on integers. Symmetric key cryptosystems (where Alice and Bob use the same key), such as DES and AES, are based on bitwise operations on bits (a bit is either 0 or 1 and is an abbreviation for binary digit). Therefore, we must convert characters into integers or bits before applying the cryptosystem to the message.
Because a computer can only handle bits, there already exists a method for converting characters into integers or bits, which uses the ASCII (American Standard Code for Information Interchange) table. A part of the ASCII table from Wikipedia is shown in the following table (note that the binary representation on the Wikipedia site uses only seven bits, but we use eight bits by prepending an extra 0):
| Character | Decimal | Hexadecimal | Binary |
|---|---|---|---|
| (space) | 32 | 20 | 00100000 |
| ! | 33 | 21 | 00100001 |
| \( \vdots \) | \( \vdots \) | \( \vdots \) | \( \vdots \) |
| A | 65 | 41 | 01000001 |
| B | 66 | 42 | 01000010 |
| \( \vdots \) | \( \vdots \) | \( \vdots \) | \( \vdots \) |
| a | 97 | 61 | 01100001 |
| b | 98 | 62 | 01100010 |
| \( \vdots \) | \( \vdots \) | \( \vdots \) | \( \vdots \) |
For example, if Alice wants to send the message "Hey Bob!" encrypted to Bob using a symmetric key cryptosystem, she first converts it into its integer representation and then into its binary representation:
\( \eqalign{ H &\rightarrow 72 &&\rightarrow 01001000 \\ e &\rightarrow 101 &&\rightarrow 01100101 \\ y &\rightarrow 121 &&\rightarrow 01111001 \\ &\rightarrow 32 &&\rightarrow 00100000 \\ B &\rightarrow 66 &&\rightarrow 01000010 \\ o &\rightarrow 111 &&\rightarrow 01101111 \\ b &\rightarrow 98 &&\rightarrow 01100010 \\ ! &\rightarrow 33 &&\rightarrow 00100001 } \)
That is, the message "Hey Bob!" is represented with integers as "72 101 121 32 66 111 98 33" and in binary as "01001000 01100101 01111001 00100000 01000010 01101111 01100010 00100001".
The exponent of a number indicates how many times the number is multiplied by itself. For example:
\( 4^{3} = 4 \cdot 4 \cdot 4 = 64 \)
Here, 3 is the exponent (or power), and 4 is the base. In words, we say "4 to the power of 3."
Here are the laws of exponents:
| Law | Example |
|---|---|
| \( x^{1} = x \) | \( 3^{1} = 3 \) |
| \( x^{0} = 1 \) | \( 4^{0} = 1 \) |
| \( x^{-1} = \frac{1}{x} \) | \( 5^{-1} = \frac{1}{5} \) |
| \( x^{m} \cdot x^{n} = x^{m+n} \) | \( x^{2} \cdot x^{3} = (x \cdot x) \cdot (x \cdot x \cdot x) = x \cdot x \cdot x \cdot x \cdot x = x^{5} = x^{2+3} \) |
| \( \frac{x^{m}}{x^{n}} = x^{m-n} \) | \( \frac{x^{4}}{x^{2}} = \frac{x \cdot x \cdot x \cdot x}{x \cdot x} = x \cdot x \cdot \frac{x \cdot x}{x \cdot x} = x \cdot x \cdot 1 = x^{2} = x^{4-2} \) |
| \( (x^{m})^{n} = x^{m \cdot n} \) | \( (x^{2})^{3} = (x \cdot x) \cdot (x \cdot x) \cdot (x \cdot x) = x \cdot x \cdot x \cdot x \cdot x \cdot x = x^{6} = x^{2 \cdot 3} \) |
| \( (x \cdot y)^{n} = x^{n} \cdot y^{n} \) | \( (x \cdot y)^{2} = (x \cdot y) \cdot (x \cdot y) = x \cdot x \cdot y \cdot y = x^{2} \cdot y^{2} \) |
| \( (\frac{x}{y})^{n} = \frac{x^{n}}{y^{n}} \) | \( (\frac{x}{y})^{3} = (\frac{x}{y}) \cdot (\frac{x}{y}) \cdot (\frac{x}{y}) = \frac{x \cdot x \cdot x}{y \cdot y \cdot y} = \frac{x^{3}}{y^{3}} \) |
| \( x^{-n} = \frac{1}{x^{n}} \) | \( x^{-3} = (x^{-1})^{3} = (\frac{1}{x})^{3} = \frac{1}{x} \cdot \frac{1}{x} \cdot \frac{1}{x} = \frac{1 \cdot 1 \cdot 1}{x \cdot x \cdot x} = \frac{1}{x^{3}} \) |
You already use modulo computation when you look at a clock and, for example, need to figure out what time it will be 3 hours after 11 o'clock, which is 2 o'clock. In mathematics, we write this as:
\( (11 + 3) \: mod \: 12 = 2 \)
Here, 12 is the modulus because we want the time as an integer between 0 and 11 (in this case, 12 o'clock is denoted by 0). In words, we say "11 plus 3 modulo 12 equals 2." The result of a modulo computation is an integer between 0 and the modulus minus 1. For example, with modulus 3, we have:
For example, if we look at \( 27 \: mod \: 5 \), modulo computes how many times 5 divides into 27 and then returns the remainder, which is 2 in this case. That is, \( 27 \: mod \: 5 = 2 \). But how do we get this result?
First, we compute how many times we can multiply 5 by an integer \( x \) so that the result is as close as possible to 27 without exceeding it. In other words, we find the maximum value of \( x \) such that \( 5 \cdot x \leq 27 \). In this case, \( x = 5 \) because \( 5 \cdot 5 = 25 \leq 27 \). Then, by subtracting 25 from 27, we get the answer: \( 27 - 25 = 2 \).
If the integer is negative, for example \( -27 \: mod \: 5 \), we have to do it slightly differently, and the answer is \( -27 \: mod \: 5 = 3 \). In this case, the integer \( x \) is negative and should be the closest integer such that \( 5 \cdot x \) does not exceed -27. That is, we find the minimum value of \( -x \) such that \( 5 \cdot -x \geq -27 \). Here, \( -x = -6 \) because \( 5 \cdot -6 = -30 \geq -27 \). Then, by subtracting -30 from -27, we get the answer: \( -27 - (-30) = -27 + 30 = 3 \).
It is important that \( x \) or \( -x \) is an integer such as \( -14, 3, 17 \), etc., and NOT a fraction or decimal such as \( \frac{1}{4}, \frac{-3}{7}, 2.5, 5.1 \), etc.
If two integers \( a \) and \( b \) modulo the same modulus \( c \) return the same remainder \( r \), then we say that \( a \) and \( b \) are congruent modulo \( c \). That is, if \( a \: mod \: c = r \) and \( b \: mod \: c = r \), then \( a \equiv b \: (mod \: c) \). Also, notice that if the modulus \( c \) is greater than the integer \( a \), i.e., \( c > a \), the result will always be \( a \: mod \: c = a \).
A prime number is an integer greater than 1 that can only be divided evenly by 1 and itself. "Divided evenly" means the result is an integer, not a float. For example, if you divide 13 by 3, you get the float \( \frac{13}{3} = 4.333 \). We see that 13 is a prime number because it can only be divided evenly by 1 and itself: \( \frac{13}{1} = 13 \) and \( \frac{13}{13} = 1 \).
If an integer is not a prime number, it is called a composite number. For example, the integer 6 is a composite number because it can be divided evenly by 1, 2, 3, and 6:
\( \frac{6}{1} = 6 \), \( \frac{6}{2} = 3 \), \( \frac{6}{3} = 2 \), and \( \frac{6}{6} = 1 \)
The term "composite" means "something made by combining things." So, a composite number is an integer made by multiplying prime numbers:
Therefore, every integer greater than 1 is either a prime number or a product of prime numbers (a composite number).
The famous Greek mathematician Euclid proved that there are infinitely many prime numbers.
Michael Rabin and Gary Miller developed an algorithm that determines whether an integer is a prime or a composite number by testing the integer with multiple bases, denoted by \( a \). The algorithm is called the Rabin-Miller primality test.
Before we describe what the greatest common divisor of two integers is, we first define what we mean by a divisor. In this context, a divisor of an integer \( x \) is any integer that divides \( x \) evenly, meaning the result is not a fraction. For example, if you divide \( x=12 \) by 5, you get the fraction \( \frac{12}{5} = 2.4 \), so 5 is not a divisor of \( x=12 \). For \( x=12 \), the divisors are 1, 2, 3, 4, 6, and 12 because \( \frac{12}{1} = 12 \), \( \frac{12}{2} = 6 \), \( \frac{12}{3} = 4 \), \( \frac{12}{4} = 3 \), \( \frac{12}{6} = 2 \), and \( \frac{12}{12} = 1 \).
Similarly, the divisors of 16 are 1, 2, 4, 8, and 16 because \( \frac{16}{1} = 16 \), \( \frac{16}{2} = 8 \), \( \frac{16}{4} = 4 \), \( \frac{16}{8} = 2 \), and \( \frac{16}{16}=1 \).
The greatest common divisor of 12 and 16 is therefore 4, because it is the largest integer among their common divisors. In mathematics, we write this as \( \gcd(12, 16) = 4 \).
Two integers whose greatest common divisor is 1 are called relatively prime numbers or co-primes. For example, 15 and 28 are relatively prime because \( \gcd(15, 28) = 1 \) (note that 28 is not a prime number).
If one of the two integers is a prime number, the greatest common divisor will always be 1, i.e., \( \gcd(a, p) = 1 \), where \( a \) is any integer (either prime or composite) and \( p \) is a prime number.
One method to compute the greatest common divisor of two integers is by using the Euclidean algorithm, developed by the famous Greek mathematician Euclid. See "The extended Euclidean algorithm" for more information about how to compute the greatest common divisor of two integers.
The extended Euclidean algorithm is an extension of the Euclidean algorithm, which only returns the greatest common divisor of two integers. Given two integers \( a \) and \( b \), the extended Euclidean algorithm returns the integers \( a \), \( b \), \( \lambda \), and \( \mu \) such that:
\( a \cdot \lambda + b \cdot \mu = \gcd(a, b) \)
Here, \( \lambda \) and \( \mu \) are called the Bézout coefficients for \( a \) and \( b \). Only if \( a \) and \( b \) are relatively prime, i.e., \( \gcd(a, b) = 1 \), then:
\( a \cdot \lambda + b \cdot \mu = 1 \)
In this case, \( \lambda \; mod \; b \) is the inverse of \( a \), denoted \( a^{-1} = \lambda \; mod \; b \), and \( \mu \: mod \: a \) is the inverse of \( b \), denoted \( b^{-1} = \mu \: mod \: a \) (see "Modulo computation" for more information about the \( mod \) operator). One useful property of an integer and its inverse is that \( a \cdot a^{-1} \; mod \; b = 1 \) and \( b \cdot b^{-1} \; mod \; a = 1 \).
You can easily compute \( \gcd(a, b) \), \( \lambda \), and \( \mu \) for example with \( a=5 \) and \( b=39 \) using a simple table. First, let us create a table with three columns (we do not yet know how many rows there will be). Let us denote the entry in the first row and first column as [1,1], the entry in the first row and second column as [1,2], the entry in the second row and first column as [2,1], and so on.
Next, we write \( b=39 \) in entry [1,1] and \( a=5 \) in entry [2,1]. Then we try to find the largest integer \( q_{1} \) such that \( q_{1} \cdot a \leq b \). We have \( q_{1}=7 \), which we write in entry [2,2], because \( 7 \cdot 5 = 35 \leq 39 \), and a remainder of \( r_{1}=4 \), which we write in entry [3,1].
Again, we try to find the largest integer \( q_{2} \) such that \( q_{2} \cdot r_{1} \leq a \). We have \( q_{2}=1 \), which we write in entry [3,2], because \( 1 \cdot 4 = 4 \leq 5 \), and a remainder of \( r_{2}=1 \), which we write in entry [4,1]. Notice that we are repeating the same process as before, just with the numbers in the next row.
The next computation returns a remainder of \( r_{3} = 0 \) because \( q_{3} \cdot r_{2} = 4 \cdot 1 = 4 \leq 4 = r_{1} \). We have now computed \( \gcd(5, 39)=r_{2}=1 \) since \( r_{3} = 0 \). Because 5 and 39 are relatively prime, we know that \( \lambda \) and \( \mu \) exist, and we can start using the last column.
First, we write \( x_{1}=0 \) in entry [4,3] and \( x_{2}=1 \) in entry [3,3]. Then we write \( x_{3}=q_{2} \cdot x_{2} + x_{1} = 1 \cdot 1 + 0 = 1 \) in entry [2,3]. For entry [1,3], we compute as before, just with numbers from the row above, i.e., \( x_{4}=q_{1} \cdot x_{3} + x_{2} = 7 \cdot 1 + 1 = 8 \).
Finally, we have that \( a \cdot x_{4} \pm b \cdot x_{3} = r_{2} \), where we need to decide whether it should be plus or minus between the two terms. Because \( a \cdot x_{4} = 5 \cdot 8 = 40 \), \( b \cdot x_{3} = 39 \cdot 1 \), and \( 40 \geq 39 \), we have \( 5 \cdot 8 - 39 \cdot 1 = 1 \) (which is the same as \( 5 \cdot 8 + 39 \cdot (-1) = 1 \)), so the Bézout coefficients are \( \lambda=8 \) and \( \mu=-1 \). Notice that \( a^{-1} = \lambda \; mod \; b = 8 \; mod \; 39 = 8\) and \( b^{-1} = \mu \; mod \; a = -1 \: mod \: 5 = 4\), where \( a \cdot a^{-1} \; mod \; b = 5 \cdot 8 \; mod \; 39 = 1 \) and \( b \cdot b^{-1} \; mod \; a = 39 \cdot 4 \; mod \; 5 = 1 \).
The table for computing \( 5 \cdot \lambda + 39 \cdot \mu = \gcd(5, 39) \) is:
| \( b=39 \) | \( x_{4}=8 \) | |
| \( a=5 \) | \( q_{1}=7 \) | \( x_{3}=1 \) |
| \( r_{1}=4 \) | \( q_{2}=1 \) | \( x_{2}=1 \) |
| \( r_{2}=1 \) | \( q_{3}=4 \) | \( x_{1}=0 \) |
| \( r_{3}=0 \) |
Lattice-based cryptography represents one of the most promising approaches to creating cryptosystems that remain secure in the post-quantum computing era. While traditional cryptographic systems like RSA and ECC (Elliptic Curve Cryptography) are vulnerable to quantum computer attacks using Shor's algorithm, lattice-based systems are believed to be resistant to both classical and quantum attacks.
A lattice is a mathematical structure consisting of points in n-dimensional space with a periodic structure. Formally, a lattice \( L \) can be defined as all integer linear combinations of a set of linearly independent vectors \( \{b_1, b_2, \ldots, b_n\} \) called a basis:
\( L = \left\{ \sum_{i=1}^{n} z_i b_i : z_i \in \mathbb{Z} \right\} \)
The security of lattice-based cryptography relies on two computationally hard problems:
These problems become exponentially harder as the dimension of the lattice increases, and no efficient quantum algorithm is currently known to solve them. This quantum-resistance is what makes lattice-based cryptography particularly valuable for future-proofing secure communications.
The National Institute of Standards and Technology (NIST) has been conducting a post-quantum cryptography standardization process since 2016, and several lattice-based algorithms have advanced to the final rounds, including CRYSTALS-Kyber for key encapsulation and CRYSTALS-Dilithium for digital signatures.
Lattice-based systems offer several advantages beyond quantum resistance:
The Merkle-Hellman knapsack cryptosystem, which we'll explore in detail below, was one of the earliest attempts at a public-key system based on the knapsack problem, which is related to lattice problems.
The Merkle-Hellman knapsack cryptosystem, proposed by Ralph Merkle and Martin Hellman in 1978, was one of the first attempts at creating a public-key encryption system. It is based on the knapsack problem, a variant of the subset sum problem: given a set of numbers and a sum, find a subset of those numbers that add up to that sum.
While the general knapsack problem is NP-complete (computationally difficult), certain special instances can be solved efficiently. The Merkle-Hellman system cleverly uses a superincreasing sequence (a sequence where each element is greater than the sum of all previous elements) to create an easily solvable private key, which is then transformed into a seemingly hard instance for the public key.
The system works as follows: Alice generates a private key consisting of a superincreasing sequence and then transforms it into a public key that appears to be a random knapsack instance. Bob uses this public key to encrypt messages bit by bit, while Alice can decrypt efficiently using her knowledge of the private key.
Unfortunately, the original Merkle-Hellman system was broken by Shamir in 1984 using lattice reduction techniques. This highlights an important aspect of lattice-based cryptography: while lattice problems are generally hard, specific instances with special structure can sometimes be vulnerable. Despite this, the Merkle-Hellman system remains historically significant as one of the earliest public-key systems not based on number-theoretic assumptions.
Modern lattice-based cryptosystems use more sophisticated approaches and stronger security assumptions to avoid the vulnerabilities that affected Merkle-Hellman.
| Key Generation | |
|
Alice:
Generates a superincreasing sequence \( w = (w_1, w_2, ..., w_n) \) where each \( w_i > \sum_{j=1}^{i-1} w_j \) Chooses a large modulus \( m > \sum_{i=1}^{n} w_i \) and a multiplier \( r \) where \( \gcd(r, m) = 1 \) Computes \( b_i = r \cdot w_i \mod m \) for each element in the sequence The public key is the sequence \( b = (b_1, b_2, ..., b_n) \) The private key is \( (w, m, r) \) |
|
| Alice sends the public key \( b = (b_1, b_2, ..., b_n) \) to Bob. | |
| Encryption | |
| Bob Converts plaintext message to binary: \( x = (x_1, x_2, ..., x_n) \) where each \( x_i \) is 0 or 1 Computes ciphertext \( c = \sum_{i=1}^{n} x_i \cdot b_i \) Sends ciphertext \( c \) to Alice | |
| Decryption | |
| Alice Computes \( c' = c \cdot r^{-1} \mod m \) where \( r^{-1} \) is the modular inverse of \( r \) Solves the easy superincreasing knapsack problem to recover \( x \) from \( c' \) The binary sequence \( x \) is the plaintext message | |
Let's walk through a complete example of the Merkle-Hellman knapsack cryptosystem:
Key Generation:
Alice generates a superincreasing sequence \( w = (2, 3, 7, 14, 30, 57, 120, 251) \). We can verify this is superincreasing because each element is greater than the sum of all previous elements.
She chooses modulus \( m = 491 \) (which is larger than the sum of all elements in \( w \), which is 484) and multiplier \( r = 41 \) (which is coprime with 491).
She computes the public key \( b \) as follows:
\( b_1 = 41 \cdot 2 \mod 491 = 82 \)
\( b_2 = 41 \cdot 3 \mod 491 = 123 \)
\( b_3 = 41 \cdot 7 \mod 491 = 287 \)
\( b_4 = 41 \cdot 14 \mod 491 = 83 \)
\( b_5 = 41 \cdot 30 \mod 491 = 239 \)
\( b_6 = 41 \cdot 57 \mod 491 = 352 \)
\( b_7 = 41 \cdot 120 \mod 491 = 410 \)
\( b_8 = 41 \cdot 251 \mod 491 = 127 \)
So the public key is \( b = (82, 123, 287, 83, 239, 352, 410, 127) \).
Encryption:
Bob wants to encrypt the message "Hi" which in ASCII is 72 and 105, or in binary: 01001000 01101001.
Taking the first 8 bits (01001000), Bob computes:
\( c_1 = 0 \cdot 82 + 1 \cdot 123 + 0 \cdot 287 + 0 \cdot 83 + 1 \cdot 239 + 0 \cdot 352 + 0 \cdot 410 + 0 \cdot 127 = 362 \)
For the second 8 bits (01101001), Bob computes:
\( c_2 = 0 \cdot 82 + 1 \cdot 123 + 1 \cdot 287 + 0 \cdot 83 + 1 \cdot 239 + 0 \cdot 352 + 0 \cdot 410 + 1 \cdot 127 = 776 \)
Bob sends the ciphertext \( (362, 776) \) to Alice.
Decryption:
Alice first computes the modular inverse of 41 modulo 491, which is 12 (since \( 41 \cdot 12 \mod 491 = 1 \)).
For the first block:
\( c_1' = 362 \cdot 12 \mod 491 = 244 \)
Now Alice solves the superincreasing knapsack problem with the sum 244:
251 > 244, so \( x_8 = 0 \)
120 > 244, so \( x_7 = 0 \)
120 + 57 = 177 < 244, so \( x_6 = 1 \) and remaining sum = 244 - 57 = 187
120 + 30 = 150 < 187, so \( x_5 = 1 \) and remaining sum = 187 - 30 = 157
120 + 14 = 134 < 157, so \( x_4 = 0 \)
120 + 7 = 127 < 157, so \( x_3 = 0 \)
120 + 3 = 123 < 157, so \( x_2 = 1 \) and remaining sum = 157 - 3 = 154
120 + 2 = 122 < 154, so \( x_1 = 0 \)
So the first byte is 01001000.
Alice repeats this process for the second block \( c_2 \) to get 01101001.
Converting from binary to ASCII, Alice recovers "Hi".
Note: This example uses small numbers for clarity. In practice, much larger values would be used to ensure security, though as mentioned earlier, even with large numbers the original Merkle-Hellman system has been broken.