A primer on encryption and hashing

​

​

Sep 2023

Vivek Pandey

Outline

• A gradation of ideas
• A primer on encryption
• Symmetric key cryptography
• Public key cryptography
• A primer on hashing
• Concepts
• Various uses of hashing
• Some hashing algos

A gradation of ideas

most profound

least profound

I can never think of such an idea

- Theory of evolution

- Theory of relativity

I can probably not think of such an idea

- public key cryptography

- neural networks

I could have thought of it

- public key cryptography

- many maths olympiad problems

I often think of such ideas

- your yet another leetcode problem

A primer on encryption

• You have a message m to send
• The channel by which you send it can be eavesdropped
• In physical world, messenger can be caught
• In digital world, http packets can be read
• You want to "encrypt" the message so that only recipient can read the message

A primer on encryption

m

f(m)

f

What is a very important property of f?

sender

receiver

A primer on encryption

m

f(m)

f

What is a very important property of f?

​

f needs to be invertible!

​

f(x) = x + 3 is invertible: g(x) = x - 3 is its inverse

f(x) = 1 if x is odd, 0 if 1 x is even is not invertible

sender

receiver

Two major types of cryptography

• Symmetric key cryptography
• Sender and receiver share a secret
• Public key cryptography
• Sender and receiver don't share a secret

Symmetric key cryptography

• Caesar cipher

Symmetric key cryptography

• Grand daddies of symmetric cryptography
• Data Encryption Standard (DES)
• Advanced Encryption Standard (AES)

1975

​

DES is developed

​

Some people argue DES can be broken

​

1977

​

DES is convincingly broken

​

1997-99

​

2001

​

AES is announced

​

AES is in use till today

​

2023

​

Essential idea of DES/AES

• Generate a random 128 bit key
• E.g. K = 0110101010111110011110100001....000101
• Break the input message M in 128 bit chunks
• E(M) = M xor K
• D(M) = M xor K
• D(E(M)) = M xor K xor K = M xor 0 = M
• This basic algo would be breakable by frequency analysis
• So, lot of other operations are done
• E.g. have an invertible map m that maps bytes to bytes, them map each byte b to m(b)
• Permute the bytes
• Repeat above operations ~10 times

Uses of AES

• It is fast
• Processor has instructions for AES operations

​

​

​

​

​

• Used extensively
• E.g. to encrypt data on disk

Problem with symmetric key cryptography

• If two parties want to talk over the internet, how do they share the key?
• That needs to happen over some other channel
• paper, phone, CD
• But in internet, there is only channel: the network
• Sharing key is impossible

Public key cryptography

• You generate an encryption key e, and a decryption key d
• You keep d with yourself and publish e
• d(e(m)) = m for all m
• Loosely using e, d as functions rather than key above
• Using e, d cannot be derived
• So if someone wants to send you a message m, they encryption it using e and get e(m)
• e(m) is garbage to anyone
• Only you have d to compute d(e(m))
• This is magic! No secret need to be exchanged beforehand between the parties!

​

RSA basic

• Take two large prime numbers p & q
• Let n = p * q
• If you only know n then no fast algo for finding p & q is known
• There is something called "Totient function" λ
• Compute λ(n). Keep it secret.
• For n = p*q, λ(n) = lcm(p - 1, q - 1)
• Choose a small e such that e and λ(n) are coprime
• E.g. e = 2^16 + 1
• Knowing λ(n) you can find d such that de = 1 (mod λ(n))

p

q

λ(n)

e

d

n

• Once you have e, n & d, throw away p, q, λ(n)
• Encryption of M is M^e (mod n)
• And then decryption of (M^e (mod n))^d (mod n) = M^ed (mod n) = M

​

• Everybody knows e & n. No one knows d. Without p & q, d cannot be got.

You need p & q to find λ(n), knowing n won't suffice

Aside: Digital signatures - 1

• Story so far
• I have my public key (e, n) published
• If you want to send me message M, send me E = M^e(mod n)
• I will do E^d (mod n) and it will equal to M
• We can also use this technique for "digital signatures"
• If a message has come to me saying that the message is from person P, how do I know it is really from P? Or someone else on internet set the message.

Aside: Digital signatures - 2

• P will have public key e_p and decryption key d_p
• Let's say my keys are e and d.
• P should send me e(d_p(M)) and I will then first find d(e(d_p(M)) = d_p(M) and then e_p(d_p(M)) = M
• If someone else sends on behalf of M, their messages will decrypt to garbage

Outline

• A gradation of ideas
• A primer on encryption
• Symmetric key cryptography
• Public key cryptography
• A primer on hashing
• Concepts
• Some uses of hashing
• Some hashing algos

Hash function, mathematically

• Hash function takes an arbitrary length input and outputs a fixed length output

m

f(m)

f

Can f be invertible?

Hash function, mathematically

• Hash function takes an arbitrary length input and outputs a fixed length output

m

f(m)

f

Can f be invertible?

​

No: because give some specifically hash value, many inputs can map to that value.

Some desirable properties of hash functions

• Let's say output of hash is 128 bit number.
• So, there are 2¹²⁸ possibilities
• Given an input, all these possibilities should be equally likely as output
• Even if inputs exhibit some pattern
• h(x) = 0 all the time is not a good hash function
• For cryptographic use cases, given an output, it should be hard to find an input with that output
• Brute force check is only way

Where do we use hash functions - 1

• Hash tables
• O(1) insertion, O(1) search
• Let's say you want to store some integers
• Maintain an array A of some fixed size, say 10000
• If you want insert an integer, say 73, you find h(73) = 834 (say) and do A[834] = 73

Where do we use hash functions - 2

• As checksum
• Suppose you are storing a data D on disk
• Disk error can flip a bit / few bits, so D may get changed to D'
• How can you detect D has got tampred
• Store <D, H(D)>. ie store D followed by H(D).
• When you read D' and H' back from the disk, check that H' = H(D')
• If not some error has happed

Where do we use hash functions - 3

• Checking for equality without storing actual value
• When we create login/password on some website, website should not store password in plaintext
• They should store hash of password
• When user enters as password to login, you take its hash and compare against stored value
• If database is compromised, passwords are not compromised

Where do we use hash functions - 4

• Which redis node to store the data in
• You have a redis cluster with 10 nodes
• Given a <k, v> to insert in the cluster, which node to go to?
• You store it in node numbered h(k) mod 10

Some bad hash functions

• Assume that input is an arbitrary sequence of 0s and 1s
• h(x) = x mod (2¹²⁸)
• Given an output, many inputs can be found which map to that
• If inputs happen to be 2¹²⁸ apart, outputs will all be the same
• Break input into 128 bit chunks, and then xor all those chunks

Some good hash functions

• md5
• Designed by Rivest of RSA fame
• 128 bit output
• md6
• 256 bit output
• sha1
• 160 bit output
• sha2
• 224-512 bit outputs depending on variation

Collision probability

• Let's say you use 256 bit hash
• For a given input there are 2^256 hashes possible, all equally likely
• 2^256 <> 10^77
• Even if you hash 10^10 objects, probability of a collision is << 10^-30
• Smaller than probability of nuclear holocaust etc