Skip to content

Introduction

Cryptography is an important part of modern communications. It is important in preventing attacks to critical infrastructure, keeping communications secure, and more recently things such as IoT.

Privacy achieved through cryptography is an ongoing debate, and as recently as 2015, the UK Government wanted to ban specific encryption schemes from being used.

Cryptography is defined as the science of secret writing with the goal of hiding the meaning of the message. It provides the basic building blocks to construct secure systems. It is not a catch-all and is only reliable if implemented properly.

Cryptanalysis on the other hand is what the attacker does, and deciphering or decryption is what the legitimate receiver does.

Caesar Cipher

Take the simple Caesar Cipher encoded message, for example:

ooit gepq erh gevvc sr

This likely includes the word the, which we can try and substitute in for the erh. Doing this, we can form the following substitution list:

ABCDEFGHIJKLMNOPQRSTUVWXYZ
PQRSTUVWXYZABCDEFGHIJKLMNO

Using this substitution, we get

dxxi vtef tgw vtkkr hg
which, to anyone with working eyes, is complete and utter nonsense. Another common English word we can try is and, creating the following substitution:
ABCDEFGHIJKLMNOPQRSTUVWXYZ
WXYZABCDEFGHIJKLMNOPQRSTUV

Application of this to the message gives us the following:

keep calm and carry on

The Caesar Cipher is one of the most popular monoalphabetic substitution ciphers, and is probably the first type of cipher that everyone is taught.

It is known as monoalphabetic, as we use the same substitution throughout the text. For example, d is always replaced with z. It is called a substitution cipher as each letter is substituted for another one, and this may be done with a simple mapping, or something more complicated. Transposition is the other main type of cipher, where the same letters are kept, but moved around.

History

Cryptography is a well established science, dating back to 3000 BC. Cryptographers establish new schemes of encryption, and eventually cryptanalysts break these schemes.

  • ~3000 BC: Monoalphabetics
  • 900 AD: al-Kindi shows frequency analysis
  • 1460: Leon Alberti has first polyalphabetic cipher
  • Shortly after Vignere Cipher made
  • 1863: Kasiski publishes an attack on the Vignere cipher
  • 1918: Mauborgne invents one time pad
  • 1939: Enigma created
  • Shortly after Rejewski shows repeated message-key attack
  • Shortly after Enigma adds rotors to stop repeated key
  • 1945: Turing shows loop attacks, Colossus
  • 1973: Feistel Block Cipher, DES
  • 1978: Public Key
  • Future: Quantum

Modern History

In 2015, Toshiba and BT show that they have an unhackable network with their use of new quantum cryptography. In 2016, we establish that this might not be as secure as we initially thought. The US Government gets onboard with NIST and trying to standardise a new set of quantum-safe algorithms. In 2019, Google argued that they had achieved quantum supremacy. In 2020, NIST finally selects algorithms for post-quantum crypto. In 2021, Qrate set new world record for quantum cryptography efficiency.

July 2022 saw the first four NIST-approved quantum algorithms, however this was not the be-all and end-all of quantum solutions. In August, one of the algorithms was cracked using a classical PC, showing the weakness of relying solely on quantum algorithms as forms of encryption.

Administrivia

The module covers classical ciphers; newer symmetric key cryptosystems, such as AES, used in most modern symmetric encryption, and DES, which is the older encryption standards; public key cryptosystems, such as ED25519 and RSA; message authentication codes; modular arithmetic and group theory; quantum cryptography; and post quantum-computing cryptosystems.

The module is assessed through a 20% coursework, and an exam which seems to historically be closed-book written.

Coursework

This is an individual assignment, which is unique to each student. The assignment includes a number of challenges, which may include cryptanalysis, or construction of an example encryption system.

Prerequisite Knowledge

The course relies heavily on:

The probability theory seems to have largely been covered by previous modules, most notably COMP2208 Intelligent Systems. This can probably be recapped in an evening. The second book linked is arguably less accessible, and immediately dives into proofs and theorems after restating a lot of the simple notation that would have been covered in COMP1215 Foundations of Computer Science, and COMP2210 Theory of Computing.

The second one seems to be the one to consult if the slides are confusing.

Key Terminology

Term Description
Plaintext Message in the clear form
Steganography Conceals the existence of the message. The message itself may or may not be encoded.
Cryptography Message in plain view, but meaning is concealed
Cipher Ciphertext is \(f(plaintext, key)\), operating on groups of characters.
Crib Known sequence of letters or words, e.g., u usually follows q.