Cipher

Quarto Markdown Demo

  • I have a tendency to write things inside of bulleted lists.
  • I have tendency to write code blocks interspersed with bulleted lists.
print("hello world")
hello world
  • We can try a Linux command via a linemagic.
    • Linemagic are prefaced with a single %
%ls
cipher.html  cipher.qmd  cipher.quarto_ipynb  cipher_files/
  • We can do terminal commands in .qmd…
  • But it isn’t always the easiest way to do them.

Ciphers

  • Material adapted from Cryptobook
  • The first of the chapters in this book is “Chapter 2”
    • We make fun of languages for being zero or one indexed.
    • Python is 0-indexed
    • R is 1-indexed
    • Heaps when embedded in arrays are often 1-indexed
    • Cryptobook is 2-indexed

Shannon ciphers and perfect security

  • Introduce a Shannon cipher with a mathematical definition.
  • “A Shannon cipher is a pair of functions.”
cipher = lambda e, d: (e,d)
  • The first function, denoted e is the encryption function.
    • It accepts two inputs:
      • The first is some key k
      • The second is some message m
        • I often denote the message as msg
    • It produces as output:
      • A ciphertext c
e = lambda k, m: ""

k = 'key'
m = 'msg'

c = e(k,m)
  • The second function, denoted d is the decryption function.
    • It accepts two inputs:
      • The first is some key k
      • The second is some ciphertext c
    • It produces as output:
      • A message m, that is equal to original message.
d = lambda k, c: ""

# c is previously defined

m_out = d(k,c)
  • We want to be able to encrypt and decrypt messages such that:
m = ""
assert(d(k,e(k,m)) == m)

Alternate, functional implementation

  • We need not view (en/de)cryption as a function over two inputs.
  • Equivalently, we can argue that”
    • A key is a function, or…
    • The encryption function is the output of a function:
      • Accepts as input a msg/ciphertext
      • Produces as output a ciphertext/msg
make_f = lambda k: lambda m: ""

k = 'key'
m = 'msg'

e = make_f(k)

c = e(m)
  • Do the same with decrypt
d = make_f(k)

m_out = d(c)
  • We can reformulate the assert statement as well…
m, e, d = "", make_f(k), make_f(k)

assert(d(e(m)) == m)
  • We can also write it out fully…
m = ""
assert((make_f(k))((make_f(k))(m)) == m)

Motivating Example: Enigma

  • The Enigma machine was type-writer-like, except that
    • Pressed keys did not correspond to printing the pressed letter, rather
    • They corresponded to some encrpyed letter.
  • We begin with a minimal example.
rs = [                            # rotors
    "BDFHJLCPRTXVZNYEIWGAKMUSQO", # fast
    "AJDKSIRUXBLHWTMCQGZNPYFVOE", # medium
    "EKMFLGDQVZNTOWYHXUSPAIBRCJ", # slow
    "IXUHFEZDAOMTKQJWNSRLCYPBVG"  # reflect
]
  • To start off, we arbitrarily select one such “rotor” for use a “key” to a cipher.
r = rs[0]
  • In Enigma, it is initially most helpful to think of messages as a single letter…
    • We need a function, that creates a function
      • The created function accepts on letter
      • And produces one letter
make_f = lambda k : lambda a : ""
  • What do we write inside?
    • Reference the visual…
  • We are likely to use the alphabet in our expression.
abcs = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
  • We can use the alphabet and built-in Python functions/methods to convert a letter into an index.
abcs.index("E")
4
  • Given an index, we can find the letter at the index within the “rotor” which is a key…
r[4]
'J'
  • With this insight, we can finally implement make_f
make_e = lambda k : lambda a : k[abcs.index(a)]
  • Let’s test it.
    • First, let’s make our encryption function
e = make_e(r)
  • Wait, what find of thing is e?
print("e ->", e, "\ntype(e) -> ", type(e))
e -> <function <lambda>.<locals>.<lambda> at 0x7ff95025f130> 
type(e) ->  <class 'function'>
  • What happens when we apply e to some letter, such as “E”
e("E")
'J'
  • How do we make d?
  • We simply reverse the process…
make_d = lambda k : lambda a : abcs[k.index(a)]
  • We make the decrpytion function
d = make_d(r)
  • We also test d
print("d ->", d, "\ntype(d) -> ", type(d))
d -> <function <lambda>.<locals>.<lambda> at 0x7ff95025f760> 
type(d) ->  <class 'function'>
  • What happens when we apply d to some letter, such as “J”
d("J")
'E'
  • We can check our previous assert statement…
m = 'E'
assert(d(e(m)) == m)
  • We can test more concretely by looking at the entire alphabet…
assert(all([d(e(m)) == m for m in abcs]))
  • We can test more complete by looking at all rotors.
assert(all([all([make_d(r)(make_e(r)(m)) == m for m in abcs]) for r in rs]))