| Home Page |
| Course Page |
Overview
RSA Public Key Cracking
Software Requirements
-- Clarifications
Software Design
Submission Requirements
Grading Criteria
-- Test Cases
Late Projects
Plagiarism
Resubmission
Write a Java program that uses multiple threads to learn about thread coordination.
RSA is the most popular public key cryptosystem in the world. It is used by many, many web sites to set up secure (https://) connections. If anyone cracks a secure web site's RSA public key, security on that web site is destroyed, and secure e-commerce on that web site becomes impossible. Here is an explanation of the aspects of RSA needed to do this project.
An RSA public key consists of an exponent e and a modulus n. For this project we are only concerned with the modulus. An RSA modulus is the product of two secret prime numbers p and q: n = pq. For security, p and q are large prime numbers, typically at least 1024 bits in binary; then n is a 2048-bit binary number. Here is an example:
p = 131504983344666497997247391227148477187915980511410059153836658241896376670646449788350139815770084444640067092249971284044679154763860072283532106228154491493367366128862255154194345174844062325151089826329014721466014229328808477175986065559794374349346019013822816401505201773123511634014150881884280222199 q = 170245394201671489160339054390478038203645926235216355420353921703700353830805120706390674907934127819174341661084155376655408909357990565227256275939588716046778366293485012051209360100097076072275310280959158660203029609664278271759867465267588579646633719784702645993243077686872322430924369441276297242751 n = 22388117728996991573266070571577825430301386113027161337459043126449048908415228998507558449856779151445304433725318912994261324170148188781331203814761116857774682433277397592707425208397747471669951098693581044485791678719131646146233189901461026354979683435039656066495102434288959201375691143874027872750089414633756790430523886905678415587248852600608589995154234481041078367109794938826903417447744118225141086160785883392168834038011994467341446256182233246944523249038665678383414791268158887147073059163997289161036147899525530899576857045226756191639136368576638195655236811969381274032567121602825322029449
To crack an RSA modulus n, you find its two factors p and q. However, the fastest known integer factoring algorithms simply are not practical when n is this large; the universe will have ended before the algorithm finds the factors. The security of RSA rests on the difficulty of factoring large integers.
However, there is another way to crack RSA moduli. Suppose we have two RSA moduli: n1 = p1q1 and n2 = p2q2. p1, q1, p2, and q2 are secret. But suppose p1 = p2; that is, n1 and n2 have a common factor. Then computing the greatest common denominator (GCD) of n1 and n2 yields that common factor. Unlike finding the factors of an integer, there is a very simple algorithm for finding the GCD of two integers, namely the Euclidean Algorithm. This algorithm runs quickly, even on 2048-bit numbers.
If GCD(n1,n2) = 1, then we learn nothing about the factors of n1 and n2 (except the trivial fact that both are divisible by 1). Otherwise, GCD(n1,n2) = p1, the common factor. We can then easily find the other factor q1 = n1/p1. Likewise, q2 = n2/p1.
No two RSA moduli are ever supposed to have a common factor. However, it turns out that in the real world, about two out of 1000 secure web sites' RSA moduli do have common factors, and thus are susceptible to cracking. This was published recently:
Programming Project 2 is multithreaded Java program that cracks RSA moduli. To write this program, you will need to work with class java.math.BigInteger. Refer to the Javadoc for a complete list of class BigInteger's constructors and methods. Here are some you may find useful.
The RSA cracking program's input is stored in a plain text file. Each line of the file contains one RSA modulus. These RSA moduli might or might not have common factors.
The program reads the input file and creates multiple threads, one thread for each different pair of RSA moduli from the file. Each thread attempts to find the factors of its two RSA moduli, using the technique described above.
The program prints its results on the console. For each RSA modulus in the input file for which the program was able to find the factors, the program prints one line of output. The line consists of the modulus, a space character, one factor of the modulus, a space character, and the other factor of the modulus. The two factors may appear in either order on the line. The lines must appear in ascending order of the modulus.
java RsaCrack <filename>where <filename> is the name of the plain text input file.
Note: This means that the program's class must be named RsaCrack, and this class must not be in a package.
Clarifications to the Requirements
Note: This means the main thread must not print the program's results, and there must not be a separate thread that prints the program's results.
Your project submission will consist of a Java archive (JAR) file containing the Java source file for every class and interface in your project. Put all the source files into a JAR file named "<username>.jar", replacing <username> with the user name from your Computer Science Department account. The command is:
jar cvf <username>.jar *.java
If your program uses classes or interfaces from the Computer Science Course Library without changes, then you do not need to include these classes' or interfaces' source files in your JAR file. If your program uses classes or interfaces from the Computer Science Course Library with changes, then you do need to include these classes' or interfaces' source files in your JAR file.
Send your JAR file to me by email at ark@cs.rit.edu. Include your full name and your computer account name in the email message, and include the JAR file as an attachment.
When I get your email message, I will extract the contents of your JAR file into a directory. However, I will not replace any of the source files in the Computer Science Course Library with your source files; your project must compile and run with your files in their own separate directory. (You can do this project without needing to replace any source files in the Computer Science Course Library.) I will set my Java class path to include the directory where I extracted your files and the directory where the Computer Science Course Library is installed. I will compile all the Java source files in your program using the JDK 1.6.0 compiler. I will then send you a reply message acknowledging I received your project and stating whether I was able to compile all the source files. If you have not received a reply within one business day (i.e., not counting weekends), please contact me. Your project is not successfully submitted until I have sent you an acknowledgment stating I was able to compile all the source files.
The submission deadline is Wednesday, January 16, 2013 at 11:59pm. The date/time at which your email message arrives in my inbox (not when you sent the message) will determine whether your project meets the deadline.
You may submit your project multiple times before the deadline. I will keep and grade only your most recent submission that arrived before the deadline. There is no penalty for multiple submissions.
If you submit your project before the deadline, but I do not accept it (e.g. I can't compile all the source files), and you cannot or do not submit your project again before the deadline, the project will be late (see below). I strongly advise you to submit the project several days before the deadline, so there will be time to deal with any problems that may arise in the submission process.
I will grade your project by:
When I run your program, the Java class path will point first to the directory with your compiled class files, followed by the directory where the Computer Science Course Library is installed. I will use JDK 1.6.0 to run your program.
I will grade the test cases based solely on whether your program produces the correct output as specified in the above Software Requirements. Any deviation from what is specified will result in a grade of 0 for the test case. This includes errors in the formatting (such as extra spaces, missing spaces, the use of a tab instead of a space), incorrect upper/lowercase, incorrect punctuation, misspelled words, missing output, and extraneous output not called for in the requirements. The requirements state exactly what the output is supposed to be, and there is no excuse for outputting anything different. If any requirement is unclear, please ask for clarification.
If there is a defect in your program and that same defect causes multiple test cases to fail, I will deduct points for every failing test case. The number of points deducted does not depend on the size of the defect; I will deduct the same number of points whether the defect is 1 line, 10 lines, 100 lines, or whatever.
After grading your project I will put your grade and any comments I have in your encrypted grade file. For further information, see the Course Grading and Policies and the Encrypted Grades.
| Command and input file | Correct output | |
| 1. | java RsaCrack | Error message, missing file name |
| 2. | java RsaCrack test02in.txt | Error message, invalid modulus |
| 3. | java RsaCrack test03in.txt | test03out.txt |
| 4. | java RsaCrack test04in.txt | test04out.txt |
| 5. | java RsaCrack test05in.txt | test05out.txt |
| 6. | java RsaCrack test06in.txt | test06out.txt |
| 7. | java RsaCrack test07in.txt | test07out.txt |
| 8. | java RsaCrack test08in.txt | test08out.txt |
| 9. | java RsaCrack test09in.txt | test09out.txt |
| 10. | java RsaCrack test10in.txt | test10out.txt |
If I have not received a successful submission of your project by the deadline, your project will be late and will receive a grade of 0. You may request an extension for the project. There is no penalty for an extension. See the Course Policies for my policy on extensions.
Programming Project 2 must be entirely your own individual work. I will not tolerate plagiarism. If in my judgment the project is not entirely your own work, you will automatically receive, as a minimum, a grade of zero for the assignment. See the Course Policies for my policy on plagiarism.
If you so choose, you may submit a revised version of your project after you have received the grade for the original version. You are allowed to make one and only one resubmission of the project. However, if the original project was not successfully submitted by the (possibly extended) deadline or was not entirely your own work (i.e., plagiarized), you are not allowed to submit a revised version. Submit the revised version via email in the same way as the original version. I will accept a resubmission up until 11:59pm Monday 28-Jan-2013. I will grade the revised version using the same criteria as the original version, then I will subtract 2 points as a resubmission penalty. The revised grade will replace the original grade, even if the revised grade is less than the original grade.
| Course Page |
| Home Page |