{
"cells": [
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"deletable": false,
"editable": false,
"tags": []
},
"outputs": [],
"source": [
"# Initialization cell\n",
"try: # for CS1302 JupyterLite pyodide kernel\n",
" import piplite\n",
"\n",
" with open(\"requirements.txt\") as f:\n",
" for package in f:\n",
" package = package.strip()\n",
" print(\"Installing\", package)\n",
" await piplite.install(package)\n",
"except ModuleNotFoundError:\n",
" pass\n",
"\n",
"import jupytext\n",
"import otter\n",
"from ipywidgets import interact\n",
"\n",
"grader = otter.Notebook(\"main.ipynb\")\n",
"%reload_ext divewidgets"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"# Lab 7: Cybersecurity"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "-"
},
"tags": [
"remove-cell"
]
},
"source": [
"**CS1302 Introduction to Computer Programming**\n",
"___"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Python is a popular tool among hackers and engineers. In this lab, you will learn Cryptology in cybersecurity, which covers\n",
"- [Cryptography](https://en.wikipedia.org/wiki/Cryptography): Encryption and decryption using a cipher.\n",
"- [Cryptanalysis](https://en.wikipedia.org/wiki/Cryptanalysis): Devising an attack to break a cipher."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Caesar symmetric key cipher"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"We first implement a simple cipher called the [Caesar cipher](https://en.wikipedia.org/wiki/Caesar_cipher)."
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"ExecuteTime": {
"end_time": "2021-03-20T14:32:51.506515Z",
"start_time": "2021-03-20T14:32:51.496879Z"
},
"slideshow": {
"slide_type": "-"
},
"tags": [
"hide-input"
]
},
"outputs": [
{
"data": {
"text/html": [
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"%%html\n",
""
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
},
"tags": []
},
"source": [
"### Encrypt/decrypt a character"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"**How to encrypt a character?**"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"The following code encrypts a character `char` using a non-negative integer `key`."
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {
"ExecuteTime": {
"end_time": "2021-03-20T14:32:59.746831Z",
"start_time": "2021-03-20T14:32:59.744992Z"
},
"code_folding": [],
"slideshow": {
"slide_type": "-"
}
},
"outputs": [],
"source": [
"cc_n = 1114112\n",
"\n",
"\n",
"def cc_encrypt_character(char, key):\n",
" \"\"\"\n",
" Return the encryption of a character by an integer key using Caesar cipher.\n",
"\n",
" Parameters\n",
" ----------\n",
" char: str\n",
" a unicode (UTF-8) character to be encrypted.\n",
" key int:\n",
" secret key to encrypt char.\n",
" \"\"\"\n",
" char_code = ord(char)\n",
" shifted_char_code = (char_code + key) % cc_n\n",
" encrypted_char = chr(shifted_char_code)\n",
" return encrypted_char"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"For example, to encrypt the letter `'A'` using a secret key `5`:"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {
"ExecuteTime": {
"end_time": "2021-03-20T14:33:00.944145Z",
"start_time": "2021-03-20T14:33:00.940948Z"
},
"slideshow": {
"slide_type": "-"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'F'"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"cc_encrypt_character(\"A\", 5)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"The character `'A'` is encrypted to the character `'F'` as follows:\n",
"\n",
"1. `ord(char)` return the integer `65`, which is the code point (integer representation) of the unicode of `'A'`. \n",
"2. `(char_code + key) % cc_n` cyclic shifts the code by the key `5`.\n",
"3. `chr(shifted_char_code)` converts the shifted code back to a character, which is `'F'`.\n",
"\n",
"| Encryption | | | | | | | | |\n",
"| ------------------------------- | --- | ----- | --- | --- | --- | --- | --- | --- |\n",
"| `char` | ... | **A** | B | C | D | E | F | ... |\n",
"| `ord(char)` | ... | **65**| 66 | 67 | 68 | 69 | 70 | ... |\n",
"| `(ord(char) + key) % cc_n` | ... | **70**| 71 | 72 | 73 | 74 | 75 | ... |\n",
"| `(chr(ord(char) + key) % cc_n)` | ... | **F** | G | H | I | J | K | ... |"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"You may learn more about `ord` and `chr` from their docstrings:"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"ExecuteTime": {
"end_time": "2021-03-02T13:43:05.568346Z",
"start_time": "2021-03-02T13:43:05.564036Z"
},
"slideshow": {
"slide_type": "-"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Help on built-in function ord in module builtins:\n",
"\n",
"ord(c, /)\n",
" Return the Unicode code point for a one-character string.\n",
"\n",
"Help on built-in function chr in module builtins:\n",
"\n",
"chr(i, /)\n",
" Return a Unicode string of one character with ordinal i; 0 <= i <= 0x10ffff.\n",
"\n"
]
}
],
"source": [
"help(ord)\n",
"help(chr)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"**How to decrypt a character?**"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Mathematically, we define the encryption and decryption of a character for Caesar cipher as\n",
"\n",
"$$ \\begin{aligned} E(x,k) &:= x + k \\mod n & \\text{(encryption)} \\\\\n",
"D(x,k) &:= x - k \\mod n & \\text{(decryption),} \\end{aligned}\n",
"$$\n",
"where $x$ is the character code in $\\{0,\\dots,n\\}$ and $k$ is the secret key. `mod` operator above is the modulo operator. In Mathematics, it has a lower precedence than addition and multiplication and is typeset with an extra space accordingly."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"The encryption and decryption satisfy the recoverability condition\n",
"\n",
"$$ D(E(x,k),k) = x $$\n",
"so two people with a common secret key can encrypt and decrypt a character, but others without the key cannot. This defines a [symmetric cipher](https://en.wikipedia.org/wiki/Symmetric-key_algorithm)."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"The following code decrypts a character using a key."
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {
"ExecuteTime": {
"end_time": "2021-03-02T13:43:07.758160Z",
"start_time": "2021-03-02T13:43:07.754256Z"
},
"slideshow": {
"slide_type": "-"
}
},
"outputs": [],
"source": [
"def cc_decrypt_character(char, key):\n",
" \"\"\"\n",
" Return the decryption of a character by the key using Caesar cipher.\n",
"\n",
" Parameters\n",
" ----------\n",
" char: str\n",
" a unicode (UTF-8) character to be decrypted.\n",
" key: int\n",
" secret key to decrypt char.\n",
" \"\"\"\n",
" char_code = ord(char)\n",
" shifted_char_code = (char_code - key) % cc_n\n",
" decrypted_char = chr(shifted_char_code)\n",
" return decrypted_char"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"For instance, to decrypt the letter `'F'` by the secret key `5`:"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {
"ExecuteTime": {
"end_time": "2021-03-02T13:43:08.544725Z",
"start_time": "2021-03-02T13:43:08.538661Z"
},
"slideshow": {
"slide_type": "-"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'A'"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"cc_decrypt_character(\"F\", 5)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"The character `'F'` is decrypted back to `'A'` because\n",
"`(char_code - key) % cc_n` reverse cyclic shifts the code by the key `5`.\n",
"\n",
"| Encryption | | | | | | | | | Decryption |\n",
"| ------------------------------- | --- | ----- | --- | --- | --- | --- | --- | --- | ------------------------------- |\n",
"| `char` | ... | **A** | B | C | D | E | F | ... | `(chr(ord(char) - key) % cc_n)` |\n",
"| `ord(char)` | ... | **65**| 66 | 67 | 68 | 69 | 70 | ... | `(ord(char) - key) % cc_n` |\n",
"| `(ord(char) + key) % cc_n` | ... | **70**| 71 | 72 | 73 | 74 | 75 | ... | `ord(char)` |\n",
"| `(chr(ord(char) + key) % cc_n)` | ... | **F** | G | H | I | J | K | ... | `char` |"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"**Exercise** (modulo-arithmetic)\n",
"\n",
"Why did we set `cc_n = 1114112`? Explain whether the recoverability property may fail if we set `cc_n` to a bigger number or remove `% cc_n` for both `cc_encrypt_character` and `cc_decrypt_character`."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"1114112 is the total number of code points of unicode. If the value of k is being set as a large number like larger than 1114112, an out of index error will occur."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
},
"tags": []
},
"source": [
"### Encrypt a plaintext and decrypt a ciphertext"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Of course, it is more interesting to encrypt a string instead of a character. The following code implements this in one line."
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {
"ExecuteTime": {
"end_time": "2021-03-02T13:43:11.391788Z",
"start_time": "2021-03-02T13:43:11.386464Z"
},
"slideshow": {
"slide_type": "-"
}
},
"outputs": [],
"source": [
"def cc_encrypt(plaintext, key):\n",
" \"\"\"\n",
" Return the ciphertext of a plaintext by the key using the Caesar cipher.\n",
"\n",
" Parameters\n",
" ----------\n",
" plaintext: str\n",
" A unicode (UTF-8) message to be encrypted.\n",
" public_key: int\n",
" Public key to encrypt plaintext.\n",
" \"\"\"\n",
" return \"\".join([chr((ord(char) + key) % cc_n) for char in plaintext])"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"The above function encrypts a message, referred to as the *plaintext*, by replacing each character with its encryption. \n",
"This is referred to as a [*substitution cipher*](https://en.wikipedia.org/wiki/Substitution_cipher)."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"**Exercise** (cc-decrypt)\n",
"\n",
"Define a function `cc_decrypt` that\n",
"- takes a string `ciphertext` and an integer `key`, and\n",
"- returns the plaintext that encrypts to `ciphertext` by the key using Caesar cipher."
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {
"ExecuteTime": {
"end_time": "2021-03-02T13:43:13.920613Z",
"start_time": "2021-03-02T13:43:13.915211Z"
},
"nbgrader": {
"grade": false,
"grade_id": "cc_decrypt",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
},
"slideshow": {
"slide_type": "-"
},
"tags": [
"remove-output"
]
},
"outputs": [],
"source": [
"def cc_decrypt(ciphertext, key):\n",
" \"\"\"\n",
" Return the plaintext that encrypts to ciphertext by the key using Caesar cipher.\n",
"\n",
" Parameters\n",
" ----------\n",
" ciphertext: str\n",
" message to be decrypted.\n",
" key: int\n",
" secret key to decrypt the ciphertext.\n",
" \"\"\"\n",
" return \"\".join([chr((ord(char) - key) % cc_n) for char in ciphertext])"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {
"deletable": false,
"editable": false
},
"outputs": [
{
"data": {
"text/html": [
"
cc-decrypt
passed!
"
],
"text/plain": [
"cc-decrypt results: All test cases passed!"
]
},
"execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"grader.check(\"cc-decrypt\")"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
},
"tags": []
},
"source": [
"## Brute-force attack"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Create an English dictionary"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"You will launch a brute-force attack to guess the key that encrypts an English text. The idea is simple: \n",
"\n",
"- You try decrypting the ciphertext with different keys, and \n",
"- see which of the resulting plaintexts make the most sense (most English-like)."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"To check whether a plaintext is English-like, we need to have a list of English words. One way is to type them out\n",
"but this is tedious. Alternatively, we can obtain the list from the *Natural Language Toolkit (NLTK)*:"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Collecting nltk\n",
" Using cached nltk-3.7-py3-none-any.whl (1.5 MB)\n",
"Requirement already satisfied: tqdm in /opt/conda/lib/python3.10/site-packages (from nltk) (4.64.1)\n",
"Collecting regex>=2021.8.3\n",
" Using cached regex-2022.10.31-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (770 kB)\n",
"Requirement already satisfied: click in /opt/conda/lib/python3.10/site-packages (from nltk) (8.1.3)\n",
"Requirement already satisfied: joblib in /opt/conda/lib/python3.10/site-packages (from nltk) (1.2.0)\n",
"Installing collected packages: regex, nltk\n",
"Successfully installed nltk-3.7 regex-2022.10.31\n"
]
}
],
"source": [
"!pip install nltk"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {
"ExecuteTime": {
"end_time": "2021-03-02T13:43:18.201267Z",
"start_time": "2021-03-02T13:43:17.512943Z"
},
"slideshow": {
"slide_type": "-"
}
},
"outputs": [
{
"name": "stderr",
"output_type": "stream",
"text": [
"[nltk_data] Downloading package words to /home/ylchan356/nltk_data...\n",
"[nltk_data] Package words is already up-to-date!\n"
]
}
],
"source": [
"import nltk\n",
"\n",
"nltk.download(\"words\")\n",
"from nltk.corpus import words"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"`words.words()` returns a list of words. We can check whether a string is in the list using the operator `in`."
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {
"ExecuteTime": {
"end_time": "2021-03-02T13:43:21.788615Z",
"start_time": "2021-03-02T13:43:21.530613Z"
},
"slideshow": {
"slide_type": "-"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"'Ada' in dictionary? True\n",
"'ada' in dictionary? False\n",
"'Hello' in dictionary? False\n",
"'hello' in dictionary? True\n"
]
}
],
"source": [
"for word in \"Ada\", \"ada\", \"Hello\", \"hello\":\n",
" print(\"{!r} in dictionary? {}\".format(word, word in words.words()))"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"However, there are two issues:\n",
"- Checking membership is slow for a long list.\n",
"- Both 'Hello' and 'ada' are English-like but not in the words list."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"**Exercise** (dictionary)\n",
"\n",
"Using the method `lower` of `str` and the constructor `set`, assign `dictionary` to a set of lowercase English words from `words.words()`."
]
},
{
"cell_type": "code",
"execution_count": 37,
"metadata": {
"ExecuteTime": {
"end_time": "2021-03-02T13:43:23.973199Z",
"start_time": "2021-03-02T13:43:23.707381Z"
},
"nbgrader": {
"grade": false,
"grade_id": "nltk",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
},
"scrolled": true,
"slideshow": {
"slide_type": "-"
},
"tags": [
"remove-output"
]
},
"outputs": [],
"source": [
"dictionary=set() \n",
"for word in words.words():\n",
" dictionary.add(word.lower())"
]
},
{
"cell_type": "code",
"execution_count": 38,
"metadata": {
"deletable": false,
"editable": false
},
"outputs": [
{
"data": {
"text/html": [
"
dictionary
passed!
"
],
"text/plain": [
"dictionary results: All test cases passed!"
]
},
"execution_count": 38,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"grader.check(\"dictionary\")"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
},
"tags": []
},
"source": [
"### Identify English-like text"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"To determine how English-like a text is, we calculate the following score:\n",
"\n",
"$$\n",
"\\frac{\\text{number of English words in the text}}{\\text{number of tokens in the text}} \n",
"$$\n",
"where tokens are substrings, not necessarily English words, separated by white space characters in the text."
]
},
{
"cell_type": "code",
"execution_count": 39,
"metadata": {
"ExecuteTime": {
"end_time": "2021-03-02T13:43:28.853823Z",
"start_time": "2021-03-02T13:43:28.845337Z"
},
"slideshow": {
"slide_type": "-"
}
},
"outputs": [
{
"data": {
"text/plain": [
"(1.0, 0.0)"
]
},
"execution_count": 39,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def tokenizer(text):\n",
" \"\"\"Returns the list of tokens of the text.\"\"\"\n",
" return text.split()\n",
"\n",
"\n",
"def get_score(text):\n",
" \"\"\"Returns the fraction of tokens which appear in dictionary.\"\"\"\n",
" tokens = tokenizer(text)\n",
" words = [token for token in tokens if token in dictionary]\n",
" return len(words) / len(tokens)\n",
"\n",
"\n",
"# tests\n",
"get_score(\"hello world\"), get_score(\"Hello, World!\")"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"As shown in the tests above, the code fails to handle text with punctuations and uppercase letters properly. \n",
"In particular, \n",
"- while `get_score` recognizes `hello world` as English-like and returns the maximum score of 1, \n",
"- it fails to recognize `Hello, World!` as English-like and returns the minimum score of 0."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Why? Every word in `dictionary`\n",
"- are in lowercase, and\n",
"- have no leading/trailing punctuations."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"**Exercise** (tokenizer)\n",
"\n",
"Define a function `tokenizer` that \n",
"- takes a string `text` as an argument, and\n",
"- returns a `list` of tokens obtained by\n",
" 1. splitting `text` into a list using `split()`;\n",
" 2. removing leading/trailing punctuations in `string.punctuation` using the `strip` method; and\n",
" 3. converting all items of the list to lowercase using `lower()`."
]
},