Appendix

Math Review

A.1. Strings

Definition A.1.1 (Strings)

$\bits^n$ denotes the set of $n$ -bit binary strings. $|X|$ denotes the length of the string $X$ , usually measured in bits.

When it is clear from context that we are talking about strings, $\bit 0^n$ means “the string of $n$ $\bit 0$ 's,” not the integer 0 to the $n$ th power. Similarly, $\bit 1^n$ refers to the string of $n$ $\bit 1$ 's.

Definition A.1.2 (XOR)

When $X$ and $Y$ are strings of the same length, $X \oplus Y$ denotes the bitwise exclusive-or (xor) of the two strings.

For example, $\bit{0011} \oplus \bit{0101} = \bit{0110}$ . The following algebraic facts about the xor operation are frequently useful:

\begin{aligned} X \oplus X &= \bit{0}^n, \\ X \oplus \bit{0}^n &= X, \\ X \oplus Y &= Y \oplus X, \\ (X \oplus Y) \oplus Z &= X \oplus (Y \oplus Z). \end{aligned}

There are two ways to think about xor that can be helpful in different situations:

As bit-flipping: xor'ing a bit with $\bit0$ has no effect; xor'ing with $\bit1$ flips that bit. You can think of $X \oplus Y$ as: “starting with $X$ , flip the bits at all the positions where $Y$ has a $\bit1$ .”
As addition mod 2: xor is just addition mod 2 in every position. This interpretation of xor helps to justify its algebraic properties, like the fact that it is commutative and associative. Also, $1+1$ is congruent to 0 mod 2, which explains why $X \oplus X = \bit 0^n$ .

Definition A.1.3 (Concatenation)

We write the result of concatenating two strings $X$ and $Y$ as $\hl{X \| Y}$ .

A.2. Probability

Definition A.2.1 (Probability distributions)

A (discrete) probability distribution over a set $X$ of outcomes is written as a function $\Pr$ that associates each outcome $x \in X$ with a probability $\PR{x}$ . We often say that the distribution assigns probability $\PR{x}$ to outcome $x$ . For each outcome $x \in X$ , the probability distribution must satisfy the condition $0 \le \PR{x} \le 1$ . The sum of all probabilities $\sum_{x \in X} \PR{x}$ must also equal 1.

Definition A.2.2 (Uniform distribution)

The uniform distribution over a finite set $X$ assigns probability $\PR{x} = 1/|X|$ to every $x \in X$ .

The $\Pr$ notation is defined over individual outcomes, but we also extend it to apply to events, which are just collections of many outcomes. For example, when I roll a six-sided die, the event “I rolled an even number” corresponds to the events 2, 4, and 6. Formally, an event $A$ defines a subset of outcomes, and its probability is defined to be $\PR{A} = \sum_{x\in A} \PR{x}$ .

Example A.2.3 (Rolling dice)

A six-sided die has faces numbered $\{1, 2, \ldots, 6\}$ . When rolling such a die (at least in a math problem) the outcome is uniformly distributed. Thus,

\begin{aligned} \PR{\text{3 is rolled}} &= 1/6 \\ \PR{\text{an odd number is rolled}} &= 1/2 \\ \PR{\text{a prime is rolled}} &= 1/2\end{aligned}

Claim A.2.4

If $A$ and $B$ are events, then we write $A \land B$ to denote the event that $A$ happens and $B$ happens. If $A$ and $B$ are independent events, then $\PR{A \land B} = \PR{A} \cdot \PR{B}$ .

Upper Bounds

We often use probabilities to describe a certain “bad event” that violates security. In these cases, it is enough to show just an upper bound on the probability.

Claim A.2.5 (Union bound)

If $A$ and $B$ are events, then we write $A \lor B$ to denote the event that $A$ happens or $B$ happens (or both). The union bound states that:

\PR{A \lor B} \le \PR{A} + \PR{B}.

The sum $\PR{A}+\PR{B}$ is an upper bound because it might double-count the probability that both $A$ and $B$ happen. Importantly, events $A$ and $B$ don't have to be independent for the union bound to apply. We most commonly see the union bound show up in the following way:

Example A.2.6 (Union bound)

Suppose I toss a 100-sided die, ten times, and consider the probability that I observed a $\bit1$ in any of those rolls. We can use the union bound to derive a simple upper bound on the probability:

