{
"cells": [
{
"cell_type": "markdown",
"id": "2473ba79-651d-4710-9299-137ae6cbd8d3",
"metadata": {},
"source": [
"# Foundations of Cryptography\n",
"\n",
"## Modular Arithmetic\n",
"\n",
"A number $x \\bmod N$ is the equivalent of asking for the remainder of $x$ when divided by $N$. \n",
"\n",
"Two integers $a$ and $b$ are said to be **congruent** (or in the same equivalence class) modulo $N$ if they have the same remainder upon division by $N$. In such a case, we say that \n",
"\n",
"$$a \\equiv b \\pmod N$$\n",
"\n",
"<br>\n",
"\n",
"### Addition in Modular Arithmetic\n",
"\n",
"1. If $a + b = c$, then $a \\pmod N + b \\pmod N \\equiv c \\pmod N$\n",
"\n",
"2. If $a \\equiv b \\pmod N$, then $a + k \\equiv b + k \\pmod N$ for any integer $k$\n",
"\n",
"3. If $a \\equiv b \\pmod N$ and $c \\equiv d \\pmod N$, then $a + c \\equiv b + d \\pmod N$\n",
"\n",
"4. If $a \\equiv b \\pmod N$, then $-a \\equiv -b \\pmod N$\n",
"\n",
"<br>\n",
"\n",
"### Multiplication in Modular Arithmetic\n",
"\n",
"1. If $a \\cdot b = c$, then $a \\pmod N \\cdot b \\pmod N \\equiv c \\pmod N$\n",
"\n",
"2. If $a \\equiv b \\pmod N$, then $k \\cdot a \\equiv k \\cdot b \\pmod N$ for any integer $k$\n",
"\n",
"3. If $a \\equiv b \\pmod N$ and $c \\equiv d \\pmod N$, then $a \\cdot c \\equiv b \\cdot d \\pmod N$\n",
"\n",
"<br>\n",
"\n",
"### Exponentiation in Modular Arithmetic\n",
"\n",
"1. If $a \\equiv b \\pmod N$, then $a^k \\equiv b^k \\pmod N$ for any integer $k$\n",
"\n",
"<br>\n",
"\n",
"### Division in Modular Arithmetic\n",
"\n",
"1. If $\\gcd(k, N) = 1$ and $k \\cdot a \\equiv k \\cdot b \\pmod N$, then $a \\equiv b \\pmod N$\n",
"\n",
"This property is true, because if $k \\cdot (a−b)$ is a multiple of $N$ and $\\gcd(k, N) = 1$, then $N$ must divide $a-b$, or equivalently $a \\equiv b \\pmod N$.\n",
"\n",
"**Example**: Consider $4 \\equiv 8 \\pmod 4$. Note that we cannot simply divide both sides of the equation by $2$, since $2 \\not \\equiv 4 \\pmod 4$.\n",
"\n",
"<br>\n",
"\n",
"### Multiplicative Inverse in Modular Arithmetic\n",
"\n",
"If $a$ and $N$ are integers such that $\\gcd(a, N) = 1$ (coprime or relatively prime), then there exists an integer $b$ such that $a \\cdot b \\equiv 1 \\pmod N$. $b$ is called the multiplicative inverse of $a \\bmod N$.\n",
"\n",
"**Examples**:\n",
"\n",
"* $2 \\cdot 3 \\equiv 1 \\pmod{5}$\n",
"* $2 \\cdot 6 \\equiv 1 \\pmod{11}$"
]
},
{
"cell_type": "code",
"execution_count": 1,
"id": "7e02a076-d72b-40b2-abc2-9305e9b7e4fb",
"metadata": {},
"outputs": [],
"source": [
"# reference: https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Pseudocode\n",
"def mod_inv(x, m):\n",
" r0, r1 = x, m\n",
" s0, s1 = 1, 0\n",
" while r1 != 0:\n",
" quotient = r0 // r1\n",
" r0, r1 = r1, r0 - quotient * r1\n",
" s0, s1 = s1, s0 - quotient * s1\n",
" if r0 != 1:\n",
" return None\n",
" return s0 if s0 >= 0 else s0 + m"
]
},
{
"cell_type": "code",
"execution_count": 2,
"id": "42037c5e-bc7a-4204-8310-45c22e8bfd46",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"6"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"mod_inv(2, 11)"
]
},
{
"cell_type": "markdown",
"id": "0bf78190-2540-4b3a-b93e-1f925c23df8e",
"metadata": {},
"source": [
"## The XOR Operation\n",
"\n",
"The boolean XOR (exclusive OR) operation form an **abelian group** $(\\,\\{T, F\\}^N, \\,\\oplus\\,)$ over the set of **boolean vectors** of length $N$:\n",
"\n",
"* **Closure**: when you XOR two boolean vectors $A$ and $B$, the result $C$ is also a boolean vector\n",
"\n",
"* **Commutative**: $A \\oplus B = B \\oplus A$\n",
"\n",
"* **Associative**: $A \\oplus (B \\oplus C) = (A \\oplus B) \\oplus C$\n",
"\n",
"* The **identity element** for the XOR operation is $T^N$ with $A \\oplus T^N = T^N \\oplus A = A$\n",
"\n",
"* **Inverse element**: each element is its own inverse, i.e. $A \\oplus A = T^N$\n",
"\n",
"### Isomorphism\n",
"\n",
"Two groups are said to be **isomorphic** if there is a **one-to-one mapping** between the **elements** of the sets that **preserves the operation**.\n",
"\n",
"<br>\n",
"\n",
"The group $(\\,\\{T, F\\}^N, \\,\\oplus\\,)$ is isomorphic to the group $(\\,\\{0, 1\\}^N, \\, + \\,)$ of **addition modulo 2** over the set of vectors whose **elements** are **integers mod 2**. \n",
"\n",
"→ The isomorphism simply maps $T$ to $1$ and $F$ to $0$."
]
},
{
"cell_type": "code",
"execution_count": 3,
"id": "75d2636e-107c-44d1-8e8d-e0cd936ad869",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"0 0\n",
"1 1\n",
"1 1\n",
"0 0\n"
]
}
],
"source": [
"print((0 + 0) % 2, 0 ^ 0)\n",
"print((1 + 0) % 2, 1 ^ 0)\n",
"print((0 + 1) % 2, 0 ^ 1)\n",
"print((1 + 1) % 2, 1 ^ 1)"
]
},
{
"cell_type": "markdown",
"id": "c8d5f916-5415-410a-991a-b2893ff5a69b",
"metadata": {},
"source": [
"<br>\n",
"\n",
"The group $(\\,\\{T, F\\}^N, \\,\\oplus\\,)$ is also isomorphic to the group $(\\,\\text{S}^N, \\, \\Delta \\;)$ of **symmetric difference** $\\Delta$ over the **power set** of $N$ elements (set of all possible subsets of $\\text{S}$).\n",
"\n",
"Symmetric difference is a **set** operation that gives the set of elements that are in either of the sets but **not in their intersection**:\n",
"\n",
"$$\n",
"\\begin{align}\n",
"A \\, \\Delta \\, B &= (A / B) \\cup (B / A) \\qquad \\text{or} \\\\[8pt]\n",
"A \\, \\Delta \\, B &= (A \\cup B) / (B \\cap A)\n",
"\\end{align}\n",
"$$\n",
"\n",
"→ The isomorphism maps $T$ to *included in the set* and $F$ to *excluded from the set* for each of the $N$ entries of the Boolean vector.\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "aba84d4b-317e-44a7-9df8-fdc9b89dc6f3",
"metadata": {},
"source": [
"### Properties of the XOR Operation\n",
"\n",
"#### Toggling\n",
"\n",
"The combined value $A \\oplus B$ *remembers* both states, and one state is the key to getting at the other:\n",
"\n",
"$$\n",
"\\begin{align}\n",
"A \\oplus (A \\oplus B) &= (A \\oplus A) \\oplus B \\\\[6pt]\n",
"&= 0 \\oplus B \\\\[6pt]\n",
"&= B\n",
"\\end{align}\n",
"$$\n",
"\n",
"and\n",
"\n",
"$$\n",
"\\begin{align}\n",
"B \\oplus (A \\oplus B) &= B \\oplus (B \\oplus A) \\\\[6pt]\n",
"&= (B \\oplus B) \\oplus A \\\\[6pt]\n",
"&= 0 \\oplus A \\\\[6pt]\n",
"&= A\n",
"\\end{align}\n",
"$$\n",
"\n",
"#### Parity\n",
"\n",
"A powerful interpretation of XOR is in terms of parity, i.e. whether something is odd or even. \n",
"\n",
"For any $n$ bits, $A_1 \\oplus A_2 \\oplus \\ldots \\oplus A_n = 1$ if and only if the number of $1$s is **odd**.\n",
"\n",
"<br>\n",
"\n",
"An application of XOR’s parity property is **RAID** (Redundant Arrays of Inexpensive Disks) which is a way to recover from hard drive corruption. \n",
"\n",
"If we have $n$ hard drives, we can create an **additional** one $A^*$ which contains the XOR value of all the others:\n",
"\n",
"$$\n",
"A^* = A_1 \\oplus A_2 \\oplus \\ldots \\oplus A_n\n",
"$$\n",
"\n",
"This introduces redundancy: if a failure occurs on one drive, say $A_1$, we can **restore** it from **the others** since:\n",
"\n",
"$$\n",
"\\begin{align}\n",
"A_2 \\oplus \\ldots \\oplus A_n \\oplus A^* &= A_2 \\oplus \\ldots \\oplus A_n \\oplus (A_1 \\oplus A_2 \\oplus \\ldots \\oplus A_n) \\\\[6pt]\n",
"&= A_1 \\oplus (A_2 \\oplus A_2) \\oplus \\ldots \\oplus (A_n \\oplus A_n) \\\\[6pt]\n",
"&= A_1 \\oplus 0 \\oplus \\ldots \\oplus 0 \\\\[6pt]\n",
"&= A_1\n",
"\\end{align}\n",
"$$\n",
"\n",
"(this is the same reasoning used to explain toggling earlier, but applied to $n$ inputs rather than just $2$)\n",
"\n",
"In the (highly unlikely) event that 2 drives fail simultaneously, the above would not be applicable so there would be no way to recover the data."
]
},
{
"cell_type": "markdown",
"id": "12ccdd74-43a0-4b61-98a1-3d4cee456d55",
"metadata": {},
"source": [
"# Cryptography Principles\n",
"\n",
"## Kerckhoffs's Principle\n",
"\n",
"<span style=\"background-color:rgba(255,0,0,0.3)\"> TODO </span>\n",
"\n",
"## Key-Space\n",
"\n",
"The **key space** should be large enough to prevent **brute-force** and exhaustive-search attacks."
]
},
{
"cell_type": "markdown",
"id": "aec82972-a1d6-4590-b43d-360644096210",
"metadata": {},
"source": [
"# Encryption Schemes\n",
"\n",
"<div style=\"border:solid 2px #ccc;padding:1rem;\">\n",
" \n",
"A private-key encryption scheme $(\\textbf{M}, \\textbf{K}, \\text{Gen}, \\text{Enc}_k, \\text{Dec}_k)$ is defined by a message space with the algorithms:\n",
"\n",
"1. **Key generation** $\\text{Gen}$ which generates a **key** $k \\in \\textbf{K}$ from the **key space**,\n",
"\n",
"<br>\n",
"\n",
"2. **Encryption** $\\text{Enc}_k$ which takes key $k$ and message $m \\in \\textbf{M}$ from the **message space** as input and outputs a **ciphertext** $c \\in \\textbf{C}$ from the **ciphertext space**\n",
"\n",
"$$c \\gets \\text{Enc}_k (m)$$\n",
"\n",
"<br>\n",
"\n",
"3. **Decryption** $\\text{Dec}_k$ which takes key $k$ and ciphertext $c$ as input and outputs message $m$\n",
"\n",
"$$m := \\text{Dec}_k (c)$$\n",
"\n",
"<br>\n",
"\n",
"$\\text{Dec}_k$ should decrypt **correctly**:\n",
"\n",
"$$\\forall k, \\forall m: \\quad \\text{Dec}_k(\\text{Enc}_k(m)) = m$$\n",
"\n",
"</div>\n",
"\n",
"<br>\n",
"\n",
"Here \n",
"\n",
"* the **left arrow** $\\gets$ notation denotes assignment to the output of an algorithm that might be **randomized**. Meaning that the output of the algorithm may be different, even when run twice on the same set of inputs,\n",
"\n",
"* the **colon equals** $:=$ denotes an assignment to the output of a **deterministic** algorithm and\n",
"\n",
"* If the key $k$ is the same for encryption and decryption, then we call it a **symetrci cipher**."
]
},
{
"cell_type": "markdown",
"id": "678a033e-58de-4550-b60d-5d64572176ad",
"metadata": {},
"source": [
"## On Probability\n",
"\n",
"* a **random valriable** is a variable that takes on (discrete) values with certain **probabilities**.\n",
"\n",
"* a **probability distribution** of a random variable specifies the probabilities with which the variable taes on each possible value\n",
"\n",
"* an **event** $\\text{E}$ is a particular occurence in some experiment with the probability $\\text{P}[\\,\\text{E}\\,]$\n",
"\n",
"* the probability that one event occurs, *assuming* some other event occured is called **conditional probability** ( $\\cap$ corresponds to \"and\")\n",
"\n",
"$$\\text{P}[\\,\\text{A}\\, | \\,\\text{B}\\,] = \\frac{\\text{P}[\\,\\text{A}\\, \\cap \\text{B}\\,]}{\\text{P}[\\,\\text{B}\\,]}$$\n",
"\n",
"* two random variables $\\text{A}$ and $\\text{B}$ are **independent** if for all $a$ and $b$\n",
"\n",
"$$\\text{P}[\\,\\text{A} = a\\, | \\,\\text{B} = b\\,] = \\text{P}[\\,\\text{A} = a\\,]$$\n",
"\n",
"* **Law of total probability**: given that $\\text{E}_1, \\ldots, \\text{E}_n$ are *partitions* of all possibilities, then for any $\\text{A}$\n",
"\n",
"$$\n",
"\\begin{align}\n",
"\\text{P}[\\,\\text{A}\\,] &= \\sum_i \\text{P}[\\,\\text{A} \\cap \\text{E}_i\\,] \\qquad \\text{or alternatively} \\\\[6pt]\n",
"&= \\sum_i \\text{P}[\\,\\text{A}\\, | \\,\\text{E}_i\\,] \\cdot \\text{P}[\\,\\text{E}_i\\,]\n",
"\\end{align}\n",
"$$\n",
"\n",
"* **Bayes Theorem**\n",
"\n",
"$$\n",
"\\text{P}[\\,\\text{A}\\, | \\,\\text{B}\\,] = \\frac{\\text{P}[\\,\\text{B}\\, | \\,\\text{A}\\,] \\cdot \\text{P}[\\,\\text{A}\\,]}{\\text{P}[\\,\\text{B}\\,]}\n",
"$$\n"
]
},