EECS 475 Final Exam Review

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

    • Advanced Encryption Standard (AES)

      • Rijndael

        • 128-bit blocksize

        • 128/192/256-bi