Transcript A tutorial on cryptography.

A Cryptography Tutorial
• Jim Xu
• College of Computing
• Georgia Tech
• http://www.cc.gatech.edu/~jx
Why Cryptography?
• Network information needs to be
communicated through insecure channel.
• Stored information may be accessed without
proper authorization.
• Cryptography is a systematic way to make
that harder.
Common Security Requirements
•
•
•
•
Secrecy(encryption)
Authenticity(signature/encryption)
Integrity (signature/encryption)
Non-repudiation (signature)
What Cryptography can do?
• Encryption: only the authorized party can
understand the encrypted message.
• Signature: allow people to verify the
authenticity of the message.
Classical Cryptography
•
•
•
•
•
•
Shift Cipher (a special case used by Caesar)
Substitution Cipher
Affine Cipher
Vigenere Cipher
Hill Cipher
Permutation Cipher
Cryptoanalysis
•
•
•
•
Ciphertext-only attack
Known plaintext attack
Chosen plaintext attack
Adaptive Chosen plaintext attack
Cryptoanalysis
•
•
•
•
•
•
Shift Cipher: English histogram
Substitution Cipher: histogram again
Affine Cipher: histogram
Vigenere Cipher: more complicated stat
Hill Cipher: Known plaintext attack
Permutation Cipher: histogram + semantics
Frequency of Letter Occurance
How to achieve perfect secrecy?
• One-pad: have a key as long as the plaintext
• For example, shift cipher is perfectly secure
if the key is random and it is only used to
encrypt one character!
• Spurious keys: S(n) >= |K|/(|P|^(n*R))-1
• Unicity distance: that n to make S(n) zero
Modern Cryptography
• Two broad classes
– 1. Shared-key cryptography
– 2. Public-key cryptography
Shared-key cryptography
•
•
•
•
•
Rooted in computational complexity
Sender has M
Sender sends (M XOR f(x, k), x)
f is a random function
Algorithms:
– DES, Various fishes, Lucifer, Fiestel, AES
standards (Rijendel), ...
DES
• A round can be described as:
– Li = Ri-1
R  L  P(S ( E ( R )  K ))
• The key generation is performed
i
i 1
i 1
i
– An initial permutation PC1 which selects 56 bits and
divide them in two halves
– In each round
• Select 24 bits from each half using a permutation function PC2
• Rotate left each half by one or two position
Rich theory on
pseudorandomness
• Pseudorandom number/bit generator
• Pseudorandom functions (ideal
cryptographic hash functions)
• Stretch a small completely random string
into a longer but less random string
• Though less random, indistinguishable to
“naked eyes”
Public Key Cryptography
• Public/private key pair
• Only the owner knows the private key, but
everyone knows the public key
• If the message is encrypted with the private
key, then everyone with the public key can
recover the message, but only the owner can
generate the encrypted message
Continued
• If the message is encrypted with the public
key, only the owner can decrypted it using
its private key
• The first property can be used for signature
and the second property can be used for
encryption.
Digital signature
• Sender sends M, T=E(hash(M), private)
• The receiver compares E(T, public) and
compares it with hash(M)
• M is considered genuine if they match
RSA
• Find two big prime numbers p and q
• Let B = p*q
• Choose private key C to be a number that is
coprime with (p-1)*(q-1)
• Choose public key D such that C*D=1 mod
(p-1)*(q-1)
Continued
•
•
•
•
Encrypt M: T=M^C (or M^D)
Decrypt M: M = T^D (or T^C)
Theorem: (M^C)^D = M mod B
Why: all the numbers that is coprime with B
form a group, and the size of that group is
(p-1)(q-1)
Security of RSA
• Hinge upon how hard the factorization is
• If one can break down B into p and q
• then finding C: C*D = 1 mod (p-1)(q-1) is
easy
• Factorization is found to be quite hard, at
least for now.
Cryptographic Protocols
• System needs are more complicated than
what the primitives can provide
• Improperly designed, be broken even if
none of the underlying primitives are
broken
• Hard to check whether it is properly
designed (proof logic/model
checking/theorem proving methods are
involved)
Key exchange
• Diff-Hellman
• Based on the assumption that knowing
prime p and p^n, finding n will be hard
• Allow two party to share a key
• A senders B p^a and remembers a
• B senders A p^b and remembers b
• Both sides can generate p^(ab)
• Third party can not do that!
Man in the middle
• C can establish a key with both A and B, by
posing as B and A respectively
• Solution: introduce public key or using
return address as authentication method
Public Key Infrastructure
• Need this infrastructure to prevent A from
claiming that B uses the public key that A
generates
• Both hierachical and flat infrastructure are
proposed
• Revocation list a major headache
Advanced Issues
• Group encryption/signature
• Forward security
• Everlasting security