Key Exchange

All security guarantees of symmetric-key cryptography stem from the basic assumption that the sender and the receiver know a secret key that the adversary doesn't. It's finally time to face the obvious follow-up question: Where does this secret key come from?

This chapter is about how two users, who have no shared secrets, can obtain a shared secret even in the presence of an eavesdropper.

13.1. Cyclic groups

This chapter builds towards a key exchange protocol based on an algebraic structure called a cyclic group. The concept is best illustrated by an example involving multiplication modulo a prime:

This example shows that 2 is a special element mod 13. Other elements are not so special:

Generators of cyclic group are also sometimes called primitive roots.

A cyclic group can have more than one generator. See if you can find another generator of $\{1, \ldots, 12\}$.

Multiplicative groups modulo a prime are a good mental model of cyclic groups. However, there are much better choices of cyclic groups for cryptography, which we will see later. Therefore, the results in this chapter are presented abstractly, in terms of an unspecified cyclic group.

If $G$ is cyclic with order $\nmod$, then its elements can be written as $\{ g^0, g^1, \ldots, g^{\nmod-1} \}$. Thus:

• One way to sample uniformly from $\G$ is to first sample an exponent $a$ uniformly from $\Z_\nmod$ and output $g^a$.

• Exponents in the group work mod $\nmod$. In other words, we have:

  $g^a = g^{a \pct \nmod}.$

Finding a generator: To do cryptography in a cyclic group, you need to know a generator of the group. A generator can be found by trial and error, if you know the prime factorization of the group's order. We won't prove the following fundamental fact about groups:

Another way to define the order of $g$ is the cardinality of the set $\{ g^0, g^1, \ldots \}$. If $g$ is a generator, then its order is exactly $|\G|$. In a previous example we showed that, with respect to arithmetic mod 13, $g=3$ has order 3, which indeed divides the order of the group $| \Z_{13}^* | = 12$.

Now, suppose we want to check whether $g$ is a generator of $\Z_{\nmod+1}^*$. In other words, we want to check whether $g$ has order $\nmod$. We simply need to check whether $g^k = 1$ for any proper divisor $k$ of $\nmod$. So raise $g$ to the power $\nmod/q$ for every prime divisor $q$ of $\nmod$. If none of these exponentiations result in 1, then $g$ must have order $\nmod$ and be a generator.

13.1.1. The discrete logarithm problem

Since every element in a cyclic group can be written as some power of the generator, a natural question is: Given an element of the group, which power of the generator is it?

This problem is called a logarithm problem because it involves solving for the unknown exponent in an expression like $A = g^a$. But discrete logarithms are different from your usual logarithms in a few important ways:

• The solution to a discrete logarithm problem is always an integer (hence, “discrete”).

• In some cyclic groups, the discrete logarithm problem is computationally hard. There is no known polynomial-time algorithm.

This second point is relevant to cryptography: It means that in some cyclic groups, the operation $a \mapsto g^a$ is easy to compute, but its inverse $g^a \mapsto a$ is hard to compute.

Measuring Efficiency: We need to be careful when talking about the efficiency of algorithms dealing with huge numbers. Consider the following algorithm for solving the discrete log problem in a cyclic group of order $n$:

I previously claimed that there is no polynomial-time algorithm for discrete log (at least in some groups), but isn't this a $O(n)$-time algorithm that works for any group?

Indeed, this algorithm is $O(n)$, but $n$ is not the length of the algorithm's input! The algorithm receives just one group element as input, and if the group has order $n \approx 2^k$, each group element can be written in $k$ bits. The running time of this elementary discrete log algorithm, as a function of its actual input length $k$, is $O(2^k)$; it is not a polynomial-time algorithm. As we will see later in this chapter, cryptography based on cyclic groups requires groups where $n$ is huge (e.g., $n\approx 2^{256}$, $n\approx 2^{3072}$), so an algorithm running in $O(n)$ time is useless.

When we say that the discrete logarithm problem is hard, we mean there is no known algorithm for discrete log that runs in polynomial time as a function of $k$ in a group of order ${} \approx 2^k$.

13.1.2. Efficient exponentiations

Cryptography based on cyclic groups involves a lot of exponentiation, computing expressions like $g^a$. This is meant to be the “easy” direction, compared to the “hard” direction of computing discrete logarithms. So it's important to understand exactly how these expressions can be computed efficiently, in polynomial time in the number of bits required to write each group element.

For the sake of concreteness, let's consider multiplicative groups modulo a prime and use the prime $p = 2^{130}-5$ as an example. You can trust me that 2 is a generator of this group. How would you compute an expression like $2^{1234567891011} \pct p$? Even sage, which handles huge integers with ease, seems to have problems:

What went wrong? We have just asked sage to first evaluate $2^{1234567891011}$ as an integer, and then reduce it mod $p$. But that huge integer would require 1234567891011 bits (154 GB) to write down, which is beyond what sage is willing to use. And this is with a “small” exponent, a 40-bit integer. Imagine if the exponent were 256 bits long!

Concept 1: Reduce as you go: The best trick for modular arithmetic is that if you need the final answer mod $p$, then you can/should reduce all intermediate steps mod $p$. In other words, you can compute an expression like $2^{123\ldots}$ by performing many multiplications, and these should be multiplications mod $p$, not multiplications over the integers. Hopefully this makes sense, because, after all, we are thinking of a cyclic group whose operation is multiplication-mod-$p$, not multiplication over the integers.

We can ask sage to use multiplication-mod-$p$ by creating a Mod object, which overloads multiplication (and therefore exponentiation) appropriately:

Concept 2: Exponentiation by squaring: Your mental model for evaluating an expression like $X^B$ might be something like this:

But this can't possibly be how sage does it, because it can compute $2^{1234567891011}$ instantly. It could not have possibly performed 1234567891011 multiplications. And indeed, this simple exponentiation algorithm runs in $O(B)$ time, which is exponential in the number of bits required to write $B$.

A much better way to exponentiate can be illustrated with the following example:

Every “$\cdot$” or “${}^2$” in this expression represents one multiplication that must be performed, and you can see that this expression computes $X^{19}$ using not 18 multiplications, but only 6.

This exponentiation strategy is called repeated squaring, and can be written recursively:

Remember, the multiplications and squarings in this algorithm should use the cyclic group operation (in our running example, multiplication-mod-$p$) so that intermediate values are consistently reduced mod $p$.

The total cost of this algorithm is $O(\log B)$ multiplications, because at each recursive level it performs at most 2 multiplications, then recurses on a new exponent roughly half the size. Its running time is polynomial in the number of bits in $B$.

13.2. Diffie-Hellman key exchange

In 1978, Whitfield Diffie and Martin Hellman published New Directions in Cryptography, the most important paper in the history of cryptography. In this paper they describe an ingenious method for two users to generate a shared secret key “from nothing.” Their method is interactive: The two users, who share no secrets, exchange messages with each other until they can both compute a common key. Yet anyone observing their communication will not be able to learn this key. In their method, amazingly, you learn more by participating than by observing.

The Diffie-Hellman protocol uses a cyclic group with generator $g$. The main idea is that the users exchange public messages $g^a$ and $g^b$, and define $g^{ab}$ as their shared secret. The user who sent $g^a$ knows the secret $a$ and can compute the key as $(g^b)^a = g^{ab}$; the other user knows $b$ and can compute the secret as $(g^a)^b = g^{ab}$. (The usual rules of exponents hold in any cyclic group.) However, an outside observer who sees $g^a$ and $g^b$ will have difficulty computing $g^{ab}$.

Here's how to interpret a protocol diagram like this: Each user's actions are specified sequentially, starting from the top and proceeding downward. Arrows indicate messages from one user to the other. Thus, Alice samples $a$ and computes $A = g^a$, while Bob (simultaneously) samples $b$ and computes $B = g^b$. Alice sends $A$ to Bob and Bob sends $B$ to Alice. Finally, Alice computes $B^a$ and Bob computes $A^b$.

13.2.1. Passive Security

To keep things simple, in this chapter we focus on the most basic security property for a key exchange protocol: security against a completely passive eavesdropper. An adversary who merely observes the victims' interaction should not be able to learn their shared key. More precisely, the victims' shared key should look pseudorandom from the adversary's point of view.

The security condition can be formalized by saying that the following two libraries are indistinguishable:

In other words, no adversary should be able to distinguish the real key from a truly uniform, unrelated key, even after seeing the DHKE transcript. Remember, in a real application of DHKE the users will use the resulting shared key for symmetric-key cryptography. But in this attack scenario, the libraries give the key to the adversary; this is our way of saying “the DHKE shared key is just as good as a truly uniform key, no matter what it is used for.”

Given the earlier contents of this chapter, you might be expecting a proof of how DHKE is secure in this sense, assuming that the discrete logarithm problem is hard in the cyclic group $\G$. Unfortunately, no such proof is known. Instead, the Diffie-Hellman protocol is so fundamental that we simply treat its (passive) security as a “fundamental” assumption about cyclic groups, and give it a nice name:

The DDH assumption is equivalent to the statement that the DHKE protocol is passively secure. It is a useful assumption, which can be used to prove the security of many other more complicated constructions.

Disclaimer: Key exchange, as defined in this chapter, is unauthenticated. Passive security means: The two protocol participants—whoever they may be!—agree on a key that looks pseudorandom to an eavesdropper. Passive security gives no guarantees about the identity of those participants. In the real world there is rarely much use in agreeing on a key shared with “whoever might be on the other end of this connection.” Usually, one has a clear intent about their KE partner's identity.

Think of this chapter not as the complete story of key exchange, but just the beginning. What we are calling passive security is the bare minimum level of protection you might want in a key exchange protocol. Incorporating authentication into key exchange is the subject of chapter 18.

13.2.2. Choosing a strong cyclic group

Although we have built intuition about cyclic groups using multiplicative groups $\Z^*_\nmod$, these are not the best choice for Diffie-Hellman, for a few reasons. The most glaring one is that DDH is false in $\Z^*_\nmod$! There is an efficient algorithm that, given $g^a \in \Z^*_\nmod$, can determine whether $a$ is even or odd, and this is enough to contradict the DDH assumption. The exercises explore this fact in more depth.

Quadratic Residues: The problem with $\Z_\nmod^*$ has something to do with the fact that it has $\nmod-1$ elements, which is even when $\nmod$ is an odd prime. If we want the DDH assumption to hold in a cyclic group, it is helpful if the group's order does not have small prime factors, like 2 in this case. One way to eliminate this factor of 2 is to consider the subgroup of quadratic residues mod $\nmod$.

In particular, when $\Z^*_\nmod$ is cyclic, $\QR^*_\nmod$ consists of all the elements of $\Z^*_\nmod$ with even exponents:

Thus, $\QR^*_\nmod$ is also cyclic, with $g^2$ as its generator.

When $\nmod$ is an odd prime, squaring-mod-$\nmod$ is a 2-to-1 function, just like it is in the real numbers. Thus, $\QR^*_\nmod$ contains exactly half of the elements of $\Z^*_\nmod$, so $(\nmod-1)/2$. The best chance to ensure problems like DDH and discrete logarithm are hard is when $(\nmod-1)/2$ is itself prime. If $\nmod$ and $(\nmod-1)/2$ are both prime, then $\nmod$ is called a safe prime. The DDH assumption is widely believed to hold in the group of quadratic residues $\QR^*_\nmod$ modulo a safe prime.

Avoid DDH altogether: Exercise 13.8 proposes another way around the deficiencies of $\Z^*_\nmod$. It is possible to prove security of a modified variant of DHKE, under a slightly weaker assumption about the cyclic group. Although DDH does not hold in $\Z^*_\nmod$, this weaker assumption is widely believed to hold.

Elliptic curves: The best cyclic groups for Diffie-Hellman are not based on multiplication mod $\nmod$, but on an entirely different algebraic structure called an elliptic curve. These groups are introduced in more detail in section 13.4.

13.3. Key exchange in the abstract

The Diffie-Hellman protocol is just one example of a key exchange protocol. In this section we formalize key exchange as an abstract cryptographic primitive.

