Reference no: EM133001064
SIT281 Cryptography - Deakin University
GUILLERMO PINEDA-VILLAVICENCIO
INSTRUCTIONS
This is an individual assignment. The aim of the assignment is that the student applies concepts and methods studied in weeks 6-7 to solve problems on the Advanced Encryption Standard, discrete logarithms, ElGamal public-key system, and the Diffie-Hellman key exchange.
PROBLEMS
Problem (1) This question is about the Advanced Encryption Standard.
(a) In the SubBytes transformation, each of the bytes of an input matrix is changed to another byte by the Table 8.1 of the textbook (S-Box table). In the question, we compute two entries of this table. In this table, if you are given the byte abcdefgh, then you look for the entry in the abcd row and the efgh column. The rows and columns are numbered from 0 to 15. Compute the relevant entries of the S-Box table for the given bytes 10110101 and 00000000.
Note: You need to compute the relevant entries in the table. No marks will be given for directly quoting the values in the S-Box table.
(b) In the MixColumns Transformation, an input matrix is multiplied by a fixed matrix, and the resulting matrix is the output. Here the addition and mul- tiplication is done in GF (28). Compute the missing entries of the resulting matrix. Give your answer in hexadecimal base, as the other entries of the matrix.
Recall that in these matrices 02 = 00000010 = x and 1A = 00011010 = x4 + x3 + x.
Problem (2) Alice and Bob has designed a public key cryptosystem based on the ElGamal. Bob has chosen the prime p = 73 and the primitive root α = 5. Bob's private key is an integer b = 60 such that β ≡ αb ≡ 65 (mod p). Bob publishes the triple (p, α, β).
(a) Alice chooses a secret number k = 30 to send the message 123456 to Bob. What pair or pairs does Bob receive?
(b) Do you think that Alice should have chosen k = 30? Give an answer and justify it.
(c) What should Bob do to decrypt the pair or pairs he received from Alice? During computation, make sure Bob does not compute any inverses.
(d) Verify the answer of Parts (a) and (c) in sagemath.
Problem (3) This exercise is about the Diffie-Hellman exchange protocol. Alice and Bob agrees to use the public prime p = 1009 and the public primitive root α = 11. Alice also chooses a secret random number x = 101. And Bob chooses a secret random number y = 41.
(a) Describe what information Alice and Bob send each other. Justify your an- swer.
(b) Determine the shared secret that each obtains.
(c) Suppose that Eve witnesses this entire exchange, the information that Alice sent to Bob, the information that Bob sent to Alice, and the public informa- tion of this exchange. Eve cannot compute discrete logarithms directly, but she is able to compute modular exponentiation with positive exponents only. Describe how she can obtain Alice's and Bob's shared secret; this involves solving the necessary equations that Eve should solve.
Problem (4) This problem computes discrete logarithms.
(a) Describe a Baby Step, Giant Step attack to find x in 5x ≡ 46 (mod 47).
(b) In this exercise you will independently study the Pohlig-Hellman algorithm (Section of 10.2.1 of the textbook). Apply the Pohlig-Hellman algorithm to find y in 5y ≡ 20 (mod 47).
(c) Without using a Baby Step, Giant Step attack or the Pohlig-Hellman algo- rithm, compute manually 5z ≡ 27 (mod 47).
Note: In this question, you may use sagemath to compute the in- termediate modular exponentiations that you will encounter.
Attachment:- Cryptography.rar