HTCS6702 - Cryptography

Introduction

These slides are partially based on slides from J. Katz, author of text book: Introduction to Modern Cryptography
Goals
• Understand real-world crypto via a rigorous
approach
• When you encounter crypto in your career:
– Understand the key terms
– Understand the security guarantees provided
– Know how to use crypto
– Understand what goes on “under the hood”
• “Crypto mindset”
Non-goals
• Designing your own crypto schemes
• Implementing your own crypto for
real-world use

• Course goal:
realize when to consult an expert!
Cryptography (historically)
“…the art of writing or solving codes…”

• Historically, cryptography focused exclusively

on ensuring private communication
between two parties sharing secret
information in advance (using “codes” aka
private-key encryption)
Modern cryptography
• Much broader scope!
– Data integrity, authentication, protocols, …
– The public-key setting
– Group communication
– More-complicated trust models
– Foundations (e.g., number theory, quantum-
resistance) to systems (e.g., electronic voting,
cryptocurrencies)
Modern cryptography

Design, analysis, and implementation of mathematical

techniques for securing information, systems, and
distributed computations against adversarial attack
Modern cryptography
• Cryptography is ubiquitous
– Passwords, password hashing
– Secure credit-card transactions over the internet
– Encrypted WiFi
– Disk encryption
– Digitally signed software updates
– Bitcoin
–…
Cryptography (historically)
“…the art of writing or solving codes…”

• Historically, cryptography was an art

– Heuristic, unprincipled design and analysis
– Schemes proposed, broken, repeat…
Modern cryptography
• Cryptography is now much more of a science
– Rigorous analysis, firm foundations, deeper
understanding, rich theory

• The “crypto mindset” has permeated

other areas of computer security
– Threat modeling
– Proofs of security
Rough course outline
Secrecy Integrity
Private-key setting Private-key Message
encryption authentication codes
Public-key setting Public-key Digital signatures
encryption

• Building blocks
– Pseudorandom (number) generators
– Pseudorandom functions/block ciphers
– Hash functions
– Number theory
HTCS6702 - Cryptography

Classical Cryptography
Motivation
• Allows us to “ease into things…,” introduce
notation
• Shows why unprincipled approaches are
dangerous
• Illustrates why things are more difficult than
they may appear
Classical cryptography
• Until the 1970s, exclusively concerned with
ensuring secrecy of communication

• I.e., encryption
Classical cryptography
• Until the 1970s, relied exclusively on secret
information (a key) shared in advance
between the communicating parties

Private-key cryptography
– aka secret-key / shared-key / symmetric-key
cryptography
 Private-key encryption
key key
ciphertext

c
k k

m
c := Enck(m) message/plaintext m := Deck(c)

decryption
encryption
Private-key encryption

k
c
m
c := Enck(m)
c
c
k

m := Deck(c)
Private-key encryption
• A private-key encryption scheme is defined by a
message space M and algorithms (Gen, Enc, Dec):
– Gen (key-generation algorithm): outputs kÎK
– Enc (encryption algorithm): takes key k and message
mÎM as input; outputs ciphertext c
c ¬ Enck(m)
– Dec (decryption algorithm): takes key k and
ciphertext c as input; outputs m or “error”
m := Deck(c)
For all mÎM and k output by Gen,
Deck(Enck(m)) = m
Kerckhoffs’s principle
• The encryption scheme is not secret
– The attacker knows the encryption scheme
– The only secret is the key
– The key must be chosen at random; kept secret

• Some arguments in favor of this principle

– Easier to keep key secret than algorithm
– Easier to change key than to change algorithm
– Standardization
• Ease of deployment
• Public validation
The shift cipher
• Consider encrypting English text
• Associate ‘a’ with 0; ‘b’ with 1; …; ‘z’ with 25
• k Î K = {0, …, 25}
• To encrypt using key k, shift every letter of the
plaintext by k positions (with wraparound)
• Decryption just does the reverse

helloworld
jgnnqyqtnf
Modular arithmetic
• x = y mod N if and only if N divides x-y
• [x mod N] = the remainder when x is divided by N
– I.e., the unique value yÎ{0, …, N-1} such that
x = y mod N

• 25 = 35 mod 10
• 25 ≠ [35 mod 10]
• 5 = [35 mod 10]
The shift cipher, formally
• M = {strings over lowercase English alphabet}
• Gen: choose uniform kÎ{0, …, 25}
• Enck(m1…mt): output c1…ct, where
ci := [mi + k mod 26]
• Deck(c1…ct): output m1…mt, where
mi := [ci - k mod 26]

• Can verify that correctness holds…

Is the shift cipher secure?
• No -- only 26 possible keys!
– Given a ciphertext, try decrypting with every
possible key
– Only one possibility will “make sense”
– (What assumptions are we making here?)

• Example of a “brute-force” or “exhaustive-

search” attack
Example
• Ciphertext uryybjbeyq
• Try every possible key…
– tqxxaiadxp
– spwwzhzcwo
–…
– helloworld