Key exchange is more cumbersome to formalize than other primitives because it is inherently interactive. The security guarantee for KE involves two users interacting, and we need to be able to reason about the messages they exchange as well as their final output. Below is one possible approach for formalizing arbitrary interactive protocols:

I like to think of $\lib{ke-rand}$ as describing a world in which Alice and Bob run a key exchange protocol as a decoy but then a magical fairy gives them both an unrelated key $\key'$ that they use for their symmetric-key cryptography.

Remember, this is a definition of passive security, against an adversary who merely observes the victims' interaction. It implies no guarantees for the victim when an adversary participates in the protocol and possibly deviates from the specification. It provides no guarantees about the identities of the KE participants. Chapter 18 is devoted to these security properties.

13.4. ☆ Elliptic curves

In section 13.2.1 we discussed $\QR^*_\pmod$ as a group in which the DDH assumption is believed to hold, when $\pmod$ is a safe prime. However, that discussion conveniently ignored the question of how big $\pmod$ should be. This is a question about concrete security. We typically choose parameters so that the best known attacks require $2^\secpar$ effort. For example, the best known attacks against PRFs are simple brute-force, so we can choose $\secpar$-bit PRF keys. The best known attack against collision resistance is a birthday attack which is faster than brute-force, so we choose hash functions whose output length is $2\secpar$.

The best known way to break DDH in $\QR^*_\pmod$ is to solve the discrete logarithm problem mod $\pmod$. The best known discrete log algorithms are not polynomial-time, but considerably faster than brute force. Here is a table showing, for a few target values $\secpar$, how large $\pmod$ must be so that the fastest known discrete log algorithms would require $2^\secpar$ effort:

In other words, DHKE over $\QR^*_\pmod$ requires group elements that are at least 3072 bits long. Since the cost of modular exponentiation algorithms scale with the cube of the input size, these huge groups are an expensive choice.

This section is a brief overview of a completely different kind of cyclic group, called an elliptic curve group, which (disappointingly) has very little to do with ellipses. These groups lack much of the structure of $\Z^*_\pmod$ and $\QR^*_\pmod$, which is a good thing, since that additional structure is precisely what can make the discrete logarithm problem easier. The best known discrete log algorithms on elliptic curve groups require time $2^{k/2}$ in a group of order $2^k$. Thus, we can make the discrete log problem require $2^\secpar$ effort by choosing an elliptic curve group with order only $2^{2\secpar}$. Concretely, elliptic curves allow us to use Diffie-Hellman with 256-bit group elements instead of 3072-bit group elements.

13.4.1. Elliptic curves over the real numbers

We will first build some geometric intuition for elliptic curves by investigating curves defined over the real numbers. Cryptographic applications use curves defined using modular arithmetic, which we will discuss later.

Point addition: Given two points on an elliptic curve, there is a special way to “add” them, resulting in another point on the curve. This point addition operation is somewhat complicated, but it can be derived by understanding how straight lines intersect the elliptic curve.

Definition 13.4.3 might seem unsatisfying as a definition of an addition operation. But we can use it to define addition in a more concrete, procedural way.

Point addition can be performed procedurally in the following way:

Additive notation for groups: These rules define an addition operation for points on an elliptic curve, and that operation satisfies the necessary rules for a mathematical group.

Before now, we have written the operation of a (cyclic) group as multiplication, a reasonable choice for groups like $\Z_\pmod^*$ whose operation is multiplication-mod-$\pmod$. With elliptic curves, it is the convention to write their operation as addition. We can rephrase the axioms of cyclic groups using additive notation:

• There is a special element $0 \in \G$ such that $A + 0 = A$ for all $A \in \G$. In elliptic curve groups, this neutral element is the point at infinity.

• Associativity: For all $A,B,C \in \G$, we have $(A+B)+C = A+(B+C)$. This fact is notoriously tedious to prove for elliptic curve groups, and it is hard to gain any intuition from the geometry of the problem.

• Inverses: For every $A \in \G$ there is an element $-A \in \G$ such that $A + (-A) = 0$.

