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'

Binary Masking

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()

mask  = 134523459387491283741923847928374

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


def onetimepadencrypt(intm, mask):
    return intm^mask

c = onetimepadencrypt(intm,mask)
print(c)
1834256848197781910117
134523459385740348764763124533331
In [8]:
def onetimepaddecrypt(c, mask):
    return c^mask

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

add(234848729384572943857293487529348752943857293485729348529348754844443948572323485798745000002934857239487583338484858484,82734618273461827341283746912837461923847683274623876)
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