5-ExclusiveOR.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5.1 Description\n",
    "\n",
    "Another way to think of XOR is as something called a “**programmable inverter**”: one input bit decides whether to invert the other input bit, or to just pass it through unchanged. “Inverting” bits is colloquially called “flipping” bits, a term we'll use often throughout the book. \n",
    "\n",
    "In mathematics and cryptography papers, exclusive or is\n",
    "generally represented by a cross in a circle: $\\oplus$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5.2 properties of XOR\n",
    "\n",
    "1. **Commutative**: $A \\oplus B = B \\oplus A$\n",
    "2. **Associative** for any order: $(A \\oplus B) \\oplus C = A \\oplus (B \\oplus C)$\n",
    "3. **Identity element**: $A \\oplus 0 = A$\n",
    "4. **Self-Inverse**: $A \\oplus A = 0$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5.3 Bitwise XOR\n",
    "\n",
    "$$\\begin{split}\n",
    "73 \\oplus 87 &=0b1001001 \\oplus 0b1010111\\\\\n",
    "      &=\\begin{matrix} \n",
    "      1 & 0 & 0 & 1&0&0&1 \\\\\n",
    "      \\oplus & \\oplus & \\oplus & \\oplus&\\oplus&\\oplus&\\oplus \\\\\n",
    "      1 & 0 & 1 & 0&1&1&1\n",
    "   \\end{matrix} \\\\\n",
    "      &=0b0011110\\\\\n",
    "      &=30\n",
    "\\end{split}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5.4 One-time pads\n",
    "\n",
    "It's called a one-time pad because it involves a sequence (the “pad”) of random bits, and the security of the scheme depends on only using that **pad once**.\n",
    "\n",
    "If an attacker sees the ciphertext, we can prove that\n",
    "they will learn zero information about the plaintext without the key. This property is called *perfect security*."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5.5 Attacks on “one-time pads”\n",
    "\n",
    "The one-time pad security guarantee only holds if it is used correctly. First of all, the one-time pad has to consist of truly random data. Secondly, the one-time pad can only be used once (hence the name). Unfortunately, most commercial products that claim to be “one-time pads” are snake oil, and don't satisfy at least one of those two properties.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Crib-dragging\n",
    "\n",
    "A classical approach to breaking multi-time pad systems involves “crib-dragging”, a process that uses small sequences that are expected to occur with high probability. Those sequences are called “cribs”.\n",
    "\n",
    "The idea is fairly simple. Suppose we have several encrypted messages $C_i$ encrypted with the same “one-time”\n",
    "pad $K$. If we could correctly guess the plaintext for one of the messages, let's say $C_j$ , we'd know $K$:\n",
    "\n",
    "$$\\begin{split}\n",
    "C_j \\oplus P_j &= (P_j\\oplus K) \\oplus P_j\\\\\n",
    "&= K \\oplus P_j \\oplus P_j\\\\\n",
    "&= K \\oplus 0\\\\\n",
    "&= K\n",
    "\\end{split}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since $K$ is the shared secret, we can now use it to decrypt all of the other messages, just as if we were the recipient:\n",
    "$$(\\forall i \\in E)\\quad P_i = C_i \\oplus K $$ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we guess a few plaintext bits $p_i$ correctly for any of the messages, that would reveal the key bits at that position for all of the messages, since $k = c_i \\oplus p_i$. Hence, all of the plaintext bits at that position are revealed: using that value for $k$, we can compute the plaintext bits $p_i = c_i\\oplus k$  for all the other messages.\n",
    "\n",
    "This becomes even more effective for some plaintexts\n",
    "that we know more about. If some HTTP data has the\n",
    "plaintext **ent-Len** in it, then we can expand that to\n",
    "**Content-Length**:, revealing many more bytes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "While this technique works as soon as two messages are\n",
    "encrypted with the same key, itʼs clear that this becomes\n",
    "even easier with more ciphertexts using the same key, since\n",
    "all of the steps become more effective:\n",
    "\n",
    "- We get **more** cribbing **positions**.\n",
    "- More plaintext bytes are **revealed** with each successful crib and guess, leading to more guessing options elsewhere.\n",
    "- More ciphertexts are available for any given position,making guess **validation** easier and sometimes more accurate."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5.6 Remaining problems\n",
    "\n",
    "Real one-time pads, implemented properly, have an extremely\n",
    "strong security guarantee. It would appear, then,\n",
    "that cryptography is over: encryption is a solved problem,\n",
    "and we can all **go home**. Obviously, that's not the case.\n",
    "\n",
    "However, as we'll see throughout this book, **secure** symmetric encryption algorithms **aren't** the **pain point** of modern cryptosystems. Cryptographers have designed plenty of those, while practical key management remains one of the toughest challenges facing modern cryptography.\n",
    "\n",
    "We need something with manageable key sizes while maintaining secrecy. We need ways to negotiate keys over the Internet with people we've never met before."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "misc",
   "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.11.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}