Pollard’s p-1 factorization algorithm

Posted on January 15, 2023 by Dan Ma

Pollard’s p-1 factorization algorithm was invented by John Pollard in 1974. This factoring algorithm is based on Fermat Little Theorem. This algorithm is promising for factoring the composite number $n$ with a prime divisor $p$ such that $p-1$ has small prime factors. As a result, for any cryptosystem whose security is based on the hardness of the problem of factoring (e.g., RSA), it is critical that $p-1$ has at least one large prime factor.

The Ideas of Pollard’s p-1 Method

Let $p$ is a prime. According to Fermat Little Theorem, $a^{p-1} \equiv 1$ modulo $p$ whenever $a$ is an integer relatively prime to $p$ . Furthermore, if $a^M \equiv 1$ modulo $p$ , then $p-1$ divides $M$ . These two facts form the basis for Pollard’s p-1 method.

Let $N=p \times q$ where $p$ and $q$ are two distinct prime numbers. First, we describe the overall strategy of Pollard’s p-1 factorization algorithm. The goal is to find a number $M$ such that $p-1$ divides $M$ but $q-1$ does not divide $M$ . Suppose such a number $M$ is found. Then for some random number $a$ , we have $a^M \equiv 1 \ \text{mod} \ p$ since Fermat Little Theorem tells us that $a^{p-1} \equiv 1 \ \text{mod} \ p$ . On the other hand, $a^M \not \equiv 1 \ \text{mod} \ q$ . Otherwise, we would have $q-1$ divides $M$ . The fact $a^M \not \equiv 1 \ \text{mod} \ q$ implies that $a^M \not \equiv 1 \ \text{mod} \ N$ .

With $a^M \equiv 1 \ \text{mod} \ p$ , we know that the prime $p$ divides $a^M-1$ . We also know that $p$ divides $N$ . Furthermore, we know that $N$ does not divide $a^M-1$ . Thus $p$ is the greatest common divisor of $a^M-1$ and $N$ , denoted by $p=\text{GCD}(a^M-1,N)$ . Assuming that we can find $M$ , taking the GCD of $a^M-1$ and $N$ would yield the prime factor $p$ of $N$ .

The idea sounds wonderful. How do we find such a number $M$ . Note that The number $M$ captures $p-1$ in that $p-1$ divides $M$ or $M=(p-1) \times k$ for some number $k$ . We can find $M$ iteratively. Choose a random number $a$ with $1 < a < n$ . Start with $n!$ for a relatively small $n$ . Compute $a^{n!} \ \text{mod} \ N$ . Compute the GCD of the numbers $a^{n!}-1$ and $N$ , denoted by $\text{GCD}(a^{n!}-1,N)$ . If $\text{GCD}(a^{n!}-1,N)>1$ , then the GCD is a prime factor of $N$ . If the GCD is 1, then we compute $a^{(n+1)!} \ \text{mod} \ N$ and then compute $\text{GCD}(a^{(n+1)!}-1,N)$ and so on. One possibility o speeding up the calculation is that instead of incrementing the factorial by 1, we can increase it by a pre-determined value $k$ . That is, instead of using $(n+1)!$ , we can use $(n+k)!$ in the next step.

Some comments about the calculation. We do not have to derive the exact values of $n!$ except for the first one. To start, we can compute the exact value of $n!$ to compute $a^{n!} \ \text{mod} \ N$ . If we need to evaluate $a^{(n+1)!}$ , we simply perform the exponentiation $(a^{n!})^{n+1} \ \text{mod} \ N$ . Furthermore, the exponentiation $a^{n!}$ does not have to be the exact value. It can be evaluated modulo $N$ . We can choose a random number $a$ to work as the base. In practice, we can use 2. Examples are given in the next section to illustrate the algorithm.

Examples

Example 1
Use Pollard’s p-1 method to factor the integer $N$ = 1,048,561. This is a semiprime, meaning that it is a product of two prime factors.

We use $10!$ to start. We have $10!$ = 3,628,800 and $\text{GCD}(2^{10!}-1,N)=1$ . Then we continue the calculation with larger factorials. We have the following results.

$\displaystyle 2^{10!} \equiv 225138 \ \text{mod} \ N$ …………… $\text{GCD}(2^{10!}-1,N)=1$
$\displaystyle 2^{11!} \equiv 660641 \ \text{mod} \ N$ …………… $\text{GCD}(2^{11!}-1,N)=1$
$\displaystyle 2^{12!} \equiv 1024940 \ \text{mod} \ N$ ………….. $\text{GCD}(2^{12!}-1,N)=1$
$\displaystyle 2^{13!} \equiv 69237 \ \text{mod} \ N$ …………….. $\text{GCD}(2^{13!}-1,N)=911$

Thus, 911 is one of the prime factors of $N$ = 1,048,561. Then the prime factorization is $N$ = 911 x 1151. To see why we only need to go up to $13!$ in the calculation, with $p$ = 911 and $q$ = 1151, we have $p-1$ = 2 x 5 x 7 x 13 and $q-1$ = 2 x 25 x 23. The largest prime factor of $p-1$ is 13 and the largest prime factor of $q-1$ is 23. Furthermore, $p-1$ divides $13!$ and $q-1$ does not divide $13!$ . Thus, $13!$ is the desired $M$ described above. $\square$

Example 2
Use Pollard’s p-1 algorithm to factor the number $N$ = 120,035,047,163, which is a product of two prime numbers.

We use the starting point $11!$ = 39,916,800. With the GCDs being 1 for quite a few higher factorials, we only show the calculation leading to the last step.

$\displaystyle 2^{11!} \equiv 104220222835 \ \text{mod} \ N$ …………… $\text{GCD}(2^{11!}-1,N)=1$

$\displaystyle 2^{30!} \equiv 115085159489 \ \text{mod} \ N$ …………… $\text{GCD}(2^{30!}-1,N)=1$
$\displaystyle 2^{31!} \equiv 70238389359 \ \text{mod} \ N$ …………….. $\text{GCD}(2^{31!}-1,N)=1$
$\displaystyle 2^{32!} \equiv 26731042480 \ \text{mod} \ N$ …………….. $\text{GCD}(2^{32!}-1,N)=1$
$\displaystyle 2^{33!} \equiv 50408736108 \ \text{mod} \ N$ …………….. $\text{GCD}(2^{33!}-1,N)=1$
$\displaystyle 2^{34!} \equiv 117848667792 \ \text{mod} \ N$ …………… $\text{GCD}(2^{34!}-1,N)=1$
$\displaystyle 2^{35!} \equiv 71394351228 \ \text{mod} \ N$ …………….. $\text{GCD}(2^{35!}-1,N)=1$
$\displaystyle 2^{36!} \equiv 87224960905 \ \text{mod} \ N$ …………….. $\text{GCD}(2^{36!}-1,N)=1$
$\displaystyle 2^{37!} \equiv 1891194340 \ \text{mod} \ N$ ………………. $\text{GCD}(2^{37!}-1,N)=1$
$\displaystyle 2^{38!} \equiv 94274356142 \ \text{mod} \ N$ …………….. $\text{GCD}(2^{38!}-1,N)=1299601$

Thus, the factorization of $N$ is 1,299,601 x 92,363. With $p$ = 1,299,601 and $q$ = 92,363, let’s look at the factors of $p-1$ and $q-1$ .

$p-1=2^4 \times 3^2 \times 5^2 \times 19^2$

$q-1=2 \times 46181$

Now we know that $p-1$ is made up of small primes with the largest being 19 while $q-1$ has a large prime factor (relatively speaking). Note that $p-1$ does not divide $19!$ since 19 has exponent 2 in the factorization of $p-1$ . This lengthens the calculation to $38!$ . Thus, with $M=38!$ , we know that $p-1$ divides $M$ and that $q-1$ does not divide $M$ . As a result, Pollard’s p-1 calculation ends at $38!$ . $\square$

Example 3
Factor the number $N$ = 30,069,476,293, which is a product of two prime factors.

The preceding two examples show that the Pollard p-1 calculation usually needs to go up to the factorial corresponding to the largest prime factor of $p-1$ (or $q-1$ ). In this example, we show that the choice of the base $a$ also matters, though it is not a choice we can make at the outset. We use $15!$ to start and make the following calculation.

