1 of 33

History of Cryptography

June 30, 2020

​

​

2 of 33

Introductions

Kathleen: TA, Junior, Computer Science and Linguistics, Took CS10 Fall 2017

​

Murtaza: TA, Junior, Applied Math and Computer Science, Took CS10 Fall 2017, avid lover of theoretical nonsense

​

3 of 33

Administrivia

  • Project 1 Part 2 has been released!!
    • More complex than part 1 so take a look at it
  • Form to find partners on piazza if you haven’t yet
  • Aaron added office hours - Thursdays 1-2pm
    • Priority on conceptual questions
    • But other than that any questions :)
  • Meetings this Friday are optional
  • Hard deadline this Sunday 7/5

4 of 33

The Babington Plot (1586)

​

​

5 of 33

Cryptography and Security Basics

6 of 33

Origins of Cryptography

Steganography (hiding the message)

Used for 2000 years

Examples: hard-boiled egg, invisible ink, SHAVED HEAD!

​

Huge security issues – led to the development of cryptography (hiding the meaning)

7 of 33

Cryptography

Cryptography is the science concerned with secret communication.

  • Gives us a way to provide formal guarantees in the presence of a third party, or adversary.

​

Cryptography lets us communicate securely using insecure channels (i.e. the Internet).

8 of 33

Encryption

Encryption is the process of hiding information from everybody except those that have the key.

​

Think: Encryption is simply a component, or direct application, of Cryptography.

​

Questions?

​

9 of 33

Ciphers

Cipher: each letter in a phrase is replaced by another letter, number, or symbol

Plain text: the message

Cipher text: the encrypted message

​

Transposition: each letter retains its identity but changes its position

Substitution: each letter changes its identity but retains its position

​

​

​

10 of 33

An Analogy

Codemakers : codebreakers : : antibiotic: bacteria

11 of 33

Historical Examples

“Practically since humans began writing, they have been writing in code…”

12 of 33

Arab Cryptanalysis: A Golden Age

Arab scholars invented cryptanalysis, the science of unscrambling a message without knowledge of the key

​

Frequency Analysis: based on observation that some letters in a document more common than others

-Described by Abu Yusuf Ya’qub ibn Is-Haq ibn as-Sabbah ibn ‘

Imran ibn Ismail al-Kindi

​

13 of 33

Meanwhile in Europe...

Between 800 and 1200, Europe was stuck in the Dark Ages

​

Only monks really studied secret writing, in order to discover hidden meanings in the Bible

​

​

14 of 33

Some Progress

Monks begin to share their knowledge, and cryptography also began to blossom around the Renaissance

​

A few major shifts: Monoalphabetic -> polyalphabetic -> Homophonic substitution cipher

​

Example: Philibert Babou

15 of 33

Cryptographic Advancements

Cryptography becomes more well-known and industrialized

​

​

​

16 of 33

A New Concept

One-Time Pad

Based on the idea of true randomness—generate a key, use it once, then throw it out

​

If certain conditions are met, this cipher is theoretically unbreakable

​

Questions?

17 of 33

Modern Cryptography

18 of 33

World War II (Code Talkers)

​

​

​

​

​

​

19 of 33

The Enigma (World War II)

​

​

​

​

​

20 of 33

Cracking the Enigma

Alan Turing, Father of Computer Science

​

​

​

Featured in The Imitation Game!

21 of 33

Encryption Methods and Attacks

22 of 33

Symmetric-Key Cryptography

Symmetric-key Cryptography

  • The same secret key is used by both endpoints of communication.
  • ​
  • The same key is used to both encrypt and decrypt.

​

One-time pad is an example!

23 of 33

Symmetric-Key Cryptography

  • In order for symmetric-key cryptography to work, both members communicating must know the secret key!
  • ​
  • Why is this a problem?

​

  • ​

​

​

24 of 33

Public-Key (Asymmetric) Cryptography

Public-key cryptography

  • The sender and receiver use different keys
  • ​
  • Every participant has both a public key and a private key.

​

  • If Bob wants to communicate with Alice, Bob would encrypt the message with Alice’s public key, and Alice would decrypt the message with her private key.

25 of 33

Public-Key (Asymmetric) Cryptography

  • ​

26 of 33

An Example: RSA

RSA Encryption is a public-key cryptographic algorithm.

  • The name derives from its creators, Rivest, Shamir, and Adleman.

​

RSA is based on the fact that finding the factors of an integer is very difficult (a.k.a computationally expensive).

​

​

27 of 33

An Example: RSA

N = p * q

​

Bob’s public key N used to encrypt the message

​

Bob uses private key, based on p and q, used to decrypt the message

​

​

28 of 33

What makes RSA so powerful?

When N is a very large number, it is essentially impossible to factor it and figure out which primes were used to create it

​

In fact, this lies in a class of problems known as NP. Technically it is in the intersection of NP and co-NP.

​

​

​

​

29 of 33

What makes RSA so powerful?

When N is a very large number, it is essentially impossible to factor it and figure out which primes were used to create it

​

In fact, this lies in a class of problems known as NP

​

​

​

​

30 of 33

Quantum Computing

However, there is one real threat to the security of RSA

Current computers must complete tasks sequentially — each bit must be either a 0 or 1.

Quantum bits, or qubits, can exist in a state of superposition

https://www.theverge.com/2019/10/23/20928294/google-quantum-supremacy-sycamore-computer-qubit-milestone

​

31 of 33

What does the Future Hold?

History, as you now see, has been a constant battle between cryptographers (the makers) and cryptanalysts (the breakers).

​

Famous rulers, warriors, and inventors often get the credit for shaping history, but cryptography has played a huge political and social role throughout human existence

32 of 33

What does the Future Hold?

What are the implications of quantum computing?

​

Certainly a win for the codebreakers, but surprisingly, the biggest win will end up being for the codemakers: a perfect encryption

​

​

33 of 33

References

The Code Book by Simon Singh