
{
"cell_type": "markdown",
"id": "b24fa638-8e20-4f66-9a74-02b7b190edc7",
"metadata": {},
"source": [
"## Probability Distributions of Encryption Schemes\n",
"\n",
"Let $\\text{M}$ be a **random variable** denoting the value of a message from the **message space** $\\textbf{M}$ (set of all possible messages).\n",
"\n",
"This reflects the likelyhood of different messages sent by the parties, given the **attackers prior knowledge**, e.g.\n",
"\n",
"$$\n",
"\\begin{align}\n",
"&\\text{P}[\\, \\text{M} = \\text{attack today}\\,] = 0.7 \\\\\n",
"&\\text{P}[\\, \\text{M} = \\text{do not attack}\\,] = 0.3\n",
"\\end{align}\n",
"$$\n",
"\n",
"<br>\n",
"\n",
"Let $\\text{K}$ be a **random variable** denoting the key from the **key space** $\\textbf{K}$ (set of all possible keys).\n",
"\n",
"Given a **encryption scheme** $(\\text{Gen}, \\text{Enc}_k, \\text{Dec}_k)$, then $\\text{Gen}$ defines a **probability distribution** for $\\text{K}$:\n",
"\n",
"$$\n",
"\\text{P}[\\,\\text{K} = k\\,] = \\text{P}[\\,\\text{Gen outputs key}\\; k\\,]\n",
"$$\n",
"\n",
"**Example**: consider the shift cipher where the key space is $\\textbf{K} = (0, \\ldots, 25)$, then $\\text{P}[\\, \\text{K} = 15\\,] = 1/26$ \n",
"\n",
"Here we make the reasonable **assumption**, that $\\text{M}$ and $\\text{K}$ are **independent** variables, i.e. the message that a party sends does not depend on the key used to encrypt the message.\n",
"\n",
"<br>\n",
"\n",
"Given an encryption scheme $(\\text{Gen}, \\text{Enc}_k, \\text{Dec}_k)$, then a message $m$ according the given distribution $\\text{M}$ defines a **distribution** of the **ciphertext**.\n",
"\n",
"Let $\\text{C}$ be the **random variable** denoting the value of the ciphertext from the **ciphertext space** $\\textbf{C}$ (set of all possible ciphertexts).\n",
"\n",
"<br>\n",
"\n",
"### Example 1\n",
"\n",
"Given a **shift cipher**, then for all $k \\in \\{0, \\ldots, 25\\}$ we have $\\text{P}[\\, \\text{K} = k\\,] = 1/26$.\n",
"\n",
"Say we have the distribution\n",
"\n",
"$$\n",
"\\begin{align}\n",
"&\\text{P}[\\,\\text{M} = \\text{a}\\,] = 0.7 \\\\\n",
"&\\text{P}[\\, \\text{M} = \\text{z}\\,] = 0.3\n",
"\\end{align}\n",
"$$\n",
"\n",
"then what is $\\text{P}[\\, \\text{C} = \\text{b}\\,]$?\n",
"\n",
"The ciphertext $\\text{C}$ can only be $\\text{b}$, if $\\text{M} = \\text{a}$ and $\\text{K} = 1$ or if $\\text{M} = \\text{z}$ and $\\text{K} = 2$, hence\n",
"\n",
"$$\n",
"\\begin{align}\n",
"\\text{P}[\\,\\text{C} = \\text{b}\\,] &= \\text{P}[\\,\\text{M} = \\text{a}\\,] \\cdot \\text{P}[\\,\\text{K} = 1\\,] + \\text{P}[\\,\\text{M} = \\text{z}\\,] \\cdot \\text{P}[\\,\\text{K} = 2\\,] \\\\[7pt]\n",
"&= 0.7 \\cdot 1/26 + 0.3 \\cdot 1/26 \\\\[7pt]\n",
"&= 1/26 \\\\\n",
"\\end{align}\n",
"$$\n",
"\n",
"### Example 2\n",
"\n",
"Consider a **shift cipher** and the message distribution \n",
"\n",
"$$\n",
"\\begin{align}\n",
"&\\text{P}[\\,\\text{M} = \\text{one}\\,] = 0.5 \\\\\n",
"&\\text{P}[\\, \\text{M} = \\text{ten}\\,] = 0.5\n",
"\\end{align}\n",
"$$\n",
"\n",
"What is $\\text{P}[\\, \\text{C} = \\text{rqh}\\,]$?\n",
"\n",
"Due to the **law of total probability** we calculate\n",
"\n",
"$$\n",
"\\begin{align}\n",
"\\text{P}[\\,\\text{C} = \\text{rqh}\\,] &= \\text{P}[\\,\\text{C} = \\text{rqh}\\, | \\, \\text{M} = \\text{one}\\,] \\cdot \\text{P}[\\, \\text{M} = \\text{one}\\,] + \\text{P}[\\,\\text{C} = \\text{rqh}\\, | \\, \\text{M} = \\text{ten}\\,] \\cdot \\text{P}[\\, \\text{M} = \\text{ten}\\,] \\\\[7pt]\n",
"&= 1/26 \\cdot 0.5 + 0 \\cdot 0.5 \\\\[7pt]\n",
"&= 1/52 \\\\\n",
"\\end{align}\n",
"$$"
]
},
{
"cell_type": "markdown",
"id": "484de2a7-59b4-4271-9c6f-f9dae1e45a12",
"metadata": {},
"source": [
"# Core Principles of Modern Cryptography\n",
"\n",
"1. **Formal Definitions**: precise mathematical model and definition of what security means\n",
"\n",
"2. **Assumptions**: clearly stated and unambigious\n",
"\n",
"3. **Proofs of Security**: move away from design-break-patch"
]
},