monoalphabetic (simple substitution):
f
(
a
) =
a
+
k
mod
n
example: Caesar with
k
= 3, RENAISSANCE → UHQDLVVDQFH
polyalphabetic: Vigenère,
f_{i}
(
a
) = (
a
+
k_{i}
) mod
n
cryptanalysis: first do index of coincidence to see if it's monoalphabetic or polyalphabetic, then Kasiski method.
problem: eliminate periodicity of key
Long key generation
Running-key cipher: M=THETREASUREISBURIED; K=THESECONDCIPHERISAN; C=MOILVGOFXTMXZFLZAEQ; wedge is that (plaintext,key) letter pairs are not random (T/T, H/H, E/E, T/S, R/E, A/O, S/N, etc.)
Perfect secrecy: when the probability of computing the plaintext message is the same whether or not you have the ciphertext
Only cipher with perfect secrecy: one-time pads; C=AZPR; is that DOIT or DONT?
DES
Public-Key Cryptography
Basic idea: 2 keys, one private, one public
Cryptosystem must satisfy:
given public key, CI to get private key;
cipher withstands chosen plaintext attack;
encryption, decryption computationally feasible [note: commutativity
not
required]
Benefits: can give confidentiality or authentication or both
RSA
Provides both authenticity and confidentiality
Go through algorithm:
Idea:
C
=
M^{
e}
mod
n
,
M
=
C^{
d}
mod
n
, with
ed
mod PHI
(
n
) = 1.
Proof:
M^{
PHI(
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).
Example:
p
= 5,
q
= 7;
n
= 35, PHI
(
n
) = (5-1)(7-1) = 24. Pick
d
= 11. Then
de
mod PHI
(
n
) = 1, so choose
e
= 11. To encipher 2,
C
=
M^{e}
mod
n
= 2^{11}
mod 35 = 2048 mod 35 = 18, and
M
=
C^{d}
mod
n
= 18^{11}
mod 35 = 2.
Example:
p
= 53,
q
= 61,
n
= 3233, PHI
(
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