**Chapter 19**
1. Use Hasse’s theorem to find bounds for the number of points on an elliptic curve modulo 883.
2. Use Hasse’s theorem to find bounds for the number of points on an elliptic curve modulo 547.
3. Use Hasse’s theorem to find an upper bound on the smallest prime modulus that will yield at least 1000 points for any elliptic curve.
4. Use Hasse’s theorem to find an upper bound on the smallest prime modulus that will yield at least 5000 points for any elliptic curve.
5. We represented 100P as 2(2(P+2(2(2(P+2P))))), so that the multiplication could be performed more quickly. Find similar expressions for
a) 108P
b) 76P
c) 65P
d) 29P
6. Verify that 5(14, 15) = (8,8) for the elliptic curve y^{2} = x^{3} – 2x + 3 (mod 29).
7. Verify that (12, 5) + (8,8) = (15, 19) for the elliptic curve y^{2} = x^{3} – 2x + 3 (mod 29).
8. Find all solutions to y^{2} = x^{3} + 2x + 5 (mod 11).
9. Find all solution to y^{2} = x^{3} + 3x + 7 (mod 13).
10. The Rijndael S-box sends 59 to 226. Verify that the polynomial inverse / matrix method achieves the same result.
11. The Rijndael S-box sends 228 to 105. Verify that the polynomial inverse / matrix method achieves the same result.
12. Explain why the Rijndael S-box could not be defined by sending every byte to its inverse modulo x^{8} + x^{4} + x^{3} + x, followed by the matrix multiplication. Hint: the modulus was changed in a small, but significant, way.
13. Use the extended Euclidean algorithm to find the inverse of x^{5} + x^{3} + 1 modulo
x^{8} + x^{4} + x^{3} + x + 1.
14. Use the extended Euclidean algorithm to find the inverse of x^{6} + x^{5} + x^{4} modulo
x^{8} + x^{4} + x^{3} + x + 1.
15. When deciphering, to undo the MixColumns step, we need to multiply each column by
d(x) = 11*x*^{3} + 13*x*^{2} + 9*x* + 14. Represent this operation in terms of matrix multiplication, just as was done for the enciphering step using c(x).
16. Calculate RC_{10}, RC_{11}, and RC_{12}.
17. Calculate RC_{13} and RC_{14}.
18. How long would it take to break AES by brute force, on average, if a billion keys can be checked every second? Suppose an attack is found that’s a thousand times better than brute force. How long would it take now?
**Share with your friends:** |