{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Lecture 1: Basics of Cryptography\n",
"\n",
"or how to keep a secret, when everybody can hear what you say\n",
"\n",
"Book: Hoffstein, Silverman, Pipher. An Introduction to Mathematical Cryptography \n",
"\n",
"ISBN: 978-0-387-77993-5 \n",
"e-ISBN: 978-0-387-77994-2\n",
"DOI: 10.1007/978-0-387-77994-2"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Encoding vs Encrypting\n",
"\n",
"| Encoding | Encryption |\n",
"|----------|-------------|\n",
"| ASCII | RSA |\n",
"|Morse code|Ceaser cipher|\n",
"|mode change | secrecy|\n",
"\n",
"Here is how ASCII encoding works."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[77,\n",
" 111,\n",
" 118,\n",
" 101,\n",
" 32,\n",
" 116,\n",
" 104,\n",
" 105,\n",
" 114,\n",
" 100,\n",
" 32,\n",
" 98,\n",
" 97,\n",
" 116,\n",
" 116,\n",
" 97,\n",
" 108,\n",
" 105,\n",
" 111,\n",
" 110]"
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"plaintext = \"Move third battalion\"\n",
"m = [ord(letter) for letter in plaintext]\n",
"m\n",
"#This is encoding the plaintext in ascii code, letter --> number less than 256"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## The Ceasar Cipher\n",
"\n",
"It is rumored that the emperor Ceasar used the alphabetical ordering to encrypt messages."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'zxylaphone'"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def CeaserCipherEncrypt(plaintext):\n",
" m = AlphabetEncode(PreProcess(plaintext))\n",
" c = [(x + 5)%26 for x in m]\n",
" return c\n",
"\n",
"def CeaserCipherDecrypt(ciphertext):\n",
" c = AlphabetEncode(PreProcess(ciphertext))\n",
" m = [(x - 5)%26 for x in c]\n",
" return m\n",
" \n",
"def PreProcess(plaintext):\n",
" return plaintext.lower().replace(\" \", \"\")\n",
"\n",
"def AlphabetEncode(lowercaseplaintext):\n",
" #We convert text that is in lowercase and without spaces into a list of ordinal numbers < 26.\n",
" m = [ord(letter)- ord('a') for letter in lowercaseplaintext]\n",
" return m\n",
"\n",
"def AlphabetDecode(m):\n",
" p = \"\".join([chr(x+ ord('a')) for x in m])\n",
" return p\n",
"\n",
"PreProcess(\"ZxylaPH one\")"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[22, 7, 0, 19, 18, 19, 7, 4, 1, 20, 25, 25]"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"AlphabetEncode(\"whatsthebuzz\")"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'oiulkkj'"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"AlphabetDecode(AlphabetEncode(\"oiulkkj\"))"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'rtajymjymnwigfyyfqnts'"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"c = CeaserCipherEncrypt(\"Move The Third Battalion\")\n",
"ciphertext = AlphabetDecode(c)\n",
"ciphertext"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'movethethirdbattalion'"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"m = CeaserCipherDecrypt(ciphertext)\n",
"plaintext = AlphabetDecode(m)\n",
"plaintext"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Binary Masking\n",
"\n",
"If a series of 1's and 0's are agreed upon. That can be used to create a one-time pad."
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"1834256848197781910117\n",
"134523459385740348764763124533331\n"
]
}
],
"source": [
"\n",
"m = \"come here\"\n",
"m = m.encode()\n",
"\n",
"mask = 134523459387491283741923847928374\n",
"\n",
"intm = int.from_bytes(m,'big')\n",
"print(intm)\n",
"\n",
"\n",
"def onetimepadencrypt(intm, mask):\n",
" return intm^mask\n",
"\n",
"c = onetimepadencrypt(intm,mask)\n",
"print(c)"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"1834256848197781910117"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def onetimepaddecrypt(c, mask):\n",
" return c^mask\n",
"\n",
"onetimepaddecrypt(c,mask)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The reason this method is called a one-time-pad is that if you do not throw away the mask after one use then an adversary receiving the encrypted messages $m_1 \\otimes k$, $m_2\\otimes k$ can simply apply bitwise addition to both terms and get $m_1 \\otimes m_2$. It is not obvious how one can obtain back the messages at this point, but it should be worrying that we could completely get rid of the encryption key. \n",
"\n",
"\n",
"Given that a pad is chosen at random and is used only once, this method has perfect secrecy"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# What is a big number"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"435196800000000000"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"from math import log as log\n",
"SecondsSinceBigBang = 13.8*10**9*365*24*60*60\n",
"int(SecondsSinceBigBang)"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"1.2464662215329492"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"log(log(SecondsSinceBigBang,10),10)"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"1.3324143530129378\n",
"1.6766826982452132\n",
"1.9978178718298372\n"
]
}
],
"source": [
"SecondsInAYear = 365*24*60*60\n",
"SecondsUntilLastStarDies = 10**14*SecondsInAYear\n",
"SecondsUntilWhiteDwarvesDie = 10**40*SecondsInAYear\n",
"SecondsUntilLastBlackHoleEvaporates=10**92*SecondsInAYear\n",
"\n",
"print(log(log(SecondsUntilLastStarDies,10),10))\n",
"print(log(log(SecondsUntilWhiteDwarvesDie,10),10))\n",
"print(log(log(SecondsUntilLastBlackHoleEvaporates,10),10))"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"done\n",
"done\n",
"done\n",
"done\n",
"done\n",
"done\n",
"done\n",
"done\n",
"2.08 s ± 74.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
]
}
],
"source": [
"def doNothing(N):\n",
" X = range(N)\n",
" for n in X:\n",
" #do nothing\n",
" ;\n",
" print(\"done\")\n",
" \n",
"%timeit doNothing(100000000)"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"234848729384572943857293487529348752943857293485729348529348754844526683190596947626086283749847694701411431021759482360"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def add(a,b):\n",
" return a + b\n",
"\n",
"add(234848729384572943857293487529348752943857293485729348529348754844443948572323485798745000002934857239487583338484858484,82734618273461827341283746912837461923847683274623876)\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"A one way function is a function which is easy to do, but hard to undo. Multiplication is such an example. Factorization is hard. "
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [],
"source": [
"from math import sqrt as sqrt\n",
"def slowfactorize(n):\n",
" for i in range(2,int(sqrt(n))):\n",
" if n%i==0:\n",
" return (i, int(n/i))\n",
" print(\"is prime\")\n",
" return None"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"is prime\n"
]
}
],
"source": [
"a = 5434122349\n",
"slowfactorize(a)"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"is prime\n"
]
}
],
"source": [
"b= 140134439\n",
"slowfactorize(b)"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"761507686834477211\n"
]
},
{
"data": {
"text/plain": [
"(140134439, 5434122349)"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"print(a*b)\n",
"slowfactorize(a*b)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Your opponent always uses her best strategy to defeat you, not the strategy that you want her to use. Thus the security\n",
"of an encryption system depends on the best known method to break it. As new and improved methods are developed, the level of security can only get worse, never better."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Kerckhoff’s principle\n",
" The security of a cryptosystem should depend only on the secrecy of the key, and not on the secrecy of the encryption algorithm itself."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Some Mathematical Principles\n",
"\n",
"## Divisibility\n",
"\n",
"An integer $e$ is said to divide another integer $n$, and this is denoted by $e | n$, if there is another integer $f$ such that $n = ef$. \n",
"\n",
"Let $n$ and $m$ be two integers, an integer $e$ is a common divisor of $n$ and $m$ if $e|n$ and $e|m$. For example $1$ is a common divisor of all integers.\n",
"\n",
"The integer $e$ is said to be the greatest common divisor of $n$ and $m$ if $e = \\max\\{d: d | n, d|m\\}$.\n",
"\n",
"If $e$ divides both $n$ and $m$ then it also divides the linear combination $an + bm$ for any two integers $a, b$. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Division with Remainder\n",
"\n",
"Given two integers $n$ and $m$ with $m \\neq 0$. It is possible to find two integers $q$ and $r$ such that\n",
"- $n = mq + r$ \n",
"- $0\\leq r < |m|$\n",
"\n",
" Proof: Among all integers of the form $R = \\{n - m t \\in \\mathbb{N}: t \\in \\mathbb{Z}\\}$ choose the smallest element (well ordering principle: every nonempty set of natural numbers has a least integer), call it $r$. By definition $0 \\leq r$, and if it were the case that $r \\geq |m|$ one could see that we would also have $r - |m| \\geq 0$ and hence in $R$. This would contradict the fact that $r$ was the least element. The first equality is also satisfied by definition."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Greatest Common Divisors and Euclid's Algorithm\n",
"\n",
"Let $n$ and $m$ be two integers and apply division with remainder, i.e. $n = mq + r$. If $e$ is a common divisor of $n$ and $m$ it is also a divisor of $n - mq$, i.e. $r$. Conversely if $e$ is a common divisor of $m$ and $r$ it also divides $n = m + qr$. Since the set of common divisors is the same, we have that $$\\operatorname{gcd}(n,m) = \\operatorname{gcd}(m,r)$$. \n",
"\n",
"We can turn this into an agorithm, noting that $r$ is smaller than $m$, hence reducing the problem. i.e. apply division with remainder to $m$ and $r = r_1$ in the next step, with remainder $r_2$, and then we are left with finding the $\\operatorname{gcd}$ of $r_1$ and $r_2$. If at one step $r_k = 0$, we can stop, because then we know $$ \\operatorname{gcd}(n,m) = \\operatorname{gcd}(m,r_1) = \\cdots = \\operatorname{gcd}(r_{k-1},r_k) = \\operatorname{gcd}(r_{k-1}, 0) = r_{k-1}.$$"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [],
"source": [
"def gcd(n,m):\n",
" if m ==0:\n",
" return n\n",
" (n,m) = (abs(n),abs(m))\n",
" r = n%m\n",
" while r != 0:\n",
" (n, m, r) = (m,r,m%r)\n",
" return m"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"44"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"gcd(132,-176)"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"1"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"gcd(91843857293487529875234923746182377658765876576576576576576576576576461982987698768975751938401298429385723234,185720394875262348798788881923874523333970898768768768768767098760986796576363636365)"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"12387"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"gcd(0,12387)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Fast Modular Exponentiation\n",
"\n",
"On the face of it, in order to calculate $x^n$ one needs to apply $n$ many multiplications, and for $n$ large, that may be too many."
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"450382164816"
]
},
"execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def slowexp(x,n,m):\n",
" #Calculates x^n modulo m using multiplication\n",
" result = 1\n",
" for i in range(n):\n",
" result = (x*result)%m\n",
" return result\n",
"\n",
"slowexp(2,10000000,1238479234465)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Of course there is nothing special about reducing modulo $m$ at each step, it is only that the numbers quickly become too large to store if that sort of reduction is not done. Hence straight-up $x^n$ is rarely used in cyrptography.\n",
"\n",
"Another method is to use fast exponentiation, which relies on the binary expansion of the exponent $n$."
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"896181570509244152383451378"
]
},
"execution_count": 23,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def fastexp(x,n,m):\n",
" z = 1\n",
" while n!=0:\n",
" if n%2==1:\n",
" z = (z*x)%m\n",
" x = (x*x)%m\n",
" n = n//2\n",
" return z\n",
"\n",
"fastexp(2,10000000006587657657657657657657657650000,1928734619827346283746823746)\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Diffie Helman Key Exchange\n",
"\n",
"Alice and Bob agree on a large modulus $p$, and a base $g$ such that $\\operatorname{gcd}(g,p)=1$. They can share this information online, and it is okay that an eavesdropper, say Eve, knows about $p$ and $g$.\n",
"\n",
"Alice chooses a secret exponent $a$, and Bob chooses a secret exponent $b$. Alice publishes\n",
"$$A \\equiv g^a \\pmod{p} \\qquad B \\equiv g^b \\pmod p$$.\n",
"\n",
"Then Alice computes \n",
"$B^a \\equiv g^{ab} \\pmod p$ and Bob computes $A^b \\equiv g^{ab} \\pmod {p}$. Now they share a number without anyone out there knowing about it!"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"A = 11868774906762477 B = 180441110697334971\n"
]
}
],
"source": [
"p = 182374612834691863\n",
"g = 2\n",
"\n",
"a = 19283472987 #this is actually only stored in Alice's computer.\n",
"b = 92837918702 #this is actually only stored in Bob's computer.\n",
"\n",
"A = fastexp(g, a, p)\n",
"B = fastexp(g, b, p)\n",
"\n",
"print(\"A = \",A,\"B = \",B)"
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"98492732104743106"
]
},
"execution_count": 25,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"fastexp(A,b,p)"
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"98492732104743106"
]
},
"execution_count": 26,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"fastexp(B,a,p)"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"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.6.4"
}
},
"nbformat": 4,
"nbformat_minor": 2
}