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 | Encryption |
---|---|
ASCII | RSA |
Morse code | Ceaser cipher |
mode change | secrecy |
Here is how ASCII encoding works.
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
[77, 111, 118, 101, 32, 116, 104, 105, 114, 100, 32, 98, 97, 116, 116, 97, 108, 105, 111, 110]
It is rumored that the emperor Ceasar used the alphabetical ordering to encrypt messages.
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")
'zxylaphone'
AlphabetEncode("whatsthebuzz")
[22, 7, 0, 19, 18, 19, 7, 4, 1, 20, 25, 25]
AlphabetDecode(AlphabetEncode("oiulkkj"))
'oiulkkj'
c = CeaserCipherEncrypt("Move The Third Battalion")
ciphertext = AlphabetDecode(c)
ciphertext
'rtajymjymnwigfyyfqnts'
m = CeaserCipherDecrypt(ciphertext)
plaintext = AlphabetDecode(m)
plaintext
'movethethirdbattalion'
If a series of 1's and 0's are agreed upon. That can be used to create a one-time pad.
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
def onetimepaddecrypt(c, mask):
return c^mask
onetimepaddecrypt(c,mask)
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
from math import log as log
SecondsSinceBigBang = 13.8*10**9*365*24*60*60
int(SecondsSinceBigBang)
435196800000000000
log(log(SecondsSinceBigBang,10),10)
1.2464662215329492
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
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)
def add(a,b):
return a + b
add(234848729384572943857293487529348752943857293485729348529348754844443948572323485798745000002934857239487583338484858484,82734618273461827341283746912837461923847683274623876)
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.
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
a = 5434122349
slowfactorize(a)
is prime
b= 140134439
slowfactorize(b)
is prime
print(a*b)
slowfactorize(a*b)
761507686834477211
(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.
The security of a cryptosystem should depend only on the secrecy of the key, and not on the secrecy of the encryption algorithm itself.
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$.
Given two integers $n$ and $m$ with $m \neq 0$. It is possible to find two integers $q$ and $r$ such that
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.
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}.$$
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
gcd(132,-176)
44
gcd(91843857293487529875234923746182377658765876576576576576576576576576461982987698768975751938401298429385723234,185720394875262348798788881923874523333970898768768768768767098760986796576363636365)
1
gcd(0,12387)
12387
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.
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)
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$.
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)
896181570509244152383451378
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!
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
fastexp(A,b,p)
98492732104743106
fastexp(B,a,p)
98492732104743106