MATH 4176 FINAL EXAM
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
MATH 4176
FINAL EXAM
Due 11 AM, 05/05/2023
1. By using Solovay-Strassen algorithm, verify whether n = 804509 is a prime or composite number .
2. Suppose that n = 90581 and b = 17993 in the RSA Cryptosystem . Factor n by using Wiener’s algorithm .
3. By using Pollard p − 1 algorithm, factor 49349 . Write all your steps clearly. Simply writing down the factors, without any work, will not get any credit .
4. Consider p = 353 where 3 is a primitive element modulo 353 . Using Pohlig-Hellmann algorithm, solve 3x ≡ 135 mod 353 for the exponent x modulo 352 .
5. Consider p = 383 . It can be checked that α = 2 has order 191 in Z3(*)83 . Use Pollard rho discrete logarithm algorithm to compute log2 228 in Z3(*)83 .
6. Given that 5 is a primitive element modulo 47, solve 10 ≡ 5a mod 47 by using Shank’s algorithm .
7. Consider the elliptic curve E defined by y2 = x3 + 1 . It is known that the only points on this curve that have integer coordinates are (−1, 0) , (0 , ±1) , (2 , ±3) .Take these five points, along with the sixth point O that is the “point at infinity” as defined in the class . Show that these six points, under the point-addition operation defined in class, form a group by constructing a group table for these six points .
8. Let E be the elliptic curve y2 = x3 + x + 26 defined over Z127 and consider the point P = (2 , 6) on E . Using the NAF representation of 27, compute 27P with the help of Double-and-Add or Subtract algorithm . Show the partial results during each iteration of the algorithm .
9. Alice sets up an NTRU system with numerical keys (that is, a congruential cryptosystem), with q = 918293817 and private keys (f,g) = (19928 , 18643) .
(a) What is Alice’s public key h?
(b) Alice receives the ciphertext c = 619168806 from Bob . What is the plaintext?
(c) Bob sends Alice a second message by encrypting the plaintext m = 10220 using the random element r =
19564 . What is the ciphertext that Bob sends to Alice?
10. (a) Alice and Bob agree to communicate using NTRUEncrypt with (N,p,q) = (7 , 3, 37) . Alice’s private key is f (x) = −1 + x − x3 + x4 + x5 . You can check that F3 (x) = 1 + x − x2 + x4 + x5 + x6 in R3 . Alice receives the ciphertext:
c(x) = 2 + 8x2 − 16x3 − 9x4 − 18x5 − 3x6
from Bob . Decipher the message and find the plaintext .
(b) Alice and Bob decide to communicate using NTRUEncrypt with parameters (N,p,q) = (7 , 3 , 29) . Alice’s public key is: h(x) = 3 + 14x − 4x2 + 13x3 − 6x4 + 2x5 + 7x6 . Bob sends Alice the plaintext message m(x) = 1 + x − x2 − x3 − x6 using the random element r(x) = −1 + x2 − x5 + x6 . What ciphertext does
Bob send to Alice?
11. Bonus Problem (5 points): Are ’ellipses’ related to ’elliptic curves’ ? As it turns out, there is actually a beautiful story here! To see this, go to
https://www.maa.org/sites/default/files/pdf/upload_library/2/Rice-2013.pdf or click here
and read the attached paper . Write a couple of paragraphs summary (in less than 200 words) of this paper to explain how these terms are related .
2023-05-02