
{
"cell_type": "markdown",
"id": "2101cbda-f06b-4587-9794-338c2502dc0a",
"metadata": {},
"source": [
"# Perfect Secrecy\n",
"\n",
"## Informal Definition of Perfect Secrecy\n",
"\n",
"> \"Regardless of any **prior** information the attacker has about the plaintext, the ciphertext should leak **no additional** information about the plaintext\"\n",
"\n",
"<br>\n",
"\n",
"We cannot hide what may be a priori known about the message. Prior information about the message might for example be: it is in English, starts with \"Hello\", contains today's date, etc.\n",
"\n",
"<br>\n",
"\n",
"## Formal Definition of Perfect Secrecy\n",
"\n",
"The following definitions of **Shannon secrecy** is **equivalent** to the definition of **perfect secrecy**.\n",
"\n",
"### Shannon Secrecy\n",
"\n",
"The probability of seeing *a posteriori* a message $m$ after the ciphertext $c$ has been observed by an attacker, is **the same** as the *apriori* probability of seeing the message $m$ without the ciphertext, i.e. seeing a ciphertext doesn't give the attacker any extra information about the plaintext. \n",
"\n",
"$$\n",
"\\text{P}[\\, \\text{M} = m\\, | \\, \\text{C} = c \\,] = \\text{P}[\\, \\text{M} = m \\,]\n",
"$$\n",
"\n",
"<br><br>\n",
"\n",
"Let $\\text{M}$ be a random variable for sampling the messages $m$ from the message space $\\textbf{M}$. The distribution $\\text{M}$ is known to the adversary. This captures *a priori* information about the messages.\n",
"\n",
"The ciphertext $c \\gets \\text{Enc}_k (m)$ induces a distribution $\\text{C}$ over the ciphertexts $c$. The attacker obly observes $c$.\n",
"\n",
"The knowledge of the attacker about $m$ **before** observing the output of $\\text{C}$ is the distribution $\\text{P}[\\, \\text{M} \\,]$ (e.g. the knowledge that the message is in english).\n",
"\n",
"The knowledge of the attacker about $m$ **after** observing the output of $\\text{C}$ is the distribution $\\text{P}[\\, \\text{M}\\, | \\, \\text{C} \\,]$.\n",
"\n",
"**Shannon Secrecy**: distribution $\\text{P}[\\, \\text{M} \\,]$ and $\\text{P}[\\, \\text{M}\\, | \\, \\text{C} \\,]$ must be **identical**. Intuitively, this means that $\\text{C}$ contains no **new** information about $m$.\n",
"\n",
"<br>\n",
"\n",
"### Perfect Secrecy\n",
"\n",
"The probability of ciphertext $c$ is **equally likely** for each pair of messages $m_0$ and $m_1$.\n",
"\n",
"$$\n",
"\\text{P}[\\, \\text{C} = c\\, | \\, \\text{M} = m_0 \\,] = \\text{P}[\\, \\text{C} = c\\, | \\, \\text{M} = m_1 \\,]\n",
"$$\n",
"\n",
"This definition is simpler than Shannon Secrecy, it basically says that\n",
"\n",
"> Even if given a **choice** of **two plaintexts** for a ciphertext, where one the real one, you **cannot distinguish** which plaintext is the **real one**.\n",
"\n",
"<br>\n",
"\n",
"### Perfect Indistinguishability\n",
"\n",
"Let $\\Pi = (\\text{Gen}, \\text{Enc}, \\text{Dec})$ be an encryption scheme, and let $A$ be an adversary (or Algorithm). Say we have two messages $m_0$ and $m_1$ and one is choosen at random and encrypted (using an uniform $k$). If an adversary $A$ given $c$ and tries to determine which message was encrypted, then \n",
"\n",
"> *$\\Pi$ is secure if no adversary $A$ can guess correctly with probability any better than $1/2$*\n",
"\n",
"<br>\n",
"\n",
"Define a **randomized experiment** $\\text{K}_{A, \\Pi}$ which depend on $A$ and $\\Pi$:\n",
"\n",
"1. $A$ outputs $m_0, m_1 \\in \\textbf{M}$ (i.e. $A$ knows both messages)\n",
"\n",
"2. $k \\gets Gen$, $b \\gets \\{0, 1\\}$ and $c \\gets \\text{Enc}_k(m_b)$ ($c$ is called the **challenge cipertext**)\n",
"\n",
"3. $b' \\gets A(c)$\n",
"\n",
"4. $A$ succeeds if $b = b'$ and the experiment evaluates to $1$ in this case.\n",
"\n",
"This experiment is easy to succeed with probability $1/2$ because if an attacker $A$ outputs a **random guess** for its bit $b'$, it will be correct with probability exactly $1/2$.\n",
"\n",
"<br>\n",
"\n",
"The encryption scheme $\\Pi$ is **perfectly indistinguishable**, if for all **attackers** $A$ it holds that the attacker **succeeds** with probability exactly $1/2$:\n",
"\n",
"$$\n",
"\\text{P}[\\text{K}_{A, \\Pi} = 1] = \\frac{1}{2}\n",
"$$\n",
"\n",
"That is to say \n",
"\n",
"> *there's **no** possible **attacker** $A$ that can succeed any **better** than **one-half***.\n",
"\n",
"The scheme $\\Pi$ is perfectly indistinguishable **if and only if** it is **perfectly secret**.\n",
"\n",
"<br>\n",
"\n",
"### Constraints\n",
"\n",
"The key is as long as the message and a key should be used **uniquely** with a probability $\\frac{1}{|\\textbf{K}|}$, where $|\\textbf{K}|$ is the size of the key space $\\textbf{K}$.\n",
"\n",
"<br>\n",
"\n",
"### Equivalence Theorem\n",
"\n",
"A private-key encryption scheme is perfectly secure **if and only if** it is Shannon secure.\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "05035855-1e81-4f1c-8955-e689632fde30",
"metadata": {},
"source": [
"### Example 3\n",
"\n",
"The **shift cipher** has a key space of size $|\\text{K}| = 26$. To achieve perfect secrecy, it thus can have **at most** 26 plaintexts and ciphertexts. \n",
"\n",
"With a **message space** of **one character** (and every key only used once), it would fit the definition of perfect secrecy:\n",
"\n",
"<br>\n",
"\n",
"For **perfect secrecy** we must satisfy \n",
"\n",
"$$\n",
"|\\text{K}| \\geq |\\text{C}| \\geq |\\text{M}|\n",
"$$\n",
"\n",
"For **Shannon secrecy** let\n",
"\n",
"$$\n",
"|\\text{K}| = |\\text{C}| = |\\text{M}|\n",
"$$\n",
"\n",
"then we have perfect secrecy **if and only if**:\n",
"\n",
"1. each key is used with same probability, and\n",
"2. for each $(m,c)$ pair there is unique key.\n",
"\n",
"With these rules, shift cipher has perfect secrecy."
]
},
{
"cell_type": "markdown",
"id": "d07391f8-3844-48aa-b787-05b3b0d58a9c",
"metadata": {},
"source": [
"### Example 4\n",
"\n",
"The **shift cipher** does **not** satisfy the perfect secrecy property if $|\\text{M}| \\geq 2$.\n",
"\n",
"**Proof**:\n",
"\n",
"Take $m_1 = \\text{ab}$, $m_2 = \\text{ac}$ and $c = \\text{bc}$\n",
"\n",
"Then\n",
"\n",
"$$\n",
"\\exists k \\in \\text{K}, \\quad \\text{Enc}_k(m_1) = c\n",
"$$\n",
"\n",
"namely $k = 1$.\n",
"\n",
"However\n",
"\n",
"$$\n",
"\\forall k \\in \\text{K}, \\quad \\text{Enc}_k(m_2) \\neq c\n",
"$$\n",
"\n",
"Hence\n",
"\n",
"$$\n",
"\\begin{align}\n",
"\\text{P}[\\, \\text{C} = \\text{bc} \\, | \\, \\text{M} = \\text{ab} \\,] &\\neq \\text{P}[\\, \\text{C} = \\text{bc} \\, | \\, \\text{M} = \\text{ac} \\,] \\\\[6pt]\n",
"\\frac{1}{26} &\\neq 0\n",
"\\end{align}\n",
"$$\n",
"\n",
"So the perfect secrecy requirement is violated, which requires above two probabilities to be equal."
]
},
{
"cell_type": "markdown",
"id": "b5a5f2f7-9210-474a-b308-af606931e54e",
"metadata": {},
"source": [
"### Example 5\n",
"\n",
"Consider a **shift cipher** and the message distribution\n",
"\n",
"$$\n",
"\\begin{align}\n",
"&\\text{P}[\\,\\text{M} = \\text{one}\\,] = 0.5 \\\\\n",
"&\\text{P}[\\, \\text{M} = \\text{ten}\\,] = 0.5\n",
"\\end{align}\n",
"$$\n",
"\n",
"Now, take as one particular message $m = \\text{ten}$ and as one particular ciphertext $c = \\text{rqh}$.\n",
"\n",
"What is the **probability** that the message is equal to $\\text{ten}$ conditioned on the fact that we **observed** a ciphertext $\\text{rqh}$?\n",
"\n",
"Because there is no key that match the message $m$ to the ciphertext $c$, that mean that if we observe to ciphertext $c$ it is not possible that the message is equal to $m$, hence it is not equal to the *prior probability* that the message is $\\text{ten}$:\n",
"\n",
"$$\n",
"\\begin{align}\n",
"\\text{P}[\\, \\text{M} = \\text{ten}\\, | \\, \\text{C} = \\text{rqh} \\,] &= 0 \\\\[7pt]\n",
"&\\neq \\text{P}[\\, \\text{M} = \\text{ten} \\,]\n",
"\\end{align}\n",
"$$\n",
"\n",
"This shows that the **shift cipher** does **not meet the definition** of **perfect secrecy**."
]
},
{
"cell_type": "markdown",
"id": "2a932d64-8d7b-4909-bf66-72b9dc37b3d5",
"metadata": {},
"source": [
"### Example 6\n",
"\n",
"Consider a **shift cipher** and the message distribution\n",
"\n",
"$$\n",
"\\begin{align}\n",
"&\\text{P}[\\,\\text{M} = \\text{hi}\\,] = 0.3 \\\\\n",
"&\\text{P}[\\,\\text{M} = \\text{no}\\,] = 0.2 \\\\\n",
"&\\text{P}[\\, \\text{M} = \\text{in}\\,] = 0.5\n",
"\\end{align}\n",
"$$\n",
"\n",
"What is the **probability** $\\text{P}[\\, \\text{M} = \\text{hi}\\, | \\, \\text{C} = \\text{xy} \\,]$ that the message is equal to $\\text{hi}$ conditioned on the fact that we **observed** a ciphertext $\\text{xy}$?\n",
"\n",
"With\n",
"\n",
"$$\n",
"\\begin{align}\n",
"\\text{P}[\\, \\text{C} = \\text{xy}\\, | \\, \\text{M} = \\text{hi} \\,] = 1/26\n",
"\\end{align}\n",
"$$\n",
"\n",
"and due to the law of total probability\n",
"\n",
"$$\n",
"\\begin{align}\n",
"\\text{P}[\\,\\text{C} = \\text{xy} \\,] &= \\text{P}[\\, \\text{C} = \\text{xy}\\, | \\, \\text{M} = \\text{hi} \\,] \\cdot 0.3 + \\text{P}[\\,\\text{C} = \\text{xy}\\, | \\, \\text{M} = \\text{no} \\,] \\cdot 0.2 + \\text{P}[\\,\\text{C} = \\text{xy}\\, | \\, \\text{M} = \\text{in} \\,] \\cdot 0.5 \\\\[7pt]\n",
"&= 1/26 \\cdot 0.3 + 1/26 \\cdot 0.2 + 0 \\cdot 0.5 \\\\[7pt]\n",
"&= 1/52\n",
"\\end{align}\n",
"$$\n",
"\n",
"we can calculate using the Bayes theorem\n",
"\n",
"$$\n",
"\\begin{align}\n",
"\\text{P}[\\, \\text{M} = \\text{hi}\\, | \\, \\text{C} = \\text{xy} \\,] &= \\frac{\\text{P}[\\, \\text{C} = \\text{xy}\\, | \\, \\text{M} = \\text{hi} \\,] \\cdot \\text{P}[\\,\\text{M} = \\text{hi} \\,]}{\\text{P}[\\,\\text{C} = \\text{xy} \\,]} \\\\[7pt]\n",
"&= \\frac{1/26 \\cdot 0.3}{1/52} \\\\[7pt]\n",
"&= 0.6 \\\\[7pt]\n",
"&\\neq \\text{P}[\\, \\text{M} = \\text{hi} \\,]\n",
"\\end{align}\n",
"$$\n",
"\n",
"This again shows that the **shift cipher** is **not perfectly secret**."
]
},
{
"cell_type": "markdown",
"id": "fb363dc2-25af-428b-ae20-375f4c7d00f1",
"metadata": {},
"source": [
"### Example 7 (Perfect Indistinguishability)\n",
"\n",
"Let $\\Pi$ be the shift cipher. \n",
"\n",
"For which of the following attackers (Algorithms) $A$ is $\\text{P}[\\text{K}_{A, \\Pi} = 1] > \\frac{1}{2}$?\n",
"\n",
"1. $A$ outputs $m_0 = \\text{a}$ and $m_1 = \\text{b}$. Given a one-character ciphertext $c$, output $0$ if and only if $c = \\text{a}$.\n",
"\n",
"2. $A$ outputs $m_0 = \\text{az}$ and $m_1 = \\text{ab}$. Given a two-character ciphertext $c_1c_2$, output $0$ if and only if $c_1 \\neq c_2$.\n",
"\n",
"3. $A$ outputs $m_0 = \\text{ab}$ and $m_1 = \\text{aa}$. Given a two-character ciphertext $c_1c_2$, output $0$ if and only if $c_1 \\neq c_2$.\n",
"\n",
"4. There is no such attacker, since the shift cipher is perfectly secret\n",
"\n",
"→ The answer is 3., because the attacker can determine which ciphertext $c_1c_2$ determines to $m_0$ and to $m_1$.\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "42f2a482-a483-471c-bf6f-9e133a5495c1",
"metadata": {},
"source": [
"## One-Time Pad (OTP)\n",
"\n",
"The encryption scheme that achieves **perfect secrecy** is the **one-time pad**. It was proven perfectly secret by **Shannon** in 1949.\n",
"\n",
"<br>\n",
"\n",
"If decryption is to be prevented by frequency analysis, a key may only be used for one message and must also be as long as the message. Such a concept already exists, it is called a one-time pad (Einmalblock).\n",
"\n",
"The one-time pad consists of a very long and randomly selected key. The sender of a message encrypts each plaintext character with the key bits on his one-time pad. The recipient has an identical block and decodes the individual bits of the cipher using the key characters on his block. The block are then destroyed. New key bits are used for a new message.\n",
"\n",
"If the key is an equally distributed random sequence of bits and nobody gains access to the one-time pad that was used to encrypt the message, this concept is absolutely secure. This is because there are **as many possible keys as there are possible plaintexts**, so a particular ciphertext can belong to any of the reconstructable plaintexts of the same length with the same probability.\n",
"\n",
"<br>\n",
"\n",
"### The One-Time Pad Encryption Scheme\n",
"\n",
"The one-time pad **encryption scheme** is defined as:\n",
"\n",
"* Let $\\textbf{M} = \\{0, 1\\}^n$ (the set of all binary strings of length $n$, i.e. an $n$-bit string)\n",
"\n",
"* $\\text{Gen}$: choose an uniform **key** $k \\in \\{0, 1\\}^n$. Each possible $n$-bit string is chosen with probability $\\text{P}[K] = 2^{-n}$. There are $2^n$ different strings of length $n$.\n",
"\n",
"* $\\text{Enc}_k(m) = k \\oplus m$ (bit-wise XOR)\n",
"\n",
"* $\\text{Dec}_k(c) = k \\oplus c$\n",
"\n",
"This scheme is **correct**, as\n",
"\n",
"$$\n",
"\\begin{align}\n",
"\\text{Dec}_k(\\text{Enc}_k(m)) &= k \\oplus (k \\oplus m) \\\\[6pt]\n",
"&= (k \\oplus k) \\oplus m \\\\[6pt]\n",
"&= 0 \\oplus m \\\\[6pt]\n",
"&= m\n",
"\\end{align}\n",
"$$"
]
},
{
"cell_type": "markdown",
"id": "30f3209a-96d1-4538-bd47-1c09c149c8c9",
"metadata": {},
"source": [
"### Perfect Secrecy of the One-Time Pad\n",
"\n",
"The One Time Pad is perfectly secure.\n",
"\n",
"**Prove**: \n",
"\n",
"Let's agree on some **arbitrary distribution** over the message space $\\textbf{M} \\in \\{0, 1\\}^N$, and agree on some **arbitrary message** $m$ and **arbitrary cyphertext** $c$.\n",
"\n",
"Then using the **law of total probability** we can calculate the probability of the ciphertext $c$ by summation over all possible messages $m'$:\n",
"\n",
"$$\n",
"\\begin{align}\n",
"\\text{P}[\\, \\text{C} = c \\,] &= \\sum_{m'} \\text{P}[\\, \\text{C} = c \\, | \\, \\text{M} = m' \\,] \\cdot \\text{P}[\\, \\text{M} = m' \\,] \\\\[6pt]\n",
"&= \\sum_{m'} \\text{P}[\\, \\text{K} = m' \\oplus c \\,] \\cdot \\text{P}[\\, \\text{M} = m' \\,] \\\\[6pt]\n",
"&= \\sum_{m'} 2^{-n} \\cdot \\text{P}[\\, \\text{M} = m' \\,] \\\\[6pt]\n",
"&= 2^{-n}\n",
"\\end{align}\n",
"$$\n",
"\n",
"We then calculate using Bayes Law\n",
"\n",
"$$\n",
"\\begin{align}\n",
"\\text{P}[\\, \\text{M} = m \\, | \\, \\text{C} = c \\,] &= \\frac{\\text{P}[\\, \\text{C} = c \\, | \\, \\text{M} = m \\,] \\cdot \\text{P}[\\, \\text{M} = m\\,]}{\\text{P}[\\text{C} = c \\,]} \\\\[6pt]\n",
"&= \\frac{\\text{P}[\\, \\text{K} = m \\oplus c \\,] \\cdot \\text{P}[\\, \\text{M} = m\\,]}{2^{-n}} \\\\[6pt]\n",
"&= \\frac{2^{-n} \\cdot \\text{P}[\\, \\text{M} = m\\,]}{2^{-n}} \\\\[6pt]\n",
"&= \\text{P}[\\, \\text{M} = m\\,]\n",
"\\end{align}\n",
"$$\n",
"\n",
"Here, \n",
"\n",
"* $\\text{P}[\\, \\text{C} = c \\, | \\, \\text{M} = m \\,]$ represents the probability that ciphertext $c$ is produced given plaintext $m$.\n",
"\n",
"* $\\text{P}[\\, \\text{K} = m \\oplus c \\,]$ represents the probability that key $k$ is chosen such that XORing it with plaintext $m$ produces ciphertext $c$.\n",
"\n",
"In a one-time pad, since each key is as likely as any other, the **probability** of **choosing a specific key** is the **same** as the **probability** of obtaining a **specific ciphertext** when that **key is used**. This is because each bit of the ciphertext is completely dependent on the corresponding bit of the key, and there is no bias or pattern introduced in the encryption process.\n",
"\n",
"So, $\\text{P}[\\, \\text{C} = c \\, | \\, \\text{M} = m \\,] = \\text{P}[\\, \\text{K} = m \\oplus c \\,]$ essentially reflects the inherent randomness and uniformity of the key selection process in a one-time pad cipher."
]
},
{
"cell_type": "markdown",
"id": "f8b0c51f-2407-4a8a-b8af-d21784054669",
"metadata": {},
"source": [
"### Disadvantages of the One-Time Pad\n",
"\n",
"The fact that other ciphertext methods are still being used, even though an absolutely secure method is known, is due to the **disadvantages of the one-time pad**:\n",
"\n",
"1. The key must be the **same length as the plaintext** and must be available to the recipient.\n",
"\n",
"2. Statistical deviations can lead to the system becoming insecure. The probability distribution on the key space must be the **uniform distribution** using cryptographically **secure random number** generators.\n",
"\n",
"3. Each key is **only used once** and must be **securely destroyed**.\n",
"\n",
"The problem is the transmission of such a key and the error-free use of the same key. Therefore, the procedure is generally not suitable for practical use.\n",
"\n",
"<br>\n",
"\n",
"Supposed you are using the **key twice**:\n",
"\n",
"$$\n",
"\\begin{align}\n",
"c_1 &= k \\oplus m_1 \\\\[6pt]\n",
"c_2 &= k \\oplus m_2\n",
"\\end{align}\n",
"$$\n",
"\n",
"then the **attacker** can compute\n",
"\n",
"$$\n",
"\\begin{align}\n",
"c_1 \\oplus c_2 &= (k \\oplus m_1) \\oplus (k \\oplus m_2) \\\\[6pt]\n",
"&= m_1 \\oplus m_2\n",
"\\end{align}\n",
"$$\n",
"\n",
"This **leaks information** about $m_1$ and $m_2$ makeing OTP no longer perfectly secret, e.g.:\n",
"\n",
"* $m_1 \\oplus m_2$ revelas exactly where $m_1$ and $m_2$ differ (the XOR is $1$ at diff positions)\n",
"\n",
"* even for XOR'd messages, frequency analysis is possible.\n",
"\n",
"* it's possible to exploit a specific characteristic of the ASCII representation table (see below)."
]
},
{
"cell_type": "markdown",
"id": "92f667c7-7678-4202-995d-93c613046a62",
"metadata": {},
"source": [
"### ASCII-Exploit of the One-Time Pad\n",
"\n",
"Inspecting the ASCII table shows that **all letters** begin with `01` and that the **whitespace** character `00100000` starts with `00`:"
]
},
{
"cell_type": "code",
"execution_count": 21,
"id": "d81c7226-cedd-45da-9a40-868d5d002bf0",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" 0000000 NUL 0010000 DLE 0100000 0110000 0 1000000 @ 1010000 P 1100000 ` 1110000 p \n",
" 0000001 SOH 0010001 DC1 0100001 ! 0110001 1 1000001 A 1010001 Q 1100001 a 1110001 q \n",
" 0000010 STX 0010010 DC2 0100010 \" 0110010 2 1000010 B 1010010 R 1100010 b 1110010 r \n",
" 0000011 ETX 0010011 DC3 0100011 # 0110011 3 1000011 C 1010011 S 1100011 c 1110011 s \n",
" 0000100 EOT 0010100 DC4 0100100 $ 0110100 4 1000100 D 1010100 T 1100100 d 1110100 t \n",
" 0000101 ENQ 0010101 NAK 0100101 % 0110101 5 1000101 E 1010101 U 1100101 e 1110101 u \n",
" 0000110 ACK 0010110 SYN 0100110 & 0110110 6 1000110 F 1010110 V 1100110 f 1110110 v \n",
" 0000111 BEL 0010111 ETB 0100111 ' 0110111 7 1000111 G 1010111 W 1100111 g 1110111 w \n",
" 0001000 BS 0011000 CAN 0101000 ( 0111000 8 1001000 H 1011000 X 1101000 h 1111000 x \n",
" 0001001 HT 0011001 EM 0101001 ) 0111001 9 1001001 I 1011001 Y 1101001 i 1111001 y \n",
" 0001010 LF 0011010 SUB 0101010 * 0111010 : 1001010 J 1011010 Z 1101010 j 1111010 z \n",
" 0001011 VT 0011011 ESC 0101011 + 0111011 ; 1001011 K 1011011 [ 1101011 k 1111011 { \n",
" 0001100 FF 0011100 FS 0101100 , 0111100 < 1001100 L 1011100 \\ 1101100 l 1111100 | \n",
" 0001101 CR 0011101 GS 0101101 - 0111101 = 1001101 M 1011101 ] 1101101 m 1111101 } \n",
" 0001110 SO 0011110 RS 0101110 . 0111110 > 1001110 N 1011110 ^ 1101110 n 1111110 ~ \n",
" 0001111 SI 0011111 US 0101111 / 0111111 ? 1001111 O 1011111 _ 1101111 o 1111111 DEL \n"
]
}
],
"source": [
"! ascii -b"
]
},
{
"cell_type": "markdown",
"id": "45a75564-2155-463a-83d4-4214bda3812e",
"metadata": {},
"source": [
"Given **two ciper texts** encrypted with the **same key**, an attacker can XOR both ciphertexts and **identify letters** and **spaces** by guessing that \n",
"\n",
"* any byte with a prefix of `01` corresponds to the XOR of a **letter** and a **whitespace**, and\n",
"* any byte with a prefix of `00` corresponds to the XOR of **two letters**.\n",
"\n",
"This is **not perfect** as it is possible to have two space characters that XOR to a byte with prefix `00`. Also it is possible to have punctuation characters as well that might mess this up. Nevertheless, punctuation characters and pairs of spaces are expected to be much **less frequent** than pairs of two letters and pairs of a letter and a space.\n",
"\n",
"<br>\n",
"\n",
"Now, given a byte $b_i$ with prefix `01` at a position $i$, the attacker knows with high confidence that one of the two messages has a **whitespace** at this position $i$.\n",
"\n",
"The attacker can therefore determine the corresponding letter $\\text{letter}_i$ by XOR $b_i$ with the **whitespace** character $\\text{00100000}$:\n",
"\n",
"$$\n",
"\\begin{align}\n",
"00100000 \\oplus \\text{letter}_i &= b_i \\\\\n",
"00100000 \\oplus (00100000 \\oplus \\text{letter}_i) &= 00100000 \\oplus b_i \\\\\n",
"\\text{letter}_i &= 00100000 \\oplus b_i\n",
"\\end{align}\n",
"$$"
]
},
{
"cell_type": "markdown",
"id": "fa6f481d-eb82-4bae-bfce-9f08fdd17f82",
"metadata": {},
"source": [
"### Example 1"
]
},