\begin{aligned} \PR{ \text{some roll resulted in $\bit1$} } &\le \PR{ \text{first roll was $\bit1$} } + \PR{ \text{second roll was $\bit1$} } + \cdots \\ & = 10 \cdot \left( \frac{1}{100} \right) \\ & = \frac{1}{10}.\end{aligned}

More generally:

Union Bound

If some event has probability $p$ , then after $n$ attempts, the probability of observing the event in any of the trials is at most $np$ .

Strategies For Probability

If $A$ is an event, then we write $\PR{\lnot A}$ to refer to the event that $A$ doesn't happen. The two probabilities $\PR{A}$ and $\PR{\lnot A}$ satisfy the following relationship:

\PR{A} = 1 - \PR{\lnot A}.

Often one of $\PR{A}$ and $\PR{\lnot A}$ is much easier to reason about.

Example A.2.7 (Analyze the complementary probability)

I roll a six-sided die, six times. What is the probability that I see some outcome more than once? Let's think about all the ways this could happen. Well, two of the rolls could be 1, or three of rolls could be 1, or all of them could be 1, two of them could be 1 and the rest could be 2, and so on. Wait, am I double-counting repeated 2s and repeated 1s? $\ldots$

An easier way to attack the problem is to focus on the complementary event, that all 6 rolls are distinct. The probability we care about is $1 - \PR{\text{all six rolls are distinct}}$ . All rolls are distinct if the sequence of dice rolls spell out a permutation of $\{1, \ldots, 6\}$ . There are $6! = 720$ such permutations, out of $6^6 = 46656$ total possible outcomes. Hence, the answer to the question is

\displaystyle 1 - \frac{6!}{6^6} = 1 - \frac{720}{46656} = \frac{45936}{46656} \approx 0.9846.

Another trick is to change the relative order of independent sampling events. If two values are sampled independently, then it makes no difference whether they are sampled simultaneously or sequentially, in either order. It can often be helpful to imagine that they are sampled sequentially, and to reason about probabilities from the perspective of an intermediate moment in time, after one value has been chosen/fixed but the other has not.

Example A.2.8 (Order independent events)

When rolling two six-sided dice, what is the probability that the dice match? Here is a standard (and totally correct way) to answer the question:

When rolling two six-sided dice, there are $6^2 = 36$ total outcomes (a pair of numbers), and each one has probability $1/36$ under a uniform distribution. There are six outcomes in which the dice match: both dice 1, both dice 2, both dice 3, and so on. Therefore, the probability of rolling matching dice is $6/36 = 1/6$ .

A different way to arrive at the answer goes like this:

Imagine I roll the dice sequentially, and I pause after rolling the first die but before rolling the second. The result of the first die has been fixed; let's call that value $d$ . The two dice will match only if another $d$ is rolled on the second die. Rolling this specific value of $d$ on the second die (indeed, rolling any particular value) happens with probability $1/6$ .

Linguistic Precision

Being “random” is not a property of a specific outcome, it is a property of the process that generates the outcome. It therefore doesn't make much sense to refer to a “random string.” Is 42 a random number? Is “heads” a random coin?

I try to use precise language in this book and avoid describing values as “random.” However, every cryptographer I know (yes, even your dear author) says things like “ $X$ is a random string” all the time to mean “ $X$ was chosen uniformly.” It's not a terrible sin to speak in this way, just keep in mind that this is merely a (lazy?) shortcut for a more precise meaning.

A.3. Modular arithmetic

Definition A.3.1 (Divisors)

When $x$ and $\nmod$ are integers, we say that $x$ divides $\nmod$ (equivalently, $x$ is a factor of $\nmod$ , and $\nmod$ is a multiple of $x$ ), and write $x \mid \nmod$ , if there exists an integer $k$ such that $\nmod = kx$ . When $x$ does not divide $\nmod$ , we write $x \nmid \nmod$ .

This definition applies to both positive and negative numbers (and to zero).

Example A.3.2 (Divisors)

\begin{aligned} 7 & \mid 84 & \text{because} && 84 & = 12 \cdot 7; \\ 7 & \mid 0 & \text{because} && 0 & = 0 \cdot 7; \\ 7 & \mid -77 & \text{because} && -77 & = (-11) \cdot 7; \\ -7 & \mid 42 & \text{because} && 42 & = (-6)\cdot (-7).\end{aligned}

Definition A.3.3 (Modular reduction)

