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

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\).

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

Advanced Encryption Standard (AES)

Rijndael

128-bit blocksize

128/192/256-bi

## Share on Social Media