
{
"cell_type": "code",
"execution_count": 75,
"id": "d3408231-d69b-43b0-ab17-3178da3c297d",
"metadata": {},
"outputs": [],
"source": [
"import secrets\n",
"from textwrap import wrap\n",
"\n",
"def xor(a, b):\n",
" return [format(int(int(a, 2) ^ int(b, 2)), '08b') for a, b in zip(a, b)]\n",
" \n",
"def gen(size):\n",
" return [format(int(k, 16), '08b') for k in (wrap(secrets.token_hex(size), 2))]\n",
"\n",
"def enc(key, message):\n",
" message = [format(ord(m), '08b') for m in message]\n",
" return message, xor(key, message)"
]
},
{
"cell_type": "code",
"execution_count": 76,
"id": "dd82ad7d-eeb7-4621-9bf0-d5561c63326e",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" key: ['11011100', '10111110', '10000001', '00111101', '10001101', '10100001', '00011011', '00111110', '01010010', '10011001', '10100110']\n"
]
}
],
"source": [
"key = gen(11)\n",
"print(f' key: {key}')"
]
},
{
"cell_type": "code",
"execution_count": 77,
"id": "4f1a99f0-e755-4747-8cd4-b2c9f33dda3c",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" message: ['01001000', '01100101', '01101100', '01101100', '01101111', '00100000', '01010111', '01101111', '01110010', '01101100', '01100100']\n",
"ciphertext: ['10010100', '11011011', '11101101', '01010001', '11100010', '10000001', '01001100', '01010001', '00100000', '11110101', '11000010']\n"
]
}
],
"source": [
"m1, c1 = enc(key, 'Hello World')\n",
"print(f' message: {m1}')\n",
"print(f'ciphertext: {c1}')"
]
},
{
"cell_type": "code",
"execution_count": 78,
"id": "658f764e-31f7-4edc-9f0e-21b364eafda7",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" message: ['01000110', '01101111', '01101111', '00100000', '01000010', '01100001', '01110010', '00100000', '01000010', '01100001', '01111010']\n",
"ciphertext: ['10011010', '11010001', '11101110', '00011101', '11001111', '11000000', '01101001', '00011110', '00010000', '11111000', '11011100']\n"
]
}
],
"source": [
"m2, c2 = enc(key, 'Foo Bar Baz')\n",
"print(f' message: {m2}')\n",
"print(f'ciphertext: {c2}')"
]
},
{
"cell_type": "code",
"execution_count": 79,
"id": "779177eb-21ec-4b87-8d9d-19fe15f9f677",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"c_1 ⨁ c_2: ['00001110', '00001010', '00000011', '01001100', '00101101', '01000001', '00100101', '01001111', '00110000', '00001101', '00011110']\n"
]
}
],
"source": [
"print(f'c_1 ⨁ c_2: {xor(c1, c2)}')"
]
},
{
"cell_type": "code",
"execution_count": 80,
"id": "65e998db-41c1-416b-8e7e-47404b458de9",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"c_1 ⨁ c_2 = 00001110 00001010 00000011 \u001b[31m01001100\u001b[0m 00101101 \u001b[31m01000001\u001b[0m 00100101 \u001b[31m01001111\u001b[0m 00110000 00001101 00011110\n"
]
}
],
"source": [
"from termcolor import colored\n",
"print(f'c_1 ⨁ c_2 = {' '.join([colored(x, 'red') if x.startswith('01') else x for x in xor(c1, c2)])}')"
]
},
{
"cell_type": "code",
"execution_count": 81,
"id": "3aa77130-0274-4507-8601-5924c3e5751e",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"00001110 00001010 00000011 \u001b[31ml\u001b[0m 00101101 \u001b[31ma\u001b[0m 00100101 \u001b[31mo\u001b[0m 00110000 00001101 00011110\n"
]
}
],
"source": [
"print(f'{' '.join([colored(chr(int(x, 2) ^ int('00100000', 2)), 'red') if x.startswith('01') else x for x in xor(c1, c2)])}')"
]
},
{
"cell_type": "markdown",
"id": "d4d44a2b-d827-4dda-b4f8-a5315b673ae3",
"metadata": {},
"source": [
"<br>\n",
"\n",
"### Example 2\n",
"\n",
"Given **three ciphertexts** from encryption of ASCII plaintexts using the the **same key** $k_1 = k_2 = k_3$:\n",
"\n",
"1. The 10th byte of the **first** ciphertext is $c_1 = \\text{0xA8}$,\n",
"2. the 10th byte of the **second** ciphertext is $c_2 = \\text{0xED}$, and\n",
"3. the 10th byte of the **third** ciphertext is $c_3 = \\text{0xBD}$.\n",
" \n",
"What is the 10th ASCII character $m_3$ of the third plaintext?"
]
},
{
"cell_type": "code",
"execution_count": 5,
"id": "3b6e2f41-c94f-43a6-b889-6ca5f3526c91",
"metadata": {},
"outputs": [],
"source": [
"def xor(h1, h2):\n",
" print(f\"{format(int(h1, 16), '08b')} ⨁ {format(int(h2, 16), '08b')} = {format(int(int(h1, 16) ^ int(h2, 16)), '08b')}\")"
]
},
{
"cell_type": "code",
"execution_count": 6,
"id": "c79c5932-dac7-43ad-8647-fc5fdf4e7942",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"10101000 ⨁ 11101101 = 01000101\n"
]
}
],
"source": [
"xor('A8', 'ED')"
]
},
{
"cell_type": "markdown",
"id": "3b39a6f3-79be-4b83-a8da-8e6bff5b6253",
"metadata": {},
"source": [
"$m_1$ or $m_2$ is a whitespace as $c_1 \\oplus c_2 = m_1 \\oplus m_2 = \\text{01000101}$"
]
},
{
"cell_type": "code",
"execution_count": 7,
"id": "31bdf8ec-ee3b-4d75-bad4-d58d38b527ae",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"10101000 ⨁ 10111101 = 00010101\n"
]
}
],
"source": [
"xor('A8', 'BD')"
]
},
{
"cell_type": "markdown",
"id": "090f240e-8447-4137-a2b9-9988de8d68fc",
"metadata": {},
"source": [
"$m_1$ and $m_3$ are letters as $c_1 \\oplus c_3 = m_1 \\oplus m_3 = \\text{00010101}$"
]
},
{
"cell_type": "code",
"execution_count": 8,
"id": "76ae8a88-5c72-46b5-91c2-5155b88653ea",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"11101101 ⨁ 10111101 = 01010000\n"
]
}
],
"source": [
"xor('ED', 'BD')"
]
},
{
"cell_type": "markdown",
"id": "3d6922b1-d5c1-4155-83dc-2576df2bcf56",
"metadata": {},
"source": [
"$m_2$ or $m_3$ is a whitespace as $c_2 \\oplus c_3 = m_2 \\oplus m_3 = \\text{01010000}$"
]
},
{
"cell_type": "markdown",
"id": "e57c0828-5c60-4f6b-9a87-8b5ccff64deb",
"metadata": {},
"source": [
"→ from this follows that $m_2$ is a whitespace, hence \n",
"\n",
"$$\n",
"\\begin{align}\n",
"m_2 \\oplus m_3 &= c_2 \\oplus c_3 \\\\[6pt]\n",
"00100000 \\oplus m_3 &= 01010000 \\\\[6pt]\n",
"m_3 &= 01010000 \\oplus 00100000 \\\\[6pt]\n",
"m_3 &= 01110000\n",
"\\end{align}\n",
"$$ "
]
},
{
"cell_type": "code",
"execution_count": 89,
"id": "1c940444-1852-4286-ad82-e0996e6f955d",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'p'"
]
},
"execution_count": 89,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"chr(int('01010000', 2) ^ int('00100000', 2))"
]
},
{
"cell_type": "markdown",
"id": "e919aac1-9871-460e-9b2c-517a4217dfb9",
"metadata": {},
"source": [
"The 10th ASCII character $m_3$ is `p`."
]
},