Let $a$ and $\nmod$ be integers, with $\nmod$ positive. Then $a \pct \nmod$ (pronounced “ $a$ mod $\nmod$ ”) denotes the remainder after dividing $a$ by $\nmod$ . More formally, $a\pct \nmod$ is the unique value $r \in \{0, \ldots, \nmod-1\}$ such that $n \mid (a-r)$ .

Pay special attention to the fact that $a \pct \nmod$ is always a nonnegative number, even if $a$ is negative. A good way to remember how this works is:

Mnemonic For The Mod Operation

$a$ is $(a \pct \nmod)$ more than a multiple of $\nmod$ .

Not “closer to zero than” but “more than” a multiple of $\nmod$ .

Example A.3.4 (Modular reduction)

\begin{aligned} 21 \pct 7 & = 0 & \text{because} && 21 & = 3 \cdot 7 + \hl{0}; \\ 20 \pct 7 & = 6 & \text{because} && 20 & = 2 \cdot 7 + \hl{6}; \\ -20 \pct 7 & = 1 & \text{because} && -20 & = (-3) \cdot 7 + \hl{1}; \\ -1 \pct 7 & = 6 & \text{because} && -1 & = (-1) \cdot 7 + \hl{6}.\end{aligned}

In the third example, $-20$ is 1 more than $-21$ , which is a multiple of 7. In the fourth example, $-1$ is 6 more than $-7$ , which is a multiple of 7.

Unfortunately, some programming languages define $\pct$ for negative numbers as $(-a)\pct \nmod = -(a\pct \nmod)$ , so they would define $-20 \pct 7$ to be $-(20 \pct 7) = -6$ . This is clearly absurd, and it's about time we stood up to these programming language designers and smashed them over the head with some mathematical truth! For now, if you are experimenting using a programming language, be sure to check whether it defines $\pct$ in the correct way.

Definition A.3.5 (Integers mod

\nmod

)

For positive $\nmod$ , we write $\hl{\Z_\nmod} = \{0,\ldots, \nmod-1\}$ to denote the set of integers modulo $\nmod$ . These are the possible remainders that result when you divide by $\nmod.$

Definition A.3.6 (Modular congruence)

For positive $\nmod$ , we say that integers $a$ and $b$ are congruent modulo $\nmod$ , and write $a \equiv_\nmod b$ , if $\nmod \mid (a-b)$ . An alternative definition is that $a \equiv_\nmod b$ if and only if $a \pct \nmod = b \pct \nmod.$

It's important to appreciate the (subtle) distinction between $a \equiv_\nmod b$ and $a = b \pct \nmod$ :

Example A.3.7 (Important distinction)

$99 \equiv_{10} 19$ is true, because $10$ divides $99-19$ . Neither side of the equation (congruence) are from the set $\Z_{10}$ , and that's fine.

$99 = 19 \pct 10$ is false. The right-hand side evaluates to the integer $9$ . The equals-sign compares equality as integers; $99$ and $9$ are different integers.

Expressions like $a \equiv_\nmod b$ make sense for any $a, b$ (including negative!), but expressions like $a = b \pct \nmod$ make sense only if $a \in \Z_\nmod.$

In other resources you might see the notation “ $a \equiv b ~(\text{mod}~\nmod)$ ” instead of “ $a \equiv_\nmod b$ .” I dislike this notation because “ $(\text{mod}~\nmod)$ ” is easily mistaken for an operation or action that affects only the right-hand side of the equation. In reality, it modifies the entire expression $a \equiv b$ . Even though subscripts on the $\equiv$ symbol look weird at first, I think it's worth it.

Definition A.3.8 (Common divisors)

If $d \mid x$ and $d \mid y$ , then $d$ is a common divisor of $x$ and $y$ . The largest possible such $d$ is called the greatest common divisor (GCD), denoted $\gcd(x,y)$ . If $\gcd(x,y)=1$ , then we say that $x$ and $y$ are relatively prime.

The recursive algorithm that we still use today to compute GCDs was first described by Euclid around 300bce. It is widely regarded as the first numerical algorithm:

// Euclid's algorithm:

\subname{gcd}(x,y)

y=0

then return

x

else return

\subname{gcd}(y, x \pct y)

Strategies For Modular Arithmetic:

You may often need to compute a value like:

(\text{some complicated arithmetic expression}) \pct \nmod.

The straightforward way to evaluate this expression is to first compute the value of the complicated expression over the integers, then reduce the answer mod $\nmod$ . You'll get the correct answer this way, but there's often a better choice.

