乐趣区

关于后端:COMP90043-CRYPTOGRAPHY

The University of Melbourne
Department of Computing and Information Systems
COMP90043-CRYPTOGRAPHY AND SECURITY
Practice Exam 2021
Exam Duration: 15 minutes reading + 120 minutes Exam writing;
Instructions to Students:
Total marks for the exam is 40 (Worth 40% of the final mark in the subject).
Note that you should complete writing the exam within 2.15 minutes. Then you will
have 30 minutes to scan and uplaod the work. Other exam rules apply.
The exam will have two parts: Part A is a quiz on canvas, Part B is this assignment
and will have 10 questions.
The test is open book, which means you may only use course materials provided
via the LMS or the text book but must not use any other resource including the
Internet.
You also must not contact or communicate with any other person (other than teach-
ing team) or make use of the Internet.
Solutions must be written on blank A4 page paper with pen and pencil. You must
write your solutions to each question on a new sheet of paper by clearly identifying
the question number.
You must not use tablet or any electronic device to generate your solution.
Scanning instructions are already made available on Canvas in an announcement.
Page 1 of 13 continued on next page
Part A (Q1-3
Please complete the Quiz on Canvas available at Assignments – Practice Exam – Part A
Part B: This Assignment:

  1. Classical Ciphers (3 marks)
    (a) The Vatsyana cipher is a specific version of a classical substitution cipher with
    the following two conditions:
    i. A character x is mapped to another distinct character y and
    ii. If a character x is mapped to y, then the character y will be mapped to x.
    In other words, substitution happens in pairs where the characters in each
    pair are mapped to each other.
    How many possible keys are there when the cipher is defined over 26 English
    characters?
    (b) Consider the following version of a classical cipher where plain text and cipher
    text elements are from integers from 0 to 25. The encryption function, which
    takes any plain text p to a cipher text c, is given by
    c = Ea,b = (ap + b) mod 26,
    where a and b are integers less than 26.
    Show how an adversary can attack the system under the“Chosen Plaintext
    Attack”model.
  2. (3 marks) This question is about computing the inverse of a number modulo n, where
    n a positive integer. Note: Inverse of a number a mod n is a number x such that
    xa = 1 mod n. In this semester, we studied methods for finding inverse modulo n
    using the Extended GCD algorithm (XGCD) and Fermat’s or Euler’s theorems.
    (a) When n is a prime number, write a pseudocode for the function inverse modulo
    n using the properties of the Fermat’s theorem.
    Page 2 of 13 continued on next page
    (b) The Extended GCD algorithm (XGCD), also known as the Euclidean algo-
    rithm, takes two given integers a and b as inputs and returns three integers g,
    x and y such that
    a x + b y = g,
    where g is the greatest common divisor of the input integers.
    You have provided the results from the XGCD function and exponentiation
    modular identities below:
    i. XGCD(12986, 46799) = 1, 8905,2471
    ii. XGCD(12, 39) = 3,3, 1
    iii. XGCD(17, 29) = 1, 12,7
    iv. 1229 mod 31 = 13
    v. 1029 mod 31 = 28
    Now determine the inverse of the following numbers:
    i. 12 mod 39
    ii. 12986 mod 46799
    iii. 17 mod 29
    iv. 12 mod 17
    v. 12 mod 31
    vi. 10 mod 31
    Page 3 of 13 continued on next page
  3. (4 marks) This question is about hash and MAC.
    (a) What is the main difference between hash functions and message authentication
    codes (MAC)?
    (b) Consider a version of the practical RSA signature algorithm discussed in the
    lectures. Let n, e be Alice’s RSA public key and d be Alice’s private key. The
    signature of a message m, 0 < m < n? 1 is given by
    (m, s = (h(m))d mod n),
    where h is a hash function. Answer the following questions:
    i. What is the verification equation?
    ii. Describe the“second preimage resistant”property of the hash functions.
    Page 4 of 13 continued on next page
    iii. A researcher discovers that the hash function used in the above scheme
    failed the second preimage resistance property. What are the consequences
    for the collision resistance property of the function and the security of the
    signature algorithm? Explain your answers.
    (c) (For Study) In the subject, we looked at the seven requirements of Hash func-
    tions. Out of these, one-way property, second image resistance and collision
    resistance are the three key requirements. Describe these three requirements.
  4. (2 marks) Consider the finite field GF (23) as poynomails modulo 1 + x2 + x3 .
    i Elements:xi As Polynomials As Vectors
    ?∞ 0 0 [0, 0, 0]
  5. 1 1 [1, 0, 0]
  6. x x [0, 1, 0]
  7. x2 x2 [0, 0, 1]
  8. x3 []
  9. x4 []
  10. x5 []
  11. x6 []
  12. x7 1 [1, 0, 0]
    Table 1: Elements of GF (23) as powers of x
    (a) Complete the polynomial representations of the missing elements of the table.
    (b) Solve the equation in y: xy = x3.
    (c) Compute x3 + x6 + x5;
    Page 5 of 13 continued on next page
  13. (3 marks) Consider the ElGamal signature scheme over the prime field GF (q) given
    in lectures. Let H be a public hash function, yA = a
    xA mod q be the public key of
    Alice, where xA, 1 < xA < q 1 is the private key and a is a primitive element in
    the field. Alice uses the following equation to define the ElGamal signature scheme:
    k S2 + xAS1 = m mod (q 1),
    where m = H(M), M an arbitrary message and k, S1 and S2 are the signature
    parameters used in the scheme.
    (a) What are the signing and verification equations?
    (b) What is the consequence of using same k for signing two different messages?
    (c) What is the consequence if the function H used in the signing equation violates
    the second preimage resistant property of hash functions?
  14. (3 mark) Assume the RSA signature parameters for this question. Marvin (an
    adversary) accidentally discovers the following message and signature pairs in Alice,s
    computer.
    (m1, s1) and (m2, s2),
    where s1 = (m1)
    d mod n and s2 = (m2)
    d mod n. To his amazement, he discovers
    that the message he wanted to forge was exactly m = (m31 m2) mod n. Is it possible
    to forge Alice,s signature on the message m? If so, describe how to construct a forged
    signature on the message. Note that in this question we assume the basic textbook
    RSA signature scheme which do not employ any hash function.
  15. (3 marks) Alice and Bob exchange their authentic RSA key parameters. Let na, ea
    and nb, eb be public RSA parameters of Alice and Bob respectively. Similarly let da
    and db be private RSA keys of Alice and Bob respectively. Let Ek() and Dk() be
    encryption and decryption functions of the popular symmetric key cipher AES. Bob
    wants to send a large file FILE to Alice as explained below:
    Page 6 of 13 continued on next page
    (a) Chooses a random session key ks, and encrypts as C = k
    ea
    s mod na.
    (b) Encrypts FILE using the AES cipher as: ENC FILE = Eks(FILE).
    (c) Computes h = HASH(FILE), where HASH is a public hash function.
    (d) Computes the signature as S = hdb mod nb.
    (e) Sends (ENC FILE, C, S) to Alice.
    Now complete the missing parameters in the following steps to be performed by
    Alice if the messages are error free and not tampered.
    (a) ks = ……………………….. modna.
    (b) FILE RECEIVED = …………………………
    (c) h? = HASH(………………………..).
    (d) Seb mod nb = …………………………
    Page 7 of 13 continued on next page
  16. (2 marks) The following equations and figure describe one of the standard modes of
    usage of symmetric key encryption.
    Figure 1: A Standard Mode of Encryption
    Encryption:
    C1 = (EK [IV ⊕ P1]).
    Cj = (EK [Cj?1 ⊕ Pj]), j > 1.
    (a) What is the name of this mode?
    (b) Expand the abbreviations and functions used in the equations:
    i. IV = ………………………..
    ii. K = ………………………..
    iii. Cj = ………………………..
    iv. Pj = ………………………..
    v. Ey[x] = ………………………..
    (c) Complete the equations for decryption below:
    Decryption:
    P1 = ————–.
    Pj = ————–.
    (d) What is the effect on the plain text of a one bit error in the transmission of an
    encrypted“block Cj”?
    Page 8 of 13 continued on next page
  17. (3 marks) Consider the following two protocols considered in the subject which are
    variations of Needham-Schroeder protocol:
    Protocol A (Denning’s Protocol):
  18. A → KDC: IDA || IDB
  19. KDC → A: E(KA, [Ks||IDB||T ||E(Kb, [Ks||IDA||T])])
  20. A → B: E(KB, [Ks||IDA||T])
  21. B →A: E(Ks, N1)
  22. A → B E(Ks, f(N1))
    Protocol B (An improvement to Denning’s Protocol):
  23. A → B: IDA || Na
  24. B → KDC: IDB||Nb||E(Kb, [IDA||NA||Tb])
  25. KDC → A: E(KA, [IDB, Na||Ks||Tb])||E(KB, [IDA,Ks||Tb])||Nb
  26. A →B: E(Kb, [IDA||Ks||Tb])||E(Ks, Nb)
    (a) What is the role of T in Protocol A?
    (b) What is Suppress-Replay Attack?
    (c) Is Protocol A susceptible to Suppress-Replay Attack? Explain your answer and
    suggest a remedy if your answer is yes.
    Page 9 of 13 continued on next page
    (d) Explain how Protocol B address the above susceptibility.
  27. (4 marks)
    (a) Describe the Diffie-Hellman (DH) key agreement protocol defined over the
    group of integers modulo p, where p is a prime number. You are welcome
    to use any assumptions required to complete the statement of the protocol.
    Your answer should include the public parameters of the scheme and series of
    messages exchanged between the users A and B.
    Page 10 of 13 continued on next page
    (b) Show how this protocol is susceptible to a man-in-the-middle attack.
    Page 11 of 13 continued on next page
    (c) Modify the protocol in part (a) so that it is secure against the vulnerability
    found in part (b) using the public key certificate scheme as defined in this
    subject. Briefly justify your solution. For your benefit, some relevant details
    about the certificate scheme are given below. You may have to fill in missing
    details if required.
    Let [PUauth, PRauth] be the public and private key pair of the certificate
    authority.
    Let E(PU, .) and D(PR, .) be the public key encryption and decryption
    functions used in the scheme.
    The format of the certificate for a user A is given as CA = E(PRauth, [T ‖
    IDA ‖ PUA]), where T is a timestamp.
    Page 12 of 13 continued on next page
退出移动版