• A generator of a cyclic group $\G$ (in additive notation) is an element $G$ such that

  $\G = \{G, \quad G+G, \quad G+G+G, \quad \ldots \}.$

  Expressions like $G+G+G$ are usually written as $3G$ or $[3]G$, so exponentiation becomes “scalar multiplication.” When using additive notation, we generally write group elements (including the generator) in uppercase and scalars in lowercase, in an attempt to reduce confusion.

• Keeping in mind that $g^i = g \cdot g \cdots g$ (with $i$ terms), the discrete logarithm problem in additive notation is: Given $A \in \G$ and a generator $G$, find an integer $a$ such that $A = aG = G + G+ \cdots +G$ (with $a$ terms). Of course the name “logarithm” is not as prominently reflected in additive notation.

If you want to become a cryptographer, it's imperative that you develop very passionate feelings about additive vs. multiplicative notation.

13.4.2. Elliptic curves modulo a prime

Elliptic curves over the real numbers are helpful for developing a geometric intuition. But cryptography uses elliptic curves defined over the integers mod $p$, where $p$ is a prime. Such a curve consists of all points $(X,Y)$ — where now $X$ and $Y$ belong to $\Z_\pmod$ — that satisfy the curve equation $Y^2 = X^3 + aX + b$.

Group addition works by expressing the geometric steps from definition 13.4.3 algebraically and “simply” performing that algebraic manipulation mod $p$. Some of these steps, like finding the line passing through two points, require division, and thus $p$ must be prime to ensure the existence of multiplicative inverses.

As you can see, geometric intuition is limited when working mod $p$, and it's best to rely on algebra alone.

There are many choices for an elliptic curve; how should you choose one? The easy answer is to not choose your own but to use a standard, vetted curve from a reputable library. The choices that motivate standard elliptic curves are beyond the scope of this short introduction.

13.4.3. Elliptic curves in Sage

Here is how I used Sage to list all points on the curve from example 13.4.8:

Zmod(29) tells Sage to generate a curve with operations mod 29. The list [-2,4] gives parameters of the curve equation. If you wonder why Sage prints the curve equation as $Y^2 = X^3 \hl{+27}X + 4$ when we asked for a coefficient of $-2$, it's because $-2 \equiv_{29} 27$.

The .points() method will return all of the points on the curve (so don't do this for a curve with $2^{256}$ points). But if you print a point on the curve, it will display in a different coordinate system that we will not discuss. (This alternate coordinate system avoids special cases to handle the point at infinity.) These point objects can be converted to a more familiar $(X,Y)$ pair with the .xy() method, which will raise an exception for the point at infinity, since it has no $(X,Y)$ coordinates.

To convert an $(X,Y)$ pair to a elliptic curve point object, whose addition operation is overloaded appropriately, you can just use the elliptic curve object E as a constructor:

13.4.4. Pitfalls and fine print

A complete treatment of elliptic curves is well beyond the scope of this book. To give you a peek into the guts of elliptic curves, here are a few issues that arise:

Degenerate curves: The right-hand side of the elliptic curve equation $X^3 + aX + b$ is a cubic expression of $X$, and usually has three distinct roots. However, if $4a^3 + 27 b^2=0$ then the cubic has repeated roots. We call the elliptic curve degenerate in this case. Degenerate curves have points with an undefined tangent, and the curve addition law breaks down for these points.

We always restrict our attention to $a$ and $b$ that avoid this degeneracy condition.

Curve Equations: The point addition algorithm for elliptic curves involves many special cases, like when $A=B$, when one of $A,B$ is the point at infinity, when $A+B$ is the point at infinity, and so on. These special cases can be tricky to implement correctly, and if one is not careful, the running time of the point addition algorithm may leak information about secret exponents (scalars).

One way to improve the point addition algorithm is to use a different kind of defining equation for the curve. So far we have considered only curves defined by $Y^2 = X^3 + aX +b$, known as a Weierstrass curve equation. Other curve equations are possible, notably:

• Edwards curves are defined by $X^2 + Y^2 = 1 + d X^2 Y^2$.

• Montgomery curves are defined by $bY^2 = X^3 + aX^2 + X$.

Not every curve can be expressed by these special kinds of curve equation, but those that can enjoy improved point addition algorithms: faster, and with fewer special cases than Weierstrass curves.

Twists: If $(X,Y)$ is on an elliptic curve, then so is $(X,-Y)$, and these are the only two points on the curve with this $X$ coordinate. Thus, it is common to communicate points on the curve using only their $X$-coordinate, plus one bit representing the sign of $Y$.

However, not every $X$ coordinate corresponds to a point on the curve. For example, in the elliptic curve $Y^2 = X^3 - 2X + 4$ over $\Z_{29}$, there is no point with $X$-coordinate 5, because the right-hand side of the curve equation evaluates to $X^3 - 2X + 4 = 5^3 - 2\cdot 5 + 4 \equiv_{29} 3$, but there is no $Y$ satisfying $Y^2 \equiv_{29} 3$.

For every elliptic curve there is a companion curve, called the twist. Interestingly, every $X$-coordinate corresponds to a point either on the primary curve or its twist, and never both: The two curves exactly partition the set of $X$-coordinates. The twist of our example curve $Y^2 = X^3 - 2X + 4$ has the form $Y^2 = c (X^3 - 2X + 4)$, where $c$ can be any non-square (non-quadratic-residue)—say, 3 in our example above.

Twists can be problematic. Suppose a victim is running DHKE, so they expect to receive an elliptic curve element and “exponentiate” it with their secret Diffie-Hellman exponent (apologies for mixing additive and multiplicative terminology here). If group elements are communicated using only their $X$-coordinates, and an adversary sends an $X$ coordinate from the twist, then the victim will perform the exponentiation over the twist curve. It is possible that the discrete logarithm problem is much easier on the twist curve than on the primary curve, in which case this attack would make it easier for an adversary to recover the secret exponent. This problem can be dealt with in two ways (not mutually exclusive):

• Always check whether a point lies on the intended curve before performing operations on it.

• Choose a cryptographically strong elliptic curve whose twist is also strong.

Cofactors and Small Subgroups: Many cryptographic applications of cyclic groups require a group of prime order. Unfortunately, elliptic curve groups often do not have prime order. For example, Edwards and Montgomery curve equations always produce a group whose order is a multiple of 4. If we want to take advantage of the algorithmic benefits of those curve equations, we need a way to cope with their composite order. Below is a general discussion of composite-order groups, which is not specific to elliptic curves. Therefore, we will use multiplicative notation.

Suppose $\G$ is a cyclic group of composite order $r \cdot s$, with generator $g$. Thus, $\G = \{g^0, g^1, g^2, \ldots, g^{rs} = g^0 \}$, and everything “in the exponent” happens mod $rs$. Now consider the powers of $g^r$:

There are only $s$ possible values before completing a cycle. We say that $g^r$ generates a cyclic subgroup of order $s$.

The math of elliptic curves often gives us a cyclic group of order $r\cdot s$, where $r$ is very small and $s$ is a huge prime. Usually, $r=4$ or $r=8$; this value is called the cofactor of the curve. Given such an elliptic curve, we can just take $g^r$ to be the generator, and everything will happen in the prime ($s$)-order subgroup. Problem solved, right? Not so fast!

Imagine a situation in which a victim receives a group element $A$ from an untrusted source and computes $A^x$, where $x$ is secret. The computation $A^x$ will work fine, not just for elements of the prime-order subgroup, but for the entire composite-order group as well. In particular, an adversary could choose $A$ from the order-$r$ subgroup (such a subgroup exists because $r$ divides the overall order). The result of $A^x$ will remain in the order-$r$ subgroup. But because $r$ is so small, it is easy to compute discrete logarithms in the order-$r$ subgroup by brute force. Thus, the adversary can compute the discrete log $x \pct r$, leaking some information about the secret $x$ which would not be possible if the computation remained in the desired order-$s$ subgroup.

These problems can be avoided by always ensuring that untrusted group elements are in the desired subgroup. The easiest way to do this is to raise an element to the $r$ power; this is called clearing the cofactor. An alternative approach is proposed later in exercise 15.29.

Exercises

1. h A group $\G$ is commutative if $AB = BA$ for all $A,B \in \G$. Prove that every cyclic group is commutative.

   Use the fact that every element in $\G$ can be written in the form $g^x$.

2. What are all the generators of $\Z_{13}^*$?

3. h Simple power analysis (SPA) is a physical attack in which the adversary observes how much voltage is drawn by the CPU while an algorithm is running. In this exercise, you will show an SPA attack against the repeated-squaring method of exponentiation, shown in section 13.1.2.

   The repeated-squaring algorithm involves multiplication and squaring steps. Suppose that by monitoring a CPU's voltage it is easy to determine whether it is performing a multiplication or squaring. (This is a very realistic assumption.) Then an SPA attack is equivalent to having the printed output of the following modified algorithm:

   $\subname{exp}(X,B)$:

   if $B=1$: return $X$

   if $B$ even:

   $R := \subname{exp}(X, B/2)^2$

   print “square” ${}$

   if $B$ odd:

   $R := X \cdot \subname{exp}(X, (B-1)/2)^2$

   print “square” ${}$

   print “multiply” ${}$

   return $R$

   Describe how you can completely recover the exponent $B$, given the printed output of this program.

   Express the concepts “$B$ is odd,” “$B$ is even,” “$B/2$,” and “$(B-1)/2$” strictly in terms of the bits of $B$.

4. Fill in the missing details of the following recursive algorithm for exponentiation, while obeying the following invariants:

   • On input $(X,B)$, the algorithm should return a pair $(X^B, X^{B+1})$.

   • No matter whether $B$ is even or odd, the algorithm should perform 1 recursive call, then 1 squaring and 1 multiplication.

   // should return a pair: $(X^B, X^{B+1})$:

   $\subname{betterexp}(X,B)$:

   if $B=0$: return $(1,X)$

   if $B$ even:

   $(U,V) := \subname{betterexp}(X, B/2)$

   // fill in the blanks:

   // one squaring, one multiplication

   if $B$ odd:

   $(U,V) := \subname{betterexp}(X, (B-1)/2)$

   // fill in the blanks:

   // one squaring, one multiplication

   Explain why this method of exponentiation is immune to the simple power analysis attack described in exercise 13.3.

5. Rewrite the recursive algorithms from exercises 13.3 and 13.4 as iterative algorithms. Your algorithms should iterate over the bits of the exponent.

6. Suppose you are given an element $A$ from a cyclic group $\G$. Assume that the discrete logarithm problem is hard in $\G$; however, I have generously agreed to tell you the discrete logarithm of any single element, except $A$. Explain a strategy by which you can efficiently learn the discrete logarithm of $A$.

7. Suppose there is a polynomial-time algorithm that solves the discrete logarithm problem in $\G$. Show that $\lib{ddh-real}^\G$ and $\lib{ddh-rand}^\G$ are not indistinguishable. Or, equivalently, show an attack against the passive security of DHKE over $\G$.

8. The computational Diffie-Hellman (CDH) assumption states that it is hard to compute $g^{ab}$ given $g^a$ and $g^b$. It is defined formally by saying that the following two libraries are indistinguishable:

   $\lib{cdh-real}$

   $a \gets \Z_\nmod$

   $b \gets \Z_\nmod$

   $\subname{cdh.get}(\,)$:

   return $(g^a, g^b)$

   $\subname{cdh.test}(X)$:

   return $X == g^{ab}$

   $\indist$

   $\lib{cdh-fake}$

   $a \gets \Z_\nmod$

   $b \gets \Z_\nmod$

   $\subname{cdh.get}(\,)$:

   return $(g^a, g^b)$

   $\subname{cdh.test}(X)$:

   return $\myfalse$

   Hashed DHKE is a variant of DHKE in which the parties exchange $g^a$ and $g^b$ as usual, but use $\ro(g^{ab})$ as their output instead of just $g^{ab}$. Prove that hashed DHKE is a passively secure key exchange in the random oracle model (modeling $\ro$ as a random oracle), if CDH holds in the cyclic group.

9. Suppose there is a polynomial-time algorithm that on input $g^a \in \G$ can determine whether $a$ is even. Show that the DDH assumption is false in $\G$. Or, equivalently, show an attack against the passive security of DHKE over $\G$.

10. Recall the additive notation for cyclic groups:

    • Closure: For any $A,B \in \G$, their sum $A \hl{+} B \in \G$.

    • Identity: There is a special element $\hl{0} \in G$ such that $0 \hl{+} A = A$ for all $A \in \G$.

    • Inverses: For any $A \in \G$, there is an element $\hl{{-A}} \in \G$ such that $A \hl{+} \hl{(-A)}= \hl{0}$.

    • Associative: For any $A,B,C \in \G$, we have $(A+B)+C = A+(B+C)$.

    • Cyclic: There is a special element $g \in \G$ such that

      $\G = \{ g, \quad g+g, \quad g+g+g, \ldots, \quad \underbrace{g+\cdots+g}_{i \text{ times}}, \ldots \}.$

    1. Prove that the additive group $\Z_\nmod$, with operation addition mod $\nmod$, satisfies the definition of a cyclic group, for any $\nmod$, not just prime $\nmod$. Be explicit about the group's generator.

    2. Translate the statement of the DDH assumption from multiplicative to additive notation.

    3. Does the DDH assumption hold in $\Z_\nmod$? Is the discrete logarithm problem hard in $\Z_\nmod$?

11. Suppose you have eavesdropped on three DHKE sessions between the same pair of users. They are using $\Z_\nmod^*$ as their cyclic group. So for each $i \in \{1,2,3\}$ you have observed $A_i$ and $B_i$ in the following:

    

    Now suppose you later learn that Alice chose $a_1, a_2, a_3$ to be consecutive integers, and similarly Bob chose $b_1, b_2, b_3$ to be consecutive. You also obtain the value of $\key_2$.

    1. Describe how you can efficiently compute $\key_1$ and $\key_3$.

    2. What are $\key_1$ and $\key_3$ in the following scenario?

       $\begin{aligned} n &= \longnum{1070538477844925558346742185962074457246009909490481180812555120827296369772531487275839473750055867983962815645557115890338108592063470237662685058208470435896631457473692427395437049096290744587009810907170636836528660370698233089143831493001369304965665492345148039330577168709331538411634016221721} \\ g &= 2 \\ A_1 &= \longnum{1037797565320021724146377497526479653112494893566203752644966232886785053133688308755692884169294571337976918667742856159151525011741827216107686024550948098265033995799432853918701021959063865833881200694509119050597210611682953107392278106002581522501641634878928892553668004817191171214602943561786} \\ B_1 &= \longnum{901697775949936253907049992659094952630481123473588678420595948841402174300000881648108423314154966611325820842764731317869613414549140160973118813037043902279187471332718799558657031384932585955321343983286876169101435759485390824261319705010405974688309919098849215361769891736907630437062385181077} \\ K_2 &= \longnum{737062786094183117391522734445098197788358661110754984423292245833445605116638567048922522967380237783103398098652109191477968418343209424300008301942837157875001158506915678403286616052346777340253660078147930230017123489482155651484349401636382342648869132571383684092041811473740996293032962275942} \end{aligned}$

12. Use the rules that define elliptic curve addition to derive the fact that $A+0=A$ for all $A$ on the curve.

Chapter Notes

The exponentiation algorithm referenced in exercise 13.4 is called the Montgomery ladder and is due to Montgomery [166].

Diffie-Hellman key exchange was proposed by Whitfield Diffie and Martin Hellman [83]. Regarding the name of the protocol, Martin Hellman has later stated:

“Merkle” refers to Ralph Merkle, who in 1974 (several years before Diffie and Hellman had their idea) proposed a different method for key exchange in a proposal for an undergraduate class project [159]. Hellman also credits John Gill for suggesting modular exponentiation as a function that is easy to compute and difficult to invert.

The DDH assumption was first explicitly considered by Brands [52].

Edwards proposed his curve equation in 2007 [94]. Bernstein and Lange proposed a generalization called twisted Edwards curves [37].

1. Previous Chapter12. Random Oracles and Other Idealized Models
2. Next Chapter14. Public-Key Encryption