The Best Trick For Modular Arithmetic

If you need to know the final result mod $\nmod$ , then you can/should simplify intermediate values mod $\nmod$ as you go. You'll get the same answer, but usually with less effort.

Example A.3.9 (Simplify intermediate values)

Consider the expression:

(6 \cdot 7 \cdot 8 \cdot 9 \cdot 10) \pct 11.

The unsophisticated way of computing this value is:

(6 \cdot 7 \cdot 8 \cdot 9 \cdot 10) \pct 11 = 30240 \pct 11 = 1.

Those of us who don't want to compute $6\cdot7\cdot8\cdot9\cdot10$ in our heads can reduce the intermediate results mod 11 as we go:

\begin{aligned} 6 \cdot 7 \cdot 8 \cdot 9 \cdot 10 &=\phantom{{}_{11}} (42) \cdot 8 \cdot 9 \cdot 10 \\ &\equiv_{11} {}\hl{9} \cdot 8 \cdot 9 \cdot 10 \\ &=\phantom{{}_{11}} (72) \cdot 9 \cdot 10 \\ &\equiv_{11} {}\hl{6} \cdot 9 \cdot 10 \\ &=\phantom{{}_{11}} (54) \cdot 10 \\ &\equiv_{11} {}\hl{10} \cdot 10 \\ &=\phantom{{}_{11}} 100 \\ &\equiv_{11} 1.\end{aligned}

“Simplify” doesn't always mean “reduce mod $\nmod$ ,” resulting in a number from $\Z_\nmod$ . It means to replace one value with a congruent value that is easier to work with. Often a negative number is more favorable than a positive one:

Example A.3.10 (Simplify intermediate values)

Here's another way to evaluate the expression from the previous example:

\begin{aligned} 6 \cdot 7 \cdot 8 \cdot 9 \cdot 10 &\equiv_{11} (-5) \cdot (-4) \cdot (-3) \cdot (-2) \cdot (-1) \\ &=\phantom{{}_{11}} {- 5} \cdot 4 \cdot 3 \cdot 2 \\ &=\phantom{{}_{11}} {-120} \\ &=\phantom{{}_{11}} {-121} + 1 \\ &\equiv_{11} 0 + 1 = 1 .\end{aligned}

Example A.3.11 (Simplify mod

\nmod

)

I can compute $7^{500} \pct 8$ in my head, by noticing that $7 \equiv_{8} -1$ . Therefore:

7^{500} \equiv_8 (-1)^{500} = 1.

I can quickly compute $89^2 \pct 99$ in my head, although I have not memorized the integer $89^2$ . I simply notice that $89 \equiv_{99} -10$ and compute this way:

89^2 \equiv_{99} (-10)^2 = 100 \equiv_{99} 1 .

A.4. Exponents and logarithms

You probably learned (and then forgot) these identities in middle school or high school:

\begin{aligned} x^a \cdot x^b &= x^{a+b}, \\ (x^a)^b &= x^{ab}, \\ \log_x (ab) &= \log_x a + \log_x b, \\ a \log_x b &= \log_x (b^a).\end{aligned}

Never ever ever write $x^a \cdot x^b = x^{ab}$ . If you do, your cryptography instructor will realize that life is too short, immediately resign from teaching, and join a traveling circus. But not before changing your grade in the course to a zero. Harsh, maybe, but fair.

A.5. Big- $O$

Big- $O$ notation describes the “shape” of a function as it approaches infinity.

Definition A.5.1 (Big-

O

)

A function $f(n)$ is in the set $O(g(n))$ if there exists $c$ and $n_0$ such that for all $n>n_0$ we have $f(n) \le c \cdot g(n)$ . In other words, $c \cdot g(n)$ eventually (after $n_0$ ) overtakes $f(n)$ .

Example A.5.2

$f(n) = 3n^2 + 4 n - 10$ is $O(n^3)$ because:

\begin{aligned} f(n) = 3n^2 + 4n - 10 &\le 3n^2 + 4n \\ &\le 3n^2 + n^2 & \text{(for all $n \ge 4$)} \\ &\le 4n^2,\end{aligned}

so the definition of $O(n^3)$ is satisfied with $n_0=4$ and $c=4$ .

We could have also written:

\begin{aligned} f(n) = 3n^2 + 4n - 10 &\le 3n^2 + 4n \\ &\le 3n^2 + 4n^2 & \text{(for all $n \ge 1$)} \\ &\le 7n^2,\end{aligned}

so the definition of $O(n^3)$ is satisfied with $n_0=1$ and $c=7$ .

A.6. Linear algebra

A matrix is a 2-dimensional grid of scalar values. An $n \times m$ matrix has $n$ rows and $m$ columns. The example below is a $2 \times 3$ matrix:

\begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix}

A vector is, according to our conventions, a matrix with one column. If $\vec x = (x_1, \ldots, x_n)^\top$ and $\vec y = (y_1, \ldots, y_n)^\top$ , then their inner product, written $\vec x^\top \vec y$ , is defined to be:

\vec x^\top \vec y = \sum_{i=1}^n x_i y_i.

If $\mat A$ is an $n \times m$ matrix and $\mat B$ is a $m \times k$ matrix, then their product $\mat A \mat B$ is an $n \times k$ matrix, and its value at row $i$ and column $j$ is the inner product of the $i$ -th row of $\mat A$ with the $j$ -th column of $\mat B$ .

The transpose of a matrix $\mat A$ , written as $\mat A^\top$ , is what results by reflecting it across its main diagonal. For example:

\begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix}^\top = \begin{bmatrix} 1 & 4 \\ 2& 5 \\ 3 & 6 \end{bmatrix}

The transpose of an $n \times m$ matrix is an $m\times n$ matrix. The transpose operation satisfies the following important properties:

\begin{aligned} (\mat A\mat B)^\top &= \mat B^\top \mat A^\top , \\ (\mat A^\top)^\top &= \mat A.\end{aligned}

Exercises

Carefully use the algebraic properties of xor to derive the following useful fact, for strings $A,B,C \in \bits^n$ :

$A = B \oplus C \iff B = A \oplus C \iff C = A \oplus B.$

In other words, if you know any two of the values in the equation “ $A = B \oplus C$ ”, then you can solve for the third.
What is the result of xor'ing every $n$ -bit string? For example, the expression below is the xor of every 5-bit string:

$\bit{00000} \oplus \bit{00001} \oplus \bit{00010} \oplus \bit{00011} \oplus \cdots \oplus \bit{11110} \oplus \bit{11111}.$

Give a convincing justification for your answer.
Compute the exact probability described in example A.2.6.
Consider rolling several $d$ -sided dice, where the sides are labeled $\{1, \ldots, d\}$ .
1. When rolling two of these dice, what is the probability of rolling a pair of 1s?
2. When rolling two of these dice, what is the probability that they don't match?
3. When rolling three of these dice, what is the probability that they all match?
4. When rolling three of these dice, what is the probability that they don't all match (including the case where two match)?
5. When rolling three of these dice, what is the probability that at least two of them match (including the case where all three match)?
6. When rolling three of these dice, what is the probability of seeing at least one 1?
h What is $[0 + 1 + 2 + \cdots + (\nmod-2) + (\nmod-1)] \pct \nmod$ ? The answer might depend on whether $\nmod$ is even or odd.

Rearrange the terms of the sum so that you get many values that are “favorable” mod $\nmod$ .
What is $(-99) \pct 10$ ?
Without using a calculator, what are the last two digits of $42798^6$ ? Start by translating “what are the last two digits” into a question about modular arithmetic.
Without using a calculator, what is $1000! \pct 427$ ? That's not me being excited about the number one thousand, it's one thousand factorial!
Which values $x \in \Z_{11}$ satisfy $x^2 \equiv_{11} 5$ ? Which satisfy $x^2 \equiv_{11} 6$ ?

Over the integers, $x^2 = (-x)^2$ . How is this fact reflected when working mod 11?
Rewrite each of these expressions as something of the form $2^x$ .
1. $\left(2^n \right)^n = {\text{??}}$
2. $2^n + 2^n = {\text{??}}$
3. $(2^n)(2^n) = {\text{??}}$
4. $(2^n)/2 = {\text{??}}$
5. $\sqrt{2^n} = {\text{??}}$
6. $\left(2^n\right)^2 = {\text{??}}$

Chapter Notes

It is possible to give sense to statements like “ $X$ is a random string” using the methodology of Kolmogorov complexity. See [146] for a comprehensive reference.

Euclid described the GCD algorithm in Book 7 of his famous Elements. He was likely not the first to discover the algorithm.

Next Chapter1. One-Time Pad and the Provable Security Mindset