CO487

Professor: Alfred Menezes | Term: Fall 2024

Chapter 1: Introduction to Cryptography

Cryptography is about securing communications in the presence of malicious adversaries.

Alice and Bob are communicating via an unsecured channel. Eve is eavesdropping (malicious). Communication should be

• Confidential: Keep data secret from everyone not authorized to see it.
• Data Integrity: Ensure data is not altered by others.
• Data Origin Authentication: Corroborating the source of data.
• Non-Repudiation: Preventing an entity from denying previous commitments or actions.

Transport Layer Security (TLS): The cryptographic protocol used by web browsers to securely communicate with websites (e.g. Facebook, Gmail).

TLS is used to assure an individual user of the authenticity of the website and establish a secure communications channel.

Symmetric-Key Cryptography: The client and server a priori share some secret information $k$ called a key.

They can encrypt their messages with AES and authenticate the resulting ciphertexts with HMAC.

Question

How do Alice and Bob share the shared secret $k$?

Public-key cryptography: The client and server a priori share some authenticated (but non-secret) information.

To establish a secret key, Alice selects the secret session key $k$, and encrypts it with Bob’s RSA public key. Then only Bob can decrypt the resulting ciphertext with its RSA private key to recover $k$.

Question

How does Alice obtain an authentic copy of Bob’s RSA public key?

Bob cannot send it to Alice over the internet because it can be intercepted.

Signature scheme: Bob’s RSA public key is signed by a Certification Authority (CA) using its secret signing key with the RSA signature scheme.

Alice can verify the signature using the CA’s RSA public verification key. In this way, Alice obtains an authentic copy of Bob’s RSA public key.

The CA’s RSA public key is embedded in Alice’s browser.

TLS potential vulnerabilities:

• The cryptography is weak
• Cryptography can be broken using quantum computers
• Weak random number generation
• Issuance of fraudulent certificates
• Software bugs
• Phishing attacks
• TLS only protects data during transit. It does not protect data stored at the server

Definition

Cybersecurity is comprised of the concepts, technical measures, and administrative measures used to protect networks, computers, programs and data from deliberate or inadvertent unauthorized access, disclosure, manipulation, or use.

Cryptography $\ne$ Cybersecurity. Cryptography provides some mathematical tools that can assist with the provision of cybersecurity services. It is a small part of a complete security solution.

Security is a chain; weak links become targets.

Chapter 2: Symmetric-Key Encryption

Fundamental Concepts

Definition

Asymmetric-key encryption scheme (SKES) consists of:

• $M$ - the plaintext space,
• $C$ - the ciphertext space,
• $K$ - they key space,
• a family of encryption functions $E_k:M\to C,\forall k\in K$,
• a family of decryption functions $D_k:C\to M,\forall k\in K$,

such that $D_k(E_k(m))=m$ for all $m\in M,k\in K$.

1. Alice and Bob agree on a secret $k\in K$ communicating over the secured channel
2. Alice computes $c=E_k(m)$ and sends the ciphertext $c$ to Bob over the unsecured channel.
3. Bob retrieves the plaintext by computing $m=D_k(c)$

Note: The secret key $k$ might be used for a fixed time interval, or it might be used a fixed number of times.

Called symmetric-key encryption since the same key is used for encryption and decryption.

The Enigma and Lorenz Machines are examples.

Substitution Cipher

• $M=$ all English messages
• $C=$ all encrypted messages
• $K=$ all permutations of the English alphabet.
• $E_k(m):$ Apply permutation $k$ to $m$, one letter at a time
• $D_k(c):$ Apply the inverse permutation $k^{-1}$ to $c$, one letter at a time

Security Model: Defined the computational abilities of the adversary, and how she interacts with the communicating parties.

Convention: We will always strive to model maximal adversary capabilities and minimal adversary goals.

Basic assumption: The adversary knows everything about the SKES, except the particular key $k$ chosen by Alice and Bob. Avoid security by obscurity.

Computational power of the adversary:

• Information-theoretic security: Eve has infinite computational resources
• Complexity-theoretic security: Eve is a “polynomial-time Turing machine”
• Computational security: Eve has a bounded amount of computational power. We say Eve is computationally bounded.

Passive Attacks:

• Ciphertext-only attack: The adversary knows some ciphertext
• Known-plaintext attack: The adversary also knows some plaintext and the corresponding ciphertext. Active Attacks:
• Chosen-plaintext attack: The adversary can also choose some plaintext and obtains the corresponding ciphertext
• Clandestine attacks: bribery, blackmail (not covered in this course)

Adversary’s goal

1. Recover the secret key $k$
2. Systematically recover plaintext from ciphertext, without necessarily learning $k$.
3. Learn some partial information about the plaintext from the ciphertext, other than its length

If the adversary can achieve 1 or 2, the SKES is said to be totally insecure.

If the adversary cannot learn any partial information about the plaintext from the ciphertext, the SKES is said to be partially secure.

Definition

A symmetric-key encryption scheme is said to be secure if it is semantically secure against chosen-plaintext attack by a computationally bounded adversary.

To break a symmetric-key encryption scheme, the adversary has to accomplish the following:

1. The adversary is given a challenge ciphertext $c$
2. During its computation, the adversary can select arbitrary plaintext and obtain the corresponding ciphertexts
3. After a feasible amount of computation, the adversary obtains some information about the plaintext $m$ corresponding to $c$.

Desirable properties of a SKES

1. Efficient algorithms should be known for computing $E_k$ and $D_k$.
2. The secret key $k$ should be small, but large enough to render exhaustive key search infeasible.
3. The scheme should be secure.
4. The scheme should be secure even against the designer of the system.

The simple substitution cipher is totally insecure against a chosen-plaintext attack.

Is exhaustive key search possible?

Number of keys to try is $26!\approx 4\times 10^{26}\approx 2^{88}$. This will take too long, even with many computers.

In this course:

• $2^{40}$ operations is considered very easy.
• $2^{56}$ operations is considered easy.
• $2^{64}$ operations is considered feasible.
• $2^{80}$ operations is considered barely feasible.
• $2^{128}$ operations is considered infeasible.

The Bitcoin network is performing about $2^{80}$ hash operations per hour.

Definition

A cryptographic scheme is said to have a security level of $\ell$ bits if the fastest known attack on the scheme takes approximately $2^{\ell }$ operations. A security level of $128$ bits is desirable in practice.

Simple frequency analysis of ciphertext letters can be used to recover the secret key.

Vigenere Cipher

The secret key is an English word having no repeated letters, e.g. $k=$ CRYPTO. We sum each letter in $m$ by $k$ to get $c$. Here $A=0,B=1,\dots ,Z=25$, and addition of letters is module $26$. Decryption is subtraction module $26:m=c-k$.

The Vigenere cipher is totally insecure against a chosen-plaintext attack.

It is also insecure against a cipher-text only attack.

Stream Ciphers

A stream cipher is a SKES that encrypts the plaintext one bit at a time. A block cipher is a SKES that encrypts the plaintext one block at a time.

One-time Pad

The secret key is a random string of letters with the same length as the message. We use the same process as the Vigenere.

The key should not be reused. If $c_1=m_1+k$ and $c_2=m_2+k$, then $c_1-c_2=(m_1+k)-(m_2+k)=m_1-m_2$. So, $c_1-c_2$ depends only on the plaintext (and not on the key $k$), and hence can leak information.

Convention: From now on, messages and keys will be assumed to be bit (binary) strings.

Notation: $\oplus$ is bitwise exclusive-or (XOR) (bitwise addition mod $2$).

Example

$1011001011\oplus 1001001001=0010000010$

Note that $x\oplus x=0,x\oplus y=y\oplus x$

So, for the one-time pad, encryption is $c=m\oplus k$ and decryption is $m=c\oplus k$.

Perfect secrecy: The one-time pad is semantically secure against ciphertext-only attack by an adversary with infinite computational resources.

This can be formally proven using concepts from information theory. Shannon proved that if plaintexts are $\ell$-bit strings, then any symmetric-key encryption with perfect secrecy must have $|K|\ge 2^{\ell }$. So perfect secrecy is useless in practice.

Basic Idea: Instead of using a random key in the one-time pad, use a “pseudorandom” key.

Definition

A pseudorandom bit generator (PRBG) is a deterministic algorithm that takes as input a (random) seed, and outputs a longer “pseudorandom” sequence called the keystream.

Stream cipher: uses a PRGB for encryption. The seed is the secret key shared by Alice and Bob.

No more perfect secrecy - security depends on the quality of the PRBG.

For a stream cipher to be secure:

• Indistinguishability requirement: The keystream should be “indistinguishable” from a random sequence.
• Unpredictability requirement: Given portions of the keystream, it should be computationally infeasible to learn any information about the remainder of the keystream
  • If an adversary knows a portion $c_1$ of ciphertext and the corresponding plaintext $m_1$, then she can easily find the corresponding portion $k_1=c_1\oplus m_1$ of the keystream.

Aside: Don’t use UNIX random number generators rand and srand for cryptographic purposes.

Now we introduce the ChaCha20 stream cipher. Designed by Dan Bernstein in 2008, the ChaCha20 is conceptually very simple. It is extremely fast in software an does not require and special hardware. No security weaknesses have been found.

Notation:

• $256-$bit $k=(k_1,k_2,k_3,\dots ,k_8)$
• $128-$bit constant $f=(f_1,f_2,f_3,f_4)$
• $96-$bit nonce $n=(n_1,n_2,n_3)$
• $32-$bit counter $c$
• A hexadecimal digit is a $4-$bit number.
  • $f_1=0x61707865$
  • $f_2=0x3320646e$
  • $f_3=0x79622d32$
  • $f_4=0x6b206574$
• A nonce is a non-repeating quantity

The initial state is:

