Outline for May 13, 2004
Reading: Chapter 9.3.2, 9.4, 12.1-12.2.2
Microsoft spent February of last year teaching its programmers how to
check their code for security vulnerabilities and how to introduce
common security flaws. Yet many Microsoft programs still have security
vulnerabilities. Wha problems do you think Microsoft encountered, and
will encounter, in trying to find and clean up the vulnerabilities in
Outline for the Day
- Provides both authenticity and confidentiality
- Go through algorithm:
Idea: C = Memod n,
M = Cdmod n,
with ed mod φ(n) = 1.
Proof: Mφ(n) mod n= 1
[by Fermat's theorem as generalized by Euler]; follows immediately from
ed mod φ(n) = 1.
Public key is (e, n);
private key is d.
Choose n = pq;
then φ(n) = (p-1)(q-1).
p = 5, q= 7; n= 35,
φ(n) = (5-1)(7-1) = 24.
Pick d = 11.
Then de mod φ(n) = 1, so choose e = 11.
To encipher 2, C = Memod n
= 211mod 35 = 2048 mod 35 = 18,
and M = Cd mod n = 1811 mod 35 = 2.
p = 53, q= 61, n= 3233,
φ(n) = (53-1)(61-1) = 3120.
Take d = 791; then e = 71.
Encipher M = RENAISSANCE: A = 00, B = 01, ..., Z = 25, blank = 26. Then:
M = RE NA IS SA NC Eblank = 1704 1300 0818 1800 1302 0426
C = (1704)71 mod 3233 = 3106; etc. = 3106 0100 0931 2691 1984 2927
- Cryptographic Checksums
- Function y = h(x): easy to compute y given x;
computationally infeasible to compute x given y
- Variant: given x and y, computationally infeasible to
find a second x' such that y = h(x').
- Keyed vs. keyless
- Basis: what you know/have/are, where you are
Here is a PDF version of this document.