Assignment 5 Solution

Goal










To get hands on experience with algorithms to perform mathematical operations on large integers, using RSA as an example.




Important note: The result of this project should NEVER be used for any security applications. It is purely academic. Always use trusted and tested crypto libraries!




High-level description










You will be writing two programs. The first will generate a 512-bit RSA keypair and store the public and private keys in files named pubkey.rsa and privkey.rsa , respectively. The second will generate and verify digital signatures using a SHA-256 hash. You will use Java's MessageDigest class to complete this project. In order for either of these programs to work, however, you will need to complete an implementation of a class to process large integers.







Specifications










1. You are provided with the start of a class to process large integers called LargeInteger . LargeInteger objects are represented internally as two's-complement raw integers using byte arrays




(i.e., instances of byte[] ).







1. Currently, LargeInteger has the following operations implemented:







A constructor to generate an n-bit random, positive, probably prime integer using a specified source of randomness. This constructor uses a probabilistic primality test to ensure that it is probably prime (with 2^-100 chance of being composite).




A constructor that creates a new LargeInteger object based on a provided byte[] .







A method to compute the sum of two LargeInteger objects.




A method to determine the negation of a LargeInteger object.







A method to compute the difference of two LargeInteger objects.







Several other helper methods.







2. Due to the use of a two's complement representation of the integers, LargeInteger objects should always have at least one leading 0 bit (indicating that the integer is positive) in their




byte[] representation. This property may cause the array to be bigger than expected (e.g., a 1024-bit generated prime will be represented using a length 129 byte array).




LargeIntegers are represented using a big-endian byte-order, so the most significant byte is at index 0 of the byte[] .



In order to generate RSA keys and perform RSA encryptions and decryptions, you will further need to implement the following functions:
LargeInteger multiply(LargeInteger other)




LargeInteger[] XGCD(LargeInteger other)




LargeInteger modularExp(LargeInteger y, LargeInteger n)




Any additional helper functions that you deem necessary.







5. You may not use any calls the Java API class java.math.BigInteger or any other JCL class







when writing LargeInteger . The probably-prime LargeInteger constructor calls BigInteger 's probablePrime method; this is the only call allowed to BigInteger in your LargeInteger class.







Once LargeInteger is complete, write a program named RsaKeyGen to generate a new RSA keypair.



To generate a keypair, follow the following steps, as described in lecture.



Pick p and q to be random primes of the appropriate size to generate a 512-bit key



Calculate n as p*q



Calculate φ(n) as (p-1)*(q-1)



Choose an e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1 (e must not share a factor with φ(n))



Determine d such that d = e⁻¹ mod φ(n)






2. After generating e, d, and n, save e and n to pubkey.rsa , and d and n to privkey.rsa .







3. Once you have your RSA keys generated, write a second program named RsaSign to sign files and verify signatures. This program should accept two command-line arguments: a flag to specify whether to sign or verify ( s or v ), and the name of the file to sign/verify.







1. If called to sign (e.g., java RsaSign s myfile.txt ) your program should:







1. Generate a SHA-256 hash of the contents of the specified file (e.g., myfile.txt ).




2.
"Decrypt" this hash value using the private key stored in privkey.rsa (i.e., raise the hash


value to the d power mod n).










Note: Your program should exit and display an error if privkey.rsa
is not found in the


current directory.








3.
Write out the signature to a file named as the original, with an extra .sig
extension (e.g.,


myfile.txt.sig ).








2. If called to verify (e.g., java RsaSign v myfile.txt ) your program should:
1.
Read the contents of the original file (e.g., myfile.txt ).






2.
Generate a SHA-256 hash of the contents of the original file.






3.
Read the signed hash of the original file from the corresponding
.sig
file (e.g.,


myfile.txt.sig ).










Note: Your program should exit and display an error if the
.sig
file is not found in the


current directory.








4.
"Encrypt" this value with the key from pubkey.rsa
(i.e., raise it to the e power mod n).


Your program should exit and display an error if
pubkey.rsa is not found in the current


directory.








5.
Compare the hash value that was generated from myfile.txt to the one that was


recovered from the signature. Print a message to the console indicating whether the signature is


valid (i.e., whether the values are the same).














Submission Guidelines










DO NOT upload any IDE package files.







You must name your key generation program RsaKeyGen.java , and your signing/verification program RsaSign.java .







You must be able to compile your program by running javac RsaKeyGen.java and javac RsaSign.java .







You must be able to run your key generation program by running java RsaKeyGen , and your signing/verification program with java RsaSign s <filename and




java RsaSign v <filename .







You must fill out info_sheet.txt .







The project is due at 11:59 PM on Saturday, December 7. Upload your progress to Box frequently, even far in advance of this deadline. No late assignments will be accepted. At the deadline, your Box folder




will automatically be changed to read-only, and no more changes will be accepted. Whatever is present in your Box folder at that time will be considered your submission for this assignment—no other submissions will be considered.




Additional Notes/Hints










An example of using java.security.MessageDigest to generate the SHA-256 hash of a file is provided in HashEx.java




You may find the creation of pubkey.rsa , privkey.rsa , and signature files to be most easily accomplished through the use of java.io.ObjectOutputStream . The format of your key and signature files is up to you.




NEVER USE CODE FROM THIS PROJECT IN PRODUCTION CODE. This is purely instructive. Always use trusted and tested crypto libraries.







Grading Rubric










LargeInteger










Feature Points




multiply
20




XGCD
25




modularExp
10







Key generation










Feature
Points




p and q are generated appropriately
3




n and φ(n) computed appropriately
3




e is selected appropriately
4




d is selected appropriately
5




Key files are generated appropriately
5




Signing










Feature
Points




Hash is generated correctly
2




Hash is "decrypted" (signed) correctly
5




Signature file is generated appropriately
3







Verification










Feature
Points




Hash is re-generated correctly
2




Signature is "encrypted" (verified) correctly
5




Signed files are appropriated verified
3







Other










Feature Points




Assignment info sheet/submission
5