Starting from:
$17.99
Homework 6 Cryptography
1. What is the prime factorization of 589449600?
2. What is φ(589449600)?
3. Using Fermat’s Theorem, determine 345625190 mod 2099.
4. Using Euler’s Theorem, determine 266051 mod 2664.
5. In an RSA scheme, p = 13, q = 31 and e = 127. What is d?
6. One of the primitive roots (also called generators) mod 29 is 2. There are 11 other primitive roots mod 29. One way to list these is 2a1 mod 29, 2a2 mod 29, ... 2a12 mod 29, where 0 < a1 < a2 < ... < a12. (Note: it’s fairly easy to see that a1 = 1, since 2 is a primitive root.) Find the values of a10, a11 and a12 and the corresponding values 2a10 mod 29, 2a11 mod 29, and 2a12 mod 29.
7. In the Diffie-Hellman Key Exchange, let the public keys be p = 29, g = 19, and the secret keys be a = 11 and b = 13, where a is Alice’s secret key and b is Bob’s secret key. What value does Alice send Bob? What value does Bob send Alice? What is the secret key they share?
8. In El Gamal, Alice chooses YA = αXA mod q. Bob, who is sending a message, calculates a value K = YAk, where k is randomly chosen with 0 < k < q. Is it possible that for different choices of k, Bob will calculate the same value K, or will each unique value of k be guaranteed to produce a different value for K? Give a brief rationale for your answer.
9. Program is Attached.
10. Program is Attached.
11. A primitive root, α, of a prime, p, is a value such that when you calculate the remainders of α, α2, α3, α4 , ... , αp-1, when divided by p, each number from the set {1, 2, 3, ..., p-1} shows up exactly once. Prove that a prime p has exactly φ(p-1) primitive roots. In writing your proof, you may assume that at least one primitive root of p exists. (Normally, this is the first part of the proof.) (Note: This question is difficult, so don't feel bad if you can't figure it out.)
12. Alice and Bob are using Diffie-Hellman to exchange a secret key. They are using the prime number p = 1234577 and the generator g = 1225529. Alice picks a secret value a and sends ga = 654127 to Bob. Bob picks a secret value b and sends gb = 221505 to Alice. What is the secret key they share?
13. Decrypt the following Message:
20429835450828679741350 =x1
26022799626812591980567 =x2
30572114224921561344399 =x3
14180424833673414562055 =x4
19539282983393676142312 =x5
2. What is φ(589449600)?
3. Using Fermat’s Theorem, determine 345625190 mod 2099.
4. Using Euler’s Theorem, determine 266051 mod 2664.
5. In an RSA scheme, p = 13, q = 31 and e = 127. What is d?
6. One of the primitive roots (also called generators) mod 29 is 2. There are 11 other primitive roots mod 29. One way to list these is 2a1 mod 29, 2a2 mod 29, ... 2a12 mod 29, where 0 < a1 < a2 < ... < a12. (Note: it’s fairly easy to see that a1 = 1, since 2 is a primitive root.) Find the values of a10, a11 and a12 and the corresponding values 2a10 mod 29, 2a11 mod 29, and 2a12 mod 29.
7. In the Diffie-Hellman Key Exchange, let the public keys be p = 29, g = 19, and the secret keys be a = 11 and b = 13, where a is Alice’s secret key and b is Bob’s secret key. What value does Alice send Bob? What value does Bob send Alice? What is the secret key they share?
8. In El Gamal, Alice chooses YA = αXA mod q. Bob, who is sending a message, calculates a value K = YAk, where k is randomly chosen with 0 < k < q. Is it possible that for different choices of k, Bob will calculate the same value K, or will each unique value of k be guaranteed to produce a different value for K? Give a brief rationale for your answer.
9. Program is Attached.
10. Program is Attached.
11. A primitive root, α, of a prime, p, is a value such that when you calculate the remainders of α, α2, α3, α4 , ... , αp-1, when divided by p, each number from the set {1, 2, 3, ..., p-1} shows up exactly once. Prove that a prime p has exactly φ(p-1) primitive roots. In writing your proof, you may assume that at least one primitive root of p exists. (Normally, this is the first part of the proof.) (Note: This question is difficult, so don't feel bad if you can't figure it out.)
12. Alice and Bob are using Diffie-Hellman to exchange a secret key. They are using the prime number p = 1234577 and the generator g = 1225529. Alice picks a secret value a and sends ga = 654127 to Bob. Bob picks a secret value b and sends gb = 221505 to Alice. What is the secret key they share?
13. Decrypt the following Message:
20429835450828679741350 =x1
26022799626812591980567 =x2
30572114224921561344399 =x3
14180424833673414562055 =x4
19539282983393676142312 =x5
1 file (22.1KB)
