Cryptography

Posted on April 6, 2015.

Notes from Cryptography, a MOOC on Coursera.

Week 4: Message Integrity

Week 5: Number Theory

Algorithmic Number Theory

Exponentiation

Modular Exponentiation Take 1:

exp(a,b,N) {
  // assume b > 0
  ans = 1;
  for (i=1, i ≤ b; i++)
    ans = [ans * a mod N]
  return ans;
}

Running time: O(b) (So polynomial time in the magnitude of b, not the length of b.

Modular Exponentiation Take 2:

exp(a, b, N) {
  // assume b ≥ 0
  x=a, t=1;
  while (b>0) {
    if (b odd)
      t = [t * x mod N], b = b -1;
    x = [x^2 mod N], b = b/2; }
  return t; }
}

Overall running time is polynomial in length of \(\|a\|\),\(\|b\|\),\(\|N\|\)

Groups

Example:

Modular Inverses

Example:

Fermat’s little theorem

Factoring

RSA Problem

Cyclic Groups

Week 6: Public Key Cryptography

Week 7: Digital Signatures and PKI

Digital Signatures

Public Key Infrastructure

SSL/TLS (Putting it all together)