$\displaystyle 2^{15!} \equiv 2640468470 \ \text{mod} \ N$ …………….. $\text{GCD}(2^{15!}-1,N)=1$
$\displaystyle 2^{16!} \equiv 11548010587 \ \text{mod} \ N$ …………… $\text{GCD}(2^{16!}-1,N)=1$
$\displaystyle 2^{17!} \equiv 17457718327 \ \text{mod} \ N$ …………… $\text{GCD}(2^{17!}-1,N)=1$
$\displaystyle 2^{18!} \equiv 28780043158 \ \text{mod} \ N$ …………… $\text{GCD}(2^{18!}-1,N)=1$
$\displaystyle 2^{19!} \equiv 19852010325 \ \text{mod} \ N$ …………… $\text{GCD}(2^{19!}-1,N)=104729$

With the above calculation, we have $N$ = 104,729 x 287,117. With $p$ = 104,729 and $q$ = 287,117, we examine the factorizations of $p-1$ and $q-1$ .

$p-1=2^3 \times 13 \times 19 \times 53$

$q-1=2^2 \times 179 \times 401$

With the largest prime factor of $p-1$ being 53, why do we not have to calculate all the way to $53!$ ? The answer is that the base 2 in this example is a good choice for a base. The order of 2 modulo $p$ is 1976, much smaller than $p-1$ = 104,729. In this case, the base 2 is not a primitive root modulo $p$ . If we use a base $a$ that is a primitive root modulo $p$ , then the calculation would extend all the way to $53!$ . Since we do not know the value of $p$ before the calculation, choosing a good base is not something we can do. Thus, there is an element of luck in the Pollard p-1 method.

We now analyze this situation further by showing how the number 1976 is determined. To determine whether the number 2 is a primitive root modulo $p$ = 104,729, we need to evaluate the exponentiation $2^{\frac{p-1}{t}}$ modulo $p$ for all prime factors $t$ of $p-1$ .

. $\displaystyle \frac{p-1}{2}=52364$ ………….. $2^{52364} \equiv 1 \ \text{mod} \ p$
. $\displaystyle \frac{p-1}{13}=8056$ ……………. $2^{8056} \equiv 2522 \ \text{mod} \ p$
. $\displaystyle \frac{p-1}{19}=5512$ ……………. $2^{5512} \equiv 48162 \ \text{mod} \ p$
. $\displaystyle \frac{p-1}{53}=1976$ ……………. $2^{1976} \equiv 1 \ \text{mod} \ p$

If the number 2 were to be a primitive root, the results on the right side of the above calculation should be all not congruent to 1. In this case, the smallest exponent of 2 is 1976, which is the order of 2 modulo $p$ . In the above explanation of Pollard’s p-1 method, we say that we need to find $M$ such that $p-1$ divides $M$ but $q-1$ does not divide $M$ . Note that $p-1$ is this case is 104,828. In this example, we do not need to go this high, we just need to find $M$ such that 1976 divides $M$ . Our calculation shows that $M$ can be $19!$ . Again, this is an element of luck. This analysis can only be performed after the fact.

For comparison, let’s use a primitive root as the base. The number 12 is a primitive root modulo $p$ . We start with $19!$ and find that the GCD is 1. Based on the analysis in the preceding paragraph, we know the calculation likely needs to go up to $53!$ . So we skip from $19!$ to $52!$ .

$\displaystyle 12^{19!} \equiv 14031100377 \ \text{mod} \ N$ …………… $\text{GCD}(12^{19!}-1,N)=1$

$\displaystyle 12^{52!} \equiv 29099088982 \ \text{mod} \ N$ …………… $\text{GCD}(12^{52!}-1,N)=1$
$\displaystyle 12^{53!} \equiv 10843640661 \ \text{mod} \ N$ …………… $\text{GCD}(12^{53!}-1,N)=104729$

The last calculation shows that if we happen to use a primitive root (modulo one prime factor $p$ of $N$ ) as the base, the calculation may take longer. Ideally, we would like to use a base that has small order. Of course, this is not a choice we can make ahead of time. $\square$

Example 4
In this example, we use Pollard’s p-1 method to factor $N$ = 21,428,053, which is a product of two prime numbers.

We start with $30!$ and compute $2^{30!}$ modulo $N$ . The GCD values of $\text{GCD}(2^{n!}-1,N)$ are all 1’s even after a long series of calculation. Thus, we only show that selected steps to give a sense of the amount of effort.

$\displaystyle 2^{30!} \equiv 16728337 \ \text{mod} \ N$ ……………. $\text{GCD}(2^{30!}-1,N)=1$

$\displaystyle 2^{100!} \equiv 8115587 \ \text{mod} \ N$ …………….. $\text{GCD}(2^{100!}-1,N)=1$

…………..

$\displaystyle 2^{150!} \equiv 18994160 \ \text{mod} \ N$ …………… $\text{GCD}(2^{150!}-1,N)=1$

…………..

$\displaystyle 2^{200!} \equiv 57349 \ \text{mod} \ N$ ……………….. $\text{GCD}(2^{200!}-1,N)=1$

…………..

$\displaystyle 2^{250!} \equiv 11825174 \ \text{mod} \ N$ …………… $\text{GCD}(2^{250!}-1,N)=1$

…………..

$\displaystyle 2^{260!} \equiv 5105076 \ \text{mod} \ N$ …………….. $\text{GCD}(2^{260!}-1,N)=1$
$\displaystyle 2^{261!} \equiv 18320624 \ \text{mod} \ N$ …………… $\text{GCD}(2^{261!}-1,N)=1$
$\displaystyle 2^{262!} \equiv 16958949 \ \text{mod} \ N$ …………… $\text{GCD}(2^{262!}-1,N)=1$
$\displaystyle 2^{263!} \equiv 15751435 \ \text{mod} \ N$ …………… $\text{GCD}(2^{263!}-1,N)=5261$

The calculation shows that $N$ = 4073 x 5261. Now that we have the answer, we can analyze the process. Here’s the factorization of $p-1$ and $q-1$ where $p$ = 5261 and $q$ = 4073.

$p-1=2^2 \times 5 \times 263$

$q-1=2^3 \times 509$

The largest prime factor of $p$ is 263. The largest prime factor of $q$ is 509. This indicates that the calculation would involve $263!$ . The base 2 is a primitive root modulo 5261, ensuring that the calculation would need to go to $263!$ . Note that the composite $N$ in this example is much smaller than the ones in Example 2 and Example 3. Yet this example requires a lot more effort because $p-1$ (or $q-1$ ) has larger prime factors. This example reinforces the point that Pollard’s p-1 algorithm excels in factoring $N$ where $p$ is one of the prime factors of $N$ and $p-1$ has small prime factors. The smaller the prime factors of $p-1$ , the lower the amount of calculation. $\square$

Fermat Numbers

The composite numbers $N$ in the four examples in the preceding section are only illustrations for Pollard’s p-1 factorization algorithm. The numbers in these examples are small enough so that the trial division, when programmed in a computer, is workable as a factorization algorithm. In this section, we mention two examples of factorization that are in much larger scale than the above examples. Both examples involves the 12th Fermat number.

A Fermat number is a positive integer of the form $F_n=2^{2^n}+1$ where $n$ is a non-negative integer. Due to their large sizes, Fermat numbers are difficult to factor or to check for primality. Pepin’s test is a primality test for Fermat numbers (see here). According to the Wikipedia entry on Fermat numbers (see here), only the Fermat numbers $F_0$ to $F_{11}$ have been completely factored as of November 2021. Currently, six factors of $F_{12}$ have been discovered so far (see here).

Edouard Lucas in 1878 proved that every factor of the Fermat number $F_n$ , $n \ge 2$ , is of the form $k \times 2^{n+2}+1$ . A number of this form is called a Proth number. One prime factor of $F_{12}$ was discovered by R. Baillie in July 25, 1986, which is a 16-digit number. The following is the 16-digit prime factor $p$ along with the factorization of $p-1$ .

$p=76668221077 \times 2^{14}+1=1256132134125569$

$p-1=2^{14} \times 7^2 \times 53 \times 29521841$

Note that the largest prime factor of $p-1$ is 29,521,841, which is small enough relatively speaking. As a result, Pollard’s p-1 method was used in this case.

A 54-digit prime factor of $F_{12}$ was discovered by M. Vang, Zimmermann & Kruppa in March 27, 2010. It is expressed as $p=m \times 2^{15}+1$ where $m$ is a 50-digit prime number. Thus, the largest prime factor of $p-1$ is the 50-digit prime number $m$ . This prime factor was discovered using the Elliptic Curve Method (ECM) and could bot have been discovered using Pollard’s p-1 method. This example reinforces the idea that for Pollard’s p-1 method to work, $p-1$ needs to be made up of “small” prime factors for one prime factor $p$ .

Remarks

One point worth mentioning is that when we obtain a new factor using Pollard’s p-1 method, we need to check its primality, e.g., using a primality test such as the Miller-Rabin test. The numbers $N$ in the four examples given above are stated as a product of two primes. As a result, any factor that results can be assumed a prime. When the factoring effort has no known facts given, we cannot just assume any factor produced is a prime number.

The four examples above are structured in a way that each $N$ is a product of two primes (i.e., they are semiprimes). Pollard’s p-1 method can certainly be used for factoring numbers that have more than two prime factors. Just that each resulting factor should be further factored if it turns out to be not a prime.

Pollard’s p-1 algorithm has elements of luck involved. For example, if we happen to use a starting point for $n!$ that is not far from the factorial that produces a prime factor, the algorithm works spectacularly well. On the other hand, if we happen to use a base $a$ that has a lower order modulo one of the prime factors, the calculation may stop as a lower value of $n!$ . Of course, the amount of calculation depends on the magnitude of the prime factors of $p-1$ . If the largest prime factor of $p-1$ is a 50-digit number as for one prime factor of the Fermat number $F_{12}$ as indicated in the preceding section, Pollard’s p-1 method should not be considered. On the other hand, another factor of the Fermat number $F_{12}$ was obtainable using Pollard’s p-1 because the largest prime factor of $p-1$ is only an 8-digit number. When doing exercise problems on factoring using Pollard’s p-1 method, the amount of effort varies. The $n!$ that produces a factor may be in the range of 10s or 100s or even 1000s for $n$ . The decision of how high of a factorial we are willing to go is based on how much effort we wish to expend or whether the computational resources at our disposal are up to the challenge.

The study of factoring adds to our understanding of cryptosystems whose security relies on the apparent difficulty of factoring large numbers. For example, with insight obtained from knowing Pollard’s p-1 method, when setting the modulus $N=p \times q$ for RSA, we can improve the security by choosing $p$ and $q$ such that $p-1$ and $q-1$ have at least one large prime factor. When the primes $p$ and $q$ are large, the resulting RSA public key may seem secure. If $p-1$ and $q-1$ have small prime factors, it is a vulnerability Pollard’s p-1 factoring method can exploit.

$\text{ }$

Dan Ma Pollard’s p-1 factoring algorithm

Dan Ma Pollard’s p-1 factoring method

Daniel Ma Pollard’s p-1 factoring algorithm

Daniel Ma Pollard’s p-1 factoring method

$\copyright$ 2023 – Dan Ma

The Goldwasser-Micali Cryptosystem

Posted on January 9, 2023 by Dan Ma

This is a discussion on how the Goldwasser-Micali cryptosystem can be used to send one bit of data securely. The Goldwasser-Micali cryptosystem is a public-key encryption algorithm developed by Shafi Goldwasser and Silvio Micali in 1982. It has the distinction of being the first probabilistic public-key encryption scheme. It also possesses a partial homomorphic capability, which is discussed and illustrated below.

Alice wishes to send Bob one bit of data, i.e., Alice wishes to send Bob the value of 0 or 1 using a public key cryptosystem. If the algorithm is deterministic in nature, there is a serious security issue with this exchange, i.e., Eve the eavesdropper can find out what the message is by encrypting both 0 and 1 and then comparing to what is sent by Alice to Bob. In fact, this problem exists for any cryptosystem that generates only a small set of possible plaintexts. All Eve has to do is to encrypt every possible plaintext using the public key from Bob and then try to find a match with the message being sent. Thus, a probabilistic encryption is called for so that the bit that is sent will appear random. We focus on one such algorithm called the Goldwasser-Micali cryptosystem.

The Goldwasser-Micali Cryptosystem

The major components of the Goldwasser-Micali cryptosystem are described below. In this presentation, Bob is the publisher of the public key and Alice is the party that encrypts the message to be sent to Bob using Bob’s public key. Bob is the party that has the knowledge of the private key allowing him to decrypt the message from Alice. Of course, Eve the eavesdropper can see all the information exchanged via an insecure channel but does not know the private key held by Bob.

Public Key
Bob chooses two large primes $p$ and $q$ . Let $N=p \times q$ . Bob also chooses a number $a$ such that the Legendre symbols $(\frac{a}{p})=(\frac{a}{q})=-1$ . The public key consists of the numbers $N$ and $a$ , which Alice can use to send one-bit to Bob. The public key is also available for Eve the eavesdropper to see.

Private Key
The private key consists of the two large primes $p$ and $q$ whose product is $N$ . Bob is to keep the knowledge of $p$ and $q$ secret.

Encryption
The message to be sent by Alice is either $m$ = 0 or $m$ = 1. Before the encryption, Alice chooses a random number $r$ such that $1<r <N$ . Using Bob’s public key, Alice calculates the ciphertext $c$ by using the following encryption scheme.

