Understanding Public-Key Cryptography and Its Applications
Public-Key Cryptography revolutionized secure communication by introducing the concept of using separate keys for encryption and decryption. Initially explored by researchers like Diffie, Hellman, and Merkle in the 70s, it addressed key distribution challenges faced by symmetric cryptography. This method involves generating unique pairs of keys for users, with the public key shared openly and the private key kept secret. Applications range from encryption and authentication to key exchange, ensuring privacy, secure commercial dealings, payment transactions, and reliable voting systems.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Overview Public Key Cryptography Crossword puzzles Diffie-Hellman RSA Elliptic Curves Digital Signatures Key Management for Public-Key Cryptography
Public-Key Cryptography Main sources: Network Security Essential / Stallings Applied Cryptography / Schneier
Motivation Until early 70s, cryptography was mostly owned by government and military Key distribution is more manageable and better funded Symmetric cryptography not ideal for commercialization Enormous key distribution problem; most parties may never meet physically Must ensure authentication, to avoid impersonation, fabrication Few researchers (Diffie, Hellman, Merkle), in addition to the IBM group, started exploring Cryptography because they realized it is critical to the forthcoming digital world Privacy Effective commercial relations Payment Voting
Public-Key Cryptography Idea: use separate keys to encrypt and decrypt First proposed by Diffie and Hellman Independently proposed by Merkle (1976) Pair of keys for each user generated by the user himself Public key is advertised Private key is kept secret, and is computationally infeasible to discover from the public key and ciphertexts Each key can decrypt messages encrypted using the other key Applications: Encryption Authentication (Digital Signature) Key Exchange (to establish Session Key)
Crossword Puzzles Ralph Merkle s Key Exchange Algorithm Alice generates MANY crossword puzzles and sends to Bob Bob chooses ONE and solves it The solution includes an identifier, and the key Bob communicates the identifier to Alice Alice and Bob communicate using the key Important observation: Eve would have to solve ALL puzzles to identify the right one and the key. First attempt, cumbersome, and not working, but very revolutionary at the time Later, Merkle suggested to use NP-Hard problems Hard to solve, but easy to check (e.g., knapsack). Also proven inadequate later...
Diffie-Hellman Key Exchange First public-key algorithm, based on the difficulty of computing discrete logarithms modulo n Protocol: Use key exchange protocol to establish session key Use session key to encrypt actual communication Algorithm: Choose a large prime n, and a primitive root g Bob Alice X=gx mod n select x Y=gy mod n select y Compute K=Yx mod n K=gxy mod n Compute K=Xy mod n
Diffie-Hellman Protocol DH does not offer authentication Trudy can use a man-in-the-middle attack Impersonating Alice to Bob and vice versa Using his own key (or different keys) with each Solution: establish a public directory Each person publishes (g,n,gx) this is the public key Note: g,n may be different from one user to another Make sure not to select x=0/1 mod n
Two-key Public-Key Encryption Sender uses the public key of the receiver to encrypt Receiver uses her private key to decrypt
Two-Key Public-key Authentication The sender encrypts some message (e.g. a certificate) with his own private key The receiver, by decrypting, verifies key possession
Public-Key Algorithms: The Requirements It is computationally feasible to generate a pair of keys It is computationally easy to encrypt using the public key It is computationally easy to decrypt using the private key It is computationally infeasible to compute the private key from the public key It is computationally infeasible to recover the plaintext from the public key and ciphertext Either of the keys can decrypt a message encrypted using the other key
RSA Developed by Rivest, Shamir, and Adleman (1977) Most widely used public key algorithm Receives its security from the difficulty of factoring large numbers Actually discovered first by UK GCHQ (Ellis and Cocks) in 1973 ! Algorithm: Works as a block cipher, where each plaintext/ciphertext block is integer between 0 and n (for some n=2k) Each receiver chooses e, d The values of e, and n are made public; d is kept secret Encryption: C=Me mod n Decryption: M=Cdmod n = Med mod n Requisites: Find e, d such that M=Med mod n, for all M<n Make sure that d cannot be computed from n and e, not even if a ciphertext is available
RSA Keys and Key Generation Select primes p and q, n=pq (n)=(p-1)(q-1) ; Euler totient of n number of integers between 1 and n that are relatively prime to n, i.e., {m | gcd(m,n)=1} Select integer e< (n) such that gcd( (n),e)=1 Guarantees that e-1 exists Calculate d such that d=e-1 mod (n), Use Euler extended GCD algorithm Now, for every M<n, we have Med = M 1 mod (n) = M Note: The message could have been encrypted with d and decrypted by e
Recall Math Backgrounder Fermat s Little Theorem For a prime p, a such that 0<a<p, a(p-1)=1 mod p Euler s extension For any n, a such that 0<a<n, a (n) mod n = 1 mod n For primes p,q, a such that gcd(a,pq)=1, a(p-1)(q-1) = 1 mod pq Hence, Med mod n = Mk(p-1)(q-1)+1 mod n = 1xM = M To generate primes, use primality test For a non-prime, Fermat s theorem will usually fail on a random a Carmichael numbers are rare exception, and if chosen decryption won t work. Can reduce the probability by checking more a s Primes are dense enough (almost one of every k k-bit numbers) GCD to select e takes O(log n) time Calculate d=e-1mod (n) - Euler extended GCD. O(log n) Exponentiation (Encrypt/Decrypt) takes O(log n) time RSA gets its security from the difficulty of factoring n=pq
RSA Example Key Generation Select p=7, q=17, n=pq=119, (119)=96 Select e=5; Calculate d=77 (77*5=385=1 mod 96)
Attacks on RSA Algorithm If one could factor n, which is available, into p and q, then d could be calculated (as inverse of e), and then the message deciphered If one could guess the value of (n)=(p-1)(q-1), even without factoring n, then again d could be computed as the inverse of e
Attacks on RSA Protocol Chosen ciphertext attack Attack: get sender to sign (decrypt) a chosen message Inputs: original (unknown) ciphertext C=Me Construct X=Re mod n, for a random R Y=XC mod n Ask sender to sign Y, obtaining U=Yd mod n Compute T=R-1 mod n TU mod n = R-1Yd mod n = R-1 Xd Cd mod n = Cd mod n = M Exploits preservation of multiplication in group Conclusion: never sign a random message sign only hashes use different keys for encryption and signature
Other precautions when implementing RSA protocol Do not use same n for multiple users A third party can sometimes decipher if same message is encrypted using both encryption (public) keys, without needing the decryption (private) key Always pad messages with random numbers, making sure that M is about same size as n If e is small, there is an attack that uses e(e+1)/2 linearly dependent messages, and if messages are small its easier to find linearly dependent ones Do not choose low values for e and d For e, see above, and there is also attack on small d s
Elliptic Curves Cryptography ECC addresses the cost of exponentiation in DH and RSA Use Abelian groups w/ addition defined on cubic equations E.g., y2 = x3 + ax + b (for some a, b) For R=P+Q, find third point of intersection on line that connects P and Q (use tangent line if P=Q). This is R, and R is its mirror. O is a point of infinity and is defined as O=P+(-P). As a result it is also the identity since P+O=P Can also be defined over GF(p) Consider Q=kP mod p Easy to compute Q from k, P Difficult to determine k from P, Q (except through brute force)
Elliptic Curves Key Exchange Key Generation Select/agree on cubic curve (p, a, b) Select a base point G with a high order n --- public i.e., smallest n such that nG=O Private key of Alice is an integer KA < n Public key of Alice is KA*G --- public Key Exchange Alice and Bob send public key to each other Each of them multiplies the result by own private key Agreed Key = KA* KB*G Like DH but uses addition instead of exponentiation
Timing and Power Attacks Ciphertext-only attack No mathematical analysis How it works Measure the effort (time, power) to decrypt a message Correlate the effort to the probability that certain key bits are on Idea Different algorithms work more on certain combinations of bit values E.g., in RSA the exponentiation effort depends on the number of bits that are 1 Solutions: Idle computation to randomize & even out
Other Public-Key Algorithms Merkle-Hellman Knapsack Algorithms First public-key cryptography (not key exch) algorithm (1976) - patented Encode a message as a series of solutions to knapsack problems (NP- Hard). Easy (superincreasing) knapsack serves as private key, and a hard knapsack as a public key. Broken by Shamir and Zippel in 1980, showing a reconstruction of superincreasing knapsacks from the normal knapsacks Rabin Based on difficulty of finding square roots modulo n Encryption is faster: C=M2 mod n (n=pq) Decryption is a bit complicated and the plaintext has to be selected from 4 possibilities (also makes it difficult to use it for signature) El Gamal Based on difficulty of calculating discrete logarithms in a finite field Elliptic Curves can be used to implement El Gamal and Diffie-Hellman faster
Digital Signatures Main sources: Network Security Essential / Stallings Applied Cryptography / Schneier
Public-Key Digital Signature Same as authentication The sender encrypts a message with his own private key The receiver, by decrypting, verifies key possession
Digital Signatures It is possible to use the entire message, encrypted with the private key, as the digital signature But, this is computationally expensive And, anyone can then decrypt the original message Alternatively, a digest can be used Should be short Prevent decryption of the original message Prevent modification of original message Difficult to fake signature for If message authentication (integrity) is needed, we may use the hash code of the message If only source authentication is needed, a different message can be used (certificate)
Digital Signature Algorithm (DSA) Proposed in 1991 by NIST as a standard (DSS) Based on difficulty of computing discrete logarithms (like Diffie- Hellman and El Gamal) Encountered resistance because RSA was already de-facto standard, and already drew significant investment DSA cannot be used for encryption or key distribution RSA is advantageous in most applications (exc. smart cards) RSA is 10x faster in signature DSA is faster in verification Concerns about NSA backdoor (table can be built for some primes) Key size was increased from 512 to 2048 and 3072 bits In DSA, the key size needs to be 4 times the security level DSA has an Elliptic Curve version Faster to compute, and requires half the bits
Description of DSA Parameters p is a prime number with up to 1024 bits q is a 160-bit factor of (p-1), and itself prime public key g=h(p-1)/q mod p (h is random) x is the private key and is smaller than q y=gx mod p is part of the public key Signature Given a message M, generate a random k<q -- keep secret Signature is a pair (r,s) send r=(gk mod p) mod q send s=k-1(H(M)+xr) mod q If r=0 or s=0, choose a new k Verification Compute w=s-1 mod q Compute u1=H(M)w mod q; u2=rw mod q Compute v=(gu1*yu2 mod p) mod q If v=r then the signature is verified public key public key -- private key public key signature signature verification
Key Generation in DSA Generate q as a SHA on an arbitrary 160-bit string If not prime, try another string Use Rabin method for primality testing To get (p-1) Concatenate additional 160 bit numbers until you get to the right size (e.g., 1024) Subtract the remainder after division by 2q q is a factor from construction Since p-1 is even, then 2 is also a factor If p is not prime, repeat the process
One-Time Signatures (Merkle) Key Generation Let t = n + 1 + log n, where n is message size Select random K1, Kt (private key) Let Vi=H(Ki) for a hash function H (public key) Signature Let C be the number of 0 s in message M Let W = M || C, and let A1 At be W s bits Signature is (S1 Su) such that Sj=Kl if Al is the jth 1-bit of W Verification Compute W as above Compute H(Si) for each bit and compare to (properly indexed) Vj
Key Management for Public Key Cryptographic Protocols Main sources: Network Security Essential / Stallings Applied Cryptography / Schneier
Certificate Authority: Verifying the Public Key How to ensure that Charles doesn t pretend to be Bob by publishing a public-key for Bob. Then, using a Man-in-the-Middle attack, Charles can read the message and reencrypt-resend to Bob Bob prepares certificate with his identifying information and his public key The Certificate Authority (CA) verifies the details and sign Bob s certificate Bob can publish the signed certificate
More on (Public) Key Management Alice may have more than one key e.g., personal key and work key Where shall Alice store her keys? Alice may not want to trust her work administrator with her personal banking key Distributed certification a la X.509 CA certifies Agents who certify organizations who certify others Distributed certification a la PGP Alice will present her certificate with introducers who will vouch for her ( PKI parties ) Key Escrow US American Escrowed Encryption Standard suggests that private keys be broken in half and kept by two Government agencies Clipper for cellular phone encryption Capstone for computer communication
Cryptography Summary Cryptography (and steganography) were always considered a strategic tool Used mostly by governments and military organizations Served to keep top secrets and in wars Different generations were characterized by either the cryptographers or cryptanalysts winning the battle Today, cryptographers seem certainly on top, with unbreakable ciphers (but, remember Vigenere s unbreakable cipher ) Must remember that cryptanalysis is not the only attack It is usually the hardest way to break a message May attack human weaknesses in crypto protocol May attack communication, hosts, etc. Much easier to get information using good old 3Bs: bribery, burglary, and bending
