Type Systems and Object
Download
Report
Transcript Type Systems and Object
Short Overview of
Cryptography
(Lecture II)
John C. Mitchell
Stanford University
Some philosophy
(my opinions)
Do something useful with your life
Computers can do many things
Have fun!
Do something that matters
Learn something about the problems you solve
If you are going to do graphics, study visual art
If you work on computational biology, try to learn
a little organic chemistry
If we are going to analyze security protocols, we
should learn a few things about cryptography
Some security objectives
Secrecy
Info not revealed
Authentication
Know identity of
individual or site
Data integrity
Msg not altered
Message
Authentication
Know source of msg
Receipt
Know msg received
Access control
Revocation
Anonymity
Non-repudiation
Some Basic Concepts
Encryption scheme:
encrypt(plaintext,key)
-1
decrypt(ciphertext,key )
Secret vs. public key
-1
-1
Secret key: more efficient; can have key = key
Public key: publishing key does not reveal key
Hash function
map long text to short hash key; ideally, no collision
Signature scheme
public key
-1
and private key provide “authentication”
Cryptosystem
A cryptosystem consists of five parts
A set P of plaintexts
A set C of ciphertexts
A set K of keys
A pair of functions
encrypt: KPC
decrypt: KCP
such that for every key kK and plaintext pP
decrypt(k, encrypt(k, p)) = p
Good def’n for now, but doesn’t include key generation or prob encryption.
Primitive Example: Shift Cipher
Shift letters using mod 26 arithmetic
Set P of plaintexts
{a, b, c, … , x, y, z}
Set C of ciphertexts {a, b, c, … , x, y, z}
Set K of keys
{1, 2, 3, … , 25}
Encryption and decryption functions
encrypt(key, letter) = letter + key (mod 26)
decrypt(key, letter) = letter - key (mod 26)
Example
encrypt(3, marktoberdorf) = pdunwrehugrui
Evaluation of Shift Cipher
Advantages
Easy to encrypt, decrypt
Ciphertext does look garbled
Disadvantages
Not very good for long sequences of English words
Few keys -- only 26 possibilities
Regular pattern
• encrypt(key,e) is same for all occurrences of letter e
• can use letter-frequency tables, etc
Letter frequency in English
Five frequency groups
[Beker and Piper]
E has probability
0.12
TAOINSHR have probability 0.06 - 0.09
DL have probability ~ 0.04
CUMWFGYPB have probability 0.015 - 0.028
VKJXQZ have probability
< 0.01
Possible to break many letter-to-letter substitution ciphers.
One-time Pad
Secret-key encryption scheme (symmetric)
Encrypt plaintext by xor with sequence of bits
Decrypt ciphertext by xor with same bit sequence
Scheme for pad of length n
Set P of plaintexts: all n-bit sequences
Set C of ciphertexts: all n-bit sequences
Set K of keys:
all n-bit sequences
Encryption and decryption functions
encrypt(key, text) = key text
(bit-by-bit)
decrypt(key, text) = key text
(bit-by-bit)
Example one-time pad
Plaintext
Key
0
1
0
1
0
1
0
1
1
0
1
0
0
1
Ciphertext
=
1
0
0
0
0
1
1
Ciphertext
1
0
0
0
0
1
1
Key
Plaintext
1
1
0
1
0
0
1
0
1
0
1
0
1
0
=
Evaluation of one-time pad
Advantages
Easy to compute encrypt, decrypt from key, text
As hard to break as possible
This is an information-theoretically secure cipher
Given ciphertext, all possible plaintexts are equally likely,
assuming that key is chosen randomly
Disadvantage
Key is as long as the plaintext
How does sender get key to receiver securely?
Idea can be combined with pseudo-random generators ...
What is a “secure” cryptosystem?
Idea
If an enemy intercepts your ciphertext, cannot
recover plaintext
Issues in making this precise
What else might your enemy know?
The kind of encryption function you are using
Some plaintext-ciphertext pairs from last year
Some information about how you choose keys
What do we mean by “cannot recover plaintext” ?
Ciphertext contains no information about plaintext
No efficient computation could make a reasonable guess
Information-theoretic Security
Remember conditional probability...
Random variables X, Y, …
Conditional probability P(X=x|Y=y)
Probability that X takes value x, given that Y=y
Apply to plaintext, ciphertext
Cryptosystem is info-theoretically secure if
P(Plaintext=p | Ciphertext=c) = P(Plaintext=p)
Ciphertext gives no advantage in guessing the plaintext.
Data Encryption Standard
Developed at IBM, widely used
Regular structure
Permute input bits
Repeat application of a certain function
Apply inverse permutation to produce output
Appears to work well in practice
Efficient to encrypt, decrypt
Not provably secure
One round of DES
L i-1
R i-1
f
Expand Ri-1 and XOR w/ Ki
Divide into 8 6-bit blocks
Apply “S-box” table-lookup
functions to each block
Permute resulting bits
Ki
Li
Ri
Function f(Ri-1 ,Ki)
Ki is permutation of key K
Invertible if K known
See Biham and Shamir for analysis
Properties of DES
Not a simple mathematical function
Difficult to analyze
All operations are linear except “S-boxes”
Security depends on “magic” S-box functions
These were designed secretly by NSA
• No S-box is a linear function
• Changing one input bit changes two output bits
Efficient to compute
Combination of bit operations and table lookup
Differential cryptanalysis of DES
Can break 8-round DES, but not 16-round DES (yet)
Complexity-based Cryptography
Some computational problems provably hard
Undecidability of halting problem
Presburger arithmetic is non-elementary
Commutative semi-groups require exponential space
Some problems are believed intractable
NP-complete optimization problems
Traveling salesman as hard as any problem in NP
No known polynomial time algorithm, in spite of effort
Factoring is not believed to be poly-time
Not NP-complete, but many years of effort
Still, useful to relate crypto to standard problems
Review: Complexity Classes
hard
PSpace
NP
BPP
P
easy
Answer in polynomial space
may need exhaustive search
If yes, can guess and check in
polynomial time
Answer in polynomial time, with
high probability
Answer in polynomial time
compute answer directly
One-way functions
A function f is one-way if it is
Easy to compute f(x), given x
Hard to compute x, given f(x), for most x
Examples (we believe)
f(x) = divide bits, x = yz, and multiply f(x)=y*z
f(x) = 3x mod p, where p is prime
f(x) = x3 mod pq, where p,q are primes with |p|=|q|
Easy and hard
(more precisely)
For any finite f, can build a table and invert f
Measure “hardness” using classes of functions
Want this to be hard as a function of choice of f
A class {fa :Df Rf | aA} is one-way if
Efficient algorithm for fa (x), given a, x
No efficient alg computes x, given a, fa (x)
where we assume Df , Rf finite and measure running
time as a function of |a|
One-way trapdoor
A function f is one-way trapdoor if
Easy to compute f(x), given x
Hard to compute x, given f(x), for most x
There is extra “trapdoor” information making it
easy to compute x from f(x)
Example (we believe)
f(x) = x3 mod pq, where p,q are primes with |p|=|q|
Compute cube root using (p-1)*(q-1)
Group theory for RSA
Group G = G, , e, ( )-1
Set of elements with
associative “multiplication”
identity e with ex = xe = x
inverse ( )-1 with xx-1 = x-1 x = e
Cyclic group
Group G = G, , e, ( )-1 with
G = { g0, g1 , g2 , ... , gk = g0}
element g is called a generator of G
number of distinct elements if called the order of group
Number theory for RSA
Group Zn* of integers relatively prime to n
multiplication mod n is associative operation
1 is identity
x-1 computed by Euclidean algorithm for gcd
order of group is (n) = | { k<n | gcd(k,n) =1 } |
What if x not relatively prime to n?
Can have zero divisors, no multiplicative inverse
If y divides x and n, then yi=x, yj=n and
therefore xj = yij 0 mod n
Only numbers relatively prime to n form group
RSA Encryption
Let p, q be two distinct primes and let n=p*q
Encryption, decryption based on group Zn *
For n=p*q product of primes, (n) = (p-1)*(q-1)
Proof: (p-1)*(q-1) = p*q - p - q + 1
Key pair: a, b with ab 1 mod (n)
Encrypt(x) = xa mod n
Decrypt(y) = yb mod n
Since ab 1 mod (n), have xab x mod n
Proof: if gcd(x,n) = 1, then by general group theory,
otherwise use “Chinese remainder theorem”.
How well does this work?
Can generate modulus, keys fairly efficiently
Efficient rand algorithms for generating primes p,q
May fail, but with low probability
Given primes p,q easy to compute n=p*q and (n)
Choose a randomly with gcd(a, (n))=1
Compute b = a-1 mod (n) by Euclidean algorithm
Public key n, a does not reveal b
This is not proven, but believed
But if n can be factored, all is lost ...
Message integrity
Theoretically, a weak point
encrypt(k*m) = (k*m)e = ke * me
= encrypt(k)*encrypt(m)
This leads to “chosen ciphertext” form of attack
If someone will decrypt new messages, then can trick
them into decrypting m by asking for decrypt(ke *m)
Implementations reflect this problem
“The PKCS#1 … RSA encryption is intended
primarily to provide confidentiality. … It is not
intended to provide integrity.”
RSA Lab. Bulletin
Recall security objectives
Secrecy
Info not revealed
Authentication
Know identity of
individual or site
Data integrity
Msg not altered
Message
Authentication
Know source of msg
Receipt
Know msg received
Access control
Revocation
Anonymity
Non-repudiation
Digital Signatures
Public-key encryption
Alice publishes encryption key
Anyone can send encrypted message
Only Alice can decrypt messages with this key
Digital signature scheme
Alice publishes key for verifying signatures
Anyone can check a message signed by Alice
Only Alice can send signed messages
RSA Signature Scheme
Publish decryption instead of encryption key
Alice publishes decryption key
Anyone can decrypt a message encrypted by Alice
Only Alice can send encrypt messages
In more detail,
Alice generates primes p, q and key pair a, b
Sign(x) = xa mod n
Verify(y) = yb mod n
Since ab 1 mod (n), have xab x mod n
Cryptographic hash functions
Function h with two main properties
Map arbitrary strings to strings of fixed length
Given h(x), impractical to find y with h(y)=h(x)
Variety of uses
More efficient digital signatures
Sign hash of message instead of entire message
Data integrity
Compute and store hash of some data
Check later by recomputing hash and comparing
Keyed hash fctns provide message authentication
???
Iterated hash functions
Repeat use of block cipher (like DES, …)
Pad input to some multiple of block length
Iterate a length-reducing function f
f : 22k -> 2k reduces bits by 2
Repeat h0= some seed
hi+1 = f(hi, xi)
Some final function g
completes calculation
x
Pad to x=x1x2 …xk
xi
f(xi-1)
f
g
General Basis for Cryptography
Cyclic group with one-way properties
multiplication, inverse easy to compute
discrete log a, an n not in O(log2 |G|)
Note: randomized algorithm in O(sqrt |G|)
Examples
Integers modulo prime p
Elliptic curve groups
Important: complexity depends on group presentation
Public-Key Cryptography
[ElGamal]
Public encryption key: g, ga
Private decryption key: a
Encryption function
Choose random b [2, |G|-1]
Send encrypt(msg) = gb , gab msg
Decryption
Compute g-ab = ((gb)a) -1
Decrypt g-ab gab msg
This is classical algorithm; better security with hash(gab) msg