Avalg homework 1 fall 2000

This homework is due Wednesday November 15th at 15.00. It can be delivered to Stefan personally at his office or put in his mail slot at the department. It can also be given to Stefan in connection with one of the lectures. Solutions handed in late are not accepted and will not be graded.

Some forms of collaboration are allowed. The size of a group of collaboration is limited to three. The group should hand in only one solution and for each problem it should be clearly marked which of the members have contributed. The homework will be returned on Monday November 20th. I will be in my room from 9-12 and 13-15 and the groups are expected to arrive at suitable moments in time. To minimize the waiting time, you should arrive when the queue is short. (You may, for example, use a randomized algorithm.) All members of the group must be present when the homework is returned.

I do not consider the set of problems below easy. Thus a performance of getting half the total score on this set is at least equivalent to the grade 4 on this subset of the course. Credit may be given for partially solved problems.

1. RSA implementation (40p)
Your task is to make a C or Java implementation of the RSA crypto system supporting key generation, encoding, and decoding. You should implement the algorithms from scratch. You may, however, use subroutines for addition, multiplication, and division taken from a standard library.

  • The code should follow Java Code Conventions (or similar C conventions). IndexTreeList.java is intended to be a good example.
  • Your library should be well documented and easy to use. The documentation could be generated using javadoc.
  • The API should be easy to understand. Only include the necessary methods and carefully design your data types: message, public key, secret key etc.
  • The code should be robust. Erroneous parameters and function calls should be handled gracefully.
  • The code should be efficient. On a workstation, key generation should take no more than a few minutes, encryption and decryption should take no more than a few seconds.
  • The code must, of course, be correct. Include code for testing all functions.

2. Fermat's little theorem (20p)
Give an elementary proof of Fermat's little theorem, i.e. you may not use any group theoretic arguments.

3. Detect a cycle in a linked list (20p)
How can you detect a cycle in a linked list? The list is in read-only memory, and you cannot mark elements. Also, you may only use a constant amount of extra memory.

4.Lemma 4.2 (20p)
Prove Lemma 4.2.

5. Cracking RSA (30p+70p)
a) Using any free software, write a program to crack RSA. You may use at most 5 minutes of user time on a work station and you must be able to convincingly demonstrate that your program is working. The bigger the keys you manage to crack, the more points are awarded.
b) Is it possible to crack RSA without factoring? What if you have no extra information except the public key and the encrypted message? What if you have some extra information?

Stefan Nilsson