# Topics Covered

• Montgomery Multiplication

• Block Ciphers

• Hash Functions

• Elliptic Curve Cryptography

• Secret Sharing

• Broadcast/Multicast Encryption: Naor Pinkas, Logical Key Hierarchy

• Side Channels and Fault Injection

• Digital Signatures and Message Authentication Codes

• Bounds Checking and Buffer Overflows

• Definitions of Security

# Montgomery Multiplication

• Goal: Reduce time cost for large Modular operations

• Speed relies on caching, large number of montgomery operations, and taking modulus with powers of two.

• M-Residue

• Let $$M$$ be a prime n-bit integer $$2^{N-1} < M < 2^N$$

• Let $$R = 2^N$$

• $$\bar{a} = a*R$$ mod $$M$$

• Logical Values

• $$\bar{z} = \bar{x} + \bar{y}$$ mod $$M$$
$$\bar{z} = (x+y)*R$$ mod $$M$$

• $$\bar{z} = \bar{x}*\bar{y}*R^{-1}$$ mod $$M$$

• Montgomery Reduction: RED($$T$$)

• Define RED($$T$$) $$= TR^{-1}$$ mod $$M$$

• Let $$M' = -M^{-1}$$ mod $$R$$

• (i.e $$RR^{-1} - M'M = 1$$)

• $$m = T*M' mod R$$

• $$t = \frac{T+mM}{R}$$

• NOTE: this is integer division

• $$t \ge M$$ return $$t-M$$, else return $$t$$.

# Block Ciphers

• Kirchoff’s Law

• Security of algorithm is based on the secret key rather than the algorithm.

• Assume nothing about the secrecy of the algorithm

• Block Cipher Basics

• Block cipher: Plaintext $$\rightarrow$$ Ciphertext on a fixed N-bit size.

• Symmetric Key cryptography; treat algorithm as a block box

• k-bit key, n-bit message, c-bit ciphertext

• Brute force key: $$O(2^k)$$

• Building a table

• $$\sum^k x \sum^n \rightarrow \sum^n$$

• Permutations from $$\sum^n \rightarrow \sum^n$$?

• $$2^n!$$

• Sterling’s Approximation: $$x! = \sqrt{2\pi x}\,(\frac{x}{e})^x$$

• How big does a table need to be to map $$\sum^n \rightarrow \sum^n$$? $$log_2(x!)$$ where $$x = 2^n$$.

• If n = 128 bits; $$k = log_2(2^{128}!) = 2^{134} bits.$$

• Real-World Block Ciphers

• Data Encryption Standard (DES)

• NIST Standard

• 56-bit keys (due to 8th bit of every byte being a parity bit)

• 64-bit block size

• Invented by IBM

• Attack: Linear Cryptanalysis - Relationships between plaintext & ciphertext (supposedly NSA improved DES to be resistent to this attack)

• Replaced by AES

• Rijndael

• 128-bit blocksize

• 128/192/256-bit keysizes

• Fast + low gate count

• RC5: Ron’s Code 5

• Simple, fast

• 32/64/128-bit block size

• 0-2040-bit key size

• Strength of a block Cipher

• Data Complexity: Known-plaintext; how many known-plaintexts does the adversary need to get?

• Storage Complexity: How much hard drive space does the adversay need?

• Computational Complexity: How much time does it take the adversary to process the key?

• Breaking Block Ciphers

• Brute Force Guess

• What if k is small?

• $$O(2^k)$$ where k is the bits of the key

• Known-plaintext attack: Get plaintext/CT pair

• Small block size attack

• What if n is small?

• Known PT attack: Create a table of PT $$\rightarrow$$ CT w/o key

• Birthday Paradox: Proportional to the square root of the size of the search space

• $$\sqrt(2^n) = 2^{n/2}$$ known plaintexts/ciphertext pairs

• Put these plaintext/ciphertext pairs in a table

• Then you listen to another $$2^{n/2}$$ ciphertexts.

• High probability that one of the rows will hit (Key-equivalent translation).

• Double Encryption: $$E_{k2}(E_{k1}(m))) = c$$

• This is not $$O(2^{2k})$$ complexity.

• Meet in the Middle Attack: $$O(2^k)$$ space $$\rightarrow O(2^k)$$ time.

• Method

• Encrypt plaintext with each possible $$k_1$$ ($$2^k$$ keys).

• Decrypt c under all possible $$k_2$$

• If we find $$c'$$ from decryption, we have found $$k_1$$ form the table.

• Use Birthday Paradox: Only need $$O(2^{k/2})$$ rows.

• Block Cipher Modes

• Types

• Electronic Code Book (ECB)

• Cipher Block Chaining (CBC)

• Output Feedback (OFB)

• Counter Mode (CTR)

• Electronic Code Book (ECB)

• Use the same key to encode every block of the message

• C