$$\begin{array}{r}\left[\begin{array}{cccc}{f}_1& f_2& f_3& f_4\\ k_1& k_2& k_3& k_4\\ k_5& k_6& k_7& k_8\\ c& n_1& n_2& n_3\end{array}\right]=\left[\begin{array}{cccc}{S}_1& S_2& S_3& S_4\\ S_5& S_6& S_7& S_8\\ S_9& S_{10}& S_{11}& S_{12}\\ S_{13}& S_{14}& S_{15}& S_{16}\end{array}\right]\end{array}$$

More Notation:

• $\oplus :$ xor
• $⊞:$ integer addition module $2^{32}$
• $<<<t:$ left-rotation by $t$ positions

Define $QR$: Quarter Round Function

Input: Four $32$-bit words $a,b,c,d$

$$\begin{array}{rl}& a\leftarrow a⊞b,d\leftarrow d\oplus a,d\leftarrow d<<<16\\ & c\leftarrow c⊞d,b\leftarrow b\oplus c,b\leftarrow b<<<12\\ & a\leftarrow a⊞b,d\leftarrow d\oplus a,d\leftarrow d<<<8\\ & c\leftarrow c⊞d,b\leftarrow b\oplus c,b\leftarrow b<<<7\end{array}$$

Output: $a,b,c,d$

ChaCha20 Keystream Generator

Select a nonce $n$ and initialize the counter $c$ to $0$. While keystream bytes are required do:

• Create the initial state $S$, and make a copy $S^{\prime }$ of $S$.
• Update $S$ by repeating the following $10$ times:
  • $QR(S_1,S_5,S_9,S_{13}),QR(S_2,S_6,S_{10},S_{14}),QR(S_3,S_7,S_{11},S_{15})$
  • $QR(S_4,S_8,S_{12},S_{16})QR(S_1,S_6,S_{11},S_{16}),QR(S_2,S_7,S_{12},S_{13})$
  • $QR(S_3,S_8,S_9,S_{14}),QR(S_4,S_5,S_{10},S_{15})$
• Output $S\oplus S^{\prime }$ ($64$ keystream bytes).
• Increment the counter $c$

Encryption: The keystream bytes are xored with the plaintext bytes to produce ciphertext bytes. The nonce is appended to the ciphertext.

Block Ciphers: DES

Definition

A block cipher is a symmetric-key encryption scheme that breaks up the plaintext into blocks of a fixed length (e.g. $128$ bits), and encrypts the blocks one at a time.

In contrast, a stream cipher encrypts the plaintext one character (usually a bit) at a time.

A historically important example of a block cipher is the Data Encryption Standard (DES):

flowchart LR
key
key -- 56 bits --> DES
plaintext -- 64 bits --> DES
DES -- 64 bits --> ciphertext

Key length: $56$ bits, size of key space: $2^{56}$, block length: $64$ bits.

Design principles articulated by Claude Shannon

Security:

1. Diffusion: Each ciphertext bit should depend on all plaintext bits.
2. Confusion: The relationship between key and ciphertext bits should be complicated.
3. Key length: Should be small, but large enough to preclude exhausting key search.

Efficiency:

1. Simplicity: Easier to implement and analyze.
2. Speed: High encryption and decryption rates.
3. Platform: Suitable for hardware and software.

The design principles of DES are still classified.

DES Problem #1: Small key size

Exhaustive search on the key space takes $2^{56}$ operations and can easily be parallelized.

DES Problem #2: Small block size

If plaintext blocks are distributed uniformly at random, then the expected number of ciphertext blocks observed before a collision occurs is $\approx 2^{32}$. This is by the birthday paradox.

Birthday paradox: Suppose that an urn contains $n$ numbered balls. Suppose that balls are drawn from the urn, one at a time, with replacement. The expected number of draws before a ball is selected for the second time (called a collision) is approximately $\sqrt{\pi n/2}\approx \sqrt{n}$.

Thus the ciphertext reveals some information about the plaintext.

Block Ciphers: Triple-DES

Recall: The only substantial weaknesses known in DES are the obvious ones: small key length and small block length.

Question

How can one construct a more secure block cipher from DES?

Multiple encryption: Re-encrypt the ciphertext one or more times using independent keys. Hope that this increases the effective key length.

Note: Multiple encryption does not necessarily result in increased security.

Example

If $E_{\pi }$ denotes the encryption function for the simple substitution cipher with the key $\pi$, then $E_{{\pi }_2}\circ E_{{\pi }_1}$ any more secure than $E_{\pi }$?

No, since $E_{{\pi }_2}\circ E_{{\pi }_1}=E_{{\pi }_2\circ {\pi }_1}$

Encryption is: $c=E_{k_2}(E_{k_1}(m))$, where $E=$ DES decryption.

The Double-DES key length is $\ell =112$ bits, so exhaustive key search takes $2^{112}$ operations.

Note: The block length is unchanged ($64$ bits).

Meet-in-the-middle Attack on Double-DES

Input: 3 plaintext/ciphertext pairs $(m_1,c),(m_2,c_2),(m_3,c_3)$ Output: The secret key $(k_1,k_2)$

1. For each $h_2\in \{0,1{\}}^{56}$ do: a. Compute $E_{h_2}^{-1}(c_1)$ and store $[E_{h_2}^{-1}(c_1),h_2]$
2. For each $h_1\in \{0,1{\}}^{56}$ do:
3. Compute $E_{h_1}(m_1)$
4. Search for $E_{h_1}(m_1)$ in the table
5. For each match $[E_{h_2}^{-1}(c_1),h_2]$ in the table:
   1. Check if $E_{h_2}(E_{h_1}(m_2))=c_2$; if so then:
      1. Check if $E_{h_2}(E_{h_1}(m_3))=c_3$; if so then:
         1. Output$(h_1,h_2)$ and STOP.

The main idea is that $c=E_{k_2}(E_{k_1}(m))⟺E_{k_2}^{-1}(c)=E_{k_1}(m)$

Question

How many plaintext/ciphertext pairs are needed for unique key determination?

Let $E$ be a block cipher with key space $K=\{0,1{\}}^{\ell }$, and plaintext and ciphertext space $\{0,1{\}}^L$.

Let $k^{\prime }\in K$ be the secret key chosen by Alice and Bob, and let $(m_i,c_i),1\le i\le t$, be known plaintext/ciphertext pairs where the plaintext $m_i$ are distinct.

Question

So how large should $t$ be to ensure that there is only one key $k\in K$ for which $E_k(m_i)=c_i$ for all $1\le i\le t$?

We select $t$ so that $FK\approx 0$ where $FK$ is the expected number of false keys.

For each $k\in K$, the encryption function $E_k:\{0,1{\}}^L\to \{0,1{\}}^L$ is a permutation (bijection).

We make the heuristic assumption that for each $k\in K,E_k$ is a random function, i.e. a randomly selected function. This assumption is certainly false since $E_k$ is not random, and because a random function is almost certainly not a permutation.

Now, fix $k\in K,k\ne k^{\prime }$.

The probability that $E_k(m_i)=c_i$ for all $1\le i\le t$ is $\underset{t}{\underbrace{\frac{1}{2^L}\cdot \frac{1}{2^L}\cdots \frac{1}{2^L}}}=\frac{1}{2^{Lt}}$ Thus, the expected number of false keys $k\in K$ for which $E_k(m_i)=c_i$ for all $1\le i\le t$ is $FK=\frac{2^{\ell }-1}{2^{Lt}}$

Time: The number of DES operations is $\approx 2^{56}+2^{56}+2\cdot 2^{48}+2(1+\frac{1}{2^{16}})\approx 2^{57}$

The security level of Double-DES is 57 bits, so Double-DES is not much more secure than DES.

A Triple-DES secret key is $k=(k_1,k_2,k_3)$, where $k_1,k_2,k_3{\in }_R\{0,1{\}}^{56}$

Encryption is: $c=E_{k_3}(E_{k_2}(E_{k_1}(m)))$, where $E=$ DES encryption.

flowchart LR
k1
k2
k3
id1[DES]
id2[DES]
id3[DES]
k1 --> id1
k2 --> id2
k3 --> id3
m -- 64 bits --> id1
id1 -- 64 bits --> id2
id2 -- 64 bits --> id3 
id3 -- 64 bits --> c

Decryption is: $m=E_{k_1}^{-1}(E_{k_2}^{-1}(E_{k_3}^{-1}(c)))$, where $E^{-1}=$ DES decryption.

The Triple-DES key length is $\ell =168$ bits, so exhaustive key search takes $2^{168}$ operations (infeasible).

Meet-in-the-middle attack takes $\approx 2^{112}$ operations. So the security level of Triple-DES is 112 bits.

Block Ciphers: AES

The Advanced Encryption Standard (AES)

Key lengths: $128$, $192$ and $256$ bits.

Block length: $128$ bits

2024: No attacks have been found on AES that are faster than exhaustive key search.

AES is an example of a substitution-permutation network.

Definition

A substitution-permutation network (SPN) is an iterated block cipher where a round consists of a substitution operation followed by a permutation operation

Components of an SPN cipher:

• $n$: the block length (in bits)
• $\ell$: the key length (in bits)
• $h$: the number of rounds
• A fixed invertible function $S:\{0,1{\}}^b\to \{0,1{\}}^b$ called substitution, where $b$ is a divisor of $n$.
• A fixed permutation $P$ on $\{1,2,\dots ,n\}$.
• A key scheduling algorithm that determines subkeys $k_1,k_2,\dots ,k_h,k_{h+1}$ from a key $k$. Note: $n,\ell ,h,S,P$ and the key scheduling algorithm are public.

The encryption looks like: $A\leftarrow$ plaintext for $i=1,2,\dots ,h$ do $A\leftarrow A\oplus k_i$ $A\leftarrow S(A)$ $A\leftarrow P(A)$ $A\leftarrow A\oplus k_{h+1}$ ciphertext $\leftarrow A$

Decryption is the reverse of encryption.

AES is an SPN, where the permutation operation is comprised of two invertible linear transformations.

