# 0x042 Cryptography

This page will cover classic cryptography, quantum cryptography and block chains. Main reference for classic cyptography will be Handbook of Applied Cryptography.

Contents Index

## Classic Cipher

Personally I think the code book by Simon Singh is a very good reference for old ciphers.

### 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$

### 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

## 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

### 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$.

### Stream Cipher

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

## Asymmetric-key Cipher

Alice and Bob use different keys

### 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)

## 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

## Block Chain

### 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