CS 431 homework assignment #4

This homework assignment is due on November 14.

Problem 1

Recall the iterated encryption attack on RSA. If the encryption exponent e is chosen so that repeatedly applying the encryption x^e mod n k times will produce x again, i.e., that
      k
     e 
    x   mod n = x
for all integers x. In such a case, the attacker can simply apply the encryption function k-1 times to the ciphertext to find the plaintext.

Let n = 35953, so that n=157*229.

  1. Describe how to carry out the iterated encryption attack on the RSA system using the modulus n and the encryption exponent 343.
  2. Carry out the attack on the ciphertext c=5666.
  3. How many exponents a between 1 and phi(n) are there such that
    1. gcd(a,phi(n))=1,
    2. encrypting a message twice with the exponent a will always produce the original message?

Problem 2

Do number 4.7 from the textbook.

Problem 3

Do problem 4.8 from the textbook, except use b_1 = 43 instead of b_1 = 945.

Return to the CS431 page.