All operations are byte oriented, e.g., $b=8$ so the $S-$box maps $8$ bits to $8$ bits. This facilitates fast implementations on software platforms.

The block length of AES is $n=128$. Each subkey is $128$ bits.

AES accepts three key lengths. The number of rounds $h$ depends on the key length.

Each round updates a variable called State which consists of a $4\times 4$ array of bytes (note $4\times 4\times 8=128$, the block length).

State is initialized with the plaintext.

Add AES round uses four invertible operations:

1. AddRoundKey (key-mixing)
2. SubBytes (S-box)
3. ShiftRows (permutation)
4. MixColumns (linear transformation)

After $h$ rounds are completed, a final subkey is XORed with State, the result being the ciphertext.

Definition

The elements of the finite filed $GF(2^8)$ are the polynomials of degree at most $7$ in ${\mathbb{Z}}_2[y]$, with addition and multiplication performed module the irreducible polynomial $f(y)=y^8+y^4+y^3+y+1$ (${\mathbb{Z}}_2[y]$ is the set of polynomials in $y$ with coefficients from ${\mathbb{Z}}_2$). We interpret an $8-$bit string $a=a_7{a}_6{a}_5\cdots a_1{a}_0$ as coefficients of the polynomial $a(y)=a_7{y}^7+a_6{y}^6+a_5{y}^5+\cdots +a_{1}y+a_0$ and vice versa.

Example

Let $a=11101100=ec$ and $b=00111011=3b$, so $a(y)=y^7+y^6+y^5+y^3+y^2$ and $b(y)=y^5+y^4+y^3+y+1$.

Addition: $a(y)+b(y)=y^7+y^6+y^4+y^2+y+1$, so $ec+3b=d7$.

Multiplication: $a(y)\cdot b(y)=y^{12}+y^{10}+y^8+y^4+y^2$, which leaves a remainder of $r(y)=y^7+y^6+y^3$ upon division by $f(y)$. Hence $a\cdot b=$ $11001000$ in $GF(2^8)$, or $ec\cdot 3b=c8$.

Inversion: $e{c}^{-1}=5d,$ since $ec\cdot 5d=01$.

Definition (S-box)

Let $p\in \{0,1{\}}^8$, and consider $p$ as an element of $GF(2^8)$.

1. Let $q=p^{-1}$ if $p\ne 0$, and $q=p$ if $p=0$
2. Define $q=(q_7{q}_6{q}_5\cdots q_1{q}_0)$
3. Compute

$$\begin{array}{r}S(p)=r=\left(\begin{array}{c}{r}_0\\ r_1\\ r_2\\ r_3\\ r_4\\ r_5\\ r_6\\ r_7\end{array}\right)=\left(\begin{array}{cccccccc}1& 0& 0& 0& 1& 1& 1& 1\\ 1& 1& 0& 0& 0& 1& 1& 1\\ 1& 1& 1& 0& 0& 0& 1& 1\\ 1& 1& 1& 1& 0& 0& 0& 1\\ 1& 1& 1& 1& 1& 0& 0& 0\\ 0& 1& 1& 1& 1& 1& 0& 0\\ 0& 0& 1& 1& 1& 1& 1& 0\\ 0& 0& 0& 1& 1& 1& 1& 1\end{array}\right)=\left(\begin{array}{c}{q}_0\\ q_1\\ q_2\\ q_3\\ q_4\\ q_5\\ q_6\\ q_7\end{array}\right)+\left(\begin{array}{c}1\\ 1\\ 0\\ 0\\ 0\\ 1\\ 1\\ 0\end{array}\right)\end{array}$$

4. Then $S(p)=r=(r_7{r}_6{r}_5\cdots r_1{r}_0)$

ShiftRows: Permute the bytes of State by applying a cyclic shift to each row.

MixColumns:

1. Read column $i$ of State as a polynomial $(a_{0,i},a_{1,i},a_{2,i},a_{3,i})=a_{0,i}+a_{1,i}x+a_{2,i}{x}^2+a_{3,i}{x}^3$ (interpret the coefficients as elements of the finite field $GF(2^8)$.
2. Multiply this polynomial with the constant polynomial with the constant polynomial $c(x)=02+01x+01x^2+03x^3$ and reduce module $x^4-1$. This gives a new polynomial $b_{0,i}+b_{1,i}x+b_{2,i}{x}^2+b_{3,i}{x}^3$

The $\oplus c(x)$ operation.

Let $a(x)=a_0+a_{1}x+a_2{x}^2+a_3{x}^3$, where each $a_i\in GF(2^8)$.

Let $c(x)=02+01x+01x^2+03x^3$, where 01, 02, 03 are elements in $GF(2^8)$ (written in hex).

To compute $a(x)\oplus c(x)$ do:

• Compute $d(x)=a(x)\times c(x)$ (polynomial multiplication where coefficient arithmetic is in $GF(2^8)$).
• Divide by $x^4-1$ to find the remainder polynomial $r(x)$. Equivalently, replace $x^4$ by $1$, $x^5$ by $x$, and $x^6$ by $x^2$, and simplify.
• Then $a(x)\oplus c(x)=r(x)$

AES Encryption

From the key $k$ derive $h+1$ subkeys $k_0,k_1,\dots k_h$.

State $\leftarrow$ plaintext

State $\leftarrow$ State $\oplus k_0$

for $i=1,2,\dots ,h-1$ do

	State ← SubBytes(State)
	State ← ShiftRows(State)
	State ← MixColumns(State)
	State ← State ⊕ k_i

State $\leftarrow$ SubBytes(State)

State $\leftarrow$ ShiftRows(State)

State $\leftarrow$ State $\oplus k_h$

ciphertext $\leftarrow$ State

AES Decryption

From the key $k$ derive $h+1$ subkeys $k_0,k_1,\dots ,k_h$

State $\leftarrow$ ciphertext

State $\leftarrow$ State $\oplus k_h$

State $\leftarrow$ InvShiftRows(State)

State $\leftarrow$ InvSubBytes(State)

for $i=h-1,\dots ,2,1$ do

	State ← State ⊕ k_i
	State ← InvMixColumns(State)
	State ← InvShiftRows(State)
	State ← InvSubBytes(State)

State $\leftarrow$ State $\oplus k_0$

plaintext $\leftarrow$ State

For 128-bit keys, AES has 10 rounds, so we need 11 subkeys.

• The first subkey is $k_0=(r_0,r_1,r_2,r_3)$ is the actual AES key.
• The second subkey is $k_1=(r_4,r_5,r_6,r_7)$
• The third subkey is $k_2=(r_8,r_9,r_{10},r_{11})$
• The eleventh subkey is $k_{10}=(r_{40},r_{41},r_{42},r_{43})$

The function $f_i:\{0,1{\}}^{32}\to \{0,1{\}}^{32}$ are defined as follows:

1. The input is divided into four bytes: $(a,b,c,d)$
2. Left-rotate the bytes: $(b,c,d,a)$
3. Apply the AES S-box to each byte: $(S(b),S(c),S(d),S(a))$
4. XOR the leftmost byte with the constant ${\ell }_i$, and output the result: $(S(b)\oplus {\ell }_i,S(c),S(d),S(a))$

The constants ${\ell }_i$ (in hex): ${\ell }_1=01,{\ell }_2=02,{\ell }_3=04,{\ell }_4=08,{\ell }_5=10,{\ell }_6=20,{\ell }_7=40,{\ell }_8=80,{\ell }_9=1b,{\ell }_{10}=36$

Modes of Operation

In practice, one usually wishes to encrypt a large quantity of data. The plaintext message is $m=m_1,m_2,\dots ,m_t$ where each $m_i$ is an $L-$bit block.

Question

How should we use a block cipher $E_k:\{0,1{\}}^L\to \{0,1{\}}^L$ to encrypt $m$?

Some modes of operation: ECB, CBC, CTR, GCM, CCM.

Suppose that the plaintext message is $m=m_1,m_2,\dots ,m_t$

Electronic Codebook Mode (ECB): encrypts the blocks independently, one at a time. Drawback: Identical plaintext result in identical ciphertext blocks.

Cipher Block Chaining (CBC) mode:

Encryption: Select $c_0{\in }_R\{0,1{\}}^L$ ($c_0$ is a random non-secret IV), and then compute $c_i=E_k(m_i\oplus c_{i-1})$ for $i=1,2,\dots ,t$. The ciphertext is $(c_0,c_1,c_2,\dots ,c_t)$.

Decryption: $m_i=E_k^{-1}(c_i)\oplus c_{i-1},$ for $i=1,2,\dots t$.

Identical plaintexts with different IVs result in different ciphertexts.

Chapter 3: Hash Functions

Fundamental Concepts

Hash functions play a fundamental role in cryptography. They are used in a variety of cryptographic primitives and protocols.

They are very difficult to design because of stringent security and performance requirements.

The most commonly used hash functions are:

• SHA-1
• SHA-2 family: SHA-224, SHA-256, SHA-384, SHA-512
• SHA-3 family

SHA-256

SHA-256: $\{0,1{\}}^{\ast }\to \{0,1{\}}^{256}$ SHA-256(“Hello there”) = $\text{0x4e47826698bb4630fb4451010062fadbf85d61427cbdfaed7ad0f23f239bed89}$

Definition

A hash function is a mapping $H$ such that:

1. $H$ maps binary messages of arbitrary lengths $\le L$ to outputs of a fixed length $n$: $H:\{0,1{\}}^{\le L}\to \{0,1{\}}^n$. ($L$ is usually large, e.g., $L=2^{64}$, whereas $n$ is small, e.g. $n=256$)
2. $H(x)$ can be efficiently computed for all $x\in \{0,1{\}}^{\le L}$

$H$ is called an $n-$bit hash function. $H(x)$ is called the hash or message digest of $x$.

Notes:

• The description of a hash function is public; there are no secret keys.
• For simplicity, we will usually write $\{0,1{\}}^{\ast }$ instead of $\{0,1{\}}^{\le L}$
• More generally, a hash function is an efficiently computable function from a set $S$ to a set $T$.

Consider $H:\{0,1{\}}^{\le 4}\to \{0,1{\}}^2$ to be a hash function mapping a bitstring to its last two digits.

$1001$ is a preimage of $01$.

$H(01,1001)$ is a collision. $01$ is a second preimage of $1011$.

Hash functions are used in all kind of applications. One reason for the widespread use of hash functions is speed.

Definition

A hash function $H:\{0,1{\}}^{\ast }\to \{0,1{\}}^n$ is preimage resistant if, given a hash value $y{\in }_R\{0,1{\}}^n$, it is computationally infeasible to find (with non-negligible success probability) any $x\in \{0,1{\}}^{\ast }$ with $H(x)=y$. ($x$ is called a preimage of $y$.)

Password protection on a multi-user computer system:

• The server stores $[$userid, $H$(password)$]$
• If the attacker obtains a copy of the password file, they do not learn any passwords.
• This requires preimage resistance.

Definition

A hash function $H:\{0,1{\}}^{\ast }\to \{0,1{\}}^n$ is 2nd preimage resistant if, given $x{\in }_R\{0,1{\}}^{\ast }$, it is computationally infeasible to find (with non-negligible success probability) any $x^{\prime }\in \{0,1{\}}^{\ast }$ with $x^{\prime }\ne x$ and $H(x^{\prime })=H(x)$

Modification Detection Codes (MDC’s):

• To ensure that a message $m$ is not modified by unauthorized means, one computes $H(m)$ and protects $H(m)$ from unauthorized modification.
• This is useful protection and requires 2nd preimage resistance.

Definition

A hash function $H:\{0,1{\}}^{\ast }\to \{0,1{\}}^n$ is collision resistant if it is computationally infeasible to find $x,x^{\prime }\in \{0,1{\}}^{\ast }$ with $x^{\prime }\ne x$ and $H(x^{\prime })=H(x)$. Such a pair $(x,x^{\prime })$ is called a collision for $H$.

Message digests for digital signature schemes:

• For reasons of efficiency, instead of signing a long message $x$, the (much shorter) message digest $h=H(x)$ is signed.
• This application requires preimage-resistance, 2nd preimage resistance, and collision resistance.
• To see why collision resistance is required, suppose that the legitimate signer Alice can find a collision $(x_1,x_2)$ for $H$. Alice can sign $x_1$ and later claimed to have signed $x_2$.

Other applications:

• Message Authentication Codes
• Pseudorandom bit generation
• Key derivation functions
• Proof-of-work
• Quantum-safe signature schemes

Relationships between PR, 2PR, CP

Breaking preimage resistance (PR):

Given: $y{\in }_R\{0,1{\}}^n$

Required: $x\in \{0,1{\}}^{\ast }$ with $H(x)=y$.

Breaking 2nd preimage resistance (2PR):

Given: $x \in_{R} {0,1}^*

Required: $x^{\prime }\in \{0,1{\}}^{\ast }$ with $x^{\prime }\ne x$ and $H(x^{\prime })=H(x)$

Breaking collision resistance (CR):

Given: $-$

Required: $x,x^{\prime }\in \{0,1{\}}^{\ast }$ with $x^{\prime }\ne x$ and $H(x^{\prime })=H(x)$

Claim $1$: If $H$ is CR, then $H$ is 2PR

Proof: Suppose that $H:\{0,1{\}}^{\ast }to\{0,1{\}}^n$ is not 2PR.

We’ll show that $H$ is not CR.

Select $x{\in }_R\{0,1{\}}^{\ast }$. Since $H$ is not 2PR, we can efficiently find $x^{\prime }\in \{0,1{\}}^{\ast },x\ne x$, with $H(x^{\prime })=H(x)$.

Thus, $(x,x^{\prime })$ is a collision for $H$ that we have efficiently found, showing that $H$ is not CR.

Note: This proof established the contrapositive statement.

Claim $2$: CR does not guarantee PR

Proof: Suppose that $H:\{0,1{\}}^{\ast }\to \{0,1{\}}^n$ is CR.

Consider the hash function $\overline{H}:\{0,1{\}}^{\ast }\to \{0,1{\}}^{n+1}$ defined by

$$\begin{array}{r}\overline{H}(x)=\{\begin{array}{ll}0||H(x),& \text{if }x\in \{0,1{\}}^n\\ 1||x,& \text{if }x\in \{0,1{\}}^n\end{array}\end{array}$$

Then $\overline{H}$ is CR (since $H$ is).

And $\overline{H}$ is not PR since preimages can be efficiently found for at least half of all $y\in \{0,1{\}}^{n+1}$, namely the hash values that begin with $1$.

Note: The hash function $\overline{H}$ is rather contrived. For somewhat uniform hash functions, i.e., hash functions for which all hash values have roughly the same number of preimages, CR does not guarantee PR.

Claim $2^{\ast }$: Suppose $H$ is somewhat uniform. If $H$ is CR, then $H$ is PR

Proof: Suppose that $H:\{0,1{\}}^{\ast }\to \{0,1{\}}^n$ is not PR.

We’ll show that $H$ is not CR.

Select $x{\in }_R\{0,1{\}}^{\ast }$ and compute $y=H(x)$. Since $H$ is not PR, we can efficiently find $x^{\prime }\in \{0,1{\}}^{\ast }$ with $H(x^{\prime })=y$. Since $H$ is somewhat uniform, we expect that $y$ has many preimages, and thus $x^{\prime }=x$ with very high probability. Thus, $(x,x^{\prime })$ is a collision for $H$ that we have efficiently found, so $H$ is not CR.

Claim $3$: PR does not guarantee 2PR

Proof: Suppose that $H:\{0,1{\}}^{\ast }\to \{0,1{\}}^n$ is PR.

Define $\overline{H}:\{0,1{\}}^{\ast }\to \{0,1{\}}^n$ by $\overline{H}(x_1,x_2,\dots ,x_t)=H(0,x_2,\dots ,x_t)$ for all $(x_1,x_2,\dots ,x_t)\in \{0,1{\}}^{\ast }$.

Then $\overline{H}$ is PR. However $\overline{H}$ is not 2PR.

Claim $4$: Suppose $H$ is somewhat uniform. If $H$ is 2PR, then $H$ is PR

Proof: Suppose that $H:\{0,1{\}}^{\ast }\to \{0,1{\}}^n$ is not PR.

We will show that $H$ is not 2PR.

So, suppose we are given $x{\in }_R\{0,1{\}}^{\ast }$. We compute $y=H(x)$.

Since $H$ is not PR, we can efficiently find $x^{\prime }\in \{0,1{\}}^{\ast }$ with $H(x^{\prime })=y$.

Since $H$ is somewhat uniform, we expect that $x^{\prime }\ne x$ with very high probability. Hence, $x^{\prime }$ is a second preimage of $x$ that we have efficiently found.

Thus $H$ is not 2PR.

Claim $5$: 2PR does not guarantee CR

Proof: Suppose that $H:\{0,1{\}}^{\ast }\to \{0,1{\}}^n$ is 2PR.

Consider $\overline{H}:\{0,1{\}}^{\ast }\to \{0,1{\}}^n$ defined by $\overline{H}(x)=H(x)$ if $x\ne 1$, and $\overline{H}(1)=H(0)$.

• Then $\overline{H}$ is not CR, since $(0,1)$ is a collision for $\overline{H}$
• Suppose now that $\overline{H}:\{0,1{\}}^{\ast }\to \{0,1{\}}^n$ is not 2PR. We’ll show that $H$ is not 2PR.

So, we are given $x{\in }_R\{0,1{\}}^{\ast }$. Since $\overline{H}$ is not 2PR, we can efficiently find $x^{\prime }\in \{0,1{\}}^{\ast },x^{\prime }\ne x$, with $\overline{H}(x^{\prime })=\overline{H}(x)$. With probability essentially $1$, we can assume that $x\ne 0,1$. Hence, $\overline{H}(x)=H(x)$.

Now, if $x^{\prime }\ne 1$, then $H(x^{\prime })=\overline{H}(x^{\prime })=\overline{H}(x)=H(x)$

And, if $x^{\prime }=1$, then $\overline{H}(x^{\prime })=\overline{H}(1)=H(0)=H(x)$.

In either case, we have efficiently found a second preimage for $x$ with respect to $H$.

Hence, $H$ is not 2PR, a contradiction. Thus, $\overline{H}$ is 2PR.

Generic Attacks

Definition

A generic attack on hash functions $H:\{0,1{\}}^{\ast }\to \{0,1{\}}^n$ does not exploit any properties that the specific hash function might have.

In the analysis of a generic attack, we view $H$ as a random function in the sense that for each $x\in \{0,1{\}}^{\ast }$, the hash value $y=H(x)$ was defined by selecting $y{\in }_R\{0,1{\}}^n$.

A random function is an ideal hash function (from a security point-of-view). However they are not practical.

Attack

Given $y{\in }_R\{0,1{\}}^n$, repeatedly select arbitrary $x\in \{0,1{\}}^{\ast }$ until $H(x)=y$.

The expected number of hash operations is $2^n$.

This generic attack is infeasible if $n\ge 128$.

Attack

Select arbitrary $x\in \{0,1{\}}^{\ast }$ and store $(H(x),x)$ in a table sorted by first entry. Repeat until a collision is found.

Analysis: By the birthday paradox, the expected number of hash operations is $\sqrt{\pi 2^n/2}\approx \sqrt{2^n}$

This generic attack is infeasible if $n\ge 256$.

This generic attack for finding collisions is optimal. The expected space required is $\sqrt{\pi 2^n/2}\approx \sqrt{2^n}$.

VW: van Oorschot & Wiener parallel collision search.

The expected number of hash operations: $\approx \sqrt{2^n}$. The expected space required is negligible.

It is easy to parallelize, $m$-fold speedup with $m$ processors.

The VW collision-finding algorithm can easily be modified to find meaningful collisions.

If collision resistance is desired, then use an $n$-bit hash function with $n\ge 256$.

Parallel Collision search (VW method)

Problem: Find a collision for $H:\{0,1{\}}^{\ast }\to \{0,1{\}}^n$.

Assumption: $H$ is a random function.

Notation: Let $N=2^n$.

Define a sequence $\{x_i{\}}_{i\ge 0}$ by $x_0{\in }_R\{0,1{\}}^n,x_i=H(x_{i-1})$ for $i\ge 1$.

Let $j$ be the smallest index for which $x_j=x_i$ for some $i<j$; such a $j$ must exist. Then $x_{j+\ell }=x_{i+\ell }$ for all $\ell \ge 1$. By the birthday paradox, $E[j]\approx \sqrt{\pi N/2}\approx \sqrt{N}$. In fact, $E[i]\approx \frac{1}{2}\sqrt{N}$ and $E[j-i]\approx \frac{1}{2}\sqrt{N}$.

Now, $i\ne 0$ with overwhelming probability, in which event $(x_{i-1},x_{j-1})$ is a collision for $H$.

Question

How to find $(x_{i-1},x_{j-1})$ without using much storage?

We only store distinguished points.

Distinguished points: Select an easily-testable distinguishing property for elements of $\{0,1{\}}^n$, e.g. leading 32 bits are all 0.

Let $\theta$ be the proportion of elements of $\{0,1{\}}^n$ that are distinguished.

VW method: Compute the sequence $x_0,x_1,x_2,x_3,\dots$ and only store the points that are distinguished.

VW Collision Finding

Stage 1: Detecting a collision

1. Select $x_0{\in }_R\{0,1{\}}^n$
2. Store $(x_0,0,-)$ in a sorted table.
3. $LP\leftarrow x_0$ ($LP$ = last point stored)
4. For $d=1,2,3,\dots$ do:
5. Compute $x_d=H(x_{d-1})$
6. If $x_d$ is distinguished then
   1. If $x_d$ is already in the table, say $x_d=x_b$ where $b<d$, then go to Stage 2
   2. Store $(x_d,d,LP)$ in the table.
   3. $LP\leftarrow x_d$

Stage 2: Finding a collision

1. Set ${\ell }_1\leftarrow b-a,{\ell }_2\leftarrow d-c$
2. Suppose ${\ell }_1\ge {\ell }_2$, and set $k \gets \ell_1 - \ell_2
3. Compute $x_{a+1},x_{a+2},\dots x_{a+k}$
4. For $m=1,2,3,\dots$ do:
5. Compute $(x_{a+k+m},x_{c+m})$
6. Until $x_{a+k+m}=x_{c+m}$
7. The collision is $(x_{a+k+m-1},x_{c+m-1})$

VW Analysis

Stage 1: Expected number of $H$-evaluations is:

$$\begin{array}{r}\sqrt{\pi N/2}+\frac{1}{\theta }\approx \sqrt{N}+\frac{1}{\theta }\end{array}$$

Stage 2: Expected number of $H-$evaluations is $\le \frac{3}{\theta }$

Overall expected running time: $\sqrt{N}+\frac{4}{\theta }$

Expected storage: $\approx 3n\theta \sqrt{N}$ bits

Example

Consider $n=128$. Take $\theta =1/2^{32}$. Then the expected run time of VW collision search is $2^{64}$ $H-$evaluations (feasible), and the expected storage is 192 gigabytes (negligible).

Iterated Hash Functions

Merkle's Meta Method

Components:

• Fixed initializing value $IV\in \{0,1{\}}^n$
• Efficiently-computable compression function $f:\{0,1{\}}^{n+r}\to \{0,1{\}}^n$

To compute $H(x)$ where $x$ has bitlength $b<2^r$ do:

1. Break up $x$ into $r-$bit blocks, $\overline{x}=x_1,x_2,\dots ,x_t$, padding the last block with $0$ bits as necessary.
2. Define $x_{t+1}$, the length-block, to hold the right-justified binary representation of $b$.
3. Define $H_0=IV$.
4. Compute $H_i=f(H_{i-1},x_i)$ for $i=1,2,\dots ,t+1$. (The $H_{i}‘s are called chaining variables).
5. Define $H(x)=H_{t+1}$

Theorem (Merkle)

If the compression function $f$ is collision resistant, then the iterated hash function $H$ is also collision resistant.

Merkle’s theorem reduces the problem of designing collision-resistant hash functions to that of designing collision-resistant compression functions.

A major theme in cryptographic research is to formula precise security definitions and assumptions, and then prove that a protocol is secure.

A proof of security is certainly desirable since it rules out the possibility of attacks being discovered in the future.

However, it isn’t always easy to asses the practical security assurances (if any) that a security proof provides).

• Assumptions might be unrealistic, or false, or circular.
• The security model might not account for certain kinds of realistic attacks.
• The security proof might be asymptotic.

Proof of Merkle’s Theorem ($f$ is CR $⟹H$ is CR)

Suppose that $H$ is not CR. We’ll show that $f$ is not CR.

Since $H$ is not R, we can efficiently find messages $x,x^{\prime }\in \{0,1{\}}^{\ast }$, with $x\ne x^{\prime }$ and $H(x)=H(x^{\prime })$.

Let $\overline{x}=x_1,x_2,\dots ,x_t$, $b$ = bit-length($x$), $x_{t+1}=$ length block.

Let $\overline{x^{\prime }}=x_1^{\prime },x_2^{\prime },\dots ,x_t^{\prime }$, $b^{\prime }$ = bit-length($x^{\prime }$), $x_{t+1}^{\prime }=$ length block.

We can efficiently compute:

$$\begin{array}{rl}{H}_0& =IV\\ H_1& =f(H_0,x_1)\\ H_2& =f(H_1,x_2)\\ & ⋮\\ H_{t-1}& =f(H_{t-2},x_{t-1})\\ H_t& =f(H_{t-1},x_t)\\ H(x)=H_{t+1}& =f(H_t,x_{t+1})\end{array}$$ $$\begin{array}{rl}{H}_0& =IV\\ H_1^{\prime }& =f(H_0,x_1^{\prime })\\ H_2^{\prime }& =f(H_1^{\prime },x_2^{\prime })\\ & ⋮\\ H_{t^{\prime }-1}^{\prime }& =f(H_{t^{\prime }-2}^{\prime },x_{t^{\prime }-1}^{\prime })\\ H_{t^{\prime }}^{\prime }& =f(H_{t^{\prime }-1}^{\prime },x_{t^{\prime }}^{\prime })\\ H(x^{\prime })=H_{t^{\prime }+1}^{\prime }& =f(H_{t^{\prime }}^{\prime },x_{t^{\prime }+1}^{\prime })\end{array}$$

Since $H(x)=H(x^{\prime })$, we have $H_{t+1}=H_{t^{\prime }+1}^{\prime }$

Case 1: Now, if $b\ne b^{\prime }$ then $x_{t+1}\ne x_{t^{\prime }+1}^{\prime }$. Thus, $(H_t,x_{t+1}),H_{t^{\prime }}^{\prime },x_{t^{\prime }+1}^{\prime }$ is a collision for $f$ that we have efficiently found.

Case 2: Suppose next that $b=b^{\prime }$. Then $t=t^{\prime }$ and $x_{t+1}=x_{t+1}^{\prime }$

• Let $i$ be the largest index, $0\le i\le t$, for which $(H_i,x_{i+1})\ne (H_i^{\prime },x_{i+1}^{\prime })$. Such an $i$ must exist since $x\ne x^{\prime }$.
• Then $H_{i+1}=f(H_i,x_{i+1})=f(H_i^{\prime },x_{i+1}^{\prime })=H_{i+1}^{\prime }$, so $(H_i,x_{i+1}),(H_i^{\prime },x_{i+1}^{\prime })$ is a collision for $f$ that we have efficiently found.

Thus, $f$ is not collision resistant $\square$

MDx is a family of iterated hash functions. MD4 has 128-bit outputs. Professor Xiaoyun Wang found collisions for MD4 by hand.

MD5 is a strengthened version of MD4. MD5 should not be used if collision resistance is required, but is probably okay as a preimages-resistant hash function.

Secure Hash Algorithm (SHA) was designed by NSA and published by NIST in 1992. 160-bit iterated hash function based on MD4.

The SHA-2 design is similar to SHA-1, and thus there were lingering concerns that the SHA-1 weaknesses could eventually extend to SHA-2.

SHA-3 is used in practice, but not as widely deployed as SHA-2.

SHA-256

Iterated hash function (Merkle’s meta method). $n=256,r=512$.

Compression function is $f:\{0,1{\}}^{256+512}⟶\{0,1{\}}^{256}$

Input: bit string $x$ of arbitrary bitlength $b\ge 0$.

Output: 256-bit hash value $H(x)$ of $x$.

SHA-256 Notation

$A,B,C,D,E,F,G,H$ are 32-bit words.

• $+$: addition module $2^{32}$
• $\bar{A}$: bitwise complement
• $A\gg s$: shift $A$ right by $s$ positions
• $A\hookrightarrow s$: rotate $A$ right by $s$ positions
• $AB$: bitwise AND of $A,B$
• $A\oplus B$: bitwise exclusive-OR

$f(A,B,C)=AB\oplus \bar{A}C$

$g(A,B,C)=AB\oplus AC\oplus BC$

$r_1(A)=(A\hookrightarrow 2)\oplus (A\hookrightarrow 13)\oplus (A\hookrightarrow 22)$

$r_2(A)=(A\hookrightarrow 6)\oplus (A\hookrightarrow 11)\oplus (A\hookrightarrow 25)$

$r_3(A)=(A\hookrightarrow 7)\oplus (A\hookrightarrow 8)\oplus (A\gg 3)$

$r_4(A)=(A\hookrightarrow 17)\oplus (A\hookrightarrow 19)\oplus (A\gg 10)$

SHA-256 constants

• 32-bit initial chaining values (IVs): These words were obtained by taking the first 32 bits of the fractional parts of the square roots of the first 8 prime numbers.

• Per-round integer additive constants: These words were obtained by taking the first 32 bits of the fractional parts of the cube roots of the first 64 prime numbers.

SHA-256 preprocessing

1. Pad $x$ with 1, followed by as few 0’s as possible so that the bitlength is 64 less than a multiple 512.
2. Append the 64-bit binary representation of $b(\mathrm{mod}{2}^{64})$
3. The formatted input is $x_0,x_1,\dots ,x_{16m-1}$, where each $x_i$ is a 32-bit word
4. Initialize the words of the chaining variable: $(H_1,H_2,\dots ,H_7,H_8)\leftarrow (h_1,h_2,\dots ,h_7,h_8)$

SHA-256 Processing

For each $i$ from 0 to $m-1$ do the following:

• Copy the $i$th block of sixteen 32-bit words into temporary storage: $X_j\leftarrow x_{16i+j}0\le j\le 15$
• Expand the 16-word block into a 64-word block: For $j$ from 16 to 63 do: $X_j\leftarrow r_4(X_{j-2})+X_{j-7}+r_3(X_{j-15})+X_{j-16}$
• Initialize working variables: $(A,B,\dots ,G,H)\leftarrow (H_1,H_2,\dots ,H_7,H_8)$
• For $j$ from 0 to 63 do:
  • $T_1\leftarrow H+r_2(E)+f(E,F,G)+y_j+X_j{T}_2\leftarrow r_1(A)+g(A,B,C)$
  • $H\leftarrow G,G\leftarrow F,F\leftarrow E,E\leftarrow D+T_1,D\leftarrow C,C\leftarrow B,B\leftarrow A,A\leftarrow T_1+T_2$
• Update chaining variable: $(H_1,H_2,\dots ,H_7,H_8)\leftarrow (H_1+A,H_2+B,\dots ,H_7+G,H_8+H)$ Output: SHA256($x$) = $H_1||H_2||H_3||H_4||H_5||H_6||H_7||H_8$

Chapter 4: Message Authentication Codes

Fundamental Concepts

Definition

A message authentication code (MAC) scheme is a family of functions $MA{C}_k:\{0,1{\}}^{\ast }\to \{0,1{\}}^n$ parameterized by an $\ell$-bit key $k$, where each function $MA{C}_k$ can be efficiently computed.

$t=MA{C}_k(x)$ is called the MAC or tag of $x$ with key $k$.

MAC schemes are used for providing (symmetric-key) data integrity and data origin authentication.

To provide data integrity and data origin authentication:

1. Alice and Bob establish a secret key $k{\in }_R\{0,1{\}}^{\ell }$
2. Alice computes the tag $t=MA{C}_k(x)$ of a message $x$ and sends $(x,t)$ to Bob.
3. Bob verifies that $t=MA{C}_k(x)$

Note: There is no confidentiality or non-repudiation.

Let $k$ be the secret key shared by Alice and Bob.

The adversary does not know $k$, but is allowed to obtain (from either Alice or Bob) the tags for messages of her choosing. The adversary’s goal is to obtain the tag of a new message of the adversary’s choosing.

Definition

A $MAC$ scheme is secure if given some tags $MA{C}_k(x_i)$ for messages $x_i$‘s of one’s own choosing, it is computationally infeasible to compute a message-tag pair ($x,MA{C}_k(x))$ for a new message $x$. A $MAC$ scheme is secure if it is existentially unforgeable against chosen-message attack.

An ideal $MAC$ scheme has the following property: For each $k\in \{0,1{\}}^{\ell }$, the function $MA{C}_k:\{0,1{\}}^{\ast }\to \{0,1{\}}^n$ is a random function. (This is useless in practice).

Generic Attack

Guessing the tag of a message $x\in \{0,1{\}}^{\ast }$. Attack: Select $y{\in }_R\{0,1{\}}^n$ and guess that $MA{C}_k(x)=y$

Analysis: Assuming that the $MAC$ scheme is ideal, the success probability is $1/2^n$

Generic Attack (2)

Attack: Given $r$ message-tag pairs $(x_1,t_1),\dots (x_r,t_r)$, one can check whether a guess $h$ of the key is correct by verifying that $MA{C}_h(x_i)=t_i$ for $i=1,2,\dots ,r$.

Analysis: Assuming the $MAC$ scheme is ideal, expected number of keys for which all $(x_i,t_i)$ pairs verify is $1+FK=1+(2^{\ell }-1)/2^{nr}$.

Exhaustive key search is infeasible if $\ell \ge 128$

GSM (Global System for Mobile Communications) security is notable since it uses only symmetric-key primitives.

Objectives:

1. Entity authentication: The cell phone service provider needs the assurance that entities accessing its service are legitimate subscribers
2. Confidentiality: The data exchanged between a cell phone user and their cell phone service provider should be confidential

GSM does not provide end-to-end security.

Alice: Cell phone user. Bob: Cell phone service provider

1. Alice sends an authentication request to Bob
2. Bob selects a challenge $r{\in }_R\{0,1{\}}^{128}$ and sends $r$ to Alice
3. Alice’s SIM card uses $k$ to compute the response $t=MA{C}_k(r)$. Alice sends $t$ to Bob.
4. Bob retrieves Alice’s key $k$ from its database, and verifies that $t=MA{C}_k(r)$
5. Alice and Bob compute an encryption key $K_E=KD{F}_k(r)$, and thereafter use the encryption algorithm Enc${}_{K_E}(\cdot )$ to encrypt and decrypt messages for each other for the remainder of the session

CBC-MAC and HMAC

Let $E$ be an $n$-bit block cipher with key space $\{0,1{\}}^{\ell }$.

Assumption: Plaintext messages all have lengths that are multiples of $n$.

To compute CBC-MAC${}_k(x)$:

1. Divide $x$ into $n$-bit blocks $x_1,x_2,\dots ,x_r$
2. Compute $H_1=E_k(x_1)$
3. For $i=2,3,\dots ,r$, compute $H_i=E_k(H_{i-1}\oplus x_i)$
4. Then CBC-MAC${}_k(x)=H_r$

CBC-MAC is not secure if variable-length messages are allowed.

Here is a chosen-message attack on CBC-MAC:

1. Select an arbitrary 3-block message $x=(x_1,x_2,x_3)$
2. Obtain the tag $t_1$ of the one-block message $x_1:t_1=E_k(x_1)$
3. Obtain the tag $t_2$ of the two-block message $(t_1\oplus x_2,x_3):t_2=E_k(E_k(t_1\oplus x_2)\oplus x_3)$
4. Output the forgery $(x,t_2)$

Correctness: $t_2=E_k(E_k(t_1\oplus x_2)\oplus x_3)=E_k(E_k(E_k(x_1)\oplus x_2)\oplus x_3)=$ CBC-MAC$(x)$

One countermeasure for variable-length messages is Encrypted CBC-MAC, where CBC-MAC tag is encrypted using a second key $s$: EMAC${}_{k,s}(x)=E_s(H_r)$, where $H_r=$ CBC-MAC${}_k(x)$

Theorem

Suppose that $E$ is an ideal encryption scheme. Then EMAC is a secure MAC scheme.

Encryption scheme $E$ is ideal if for each $k\in \{0,1{\}}^{\ell },E_k:\{0,1{\}}^n\to \{0,1{\}}^n$ is a random permutation.

Hash functions were not originally designed for message authentication. In particular, they are not “keyed” primitives.

Question

How to use a hash function to construct a secure MAC?

Let $H$ be an iterated $n$-bit hash function. For simplicity, assume that all message shave bitlengths that are multiples of $r$, and suppose that the length-block is omitted.

Let $n+r$ be the input blocklength of the compression function $f:\{0,1{\}}^{n+r}\to \{0,1{\}}^n.Let$k \in_R {0,1}^n. Let $K$ denote $k$ padded with $r-n$ 0’s, so $K$ has bitlength $r$.

Definition

$MA{C}_k(x)=H(K,x)$

This is insecure. Here is a length extension attack:

• Suppose that ($x$, MAC${}_k(x)$) is known.
• Then MAC${}_k(x||y)$ can be easily computed for any $y$.

Also insecure if messages can be of any bitlength and a length block is postponed to $K||x$.

Suppose that the adversary knows a message-tag pair $(x,t)$, where $x=x_1$ is a one-block message. Hence, $t=f(f(IV,K),x_1)$.

The adversary does the following:

• Arbitrarily select a one-block message $y$.
• Compute $t^{\prime }=f(t,y)$ and set $x^{\prime }=x_1||y$. ($x^{\prime }$ is a two-block message).
• Output $(x^{\prime },t^{\prime })$

Correctness: The message-tag pair $(x^{\prime },t^{\prime })$ is a valid forgery since $t^{\prime }=f(f(f(IV,K),x_1),y)$.

Hash-based MAC. Define two $r-$bit strings: ipad $=0x36$, opad $=0x5C$

Definition

HMAC${}_k(x)=H(K\oplus$ opad, $H(K\oplus$ ipad, $x))$

HMAC is commonly used as a key derivation function (KDF).

Suppose that Alice has a secret key $k$, and wishes to derive several session keys $s{k}_i$, e.g. to encrypt data in different communication sessions.

Alice computes $s{k}_1=$ HMAC${}_k(1)$, $s{k}_2=$ HMAC${}_k(2)$, $s{k}_3=$ HMAC${}_k(3),\dots$

Rationale: Without knowledge of $k$, an adversary is unable to learn anything about any particular session key $s{k}_i$, even though she might have learnt some other session keys.

Chapter 5: Authenticated Encryption

Fundamental Concepts

A symmetric-key encryption scheme $E$ provides confidentiality.

A MAC scheme provides authentication (data origin authentication and data integrity).

Question

What if confidentiality and authentication are both required?

Alice computes $c=E_{k_1}(m)$ and $t=$ MAC${}_{k_2}(m)$, and sends $(c,t)$ to Bob. Here, $m$ is the plaintext and $(k_1,k_2)$ is the secret key she shares with Bob.

Bob decrypts $c$ to obtain $m=E_{k_1}^{-1}(c)$ and then verifies that $t=$ MAC${}_{k_2}(m)$

This generic method is not secure.

Instead consider the following.

Alice computes $c=E_{k_1}(m)$ and $t=$ MAC${}_{k_2}(c)$, and sends $(c,t)$ to Bob. Here, $m$ is the plaintext and $(k_1,k_2)$ is the secret key she shares with Bob.

Bob first verifies that $t=$MAC${}_{k_2}(c)$ and then decrypts $c$ to obtain $m=E_{k_1}^{-1}(c)$

This generic method has been proven to be secure, provided that the encryption scheme $E$ and the MAC scheme employed are secure.

Many special-purpose authenticated encryption schemes have been developed, the most popular of which is using a symmetric-key encryption such as AES in GCM. Some of these authenticated encryption schemes also allow for the authentication of “header” data.

Definition

An authenticated encryption scheme $AE$ is $AE$-secure if:

1. $AE$ is semantically secure against chosen-plaintext attack; and
2. $AE$ has ciphertext integrity, i.e., an adversary who is able to obtain ciphertext-tag pairs $(c_1,t_1),(c_2,t_2),\dots ,(c_{\ell },t_{\ell })$ for plaintext messages $m_1,m_2,\dots ,m_{\ell }$ of her choosing, is unable to produce a valid ciphertext-tag pair $(c,t)$ where $c\notin \{c_1,c_2,\dots ,c_{\ell }\}$.

AES-GCM

AES-GCM is an authenticated encryption scheme designed by David McGrew and John Viega. Uses the CTR mode of encryption and GMAC, a custom-designed MAC scheme.

CTR: Counter mode of encryption.

Let $k{\in }_R\{0,1{\}}^{128}$ be the secret key shared by Alice and Bob. Let $M=(M_1,M_2,\dots ,M_u)$ be a plaintext message, where each $M_i$ is a 128-bit block and $u\le 2^{32}-2$.

To encrypt $M$, Alice does the following:

1. Select a nonce $IV\in \{0,1{\}}^{96}$
2. Let $J_0=IV||0^{31}||1$
3. For $i$ from 1 to $u$ do: $J_i\leftarrow J_{i-1}+1$ and compute $C_i=$ AES${}_k(J_i)\oplus M_i$
4. Send $(IV,C_1,C_2,\dots ,C_u)$ to Bob.

To decrypt, Bob does the following:

1. Let $J_0=IV||0^{31}||1$
2. For $i$ from 1 to $u$ do: $J_i\leftarrow J_{i-1}+1$ and compute $M_i=$ AES${}_k(J_i)\oplus C_i$

CTR mode of encryption can be viewed as a stream cipher. As was the case with CBC encryption, identical plaintexts with different IVs result in different ciphertexts. Unlike CBC encryption, CTR encryption is parallelizable. Note that AES${}^{-1}$ is not used. The secret key can have bitlength 128, 192, 256.

Let $a=a_0{a}_1{a}_2\dots a_{127}$ be a 128-bit block. We associate the binary polynomial $a(x)=a_0+a_{1}x+a_2{x}^2+\cdots +a_{127}{x}^{127}\in {\mathbb{Z}}_2[x]$ with $a$.

Let $f(x)=1+x+x^2+x^7+x^{128}$.

If $a$ and $b$ are 128-bit blocks, then define $c=a\cdot b$ to be the block corresponding to the polynomial $c(x)=a(x)\cdot b(x)(\mathrm{mod}f(x))$.

That is, $c(x)$ is the remainder upon dividing $a(x)\cdot b(x)$ by $f(x)$ in ${\mathbb{Z}}_2[x]$. This is multiplication in the Galois field $GF(2^{128})$.

Let $A=(A_1,A_2,\dots ,A_v)$, where each $A_i$ is a 128-bit block. Let $L$ be the bitlength of $A$. Let $k{\in }_R\{0,1{\}}^{128}$ be the secret key.

1. Ket $J_0=IV||0^{31}||1$, where $IV\in \{0,1{\}}^{96}$ is a nonce.
2. Compute $H=$ AES${}_k(0^{128})$
3. Let $f_A(x)=A_1{x}^{v+1}+A_2{x}^v+\cdots +A_{v-1}{x}^3+A_v{x}^2+Lx\in GF(2^{128})[x]$
4. Compute the authentication tag $t=$ AES${}_k(J_0)\oplus f_A(H)$
5. Send $(IV,A,t)$

Example

Let $A=(A_1,A_2,A_3)$ Then $f_A(x)=A_1{x}^4+A_2{x}^3+A_3{x}^2+Lx$ Hence, $f_A(H)=A_1{H}^4+A_2{H}^3+A_3{H}^2+LH$ $f_A(H)$ can be computed using Horner’s rule: $f_A(H)=((((((A_1\cdot H)+A_2)\cdot H)+A_3)\cdot H)+L)\cdot H$ This requires three additions and four multiplications in $GF(2^{128})$

In general, if $A$ has blocklength $v$, then computing $f_A(H)$ using Horner’s rule requires $v$ additions and $v+1$ multiplications in $GF(2^{128})$.

Consider the simplified tag: $t^{\prime }=f_A(H)$

An adversary can guess the tag $t^{\prime }$ of a message $A$ with success probability $\frac{1}{2^{128}}$. She can also guess the tag $t^{\prime }$ by making a guess $H^{\prime }$ for $H$ and computing $f_A(H^{\prime })$. Her success probability is at most $\frac{v+1}{2^{128}}$, where $v$ is the blocklength of $A$. However, if the adversary sees a single valid message-tag pair $(A,t^{\prime })$ she can solve the polynomial equation $f_A(H)=t^{\prime }$ for $H$. To circumvent the aforementioned attack, a second secret AES${}_k(J_0)$ is used to hide $t^{\prime }:t=$ AES${}_k(J_0)\oplus f_A(H)$. The secret AES${}_k(J_0)$ serves as a one-time pad for $t^{\prime }$.

Input:

AAD (Additional Authenticated Data), also called encryption context: Data to be authenticated (but not encrypted): $A=(A_1,A_2,\dots ,A_v)$ Data to be encrypted and authenticated: $M=(M_1,M_2,\dots ,M_u),u\le 2^{32}-2$. Secret key $k{\in }_R\{0,1{\}}^{128}$, shared between Alice and Bob.

Output: $(IV,A,C,t)$ where

• $IV$ is a 96-big initialization vector.
• $A=(A_1,A_2,\dots ,A_v)$ is the additional authenticated data.
• $C=(C_1,C_2,\dots ,C_u)$ is the encrypted/authenticated data.
• $t$ is a 128-bit authentication tag.

Alice does the following:

1. Let $L=L_A||L_M$, where $L_A,L_M$ are bitlengths of $A,M$ expressed as 64-bit integers.
2. Select a nonce $IV\in \{0,1{\}}^{96}$ and let $J_0=IV||0^{31}||1$
3. Encryption: For $i$ from 1 to $u$ do: Compute $J_i=J_{i-1}+1$ and $C_i=$ AES${}_k(J_i)\oplus M_i$
4. Authentication: Compute $H=$ AES${}_k(0^{128})$. Compute $t=$ AES${}_k(J_0)\oplus f_{A,C}(H)$
5. Output: $(IV,A,C,t)$

Note: $f_{A,C}(x)=A_1{x}^{u+v+1}+A_2{x}^{u+v}+\cdots A_{v-1}{x}^{u+3}+A_v{x}^{u+2}+C_1{x}^{u+1}+C_2{x}^u+\cdots +C_{u-1}{x}^3+C_u{x}^2+Lx$

Upon receiving $(IV,A,C,t)$ Bob does the following:

1. Let $L=L_A||L_C$, where $L_A,L_C$ are bitlengths of $A,C$ expressed as 64-bit integers.
2. Authentication: Compute $H=$ AES${}_k(0^{128})$. Compute $t^{\prime }=$ AES${}_k(J_0)\oplus f_{A,C}(H)$. If $t^{\prime }=t$ then proceed to decryption; if $t^{\prime }\ne t$ then reject.
3. Decryption: Let $J_0=IV||0^{31}||1$. For $i$ from 1 to $u$ do: Compute $J_i=J_{i-1}+1$ and $M_i=$ AES${}_k(J_i)\oplus C_i$
4. Output: $(A,M)$

IV’s should not be repeated (with the same key $k$). Suppose an IV is reused, and an eavesdropped captures two transmissions: $(IV,A_1,C_1,t_1),(IV,A_2,C_2,t_2)$. Suppose also that $M_1$ and $M_2$ have the same blocklengths, and that the eavesdropper knows $M_1$.

Then $t_1=$ AES${}_k(J_0)\oplus f_{A_1,C_1}(H)$ and $t_2=$ AES${}_k(J_0)\oplus f_{A_2,C_2}(H)$, so $t_1\oplus t_2=f_{A_1,C_1}(H)\oplus f_{A_2,C_2}(H)$.

This polynomial equation can be quickly solved for $H$, and then AES${}_k(J_0)=t_1\oplus f_{A_1,C_1}(H)$ can be computed.

Thereafter, the adversary can properly encrypt/authenticate any plaintext (of blocklength at most that of $M_1$).

Chapter 6: Public-Key Cryptography

Fundamental Concepts

Symmetric-key cryptography: Communicating parties a priori share some secret keying information.

The shared secret keys can then be used to achieve confidentiality (e.g. using AES-CBC), or authentication (e.g. using HMAC), or both (e.g. using AES-GCM).

Question

How can Alice and Bob establish the secret key $k$?

Method 1: Point-to-point key distribution

flowchart LR
Alice --->|k| Bob

The secured channel could be:

• A trusted courier
• A face-to-face meeting
• A SIM card that contains an authentication key

Method 2: Use a Trusted Third Party (TTP) $T$.

Each user $A$ shares a secret key $K_{AT}$ with $T$ for a symmetric-key encryption scheme $E$. To establish this key, $A$ must visit $T$ once.

$T$ serves as a key distribution centre (KDC).

flowchart LR
A --->|Request A,B| T
T --->|EkBTk| B
T --->|EkATk| A

1. $A$ sends $T$ a request for a key to share with $B$
2. $T$ selects a session key $k$, and encrypts it for $A$ using $k_{AT}$
3. $T$ encrypts $k$ for $B$ using $k_{BT}$

Drawbacks of using a KDC:

1. The TTP must be unconditionally trusted
2. The TTP is an attractive target
3. The TTP must be on-line, and is therefore a potential bottleneck and critical reliability point.

With a network of $n$ users, each user has to share a different secret key with every other user. Each user has to store and manage $n-1$ different secret keys. The total number of secret keys is $\left(\genfrac{}{}{0ex}{}{n}{2}\right)\approx \frac{n^2}{2}$

Non-repudiation is impractical.

Public-key cryptography: Communicating parties a priori share some authenticated (but non-secret) information.

Merkle Puzzles

Alice and Bob establish a secret session key by communicating over an authenticated (but non-secret) channel.

1. Alice creates $N$ puzzles $P_1,P_2,\dots ,P_N$ (e.g., $N=10^9$). Each puzzle takes $t$ hours to solve. The solution to $P_i$ reveals a 128-bit session key $s{k}_i$ and a randomly selected 128-bit serial number $n_i$
2. Alice sends $P_1,P_2,\dots ,P_N$ to Bob
3. Bob selects $j{\in }_R[1,N]$ and solves puzzle $P_j$ to obtain $s{k}_j$ and $n_j$
4. Bob sends $n_j$ to Alice.
5. The secret session key is $s{k}_j$

Key pair generation for public key cryptography:

Each entity $A$ does the following:

1. Generate a key pair $(P_A,S_A)$
2. $A$‘s public key is $P_A$ and her secret key is $S_A$.

Security requirement: It should be infeasible for an adversary to recover $S_A$ from $P_A$.

Example

$S_A=(p,q)$ where $p,q$ are randomly-selected prime numbers, and $P_A=p\cdot q$

To encrypt a message $m$ for Bob, Alice does:

1. Obtain an authentic copy of Bob’s public key $P_B$
2. Compute $c=E(P_B,m)$, where $E$ is the encryption function.
3. Send $c$ to Bob.

To decrypt $c$, Bob does:

1. Compute $m=D(S_B,c)$ where $D$ is the decryption function.

To sign a message $m$, Alice does:

1. Compute $s=$ Sign($S_A,m$).
2. Send $(m,s)$ to Bob

To verify Alice’s signature $s$ on $m$, Bob does:

1. Obtain an authentic copy of Alice’s public key $P_A$.
2. Accept if Verify$(P_A,m,s)=$ “Accept”

If Alice generates a signed message $(m,s)$, anyone who has the authentic copy of Alice’s public key $P_A$ can verify the authenticity of the signed message.

Advantages of public-key cryptography

• No requirement for a secured channel
• Each user has only one key pair
• A signed message can be verified by anyone

Disadvantages of public-key cryptography

• Public-key schemes are slower than their symmetric-key counterparts.

In practice, symmetric-key and public-key schemes are used together.

Elementary Number Theory

Content covered in MATH135

The set of integers is $\mathbb{Z}=\{\dots ,-3,-2,-1,0,1,2,3,\dots \}$

An integer $a$ is said to divide an integer $b$, written $a|b$ if there exists and integer $c$ such that $b=ca$.

Division algorithm: If $a$ and $b$ are integers with $b\ge 1$, then the orginary long division of $a$ by $b$ yields unique integers $q$ and $r$ with $a=qb+r$ and $0\le r<b$.

An integer $p\ge 2$ is said to be prime if its only positive divisors are $1$ and $p$. Otherwise, $p$ is called composite.

Fundamental Theorem of Arithmetic: Every integer $n\ge 2$ has a factorization as a product of prime powers: $n=p_1^{e_1}{p}_2^{e_2}\cdots p_k^{e_k}$, where the $p_i$ are distinct primes and the $e_i$ are positive integers. Furthermore, the factorization is unique up to rearrangement of factors.

Prime Number Theorem: For $x\ge 2$, let $\pi (x)$ denote the number of primes between $2$ and $x$. For all $x\ge 114$, we have $\frac{x}{{\log }_{e}x}<\pi (x)<1.25\frac{x}{{\log }_{e}x}$

Let $a$ and $b$ be integers, not both $0$. The greatest common divisor of $a$ and $b$, denoted $gcd(a,b)$, is the largest positive integer $d$ that divides both $a$ and $b$.

Integers $a$ and $b$ are said to be relatively prime, or coprime, if $gcd(a,b)=1$.

Fact

If $a$ and $b$ are positive integers with $a\ge b$, then $gcd(a,b)=gcd(b,a(\mathrm{mod}b))$.

Euclidian algorithm for computing $gcd(a,b)$ where $a\ge b$.

While $b\ne 0$ do the following:

• Set $r\leftarrow a(\mathrm{mod}b)$, a \gets b, b \gets r

Return$(a)$.

Integers modulo $n$: ${\mathbb{Z}}_n=\{0,1,2,\dots ,n-1\}$, where addition subtraction and multiplication are performed modulo $n$.

Definition

Let $a\in {\mathbb{Z}}_n$. The multiplicative inverse of $a$ modulo $n$ is an integer $x\in {\mathbb{Z}}_n$ such that $ax\equiv 1(\mathrm{mod}n)$. If such an $x$ exists, then it is unique, and $a$ is said to be invertible modulo $n$; the inverse of $a$ modulo $n$ is denoted by $a^{-1}\mathrm{mod}n$

Fact

Let $a\in {\mathbb{Z}}_n$. Then $a^{-1}\mathrm{mod}n$ exists if and only if $\gcd (a,n)=1$

Computing inverses modulo $n$. Let $a\in [1,n-1]$ with $\gcd (a,n)=1$. Use the EEA to find integers $x$ and $y$ such that $ax+ny=1$. Then $ax\equiv (\mathrm{mod}n)$, so $a^{-1}\mathrm{mod}n=x\mathrm{mod}n$

Algorithmic Number Theory

Theorem: Every integer $n\ge 2$ has a unique prime factorization.

How we find this prime factorization efficiently is a hard problem. How we verify a prime factorization is easy. Deciding whether a number $n$ is prime or composite is easy.

An algorithm is a “well-defined computational procedure” that takes a variable input and eventually halts with some output.

The efficiency of an algorithm is measured by the scarce resources it consumes.

Definition

The input size is the number of bits required to write down the input using a reasonable encoding. e.g., the size of a positive integer $n$ is $\lfloor {\log }_{2}n\rfloor +1$ bits.

Definition

The running time of an algorithm is an upper bound, as a function of the input size, of the worst case number of basic operations the algorithm executes over all inputs of a fixed size.

Definition

An algorithm is a polynomial-time algorithm if its expected running time is $O(k^c)$, where $k$ is the input size and $c$ is a fixed positive integer.

Definition

If $f(n)$ and $g(n)$ are functions from the positive integers to the real numbers, then $f(n)=O(g(n))$ means that there exists a positive constant $c$ and a positive integer $n_0$ such that $f(n)\le cg(n)\forall n\ge n_0$.

Modular exponentiation.

Input: A $k$-bit integer $n$, and integers $a,m\in [0,n-1]$

Output: $a^m\mathrm{mod}n$

Naïve algorithm #1:

1. Compute $d=a^m$
2. Return ($d\mathrm{mod}n$)

Analysis: The bitlength of $d$ is $\approx {\log }_{2}d={\log }_2{a}^m=m{\log }_{2}a=O(2^{k}k)$ since $m\approx 2^k$. Hence the algorithm is not polytime.

Naïve algorithm #2:

1. $A\leftarrow a$
2. For $i$ from 2 to $m$ do:
   1. $A\leftarrow A\times a\mathrm{mod}n$
3. Return($A$)

This algorithm is also not polytime.

Let the binary representation of $m$ be $m={\sum }_{i=0}^{k-1}{m}_i{2}^i$, where $m_i\in \{0,1\}$. Then:

$$\begin{array}{r}{a}^m=a^{{\sum }_{i=0}^{k-1}{m}_i{2}^i}=\prod _{i=0}^{k-1}{a}^{m_i{2}^i}=\prod _{0\le i\le k-1}{a}^{2^i}(\mathrm{mod}n)\end{array}$$

We can do the following repeated square-and-multiply algorithm for computing $a^m\mathrm{mod}n$

Write $m$ in binary $m={\sum }_{i=0}^{k-1}{m}_i{2}^i$

1. If $m_0=1$ then $B\leftarrow a$; else $B\leftarrow 1$.
2. $A\leftarrow a$
3. For $i$ from 1 to $k-1$ do:
   1. $A\leftarrow A^2\mathrm{mod}n$
   2. If $m_i=1$ then $B\leftarrow B\times A\mathrm{mod}n$
4. Return ($B$)

Analysis: At most $k$ modular squaring and $k$ modular multiplications, so the worst case running time is $O(k^3)$ bit operations. This is polytime.

Chapter 7: RSA

Basic RSA

RSA is used for public-key encryption and signatures.