
{
"cell_type": "code",
"execution_count": 51,
"metadata": {
"ExecuteTime": {
"end_time": "2021-03-02T13:43:31.856236Z",
"start_time": "2021-03-02T13:43:31.851786Z"
},
"nbgrader": {
"grade": false,
"grade_id": "tokenizer",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
},
"slideshow": {
"slide_type": "-"
},
"tags": [
"remove-output"
]
},
"outputs": [],
"source": [
"import string\n",
"\n",
"\n",
"def tokenizer(text):\n",
" \"\"\"Returns the list of tokens of the text such that\n",
" 1) each token has no leading or trailing spaces/punctuations, and\n",
" 2) all letters in each token are in lowercase.\"\"\"\n",
" text=text.split()\n",
" for n in range(len(text)):\n",
" text[n]= text[n].strip(' ,./?:;\"!£$%^&*()')\n",
" text[n]= text[n].lower()\n",
" return text"
]
},
{
"cell_type": "code",
"execution_count": 52,
"metadata": {
"deletable": false,
"editable": false
},
"outputs": [
{
"data": {
"text/html": [
"
tokenizer
passed!
"
],
"text/plain": [
"tokenizer results: All test cases passed!"
]
},
"execution_count": 52,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"grader.check(\"tokenizer\")"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
},
"tags": []
},
"source": [
"### Launch a brute-force attack"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"**Exercise** (cc-attack)\n",
"\n",
"Define the function `cc_attack` that \n",
"- takes as arguments\n",
" - a string `ciphertext`,\n",
" - a floating point number `threshold` in the interval $(0,1)$ with a default value of $0.6$, and\n",
"- returns a generator that \n",
" - generates one-by-one in ascending order guesses of the key that\n",
" - decrypt `ciphertext` to texts with scores at least the `threshold`."
]
},
{
"cell_type": "code",
"execution_count": 63,
"metadata": {
"ExecuteTime": {
"end_time": "2020-11-17T03:09:28.289722Z",
"start_time": "2020-11-17T03:09:28.283197Z"
},
"nbgrader": {
"grade": false,
"grade_id": "cc_attack",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
},
"slideshow": {
"slide_type": "-"
},
"tags": [
"remove-output"
]
},
"outputs": [],
"source": [
"def cc_attack(ciphertext, threshold=0.6):\n",
" \"\"\"Returns a generator that generates the next guess of the key that\n",
" decrypts the ciphertext to a text with get_score(text) at least the threshold.\n",
" \"\"\"\n",
" n=0\n",
" while True:\n",
" n+=1\n",
" if get_score(cc_decrypt(ciphertext, n)) >= threshold:\n",
" yield n"
]
},
{
"cell_type": "code",
"execution_count": 64,
"metadata": {
"deletable": false,
"editable": false
},
"outputs": [
{
"data": {
"text/html": [
"
cc-attack
passed!
"
],
"text/plain": [
"cc-attack results: All test cases passed!"
]
},
"execution_count": 64,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"grader.check(\"cc-attack\")"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Challenge"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Another symmetric key cipher is [columnar transposition cipher](https://en.wikipedia.org/wiki/Transposition_cipher#Columnar_transposition). A transposition cipher encrypts a text by permuting instead of substituting characters."
]
},
{
"cell_type": "markdown",
"metadata": {
"ExecuteTime": {
"end_time": "2020-11-02T16:48:02.519406Z",
"start_time": "2020-11-02T16:48:02.515508Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"**Exercise** (columnar)\n",
"\n",
"Study and implement the irregular case of the [columnar transposition cipher](https://en.wikipedia.org/wiki/Transposition_cipher#Columnar_transposition) as described in the Wikipedia page. Define the functions \n",
"- `ct_encrypt(plaintext, key)` for encryption, and \n",
"- `ct_decrypt(ciphertext, key)` for decryption. \n",
"\n",
"You can assume the plaintext is in uppercase and has no spaces/punctuations."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"```{hint}\n",
"See the test cases for examples of `plaintext`, `key`, and the corresponding `ciphertext`.\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {
"ExecuteTime": {
"end_time": "2020-11-24T04:05:49.137601Z",
"start_time": "2020-11-24T04:05:49.118597Z"
},
"nbgrader": {
"grade": false,
"grade_id": "ct",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
},
"slideshow": {
"slide_type": "-"
},
"tags": [
"remove-output"
]
},
"outputs": [],
"source": [
"import array as arr\n",
"def argsort(seq):\n",
" '''A helper function that returns the tuple of indices that would sort the\n",
" sequence seq.'''\n",
" return tuple(x[0] for x in sorted(enumerate(seq), key=lambda x: x[1]))\n",
"\n",
"\n",
"def ct_idx(length, key):\n",
" '''A helper function that returns the tuple of indices that would permute \n",
" the letters of a message according to the key using the irregular case of \n",
" columnar transposition cipher.'''\n",
" seq = tuple(range(length))\n",
" new=tuple()\n",
" for j in argsort(key):\n",
" for i in range(len(key)-1):\n",
" if j+(i*len(key)) <= length-1:\n",
" new+=tuple([j+(i*len(key))])\n",
" return new\n",
" \n",
"def ct_ddx(length, key):\n",
" '''A helper function that returns the tuple of indices that would permute \n",
" the letters of a message according to the key using the irregular case of \n",
" columnar transposition cipher.'''\n",
" seq = tuple(range(length))\n",
" new=list(range(length))\n",
" cted=ct_idx(length,key)\n",
" for n in range(len(seq)):\n",
" x=cted[n]\n",
" new[x]=n\n",
" return tuple(new)\n",
"\n",
"\n",
"def ct_encrypt(plaintext, key):\n",
" '''\n",
" Return the ciphertext of a plaintext by the key using the irregular case\n",
" of columnar transposition cipher.\n",
"\n",
" Parameters\n",
" ----------\n",
" plaintext: str\n",
" a message in uppercase without punctuations/spaces.\n",
" key: str\n",
" secret key to encrypt plaintext.\n",
" '''\n",
" return ''.join([plaintext[i] for i in ct_idx(len(plaintext), key)])\n",
"\n",
"\n",
"def ct_decrypt(ciphertext, key):\n",
" '''\n",
" Return the plaintext of the ciphertext by the key using the irregular case\n",
" of columnar transposition cipher.\n",
"\n",
" Parameters\n",
" ----------\n",
" ciphertext: str\n",
" a string in uppercase without punctuations/spaces.\n",
" key: str\n",
" secret key to decrypt ciphertext.\n",
" '''\n",
" return ''.join([ciphertext[i] for i in ct_ddx(len(ciphertext), key)])"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {
"deletable": false,
"editable": false
},
"outputs": [
{
"data": {
"text/html": [
"