$\displaystyle c \equiv \left\{ \begin{array}{rl} r^2 \ \text{mod} \ N &\ \text{if } m = 0\\ a \cdot r^2 \ \text{mod} \ N &\ \text{if } m = 1 \end{array} \right.$

The ciphertext $c$ is sent to Bob by Alice.

Decryption
Once Bob receives the ciphertext $c$ , he computes the Legendre symbol $(\frac{c}{p})$ . The plaintext is recovered according to the following scheme.

$\displaystyle m = \left\{ \begin{array}{rl} 0 &\ \text{if } \displaystyle \biggl(\frac{c}{p} \biggr) = 1\\ 1 &\ \text{if } \displaystyle \biggl(\frac{c}{p} \biggr) = -1 \end{array} \right.$

More on Goldwasser-Micali

Recall that $N=p \times q$ and with $p$ and $q$ unknown except to Bob. Bob is in a position to make use of this private information to determine whether the received ciphertext $c$ is a quadratic residue. Note that a number $a$ is a quadratic residue modulo $N$ if and only if $a$ is a quadratic residue modulo $p$ and $a$ is a quadratic residue modulo $q$ . Once Bob receives the ciphertext $c$ , he can check whether $c$ is a quadratic residue modulo $p$ and then modulo $q$ . If $c$ is a quadratic residue modulo both $p$ and $q$ , then $c$ is square modulo $N$ and the plaintext is 0. If the ciphertext $c$ is a quadratic nonresidue modulo one of $p$ and $q$ , then the plaintext is a 1. However, the decryption can be carried out according to scheme in the preceding section. The following shows why the decryption scheme works.

$\displaystyle \biggl(\frac{c}{p} \biggr) = \left\{ \begin{array}{ll} \displaystyle \biggl(\frac{r^2}{p} \biggr)=\biggl(\frac{r}{p} \biggr)^2=1 &\ \text{if } m = 0\\ \displaystyle \biggl(\frac{a r^2}{p} \biggr)=\biggl(\frac{a}{p} \biggr) \times \biggl(\frac{r}{p} \biggr)^2=-1 &\ \text{if } \displaystyle m = 1 \end{array} \right.$

Thus, all Bob has to do to recover the plaintext $m$ from the ciphertext $c$ is to evaluate a Legendre symbol, which is an efficient algorithm. This is possible for Bob to do since he possesses the private key, which is the prime factorization of the modulus $N$ .

During the entire exchange, Eve the eavesdropper can see the numbers $N$ , $a$ (the public key) and the ciphertext $c$ . When the plaintext is $m$ = 0, the ciphertext $c$ is a quadratic residue modulo $N$ , i.e., $c$ is a square. When the plaintext is $m$ = 1, the ciphertext $c$ is a quadratic nonresidue modulo $N$ . If Eve can determine whether the ciphertext $c$ is a quadratic residue modulo $N$ , she would know the plaintext $m$ . This is precisely solving the quadratic residuosity problem (discussed here). At the root, the security of the Goldwasser-Micali cryptosystem is based the assumption that it is hard to determine of a number is a square modulo $N$ if the two prime factors of $N$ are unknown.

Note the difference between Bob and Eve. Bob uncovers the plaintext using the private key that he possesses. For Eve to obtain the plaintext, one possible way is to solve the quadratic residuosity problem. Of course, if she can factor the modulus $N$ , she can obtain the single bit $m$ that was transmitted.

Because the modulus $N$ is composite, evaluating the Jacobi symbol $(\frac{c}{N})$ would not reveal the information on the plaintext. This is because the symbol $(\frac{c}{N})$ will always be 1 regardless the the value of the ciphertext, as shown below.

$\displaystyle \biggl(\frac{c}{N} \biggr) = \left\{ \begin{array}{ll} \displaystyle \biggl(\frac{r^2}{N} \biggr)=\biggl(\frac{r}{N} \biggr)^2=1 &\ \text{if } m = 0\\ \displaystyle \biggl(\frac{a r^2}{N} \biggr)=\biggl(\frac{a}{N} \biggr) = \biggl(\frac{a}{p} \biggr) \times \biggl(\frac{a}{q} \biggr)=1 &\ \text{if } \displaystyle m = 1 \end{array} \right.$

Examples

Example 1
The public key is $N$ = 80,549,389 and $a$ = 34,382,465. Let’s go through each step in the Goldwasser-Micali process for Alice and Bob.

Alice chooses a message to be sent. For the purpose of this example, we can encrypt both $m$ = 0 or $m$ = 1 for illustration. Alice chooses the random number $r$ = 70,254,916. The following calculates the encryption.

$\displaystyle c \equiv \left\{ \begin{array}{ll} 70254916^2 \equiv 1370266 \ \text{mod} \ N &\ \text{if } m = 0\\ 34382465 \cdot 70254916^2 \equiv 26807757 \ \text{mod} \ N &\ \text{if } m = 1 \end{array} \right.$

Thus, if the plaintext is $m$ = 0, the ciphertext is $c$ = 1,370,266 and if the plaintext is $m$ = 1, the ciphertext is $c$ = 26,807,757.

Once Bob receives the ciphertext from Alice, he uses his knowledge of the secret key to decrypt. The secret key is the pair $p$ = 8147 and $q$ = 9887. He then computes the following Legendre symbols depending on the received ciphertext.

$\displaystyle \biggl(\frac{c}{p} \biggr) = \biggl(\frac{1370266}{8147} \biggr)=1$

$\displaystyle \biggl(\frac{c}{p} \biggr) = \biggl(\frac{26807757}{8147} \biggr)=-1$

If the value of the symbol is 1, Bob would know the one-bit plaintext is 0 and if the value of the symbol is -1, the plaintext is 1.

For Eve, without knowing $p$ and $q$ , she would need to solve one of the following equations (depending on the ciphertext) if she wants to uncover the plaintext.

$x^2 \equiv 1370266 \ \text{mod} \ 80549389$

$x^2 \equiv 26807757 \ \text{mod} \ 80549389$

Solving these equations is precisely the quadratic residuosity problem (discussed here). Note that evaluating the Jacobi symbol $(\frac{c}{N})$ would not help. The following Jacobi symbols are evaluated here. Both are shown to be 1.

$\displaystyle \biggl(\frac{c}{N}\biggr)=\biggl(\frac{1370266}{80549389}\biggr)=1$

$\displaystyle \biggl(\frac{c}{N}\biggr)=\biggl(\frac{26807757}{80549389}\biggr)=1$

Homomorphic Properties

The Goldwasser-Micali cryptosystem has the property that we can perform a mathematical operation on the encrypted data such that the results would be the same as the encrypted results that would be produced from encrypting the results of performing the same operation on the corresponding plaintexts. This property is called the homomorphic property and the mathematical operation in this instance is the Boolean logic operation called eXclusive OR (XOR), which is widely used in cryptography and other settings.

The operation XOR takes two input bits and produces one output bit in the following manner. If the bits are the same, the result is 0. If the two bits are different, the result is 1. More specifically, $0 \bigoplus 0=0$ , $0 \bigoplus 1=1$ , $1 \bigoplus 0=1$ , and $1 \bigoplus 1=0$ .

In general, a homomorphic encryption algorithm refers to an encryption algorithm that allows certain mathematical operations such as addition and multiplication to be performed on ciphertexts so that the results are the same as the ciphertexts that would be produced from encrypting the results of performing the same operations on the corresponding plaintexts.

For the Goldwasser-Micali encryption algorithm, the homomorphic property is limited to the XOR logical operation. So, the algorithm is an example of a partial homomorphic encryption algorithm. It is a partial homomorphic encryption algorithm in this sense: If $c_1$ and $c_2$ are ciphertexts corresponding to the two bits $m_1$ and $m_2$ , respectively, then $c_1 \cdot c_2$ modulo $N$ will be the ciphertext for the bit $m_1 \bigoplus m_2$ . Here, the operation $\bigoplus$ is the Boolean logic operation XOR described above. Thus, multiplying two ciphertexts produces the same result as encrypting the XOR of the corresponding two plaintext bits.

Homomorphic encryption algorithm has huge consequence for many business enterprises. The ability to perform computation on encrypted data means data processing can be outsourced to a third party vendor. If the third party vendor has the homomorphic capability, there will be no need to trust the third party vendor to properly secure the data. The third party vendor can then perform computation on the encrypted data without the need of the secret key, and thus privacy is not compromised. We now give examples to demonstrate the homomorphic encryption in the Goldwasser-Micali algorithm.

For the following two examples, $N=p \times q$ where $p$ = 5309 and $q$ = 7639. Then $N$ = 40,555,451. The number $a$ = 25,841,451. The pair of numbers $N$ and $a$ represents Bob’s public key.

Example 2
In this example, Alice wishes to send Bob a bit of $m_1$ = 0. She chooses the random number $r$ = 19,873,118. The ciphertext is then $c_1 \equiv r^2 \equiv 35,567,683$ modulo $N$ .

Subsequently, Alice sends another bit $m_2$ = 1 to Bob. This time she uses the random number $r$ = 35,378,670. The ciphertext is then $c_2 \equiv a \cdot r^2 \equiv 33955554$ modulo $N$ .

The product of the two ciphertext is $c_1 \cdot c_2 \equiv 35,567,683 \cdot 33955554 \equiv 17149549$ modulo $N$ . If Bob were to decrypt the result $c_1 \cdot c_2$ , he would evaluate the Legendre symbol using Euler’s criterion as follows:

$\displaystyle \biggl( \frac{17149549}{5309} \biggr)=17149549^{\frac{5309-1}{2}} \equiv -1 \ \text{mod} \ 5309$

The Legendre symbol is -1. Thus the ciphertext $c_1 \cdot c_2$ corresponds to a plaintext bit of 1, which is $m_1 \bigoplus m_2=0 \bigoplus 1=1$ . Thus, multiplying the two ciphertexts gives the same ciphertext that would correspond to a ciphertext produced from encrypting $m_1 \bigoplus m_2=0 \bigoplus 1=1$ . $\square$

Example 3
In this example, Alice is to send two separate bits of 1, say, $m_3$ = 1 and $m_4$ = 1. The ciphertext for $m_3$ is denoted by $c_3$ . The ciphertext for $m_4$ is denoted by $c_4$ . We have $m_3 \bigoplus m_4=0$ . Thus, when we multiply the two individual ciphertexts $c_3$ and $c_4$ , the resulting ciphertext should correspond to a bit of 0. For $c_3$ , Alice uses the random $r$ = 27,288,758. For $c_4$ , Alice uses the random $r$ = 15,416,582. Here’s the calculation.

$\displaystyle c_3 \equiv a \cdot 27288758^2 \equiv 589148 \ \text{mod} \ N$

$\displaystyle c_4 \equiv a \cdot 15416582^2 \equiv 7848893 \ \text{mod} \ N$

$\displaystyle c_3 \cdot c_4 \equiv 589148 \cdot 7848893 \equiv 27090144 \ \text{mod} \ N$

Let’s decrypt the ciphertext $c_3 \cdot c_4$ , a job performed by Bob.

$\displaystyle \biggl( \frac{27090144}{5309} \biggr)=27090144^{\frac{5309-1}{2}} \equiv 1 \ \text{mod} \ 5309$

This shows that the combined ciphertext is for a bit of 0, which is $m_3 \bigoplus m_4=0$ . $\square$

$\text{ }$

Dan Ma Goldwasser-Micali Cryptosystem

Dan Ma Homomorphic Encryption Algorithm

Daniel Ma Goldwasser-Micali Cryptosystem

Daniel Ma Homomorphic Encryption Algorithm

Dan Ma Quadratic Residuosity Problem

Daniel Ma Quadratic Residuosity Problem

$\copyright$ 2023 – Dan Ma

Quadratic residuosity problem

Posted on January 8, 2023 by Dan Ma

Let $n$ be an odd composite positive integer whose prime factors are not known. Let $a$ be in integer that is relatively prime to $n$ . How hard is it to determine whether $a$ is a square modulo $n$ ? That is, how hard is it to know whether the congruence equation $x^2 \equiv a \ \text{mod} \ n$ has solutions in $x$ ? Here is a more precise formulation of the problem called quadratic residuosity problem.

Quadratic Residuosity Problem
Let $N=p \times q$ where $p$ and $q$ are two distinct odd primes. The values of $p$ and $q$ are not known but the value of $N$ is known. Let $a$ be an integer that is relatively prime to $N$ such that the Jacobi symbol $(\frac{a}{N})=1$ . Determine whether $a$ is a quadratic residue modulo $N$ , i.e., whether $a$ is a square modulo $N$ .

When the modulus $N$ is relatively small, we can simply square the numbers that are relatively prime to $N$ until we reach a value that is the same as $a$ . When $N$ is large (or when $p$ and $q$ are large), the quadratic residuosity problem is believed to be computationally difficult. The intractability of the problem has implications in cryptography. For example, the security of the Goldwasser-Micali cryptosystem is based on the difficulty of the quadratic residuosity problem. See here for a discussion of the Goldwasser-Micali cryptosystem.

More on the Problem

When the modulus is a prime $p$ , there is an efficient algorithm to determine whether $a$ is a square modulo $p$ or whether $a$ is a quadratic residue modulo $p$ . One way is the use Euler’s criterion by evaluating $a^{\frac{p-1}{2}}$ modulo $p$ . We can also evaluate the Legendre symbol $(\frac{a}{p})$ . Both results are the same value. If the result is congruent to 1, then $a$ is a quadratic residue modulo $p$ . If the result is congruent to -1, then $a$ is a quadratic nonresidue modulo $p$ .

When $N=p \times q$ as discussed above, the number $a$ is a quadratic residue modulo $N$ if and only if $a$ is a quadratic residue modulo both $p$ and $q$ . If $p$ and $q$ are known, we can evaluate the Legendre symbols $(\frac{a}{p})$ and $(\frac{a}{q})$ . If both are 1, then $a$ is a quadratic residue modulo $N$ . If one or both symbols is a -1, then $a$ is a quadratic nonresidue modulo $N$ . With $p$ and $q$ not known, this is not a feasible approach.

The same tools that work for prime modulus would not work for the composite modulus $N$ . Euler’s criterion is no longer applicable, which is applicable only when the modulus is an odd prime. We can evaluate the Jacobi symbol $(\frac{a}{N})$ by using the law of quadratic reciprocity for the Jacobi symbol. However, the value of the Jacobi symbol $(\frac{a}{N})$ may not nicely correspond to quadratic residue or quadratic nonresidue, unlike the situation for the Legendre symbol. For the Legendre symbol, $(\frac{a}{p})=1$ means $a$ is a quadratic residue modulo the odd prime $p$ and $(\frac{a}{p})=-1$ means $a$ is a quadratic nonresidue modulo $p$ . When the Jacobi symbol $(\frac{a}{N})$ has the value of -1, we can conclude that $a$ is a quadratic nonresidue modulo $N$ . But when $(\frac{a}{N})$ is 1, we cannot conclude that $a$ is a quadratic residue modulo $N$ . When $(\frac{a}{N})=1$ , sometimes $a$ is a quadratic residue (when $a$ is a quadratic residue modulo both $p$ and $q$ ) and sometimes $a$ is a quadratic nonresidue (when $a$ is a quadratic nonresidue modulo both $p$ and $q$ ). The examples in the next section illustrate that the Jacobi symbol may not give reliable information.

Examples

Evaluate the following Jacobi symbols $(\frac{26807757}{80549389})$ and $(\frac{1370266}{80549389})$ .

See here for information on Jacobi symbol. In the following derivation, we do not factor any odd number and instead use the law of quadratic reciprocity to flip the symbols. Once the top value is greater than the bottom value, we reduce the top value modulo the bottom value. Whenever the top value is even, we factor out the 2.

$\displaystyle \begin{aligned} \biggl(\frac{26807757}{80549389}\biggr)&=\biggl(\frac{80549389}{26807757}\biggr) =\biggl(\frac{126118}{26807757}\biggr) \\&=\biggl(\frac{2}{26807757}\biggr) \times \biggl(\frac{63059}{26807757}\biggr) \\&=(-1) \biggl(\frac{26807757}{63059}\biggr) =-\biggl(\frac{7682}{63059}\biggr) \\&=-\biggl(\frac{2}{63059}\biggr) \times \biggl(\frac{3841}{63059}\biggr) \\&=- (-1) \biggl(\frac{63059}{3841}\biggr) =\biggl(\frac{1603}{3841}\biggr) \\&=\biggl(\frac{3841}{1603}\biggr) =\biggl(\frac{635}{1603}\biggr) \\&=-\biggl(\frac{1603}{635}\biggr)=-\biggl(\frac{333}{635}\biggr) \\&=-\biggl(\frac{635}{333}\biggr)=-\biggl(\frac{302}{333}\biggr) \\&=-\biggl(\frac{2}{333}\biggr) \times \biggl(\frac{151}{333}\biggr)\\&=-(-1) \biggl(\frac{333}{151}\biggr)=\biggl(\frac{182}{151}\biggr) \\& =\biggl(\frac{2}{151}\biggr) \times \biggl(\frac{91}{151}\biggr)\\&=- \biggl(\frac{151}{91}\biggr)=- \biggl(\frac{60}{91}\biggr)\\&=- \biggl(\frac{2}{91}\biggr)^2 \times \biggl(\frac{15}{91}\biggr)\\&=- \biggl(\frac{15}{91}\biggr)\\&=- (-1)\biggl(\frac{91}{15}\biggr) =\biggl(\frac{1}{15}\biggr) \\&=1 \end{aligned}$

Following the similar process, we evaluate the second Jacobi symbol as follows.

$\displaystyle \begin{aligned} \biggl(\frac{1370266}{80549389}\biggr)&=\biggl(\frac{2}{80549389}\biggr) \times \biggl(\frac{685133}{80549389}\biggr) \\&=(-1) \biggl(\frac{80549389}{685133}\biggr) =- \biggl(\frac{388828}{685133}\biggr)\\&=- \biggl(\frac{2}{685133}\biggr)^2 \times \biggl(\frac{97207}{685133}\biggr) \\&=- \biggl(\frac{685133}{97207}\biggr)=-\biggl(\frac{4684}{97207}\biggr) \\&=- \biggl(\frac{2}{97207}\biggr)^2 \times \biggl(\frac{1171}{97207}\biggr) \\&=- (1) (-1) \biggl(\frac{97207}{1171}\biggr)=\biggl(\frac{14}{1171}\biggr) \\&=\biggl(\frac{2}{1171}\biggr) \times \biggl(\frac{7}{1171}\biggr) \\&= (-1) (-1) \biggl(\frac{1171}{7}\biggr)=\biggl(\frac{2}{7}\biggr) \\&=1 \end{aligned}$

The values of both Jacobi symbols are 1. The first one corresponds to a quadratic nonresidue modulo $N$ where $N$ = 80,549,389. The second one corresponds to a quadratic nonresidue modulo $N$ . The first Jacobi system corresponds to the equation $x^2 \equiv 26807757 \ \text{mod} \ N$ , which has no solutions. The second symbol corresponds to the equation $x^2 \equiv 1370266 \ \text{mod} \ N$ , which has solutions. One solution is $x \equiv 70254916$ .

These examples illustrate the point that evaluating Jacobi symbols is not a reliable way to solve the quadratic residuosity problem.

$\text{ }$

Dan Ma quadratic residuosity problem

Dan Ma Goldwasser-Micali cryptosystem

Daniel Ma quadratic residuosity problem

Daniel Ma Goldwasser-Micali cryptosystem

$\copyright$ 2023 – Dan Ma

Diffie-Hellman Key Exchange

Posted on January 6, 2023 by Dan Ma

This post is about the public-key Diffie-Hellman key exchange.

The Diffie-Hellman Key Exchange Protocol

This is the problem the Diffie-Hellman protocol is trying to address. Two parties, Alice and Bob, would like to exchange secret messages using a symmetric cipher. For that to be possible, they have to exchange a secret key to be used in the encryption and decryption of the messages. However, their only means of communication is through an insecure public channel. Any information they exchange can be intercepted by Eve the eavesdropper. How can Alice and Bob resolve this dilemma? With the Diffie–Hellman key exchange protocol, Alice and Bob can share a secret key securely over an insecure channel even even though they have no prior knowledge of each other.

The security of the Diffie-Hellman protocol is based on the difficulty of the discrete logarithm problem for $\mathbb{F}_p$ , the finite field consisting of the integers modulo a prime $p$ . The discrete logarithm is defined here. The discrete logarithm problem is discussed here. The following steps describe the Diffie-Hellman algorithm.

Public Information
The first step in the key exchange is for Alice and Bob to set up the public parameter, which consists of a large prime number $p$ and a positive integer $g$ modulo $p$ . Because $p$ and $g$ are made public, the information is accessible by Eve the eavesdropper.

Private Information
The next step is for Alice to choose a secret positive integer $a$ between 1 and $p-1$ and for Bob to choose a secret positive integer $b$ between 1 and $p-1$ . Alice and Bob keep their respective numbers secret. Then Alice computes the value $A \equiv g^a \ \text{mod} \ p$ and Bob computes the value $B \equiv g^b \ \text{mod} \ p$ .

Public Exchange
In this step, Alice sends the value $A$ to Bob and Bob sends the value $B$ to Alice. Because these values are sent over an insecure channel, Eve the Eavesdropper can see the values.

Private Computation to Derive the Key
Once Alice receives the value $B$ from Bob, she computes $A^* \equiv B^a \ \text{mod} \ p$ . In the meantime, Bob computes $B^* \equiv A^b \ \text{mod} \ p$ . The values $A^*$ and $B^*$ are identical. This common value is their exchanged key.

Remarks

For the base $g$ in the public parameter, we can choose a primitive root modulo the large odd prime $p$ in order to make it as difficult as possible for Eve the Eavesdropper to break the protocol. However, it is not strictly required that $g$ must be a primitive root. If $g$ is not a primitive root, its order in the finite field $\mathbb{F}_p$ should be a large prime. See Example 2 below.
To see that the private computation produces the common secret key, see the following calculation.

$A^* \equiv B^a \equiv (g^b)^a \equiv (g^a)^b \equiv A^b \equiv B^* \ \text{mod} \ p$

Once the secret key is established, Alice and Bob can use it to communicate using a symmetric cipher.

Examples

Example 1
In this example, the agreed upon public information consists of the prime number $p$ = 460,079 and the primitive root $g$ = 13,627. The private secret numbers are $a$ = 397,935 (Alice) and $b$ = 250,460 (Bob). Alice and Bob keep their respective numbers secret. Alice then computes $A \equiv g^a$ and Bob computes $B \equiv g^b$ modulo the prime $p$ .

$\displaystyle A \equiv g^a \equiv 13627^{397935} \equiv 3460 \ \text{mod} \ 460079$

$\displaystyle B \equiv g^b \equiv 13627^{250460} \equiv 312029 \ \text{mod} \ 460079$

Alice sends $A$ = 3460 to Bob and Bob sends $B$ = 312029 to Alice. Then Alice performs the calculation $B^a$ and Bob perform the calculation $A^b$ modulo $p$ .

$\displaystyle A^* \equiv B^a \equiv 312029^{397935} \equiv 282228 \ \text{mod} \ 460079$

$\displaystyle B^* \equiv A^b \equiv 3460^{250460} \equiv 282228 \ \text{mod} \ 460079$

As a result, the number 282,228 is the shared secret key for Alice and Bob. They can then use this key to communicate using a symmetric cipher. $\square$

Remarks
Eve can see the entire exchange of information between Alice and Bob. If Eve were to pay attention, she would know $p$ , $g$ (the public parameters) and the numbers $A$ (from Alice) and $B$ (from Bob). Eve can break the Diffie-Hellman algorithm, i.e., uncover the secret numbers of Alice and Bob, if she can solve either one of the congruence equations from Example 1:

$13627^a \equiv 3460 \ \text{mod} \ 460079$
$13627^b \equiv 312029 \ \text{mod} \ 460079$

If Eve the Eavesdropper can solve either one of these equations, she would be able to obtain the shared secret key between Alice and Bob. Solving either one of these two congruence equations is precisely the discrete logarithm problem (discussed here). Based on the information Eve can gather in the exchange between Alice and Bob via an insecure channel, solving the discrete logarithm problem is the one way for Eve to find the shared secret key.

Example 1 is only an illustration of the Diffie-Hellman algorithm. The prime number 460079 is too small to provide any real security. All Eve has to do is to check all the possible powers of 13,627 modulo 460,079 using a computer. How large does $p$ have to be? The current guidelines suggest that if $p$ is 2000-bit prime ( $p$ is roughly $2^{2000}$ ) and the order of the base $p$ is a prime that is roughly $\frac{p}{2}$ , then solving the discrete logarithm problem will be a daunting task.

Example 2
We continue to explore the Diffie-Hellman algorithm using Example 1. The base $g$ (= 13,627) in Example 1 is a primitive root modulo the prime 460,079. This means that every number between 1 and $p-1$ (= 470078) can be expressed as a unique power of 13,627. Thus for any $y$ with $1 \le y \le p-1$ , there is a unque $x$ such that $g^x \equiv y$ modulo $p$ . As a result, the order of this $g$ is $p-1$ , which means that the smallest integer $x$ such that $g^x \equiv 1$ is $p-1$ . For the working of the Diffie-Hellman algorithm, using a primitive root as the base is not necessary. As long as the order of $g$ is a large prime, the algorithm can be made secure.

Let’s work Example 1 using $g$ = 275,064, which is not a primitive root. The $p$ , $a$ and $b$ are still the same values as in Example 1. The following shows the calculation.

$\displaystyle A \equiv g^a \equiv 275064^{397935} \equiv 151570 \ \text{mod} \ 460079$

$\displaystyle B \equiv g^b \equiv 275064^{250460} \equiv 407220 \ \text{mod} \ 460079$

$\displaystyle A^* \equiv B^a \equiv 407220^{397935} \equiv 305882 \ \text{mod} \ 460079$

$\displaystyle B^* \equiv A^b \equiv 151570^{250460} \equiv 305882 \ \text{mod} \ 460079$

Thus, the shared secret key between Alice and Bob is 305,882. Using a different base $g$ will lead to a different shared secret key. The order of 275,064 is 461, meaning that it is the smallest integer $x$ such that $275064^x$ is congruent to 1 modulo 460,079. This means that after every 461 powers of $g$ , the values of $g^x$ repeat. Of course, this example being only an illustration, the order of the base $g$ is small. In actual practice, we would would want the order of $g$ to be a large, either $p-1$ ( $g$ would be a primitive root) or a large prime that is roughly $\frac{p}{2}$ . Using a $g$ with a small order presents a vulnerability that Eve the Eavesdropper can exploit. Using a base $g$ with a large prime order helps prevent using the Pohlig–Hellman algorithm to obtain the secret numbers $a$ and $b$ .

To see where the base $g$ = 275,064 come from and why its order is 461, note that $p-1$ is factored as $p-1$ = 2 x 461 x 499. Then $\frac{p-1}{461}=998$ and $2^{998} \equiv 275064$ modulo 460079. This indicates that the order of 275,964 is 461, which means that 461 is the smallest exponent $x$ such that $275064^x$ is congruent to 1. As a result, the powers of 275,064 repeat after every 461 iterations. In general, it is a good practice to chose a large prime $p$ so that $p-1$ has large prime factors. $\square$

Remarks
As discussed in Example 2, we can either use a primitive root $g$ for the base or a base $g$ such that the order of $g$ is a large prime. Given a prime $p$ , see here for some pointers on finding primitive roots. If the approach is not to use primitive root, here’s some ideas on how to find a base $g$ with the order that is a large prime. Let $p$ be a large prime and let $q$ be a prime factor of $p-1$ . Consider $g \equiv a^{\frac{p-1}{q}}$ modulo $p$ . If $g \equiv 1$ , then the order of $a$ is less than or equal to $\frac{p-1}{q}$ . If $g \not \equiv 1$ , then the order of $g$ is the prime $q$ . If $q$ is sufficiently large, we can use it as the base for the Diffie-Hellman algorithm.

The Diffie-Hellman Problem

In the exchange of information between Alice and Bob, Eve knows four pieces of information, $p$ (the large prime), $g$ (the base), $A$ (sent by Alice to Bob) and $B$ (sent by Bob to Alice). The number $A$ is $g^a$ and the number $B$ is $g^b$ modulo $p$ . If Eve can solve the discrete logarithm problem, then she can uncover one of the secret exponents ( $a$ or $b$ ). As a result, she can derive the shared secret key. This seems to suggest that breaking the Diffie-Hellman algorithm is equivalent to solving the discrete logarithm problem. This is not entirely correct. Breaking the Diffie-Hellman protocol is equivalent to solving the following problem.

The Diffie-Hellman Problem
Four values are given – a prime number $p$ , a positive integer $g$ , and two values of exponentiation $g^a$ and $g^b$ modulo $p$ . From these four values, derive the value of $g^{ab}$ modulo $p$ .

How hard is the Diffie-Hellman problem? It is clear that if Eve can solve the discrete logarithm problem, she can solve the Diffie-Hellman problem. How about the other way? If Eve has an efficient algorithm for solving the Diffie-Hellman problem, can she use that algorithm to solve the discrete logarithm problem? It is certainly an intriguing question. No one knows the answer.

$\text{ }$

Dan Ma Diffie-Hellman Key Exchange

Dan Ma Discrete Logarithm Problem

Daniel Ma Diffie-Hellman Key Exchange

Daniel Ma Discrete Logarithm Problem

Dan Ma Diffie-Hellman Problem

Daniel Ma Diffie-Hellman Problem

The discrete logarithm problem

Posted on January 2, 2023 by Dan Ma

In this post, we discuss the discrete logarithm problem. The notion of discrete logarithm is defined in the preceding post. The Diffie-Hellman key exchange is a cryptographic protocol that is based on the difficulty of solving the discrete logarithm problem (see here).

The discrete logarithm is the inverse of an exponential function. Let $p$ be a prime number. Coupled with the modulo $p$ addition, multiplication and division, the set $\mathbb{F}_p=\{0,1,2,\cdots,p-1 \}$ is a field. The exponential function of interest here is $g^x$ modulo $p$ where $g$ is a primitive root modulo $p$ and $x$ ranges over the non-zero elements of the finite field $\mathbb{F}_p$ . Because the base of the exponential function is a primitive root, the function $g^x$ modulo $p$ is a one-to-one map from $\{1,2,\cdots,p-1 \}$ onto itself. Thus, mathematically, the inverse of the exponential function is well defined. Given a non-zero element $a \in \mathbb{F}_p$ , we would like to find the exponent $x$ such that $g^x \equiv a$ modulo $p$ . The exponent $x$ is called the discrete logarithm of $a$ to the base $g$ modulo $p$ and is denoted by $\log_g(a) \ \text{mod} \ p$ . When the modulus is unambiguous, we can omit mod $p$ in the notation.

The discrete logarithm problem is the problem of finding the exponent $x$ such that $g^x \equiv a$ modulo $p$ when the base $g$ , the modulus $p$ and the value $a$ are given.

A Graphical Look

Let’s look at the discrete logarithm graphically. Let $p$ be the prime number 1307. The number 500 is a primitive root modulo 1307. The first graph below is the exponential function $500^x$ where $x=1,2,3,\cdots,1306$ . The second graph below is the discrete logarithm to the base 500.

Exponential Function

Discrete Logarithm

Discrete Logarithm $\log_{500}(a)$ mod 1307

It is clear that in the first graph, the exponentiation modulo 1307 varies in an irregular way with the exponent. Similarly, the discrete logarithm also varies in a very irregular way with the independent values along the horizontal axis. Both graphs exhibit random looking behavior. Thus, discrete logarithm does not bear any resemblance to the continuous counterpart of logarithm. For example, there can be no expectation that $\log_{500}(a)<\log_{500}(b)$ just because $a<b$ . Clearly, both the exponential function and the discrete logarithm function are not monotonic and do not exhibit any regular patterns, unlike their continuous counterparts. In fact, they resemble scatterplots with a random pattern with zero correlation between the values in the hoirozontal axis and the values in the vertical axis.

Cryptographic Applications

The random behavior in both the discrete logarithm seem to suggest an excellent way to hide information. The exponential function modulo $p$ is easy to evaluate. For any exponent $x$ , the exponentiation $g^x$ can be evaluated using an efficient algorithm called the fast powering algorithm (see here).

In general, how do we go about calculating the discrete logarithm of a number modulo a prime number $p$ ? Given the base $g$ , the modulus $p$ , and the number $a$ , how do we find the discrete logarithm of $a$ to the base $g$ modulo $p$ ? The most obvious way is to compute

$\displaystyle g^1,g^2,g^3,g^4,g^5,g^6,g^7,g^8,\cdots$

$p$

until we reach a value that equals $a$ . For small $p$ such as 1307 used in the above graphs, this approach is feasible. For a small or moderately sized $p$ , we can use software or build a computer program to compute all values of $g^x$ or until it reaches the desired value. If $p$ is large, for example, $p$ is a 2000-bit number (about 600 decimal digits), there is no efficient algorithm for computing the discrete logarithm. In fact, the security of some cryptographic constructions such as Diffie-Hellman key exchange and ElGamal public-key cryptosystem are based on the assumption that the discrete logarithm problem has no efficient solution.

In the above formulation of the discrete logarithm, the base $g$ is a primitive root modulo $p$ . The advantage of $g$ being a primitive root is that the values of $g^x$ span all the non-zero elements of the finite field $\mathbb{F}_p$ . As a result, the discrete logarithm of any non-zero element of $\mathbb{F}_p$ is defined. Thus, for discrete logarithm to be defined fully, the base should be a primitive root modulo $p$ . However, the discrete logarithm can be defined more limitedly as long as the least exponent $x$ such that $g^x \equiv 1$ modulo $p$ is sufficiently large. In general, give a base $g \in \mathbb{Z}_{p}$ and any $a \in \mathbb{Z}_{p}$ , the discrete logarithm of $a$ to the base $g$ is the exponent $x$ such that $g^x \equiv a$ modulo $p$ , assuming that such an exponent exists.

$\text{ }$

Dan Ma primitive root

Dan Ma discrete logarithm

Dan Ma discrete logarithm problem

Daniel Ma primitive root

Daniel Ma discrete logarithm

Daniel Ma discrete logarithm problem

Defining discrete logarithm

Posted on January 1, 2023 by Dan Ma

We illustrate discrete logarithm using a small prime modulus. This is a preparatory discussion for the discrete logarithm problem, which is discussed here. The Diffie-Hellman key exchange is a cryptographic protocol that is based on the difficulty of solving the discrete logarithm problem (see here).

The Setting

Let $p$ be a prime number. Of interest are the two sets $\{ 0,1,2,3,\cdots,p-1 \}$ and $\{ 1,2,3,\cdots,p-1 \}$ . The first one is usually denoted by $\mathbb{Z}_p$ or $\mathbb{Z} / p \mathbb{Z}$ and sometimes $\mathbb{F}_p$ . It is called the ring of integers modulo $p$ . We can perform addition, subtraction and multiplication modulo $p$ on $\mathbb{Z}_p$ . The second set is usually denoted by $(\mathbb{Z}_p)^*$ or $(\mathbb{Z} / p \mathbb{Z})^*$ , which is the set of all non-zero elements of $\mathbb{Z}_p$ . Because $p$ is prime, every non-zero element of $\mathbb{Z}_p$ has a multiplicative inverse modulo $p$ . As a result, $\mathbb{Z}_p$ is a field, which means that it is a commutative ring in which every non-zero element has a multiplicative inverse. Thus, we can perform addition, subtraction, multiplication on all elements of $\mathbb{Z}_p$ and division on the non-zero elements of $\mathbb{Z}_p$ .

Let $p$ be a prime number. Let $g$ be an element of $(\mathbb{Z}_p)^*$ . The number $g$ is called a primitive root modulo $p$ if every element of $(\mathbb{Z}_p)^*$ is a power of $g$ modulo $p$ . Thus, taking powers of $g$ produces all elements of $(\mathbb{Z}_p)^*$ . We have the following set equality:

$\{ 1,2,3,\cdots,p-1 \}=\{ g^1,g^2,g^3,\cdots,g^{p-1} \}$

As a result, for any number $a \in (\mathbb{Z}_p)^*$ , $a \equiv g^x$ modulo $p$ for some $x \in (\mathbb{Z}_p)^*$ . The number $x$ is said to be the discrete logarithm of $a$ to the base $g$ and is denoted by $\log_g(a) \ \text{mod} \ p$ . The modulus $p$ can be omitted in the notation if it is understood.

To summarize the preceding paragraph, the primitive root $g$ generates all the elements of $(\mathbb{Z}_p)^*=\{ 1,2,3,\cdots,p-1 \}$ through powering. Thus, given $a \in (\mathbb{Z}_p)^*$ , it must be a power of $g$ . The discrete logarithm of $a$ is that exponent.

Examples

Consider $p$ = 19. The number 2 is a primitive root modulo 19. The following table shows the powers of 2 modulo 19.

Primitive Root 2, Modulus 19

n	2^n mod 19	n	2^n mod 19
1	2	10	17
2	4	11	15
3	8	12	11
4	16	13	3
5	13	14	6
6	7	15	12
7	14	16	5
8	9	17	10
9	18	18	1

In the above table, the first and third columns are the non-zero elements of the finite field $\mathbb{Z}_{19}$ , ranging from 1 to 18, and the second and fourth columns are the powers of 2 modulo 19. For example, $2^{10}$ is 1024, which equals the remainder of 17 upon division by 19. Note that the values in the second and the fourth column are distinct and are exactly the same numbers as in the first and third columns, just in different order. This is because the number 2 is a primitive root modulo 19. Thus, the table shows that

$\{ 1,2,3,\cdots,18 \}=\{ 2^1,2^2,2^3,\cdots,2^{18} \}$

When $p$ is prime and $g$ is a primitive root, one characteristic of $g$ is that the smallest exponent $x$ such that $g^x \equiv 1$ modulo $p$ is $p-1$ . This is illustrated in the above table, which shows that $2^n$ is not congruent to 1 for all $n$ below 18 and that $2^{18}$ is congruent to 1 modulo 19.

Going from the first column to the second column (and from the third to the fourth) is the exponential function, i.e., the primitive root 2 raised to $n$ . Going from the second column to the first column (and from the fourth to the third) is the logarithm side of the process. For example, what is the discrete logarithm of 17 modulo 19? In other words, what is the exponent $x$ such that $2^x \equiv 17$ modulo 19? From the table, we know that $x$ = 10, i.e., $\log_2(17)$ = 10. Another example: $\log_2(12)$ = 15.

For the prime $p$ – 19, there are six primitive roots and they are 2, 3, 10, 13, 14 and 15. The following table shows the powers of 13.

Primitive Root 13, Modulus 19

n	13^n mod 19	n	13^n mod 19
1	13	10	6
2	17	11	2
3	12	12	7
4	4	13	15
5	14	14	5
6	11	15	8
7	10	16	9
8	16	17	3
9	18	18	1

In this table, the base is now 13. From the values in the table, we see that 13 is a primitive root since the smallest exponent $n$ for which $13^x \equiv 1$ is 18 (one less than the modulus). We also observe from the table that the taking the powers of 13 produces all the non-zero values of the field $\mathbb{Z}_{19}$ . To find the discrete logarithm base 13 of a number in the second column (fourth column), we read off the corresponding number in the first column (third column). For example, the discrete logarithm of 10 to the base 13 is 7, which is denoted by $\log_{13}(10)$ = 7. Another example: $\log_{13}(8)$ = 15.

To contrast, consider a base that is not a primitive root, say 5. The following table shows the powers of 5.

Base 5, Modulus 19

n	5^n mod 19	n	5^n mod 19
1	5	10	5
2	6	11	6
3	11	12	11
4	17	13	17
5	9	14	9
6	7	15	7
7	16	16	16
8	4	17	4
9	1	18	1

Because 5 is not a primitive root, there is more than one 1 in the second and fourth column. The smallest exponent $x$ such that $5^x \equiv 1$ modulo 19 is not 18 but is less than the modulus less one, in this case 9. Also note that taking the powers of 5 does not produce all the non-zero elements of finite field $\mathbb{Z}_{19}$ . In this case, the powering of 5 only gives the values 1, 4, 5, 6, 7, 9. 11. 16, and 17. As a result, discrete logarithm cannot be defined on all the non-zero values of the field $\mathbb{Z}_{19}$ . For example, the value of 3 is not found in the second or the fourth column. Thus $\log_5(3)$ is not defined. However, the discrete logarithm base 5 can be defined in a limited sense. For example, discrete logarithm to the base 5 can be defined using the first and second column in the base 5 table. For example, $\log_5(16)$ = 7.

For discrete logarithm to be defined fully, the base should be a primitive root modulo $p$ . As indicated in the preceding paragraph, the discrete logarithm can be defined more limitedly as long as the least exponent $x$ such that $g^x \equiv 1$ modulo $p$ is sufficiently large. In general, give a base $g \in \mathbb{Z}_{p}$ and any $a \in \mathbb{Z}_{p}$ , the discrete logarithm of $a$ to the base $g$ is the exponent $x$ such that $g^x \equiv a$ modulo $p$ , assuming that such an exponent exists.

Remarks

Let $p$ be a prime number. Let $g$ be a primitive root modulo $p$ . Let $a$ be a non-zero element of the finite field $\mathbb{F}_{p}$ . The discrete logarithm problem is the problem of finding the exponent $x$ such that $g^x \equiv a$ modulo $p$ . The number $x$ is called the discrete logarithm of the number $a$ to the base $g$ and is denoted by $\log_g(a) \ \text{mod} \ p$ . When the modulus is understood, the mod $p$ is omitted in the log notation.

The examples given above seem to suggest that the determination of the discrete logarithm requires the calculation of all the powers of a primitive root. The table approach with a small prime modulus shown here is just for illustration. When the modulus $p$ is small, the table approach of computing all values of $g^x$ is feasible. When $p$ is large, e.g., a prime of at least 600 digits, then it will be difficult to evaluate discrete logarithm. In general, there is no efficient algorithm for computing discrete logarithm when the prime modulus is large. Several important algorithms in public-key cryptography, e.g., Diffie-Hellman key exchange and ElGamal, base their security on the assumption that the discrete logarithm problem has no efficient solution.

$\text{ }$

Dan Ma discrete logarithm

Dan Ma discrete logarithm problem

Daniel Ma discrete logarithm

Daniel Ma discrete logarithm problem

Mathematical Cryptography

focusing on the math in public key cryptography

Monthly Archives: January 2023

Pollard’s p-1 factorization algorithm

The Goldwasser-Micali Cryptosystem

Quadratic residuosity problem

Diffie-Hellman Key Exchange

The discrete logarithm problem

Defining discrete logarithm