# Lecture 1: Basics of Cryptography¶

or how to keep a secret, when everybody can hear what you say

Book: Hoffstein, Silverman, Pipher. An Introduction to Mathematical Cryptography

ISBN: 978-0-387-77993-5 e-ISBN: 978-0-387-77994-2 DOI: 10.1007/978-0-387-77994-2

## Encoding vs Encrypting¶

Encoding Encryption
ASCII RSA
Morse code Ceaser cipher
mode change secrecy

Here is how ASCII encoding works.

In [1]:
plaintext = "Move third battalion"
m = [ord(letter) for letter in plaintext]
m
#This is encoding the plaintext in ascii code, letter --> number less than 256

Out[1]:
[77,
111,
118,
101,
32,
116,
104,
105,
114,
100,
32,
98,
97,
116,
116,
97,
108,
105,
111,
110]

## The Ceasar Cipher¶

It is rumored that the emperor Ceasar used the alphabetical ordering to encrypt messages.

In [2]:
def CeaserCipherEncrypt(plaintext):
m = AlphabetEncode(PreProcess(plaintext))
c = [(x + 5)%26 for x in m]
return c

def CeaserCipherDecrypt(ciphertext):
c = AlphabetEncode(PreProcess(ciphertext))
m = [(x - 5)%26 for x in c]
return m

def PreProcess(plaintext):
return plaintext.lower().replace(" ", "")

def AlphabetEncode(lowercaseplaintext):
#We convert text that is in lowercase and without spaces into a list of ordinal numbers < 26.
m = [ord(letter)- ord('a') for letter in lowercaseplaintext]
return m

def AlphabetDecode(m):
p = "".join([chr(x+ ord('a')) for x in m])
return p

PreProcess("ZxylaPH one")

Out[2]:
'zxylaphone'
In [3]:
AlphabetEncode("whatsthebuzz")

Out[3]:
[22, 7, 0, 19, 18, 19, 7, 4, 1, 20, 25, 25]
In [4]:
AlphabetDecode(AlphabetEncode("oiulkkj"))

Out[4]:
'oiulkkj'
In [5]:
c = CeaserCipherEncrypt("Move The Third Battalion")
ciphertext = AlphabetDecode(c)
ciphertext

Out[5]:
'rtajymjymnwigfyyfqnts'
In [6]:
m = CeaserCipherDecrypt(ciphertext)
plaintext = AlphabetDecode(m)
plaintext

Out[6]:
'movethethirdbattalion'

If a series of 1's and 0's are agreed upon. That can be used to create a one-time pad.

In [7]:
m = "come here"
m = m.encode()

intm = int.from_bytes(m,'big')
print(intm)

print(c)

1834256848197781910117
134523459385740348764763124533331

In [8]:
def onetimepaddecrypt(c, mask):


Out[8]:
1834256848197781910117

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.

Given that a pad is chosen at random and is used only once, this method has perfect secrecy

# What is a big number¶

In [9]:
from math import log as log
SecondsSinceBigBang = 13.8*10**9*365*24*60*60
int(SecondsSinceBigBang)

Out[9]:
435196800000000000
In [10]:
log(log(SecondsSinceBigBang,10),10)

Out[10]:
1.2464662215329492
In [11]:
SecondsInAYear = 365*24*60*60
SecondsUntilLastStarDies = 10**14*SecondsInAYear
SecondsUntilWhiteDwarvesDie = 10**40*SecondsInAYear
SecondsUntilLastBlackHoleEvaporates=10**92*SecondsInAYear

print(log(log(SecondsUntilLastStarDies,10),10))
print(log(log(SecondsUntilWhiteDwarvesDie,10),10))
print(log(log(SecondsUntilLastBlackHoleEvaporates,10),10))

1.3324143530129378
1.6766826982452132
1.9978178718298372

In [12]:
def doNothing(N):
X = range(N)
for n in X:
#do nothing
;
print("done")

%timeit doNothing(100000000)

done
done
done
done
done
done
done
done
2.08 s ± 74.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [13]:
def add(a,b):
return a + b


Out[13]:
234848729384572943857293487529348752943857293485729348529348754844526683190596947626086283749847694701411431021759482360

A one way function is a function which is easy to do, but hard to undo. Multiplication is such an example. Factorization is hard.

In [14]:
from math import sqrt as sqrt
def slowfactorize(n):
for i in range(2,int(sqrt(n))):
if n%i==0:
return (i, int(n/i))
print("is prime")
return None

In [15]:
a = 5434122349
slowfactorize(a)

is prime

In [16]:
b= 140134439
slowfactorize(b)

is prime

In [17]:
print(a*b)
slowfactorize(a*b)

761507686834477211

Out[17]:
(140134439, 5434122349)

Your opponent always uses her best strategy to defeat you, not the strategy that you want her to use. Thus the security 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.

## Kerckhoff’s principle¶

The security of a cryptosystem should depend only on the secrecy of the key, and not on the secrecy of the encryption algorithm itself.

# Some Mathematical Principles¶

## Divisibility¶

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$.

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.

The integer $e$ is said to be the greatest common divisor of $n$ and $m$ if $e = \max\{d: d | n, d|m\}$.

If $e$ divides both $n$ and $m$ then it also divides the linear combination $an + bm$ for any two integers $a, b$.

## Division with Remainder¶

Given two integers $n$ and $m$ with $m \neq 0$. It is possible to find two integers $q$ and $r$ such that

• $n = mq + r$
• $0\leq r < |m|$

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.

## Greatest Common Divisors and Euclid's Algorithm¶

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)$$.

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}.$$

In [18]:
def gcd(n,m):
if m ==0:
return n
(n,m) = (abs(n),abs(m))
r = n%m
while r != 0:
(n, m, r) = (m,r,m%r)
return m

In [19]:
gcd(132,-176)

Out[19]:
44
In [20]:
gcd(91843857293487529875234923746182377658765876576576576576576576576576461982987698768975751938401298429385723234,185720394875262348798788881923874523333970898768768768768767098760986796576363636365)

Out[20]:
1
In [21]:
gcd(0,12387)

Out[21]:
12387

## Fast Modular Exponentiation¶

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.

In [22]:
def slowexp(x,n,m):
#Calculates x^n modulo m using multiplication
result = 1
for i in range(n):
result = (x*result)%m
return result

slowexp(2,10000000,1238479234465)

Out[22]:
450382164816

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.

Another method is to use fast exponentiation, which relies on the binary expansion of the exponent $n$.

In [23]:
def fastexp(x,n,m):
z = 1
while n!=0:
if n%2==1:
z = (z*x)%m
x = (x*x)%m
n = n//2
return z

fastexp(2,10000000006587657657657657657657657650000,1928734619827346283746823746)

Out[23]:
896181570509244152383451378

# Diffie Helman Key Exchange¶

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$.

Alice chooses a secret exponent $a$, and Bob chooses a secret exponent $b$. Alice publishes $$A \equiv g^a \pmod{p} \qquad B \equiv g^b \pmod p$$.

Then Alice computes $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!

In [24]:
p = 182374612834691863
g = 2

a = 19283472987 #this is actually only stored in Alice's computer.
b = 92837918702 #this is actually only stored in Bob's computer.

A = fastexp(g, a, p)
B = fastexp(g, b, p)

print("A = ",A,"B = ",B)

A =  11868774906762477 B =  180441110697334971

In [25]:
fastexp(A,b,p)

Out[25]:
98492732104743106
In [26]:
fastexp(B,a,p)

Out[26]:
98492732104743106