
{
"cell_type": "markdown",
"id": "3e7dc010-4753-477f-a7af-4323c6e4a5b2",
"metadata": {},
"source": [
"# Computational Secrecy\n",
"\n",
"Computational Secrecy is about **relaxing** perfect Indistinguishability.\n",
"\n",
"## Concrete Computational Secrecy\n",
"\n",
"$\\Pi$ is $(t, \\epsilon)$-indistinguishable if for any attackers $A$ running in time at most $t$, it holds that\n",
"\n",
"$$\n",
"\\text{P}[\\text{K}_{A, \\Pi} = 1] \\leq \\frac{1}{2} + \\epsilon\n",
"$$\n",
"\n",
"So,\n",
"\n",
"* Security may fail with probability $\\leq \\epsilon$\n",
"\n",
"* Restriction attention to attackers running in time $\\leq t$\n",
"<br>"
]
},
{
"cell_type": "markdown",
"id": "b66053bf-e08b-4571-9ab0-a41c0849e6bd",
"metadata": {},
"source": [
"## Asymptotic Computational Secrecy\n",
"\n",
"For asymptotic secrecy\n",
"\n",
"* we introdcuce a **security parameter** $n \\in \\mathbb{Z}^+$ (positive integer) which\n",
" * is fixed by honest parties at initialization\n",
" * allows users to tailor the security level (for now we consider this as the **key length**)\n",
" * is known be the adversary\n",
"* and we view the\n",
" * **running times** of all parties as a **function of $n$** and\n",
" * the **success probability** of the adversary as a **function of $n$**\n",
" \n",
"<br>\n",
"\n",
"For **computational indistinguishability** we **relax** the notions of **perfect indistinguishability** in the following:\n",
"\n",
"1. Security may fail with probability **negligible** in $n$\n",
"\n",
" A function $f: \\mathbb{Z}^+ \\to \\mathbb{R}^{+,0}$ is **negligible** if for every polynomial $p$ \n",
"\n",
" $$\n",
" \\exists \\, N \\; \\text{s.t.} \\quad f(n) < \\frac{1}{p(n)} \\quad \\forall \\, n > N \n",
" $$\n",
" \n",
" A typical example is: $f(n) = \\text{poly}(n) \\cdot 2^{-cn}$.\n",
"\n",
" This means that the function $f$ is negligible, if it's **asymptotically smaller** than any **inverse polynomial function**.\n",
"\n",
"<br>\n",
"\n",
"2. Restrict attention to attackers running in time **polynomial** in $n$\n",
"\n",
" A function $f: \\mathbb{Z}^+ \\to \\mathbb{Z}^+$ is **polynomial** if \n",
"\n",
" $$\n",
" \\exists \\, c_i \\; \\text{s.t.} \\quad f(n) < \\sum_i c_i \\, n^i \\quad \\forall \\, n\n",
" $$\n",
"\n",
"<br>\n",
"\n",
"This notion of **negligibility** and **polynomiality** are choosen due to\n",
"\n",
"1. being **efficient** in the sense of **probabilistic polynomial time** (PPT)\n",
"\n",
"2. having convinient **closure properties**:\n",
" \n",
" * $\\text{poly} \\cdot \\text{poly} = \\text{poly}$\n",
" \n",
" → poly-many calls to PPT subroutine is poly-time\n",
" \n",
" * $\\text{poly} \\cdot \\text{negligible} = \\text{negligible}$\n",
"\n",
" → poly-many calls to subroutine that fails with negligible probability, fails with negligible probability overall"
]
},
{
"cell_type": "markdown",
"id": "2ea54677-4daa-46c4-8368-a3015b787e54",
"metadata": {},
"source": [
"### (Re)definition of an encryption scheme\n",
"\n",
"<div style=\"border:solid 2px #ccc;padding:1rem;\">\n",
" \n",
"A private-key encryption scheme $(\\text{Gen}, \\text{Enc}_k, \\text{Dec}_k)$ is defined by three **PPT algorithms**:\n",
"\n",
"1. **Key generation** takes as input $1^n$; outputs $k$ (assumed $|k| \\geq n$)\n",
"\n",
"2. **Encryption** takes as input the key $k$ and message $m \\in \\{0,1\\}^*$; outputs ciphertext $c$\n",
"\n",
"3. **Decryption** takes $k$ and ciphertext $c$ as input; outputs a message $m$\n"
]
},
{
"cell_type": "markdown",
"id": "d8666f4d-fb14-4c13-b13d-b619e5759af4",
"metadata": {},
"source": [
"# Pseudorandomness\n",
"\n",
"> Randomness as well as pseudorandomness is **not** a property of a **string**, but a property of a **distribution**.\n",
"\n",
"<br>\n",
"\n",
"That means the string `1101010110011111` is uniform and equaly likely as the string `0000000000000000` with a propability of $2^{-16}$.\n",
"\n",
"<br>\n",
"\n",
"A **distribution** of $n$-bit strings is a function \n",
"\n",
"$$\n",
"\\text{D}: \\{0, 1\\}^n \\to [0, 1] \\; s.t. \\quad \\sum_x \\text{D}(x) = 1\n",
"$$\n",
"\n",
"A **uniform distribution** of $n$-bit strings is the distribution $\\text{U}_n$ where\n",
"\n",
"$$\n",
"\\text{U}_n(x) = 2^{-n} \\quad \\forall x \\in \\{0, 1\\}^n\n",
"$$\n",
"\n",
"**Pseudorandom** means, that it can not be distiguished from a uniform distribution."
]
},
{
"cell_type": "markdown",
"id": "89108fdf-c236-45dc-82bb-fd1dbfb75cba",
"metadata": {},
"source": [
"## Cryptographic Definitions of Pseudorandomness\n",
"\n",
"> $\\text{D}$ is pseudorandom if it passes every *efficient* statistical test\n",
"\n",
"<br>\n",
"\n",
"### Concrete Definitions of Randomness\n",
"\n",
"Let $\\text{D}$ be a distribution of $n$-bit strings, then\n",
"\n",
"$\\text{D}$ is $(t, \\epsilon)$-pseudorandom, if for all attacker $A$ running in time $\\leq t$\n",
"\n",
"$$\n",
"| \\, \\text{P}_{x \\, \\gets \\text{D}}[\\, A(x) = 1 \\,] - \\text{P}_{x \\, \\gets \\text{U}_n}[\\, A(x) = 1 \\,] \\, | \\leq \\epsilon\n",
"$$\n",
"\n",
"Here, the notion $x \\, \\gets \\text{D}$ means *$x$ is a sample of the distribution $D$*.\n",
"\n",
"<br>\n",
"\n",
"### Asymptotic Definitions of Randomness\n",
"\n",
"Having a **security parameter** $n$ and a **polynomial** $p$, let $\\text{D}_n$ be a distribution over $p(n)$-bit strings.\n",
"\n",
"Here, pseudorandomness is a property of a **sequence** of distributions $\\{\\text{D}_n\\} = \\{\\text{D}_1, \\text{D}_2, \\ldots\\}$\n",
"\n",
"Then we say, \n",
"\n",
"$\\{\\text{D}_n\\}$, where $\\text{D}_n$ is a distribution over $p(n)$-bit strings, is **pseudorandom** if for all PPT adversaries $A$, there is a **negligible** function $\\epsilon$ such that\n",
"\n",
"$$\n",
"| \\, \\text{P}_{x \\, \\gets \\text{D}_n}[\\, A(x) = 1 \\,] - \\text{P}_{x \\, \\gets \\text{U}_{p(n)}}[\\, A(x) = 1 \\,] \\, | \\leq \\epsilon(n)\n",
"$$\n"
]
},
{
"cell_type": "markdown",
"id": "f46efcf6-a236-4236-b1b5-cee129d7bccd",
"metadata": {},
"source": [
"## Pseudorandom (Number) Generator (PRG)\n",
"\n",
"A pseudorandom generator is an **efficient deterministic algorithm** that expands a **short and uniform seed** or input into a **longer pseudorandom output**."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "49ca4396-34ea-47dd-be9e-8fb377f03923",
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.12.1"
}
},
"nbformat": 4,
"nbformat_minor": 5
}