This preview shows page 1-2-3-4-5-6 out of 19 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Q1. Explain secret and public key cryptography schemes. Use small examples to illustrate your claims. State relative advantages of each scheme. Secret Key Cryptography Overview Alice wants to send a message to Bob. Both Alice and Bob share the same secret key. To encrypt the message Alice XORs her message with the shared secret key. To decrypt the message Bob also XORs the message with his (the same) secret key. Ex. Key = 0011 Alice’s message = 0101 Alice’s message XORed with the key: 0011 XOR 0101 = 0110 What Bob Recieves = 0110 Bob applies the secret key again to get the original message: 0110 XOR key = 0101 This works for three reasons: • XOR is associative and • Any binary value XORed with itself is 0 • Any binary value XORed with 0 is itself The advantages of secret key cryptography are that 1. Performing XOR is very fast. 2. It has been well tested. The disadvantages are that 1. The key must remain secret. 2. Exchanging keys with someone must be done in secret. 3. Each communicating pair of people need to share a key. Public Key Cryptography Overview In public key cryptography there are two parts to the key: a secret part and a public part. In order for Alice to send Bob a message she first needs to obtain his public key. Because Bob likes to be contacted (albeit only via encrypted messages) he has published his public key on his homepage for anyone to download. Alice obtains his public key, encrypts a message using this key and then sends it to Bob. Bob is then able to decrypt the message using the secret part of his own key. Advantages 1. Only one part must be kept secret 2. There is no need to change your public/private key pair (unless someone finds your public key) 3. For N people to communicate there need only be N public/private key pairs. 4. There is no need for initial key exchange 5. It can serve as a digital signature a. Alice would like to post a message on a web forum and she would also like everyone reading the forum to be able to authenticate that the message was really posted by her (and not someone else claiming to be her). Alice takes her message and uses her private key to encrypt it. If the encrypted message on the forum was really posted by Alice then it should be decryptable using her public key. Since everyone has access to her public key this can be verified. Disadvantages1. Slow do to the enormous amount of computation involved. 2. Keys must be long (at least 1024 bits these days). 3. There is no proof for that any public key scheme is secure. 4. It has not been around long enough to be tested as much. Diffie-Hellman Public Key Cryptography Y = Public Key X = Secret Key User i derives Y in the following way. Yi = a^(xi) mod g User j derives Y in the same manner. Yj = a^(xj) mod g Users i and j exchange their Y’s and then perform the following computation Zij = Yj^(xi) = (a^(xj))^(xi) mod g = (a^(xi))^(xj) mod g = Zji This value of Z can then be used as the input to a random number generator. These random bits will be used to XOR the original message. Q2. Explain the Diffie-Helman key distribution scheme. Show a small example. Explain (very briefly) other public key schemes and their relative advantages and limitations. Explain the Diffie-Helman key distribution scheme: • Public key cryptography scheme • Uses a one-way function. • Security due to the difficulty of calculating logarithms as compared to the ease of calculating exponentiations. • How o Alice and Bob want to generate a secret key o Public Givens: Large prime number n g = primitive mod of n o Alice choses a random large number integer x and sends to Bob X=gx mod n o Bob choses a random large number y and sends to Alice Y = gy mod n o Alice computes k=Yx mod n o Bob computes k’=Xy mod n o The secret key k=k’=gxy mod n o No one listening can compute the value k since they only know n, g, X, Y, and it is too difficult to compute the log to obtain x and y. Show a small example:• g= 6 = 35 mod n n = 29 • Alice choses x = 101 X = 6101 • Bob choses y = 53 Y = 653 • Alice computes k = 653*101 • Bob computes k’ = 6101*53 Explain other public key schemes and their relative advantages and limitations: • RSA: Difficulty of recovering plain text from cipher test is conjectured to be equivalent to factoring products of large prime numbers Advantages: Been around a long time, and heavily studied Disadvantages: Not proven only conjectured security • McEliece: Idea: Based on Algebraic coding theory Construct an error-correcting code, specifically a Goppa code Disguise the Goppa code as a general linear code Finding a code word of a given weight in a linear binary code is NP complete but fast algorithm exists for decoding Goppa code Advantages: Fast Disdvantages: Key is enormous Data expansion is large • Eliptic Curves: Eliptical curves are utilized to implement algorithms such as Diffie-Hellman Advantages: Most efficient with regard to key • Quadratic residuity Quadratic Residue is based on number theory idea of the same name • Largest Clique Acknowledgement: Applied Crytpography by Bruce Schneier was heavily referenced Q3. Explain the Shamir's secret sharing scheme. Explain its application. Show a small example. Explain potential alternatives. Objective: Secret Sharing scheme that is both perfect and fault tolerant perfect - stored key does not reveal any information fault tolerant - if one part of key is lost - the key must still be recoverable. Using polynomial interpolation - and the idea that for any polynomial of degree k, for any k-points, there is only one line that passes through all of these points.The shares of the key are represented by these points on the k-degree polynomial. By interpolating the line at x=0, the secret is obtained. For example, for a 2-degree polynomial, if the shares are represented by the points <x1,y1>,<x2,y2>...<xn,yn> - all of these points lie on the same line. Pick any two points - draw a line through them, and the intersection at x=0 is the secret. For a k-degree polynomial, at least k points must be picked to determine the intersection at x=0. The scheme is fault-tolerant because not all shares are needed to determine the secret. In addition the scheme is perfect because the secret can be encrypted. Even complete knowledge of k-1 shares (for k-degree poly) will not reveal the secret. Shortcomings: The scheme does not


View Full Document

UCLA COMSCI 259 - Midterm Answers

Download Midterm Answers
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Midterm Answers and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Midterm Answers 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?