Skip to content

0x303 Cryptography

1. Classic Cipher

Simon Singh's book is a very good reference for old ciphers.

1.1. Substitution Ciphers

Substitution Ciphers can be easily attacked with frequency analysis (e.g: character e appears about 13% in a standard English text)

  • scytale: a transposition cipher used in ancient Greece
  • Caesar Cipher
  • Vigenere Ciper
  • ROT13: \((a+13)\%26\)

1.2. enigma

encryption three roters one plugboard Alice message -> plugboard -> three roters -> plugboard -> encryption

complexity

  • roter combination: (5x4x3)
  • roter initialization: (26x26x26)
  • plugboard combination: (factorial(26)/(factorial(6)xfactorial(10)xpower(2,10)))

total complexity: 10^21

decryption Bob set up the roter and plugboard with correct combination and feed the encrypted message, and the output will be the original message

how to break (bombe) basiclly, brute force with several tricks to reduce complexity Tricks use 'weather report' as a key word same char would not be mapped to the same char

2. Primitives

Primitives are well-established, low-level cryptographic algorithms that are frequently used to build cryptographic protocols for computer security systems

2.1. Key-Exchange

2.1.1. Diffie-Hellman Key-Exchange

The protocol depends on the difficulty of the discrete logarithm problem

Protocol flow:

  • Alice and Bob publicly agrees to \(g, p\)
  • Alice randomly generate \(a\), compute \(A = g^a (\mod p)\) and sent \(A\) to Bob
  • Bob randomly generate \(b\), comptue \(B=g^b(\mod p)\) and send \(B\) to Alice
  • Alice compute \((g^b)^a = g^{ab}\), this is the private key
  • Bob compute \((g^a)^b = g^{ab}\), this is the private key

2.2. Symmetric-key Cipher

Alice and Bob use the same key: A cipher defined over \((\mathcal{K}, \mathcal{M}, \mathcal{C})\) is a pair of efficient algorithms \((E,D)\) where \(C: \mathcal{K} \times \mathcal{M} \rightarrow \mathcal{C}\) and \(D: \mathcal{K} \times \mathcal{C} \rightarrow \mathcal{M}\)

Definitions

  • Consistency: \(D(k, E(k, m))==m\)
  • Perfect secrecy: A cipher \((E,D)\) over \((\mathcal{K}, \mathcal{M}, \mathcal{C})\) is said to have perfect secrecy if $P(E(k, m_0)==c) == P(E(k, m_1)==c) $ for all \(m_0, m_1 \in \mathcal{M}, c \in \mathcal{C}\) where \(k\) is uniformly random sampled over \(\mathcal{K}\) (Rought idea is cipher text give no info about plain text). Hard to use in practice

2.2.1. One Time Pad

Vernam 1917. One Time Pad is defined by taking XOR between text and key of same length: $\mathcal{M}, \mathcal{E} \in {0, 1}^n, \mathcal{K} \in \in {0, 1}^n $.

2.2.2. Stream Cipher

Idea: Expand a short random seed (seed is key) into a long pseudorandom bit string, and then apply One Time Pad

2.2.3. DES (3DES)

2.2.4. AES

2.3. Asymmetric-key Cipher

Alice and Bob use different keys

2.3.1. RSA

Algorithms (Key Generation)

find two prime numbers \(p,q\), and compute \(n=pq\)

Compute the Euler's totient of \(n\) (a more efficient way is to compute Carmichael's totient), recall my number note that \(\phi(p) = p-1\) for any prime number and Euler's totient is multiplicative

\[\phi(n) = (p-1)(q-1)\]

find an odd relatively prime number \(e\) with respect to \(\phi(n)\) and its multiplicative inverse \(f\).

\[ef \equiv 1 \mod \phi(n)\]

Recall finding \(f\) can be solved efficiently with extended Euclidean algorithm

The public key is \((e, n)\) and the private key is \((f, n)\)

selection of e

\(e\) having a short bit-length and small Hamming weight results in more efficient encryption – the most commonly chosen value for e is \(2^{16} + 1 = 65537\). Look at the OpenSSH format

OpenSSH

The 2048 bit format public-key id_rsa.pub is as follows:

``` ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAABAQCy9f0... The frist part is translated to

(4 bytes) 00 00 00 07 = 7 (7 bytes) 73 73 68 2d 72 73 61 = "ssh-rsa" (US-ASCII) (4 bytes) 00 00 00 03 = 3 (3 bytes for e) (3 bytes) 01 00 01 = 65537 (a common value for the RSA exponent) (4 bytes) 00 00 01 01 = 257 (256 bytes + 1, 00 appended to prevent negative two's complement issue)) (257 bytes) 00 b2 .. ca a6 0d = The key modulus ```

The private key is stored in another format, look at this blog

Algorithm (Encryption) The plain text is \(P\), we obtain the cipher text \(C\) by

\[C \equiv P^e \mod n\]

Algorithm (Decryption)

\[P \equiv C^f \mod n\]

Proof we want to show \(x^{ef} \equiv x \mod n\), notice that \(ef \equiv 1 \mod \phi(n) \implies ef - 1 = \phi(n)d\). Then by the Euler's theorem

\[x^{ef-1} \equiv x^{\phi(n)d} \equiv 1 \mod n\]

2.3.2. ECC (Elliptic Curve Crypto)

Elliptic curve is a set of \((x,y)\) over Galois Field whose points are satisfying \(y^2=x^3+ax+b\) along with inf points

Definition

  • additive identity: inf
  • scalar multiplication: \(Q = dP = P + P ... + P\). this operation will generate cyclic group

ECC Discrete logarithm Given a elliptic curve \(<G>\) where G is the base pointer, and a pointer E, find a which satisfying \(X=aG\)

Properties

  • No efficient solution for discrete logarithm (EC is hard to break)
  • efficient solution for reverse exp operation (EC is hard to encode and decode)

Curve

  • NIST curve: 192, 224, 256, 384, 521 bit (521 is selected for computation efficiency with a Mersenne prime)
  • Brainpool curve: 160, 192, 224, 256, 320, 384, 512 bit (slow than NIST curve)

2.4. Cryptographic Hash

Crypto hash takes any string as input, produces fixed size output, and should be efficiently computable. It should meet the following security properties.

collision-free: Nobody can find a pair \((x, y)\) such that \(x!=y; H(x) == H(y)\) hiding: If \(r\) is chosen from distribution with high min entropy. then given \(H(r|x)\), it is infeasible to find \(x\) puzzle-friendly: For every possible output \(y\) and \(k\) chosen from distribution with high-min entropy, it is infeasible to find \(H(k|x)=y\). avalanche effect: a small change in input space would cause a drastic change in output space

2.4.1. MD5

2.4.2. SHA

Here is a nice visualization of SHA256

2.5. Pseudorandom Number Generator

3. Systems

3.1. Digital Signature

Digital Signature employs asymmetric cryptography. A digital signature scheme typically consists of three algorithms

  • A key generation algorithm that selects a private key uniformly at random from a set of possible private keys. The algorithm outputs the private key and a corresponding public key.
  • A signing algorithm that, given a message and a private key, produces a signature.
  • A signature verifying algorithm that, given the message, public key and signature, either accepts or rejects the message's claim to authenticity.

3.2. RSA

3.3. DSA

3.4. ECDSA

Elliptic Curve Digital Signature Algorithm

3.5. Message Authentication Code

3.6. Secret Sharing

Divide information \(D\) into \(D_1, ..., D_n\) pieces where \(k\) pieces knowledge reveal the entire info \(D\), but less than \(k\) reveal nothing

Model (Shamir's scheme) Based on polynomial interpolation:

  • distribute \(n\) points \((x_i, y_i)\) of a polynomial \(y=q(x)\) with \(k-1\) degree with the secret encoded with the intercept \(q(0)\)
  • Any \(k\) points will decide the polynomial as well as the interpret \(q(0)\)
  • Any points less than \(k-1\) cannot interpolate and reveal nothing

3.7. Block Chain

3.7.1. Data Structures

Hash Pointer: a pair of (pointer to an info, hash of the info). It can verify that the info has not been changed.

Merkle tree: binary tree using hash pointer, it can be used to prove membership in \(log(n)\). Sorted merkle tree can prove non membership

4. Quantum Cipher

5. Reference

  • [1] Handbook of Applied Cryptography.
  • [2] The Code Book