 # Cryptography Problems

Subject Computer Science Cryptography

## Question

Problem 1
a. We know that encryption provides confidentiality. Does it provide privacy? (Explain)
b. SHA-256 was used to hash a message, such that SHA-256("The quick brown fox jumps over the lazy dog") = D7A8FBB307D7809469CA9ABCB0082E4F8D5651E46D3CDB762D02D0BF37C9E592.
What should be SHA-256("The quick brown fog jumps over the lazy dog")? Explain your answer.
c. List all the element of the set Zp for p=11. Does every element of Zp have an inverse?
Why/why not? For those that do, 5 and 7 (‘cause they are relatively prime with 11) give the inverse for each.

Problem 3
4-bit long message was encrypted using one-time pad to yield a cipher-text “1010” Assuming the message space consists of all 4-bit long messages, what is the probability that the corresponding plaintext was “1001”? Explain your answer.

Problem 6
1) Use the Euclidian algorithm to compute (Show all of the steps involved)
a. The GCD of 7469 and 2464.
b. The GCD of 198 and 243 (use the Extended form).

2) We also discussed the use of the Extended Euclidian algorithm to calculate modular inverses. Use this algorithm to compute the following values. Show all of the steps involved.
a. 9570-1(mod 12935)
b. 550-1 (mod 1769)

3) Let n be a product of two large primes p and q (i.e., n=pq). Assume that x, y, and g are relatively prime to n.
1) If x ≡ y (mod n), is gx ≡ gy (mod n)? Show why or why not.
2) If x ≡ y (mod Φ(n)) instead, is gx ≡ gy (mod n)? Show why or why not.

Problem 7
Alice’s uses ElGamal public key setting, with parameters, p=11, q=5, and g=4. Her public key is y=5. Bob encrypted a plaintext message m with Alice’s ElGamal public key and sent out the ciphertext (k,c) such that k=3 and c= 5, to her.
Can an adversary recover the message m, given p, q, g, y, and (k,c)? If so, what is m?
Show all steps in your solution.

Problem 8
1. How many multiplications are needed to compute x1024? (Do not tell me 1024 multiplication because it is much, much less!) Show your algorithm.
2. Bob downloaded a 50Gb tar.gz file from Alice’s server today. Bob needs to know if he downloaded the correct file and that there were no errors in the transmission, before attempting to unzip/untar it (since uncompressing such a big file might take a long time and computational resources). Unfortunately, Alice and Bob do not share any keys nor do they have a common CA. How can Bob ensure the correctness of the file? Alice and Bob know each other personally, and they are scheduled to meet in a couple of days.

Bonus
Part A. Given an elliptic curve E over Z29 and the base point P=(8,10):
E: y2=x3+4x+20 mod 29.
Calculate the following point multiplication k.P using the Double-and-Add algorithm. Provide the intermediate results after each step.
1. k=9
2. k=20
Part B. The order of the curve above is known to be #E=37. Furthermore, an additional point Q=15.P=(14,23) on this curve is given. Determine the result of the following point multiplications by using as few group operations as possible, i.e., make ‘smart’ use of the known point Q (Specify how you simplified the calculation each time.
1. 38.P
2. P+4.Q
Hint: In addition to using Q, use the fact that it is easy to compute (-P).

## Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

Problem 1

a. We know that encryption provides confidentiality. Does it provide privacy? (Explain)
Encryption can provide privacy from the third party. It can hide your communication from someone in-between listening to it. For example, if you are communicating via encrypted channel to someone, your ISP (or anybody in the path) can see the source and destination of the communication, but not the context.

b. SHA-256 was used to hash a message, such that SHA-256("The quick brown fox jumps over the lazy dog") = D7A8FBB307D7809469CA9ABCB0082E4F8D5651E46D3CDB762D02D0BF37C9E592.
What should be SHA-256("The quick brown fog jumps over the lazy dog")? Explain your answer.

It is: c223298dccec5378f3428bd697e9c84f28bf985d3906e4d9850a18e4ada9f738. The minimal change in the original results in a drastic change of the hash. Hence, it is (almost) impossible to track back the change or compute the original string. That is why it is used for storing passwords and authentication.
c. List all the element of the set Zp for p=11. Does every element of Zp have an inverse?
Why/why not? For those that do, 5 and 7 (‘cause they are relatively prime with 11) give the inverse for each.
Z11 = {0,1,2,3,4,5,6,7,8,9,10}...

This is only a preview of the solution. Please use the purchase button to see the entire solution

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.