Transcript Public key cryptography

Lecture 6: Public Key
Cryptography
RSA
Diffie-Hellman
Zero-Knowledge Proof Schemes
1
Public Key Algorithms Features
• two different numbers: e and d
• e and d are inverses; using one reverses the effect
of the other
• you shouldn’t be able to compute d from e
• if must be efficient to find a matching pair of keys
• it must be efficient to encrypt and decrypt
2
Example: Simple Algorithm
• multiplication modulo p (where p is a prime, why prime? easy to
compute e and d, more later)
– let p=127
– Choose e and d so that e*d=1 mod 127
• e.g. e=53 and d=12
– To encrypt a number, multiply by 53 mod 127
– To decrypt a number, multiply by 12 mod 127
– Decryption must restore the initial value!
• 12 is an inverse of 53 in multiplication modulo 127
(multiplicative inverse) what’s an inverse in (regular)
multiplication? Addition?
• problem: not secure
– the number 127 is too small. You could compute d from e by
trying all possible values
– modular division is possible - the inverse can be computed
quickly even when p is large (Euclid’s algorithm…patent long
expired)
3
Modulo Exponentiation
•
•
•
•
•
•
an integer x is relatively prime to n if the only common factor is 1
totient function F(n) is # of integers < n and relatively prime to n
If n is a prime, F(n) = n-1
Euler proved: xF(n) mod n = 1
So xkF(n) mod n = 1 and xkF(n)+1 mod n = x (if x<n)
If we can find d*e = 1 mod F(n), they’d be exponentiative inverses to n
– that is: xde mod n = x
• observe that given two primes p and q
F(p*q)=(p-1)(q-1) – remove multiples of p and multiples of q
4
RSA
• Named after its inventors: Rivest, Shamir, and Adelman
• pick two large primes p and q, let n be p*q
• pick e such that it is relatively prime to F(n)
that is e=1 mod F(n)
– since p and q are known F(n) is easy to compute (how?)
• find a number d such that it is a multiplicative inverse of e mod F(n)
– that is d*e=1 mod F(n)
• in this case: xed mod n = x
• encryption is: ciphertext = plaintext e mod n
• what’s is decryption process?
• why is: xed mod n = (xe mod n)*(xd mod n) mod n ?
• what is public key? private key?
• how does digital signature work?
• security of RSA hinges on difficulty of factoring large numbers – n
(to compute F(n))
5
Finding Large Primes
• If factoring is hard, how do you find large primes?
• primes get progressively “thinner” as the numbers increase
– ten digit number: probability 1/23
– hundred digit number (needed for secure RSA) 1/230
– It turns out you can test a number for primality easily even
though factoring is hard!
• Pick random large numbers and test them until you find a prime one
• Fermat’s theorem:
x p-1 mod p = 1 if p prime
• So to test if n is a prime, pick x and raise x to n-1. If it’s not 1, n
definitely not prime
• But can it be 1 even if n not prime? Yes, but probably not.
– for a 100-digit number, the non-prime prob. is 1 in 1013
– Can use different x’s
6
Optimizing Exponentiation
• brute force exponentiation of (100-digit numbers for both base and
exponent) is not possible
• optimization – compute intermediate reminders
a*a mod b = ((a mod b)(a mod b)) mod b
• another optimization: instead of multiplying the number by the same
factor multiple times – repeat squaring
a4=(a*a)*(a*a)
• can the two optimizations be combined?
7
Optimizing Encryption Operations
• Turns out RSA secure even if e in (e,n) is small (like 3 or 216+1)
• 65537=216+1 is popular because it’s prime and easily represented
in binary
– if e is small – what operations are efficient?
– can we also make d small?
• problems with 3
– if m is smaller than cube root of n then m3 mod n = m3
this makes m easy to discover, why?
• to solve – pad small message
– p and q must be chosen so that 3 is relatively prime to
• choose p and q so that 3 is relatively prime to both
p-1 and q-1
– other threats
• sooth numbers (factors of small primes) threat
• multiple message threat
• Public-Key Cryptography Standard (PKCS) standardizes use of RSA
8
to minimize threats
Diffie-Hellman
• Allows two individuals to agree on a secret key, even though they can only
communicate in public
• Alice chooses a private number and from that calculates a public number
• Bob does the same
• Each can use the other’s public number and their own private number to
compute the same secret
• An eavesdropper can’t reproduce it
Alice
agree on g,p
g<p, p - large prime
choose random A
Bob
choose random B
TA=gA mod p
TB=gB mod p
compute TAB
compute TBA
agree on gAB mod p
9
Security of Diffie-Hellman
• We assume the following is hard:
– Given g, p, and gX mod p, what is X (computing
discrete logarithm of gX mod p)?
• With the best known mathematical techniques, this is
somewhat harder than factoring a composite of the same
magnitude as p
10
Encryption with Diffie-Hellman
• D-H needs a response from both Alice and Both to initiate
communication
• this does not have to happen in real time
• suppose Bob publishes <g,p,T> in advance somewhere where
Alice cat get it
• then Alice, without Bob’s further participation, can
– select A,
– compute TA, and KAB=gAB mod p
– use KAB to encrypt the message (with secret key crypto) to
produce C
– send TA and C to Bob
– Bob is able to compute KAB and decrypt the message
11
Man-in-the-Middle Attack
• D-H provides no authentication and is vulnerable to man-in-themiddle attack
Alice
Bob
Trudy
TA=gA mod p
TT=gT mod p
TT=gT mod p
TB=gB mod p
agree on gAT mod p
agree on gTB mod p
{data}gAT mod p
{data}gTB mod p
{data}gAT mod p
{data}gTB mod p
• can Alice and Bob prevent this attack if they agree on a secret
password/answer in advance (is the fish green?/no, it is blue)
• exchange personal information Trudy does not know?
12
Signed Diffie-Hellman
(Avoiding Man-in-the-Middle)
Alice
Bob
choose random A
choose random B
[TA=gA mod p] signed with Alice’s Private Key
[TB=gB mod p] signed with Bob’s Private Key
verify Bob’s signature
verify Alice’s signature
agree on gAB mod p
if you have keys, why use D-H?
• forward secrecy – prevents intruder from decrypting the
conversation in the future even if she records all the
conversation and later discovers all the keys then available
13
Stronger than RSA and D-H
• security of RSA and D-H are based on complexity of solving certain
mathematical problems
– which ones?
• the complexity of these problems is shown to be the same
• there are solutions that are
– subexponential (less than exponential), but
– subpolinomial (more than any fixed degree polynomial)
• because of that the (private) key size is selected larger than it
needs to be – expensive private key operation
• elliptic curve cryptography (ECC) – no known subexponential
solution
– private keys are small
14
Zero Knowledge Proofs
• zero knowledge proof systems are used for authentication only
– allows Alice to prove that she knows the secret without revealing it to
Bob
• graph isomorphism
– two graphs are isomorphic if they are identical up to vertex renaming
– deciding if two graphs are isomorphic is NP-complete, generating two
isomorphic graphs and verifying isomorphism is trivial
• algorithm
– Alice generates two large (about 500 vertices) isomorphic graphs A and
B and sends them to Bob
– Alice then generates a new set of graphs G1, G2 … Gk isomorphic to A
and B
– Bob asks Alice to show isomorphism for each of G1 … Gk to ether A or B
(but not both or Bob learns isomorphism between A and B)
– Trudy can generate graphs isomorphic to A or B and she has 50%
chance of guessing which isomorphism Bob wants her to prove
• if k is large, say 30, the probability of Trudy succeeding is very 15small
Zero Knowledge Signatures
• Assuming Alice and Bob share graphs A and B
• Alice supplies the graphs G1, G2 … Gk in advance
• for a message to be signed (and send to Bob) Alice computes a
digest
• a binary version of the digest is considered to be a request to provide
isomorphism to either A (zero) or B (one).
– say, the digest is 1011, then for G1, Alice provides isomorphism to
B, for G2 – to A, for G3 and G4 – to B.
• why cannot Trudy replicate that?
• the graph isomorphism-based schemes is too inefficient to be used in
practice, instead
– a Fiat-Shamir protocol using methods similar to RSA is used
16