C programs must compile with no warnings or errors using: gcc -std=c11 -pedantic -Wall
Shell scripts should run correctly using dash.
Each source file must start with a comment containing your name and a description.
Write a shell script which extracts the modulus, prime1, and prime2 fields from the text form of an openssl RSA private key. For example:
dash p1.sh < privkey.txt > p1.outHint: use a shell while loop to read lines from standard input, and use tr -d to remove unwanted characters from the input lines.
The input privkey.txt file is available here and also in the VECR a6/ directory.
The output should be the hex modulus, prime1, and prime2 values on three separate lines written to standard output.
Reference: privkey.sh was used to create the privkey.txt file.
Design routines in C to read, add, multiply and print arbitrary size integers. Then write a main program which reads three integers representing RSA modulus, prime1, and prime2 values in hex (i.e. the output of p1.sh), and prints the primes, the sum of the primes, the product of the primes, and an error message if the product of the primes is not equal to the modulus.
Do not use any libraries except the standard C library.
Sample usage:
./p2 < p1.out > p2.outFor comparison: p2.py Python implementation
To print a byte in hex in C use format "%02x".
Arbitrary size integers can be represented using an array of unsigned char, with each element holding one byte of the value.
Use fgets() to read a hex input line
into a string, e.g. char line[BUFSIZ];
and then convert the hex string to an unsigned char array of size
strlen(line)/2
, converting two hex digits per byte.
Addition is performed byte-by-byte, using mod 256 and propagating the carries, for example (ex.in, ex.out):
123 127 253 7b 7f fd (hex) + 201 20 49 + c9 14 31 ----------------------- -------------- 302 = 1*256 + 46 1 123 127 253 + 201 20 49 ----------------------- 324 148 46 (324 = 1*256 + 68) 1 123 127 253 + 201 20 49 ----------------------- -------------- 1 68 148 46 01 44 94 2eMultiplication is also performed byte-by-byte:
123 127 253 * 201 20 49 first multiply 253 by 49 (= 12397) -------------------------------- 12397 adjust mod 256 and propagate carry 12397 = 48*256+109 (i.e. 12397/256 == 48, 12397%256 == 109) 123 127 253 * 201 20 49 now multiply 127 by 49 (= 6223) and add carry -------------------------------- 48 109 + 6223 -------------------------------- 6271 109 adjust 6271 mod 256 and propagate carry 6271 = 24*256+127 123 127 253 * 201 20 49 -------------------------------- 24 127 109 now multiply 123 by 49 (= 6027) and add carry + 6027 -------------------------------- 6051 127 109 adjust 6051 mod 256 and propagate carry 6051 = 23*256+163 123 127 253 * 201 20 49 -------------------------------- 23 163 127 109 now multiply 253 by 20 (= 5060), + 5060 shift to the left, and add 127 -------------------------------- 23 163 5187 109 adjust 5187 mod 256 and propagate carryNote that the carry may have to be propagated through more than just one position to the left. For example, if
sum = 163 + carry > 255
then 163 is replaced with sum%256
and the remaining carry
of sum/256
is propagated further.
Multiply example debug output step-by-step:
0 0 0 0 0 0 0 0 0 0 48 109 0 0 0 24 127 109 0 0 23 163 127 109 0 0 23 183 67 109 0 0 33 163 67 109 0 9 189 163 67 109 0 10 132 72 67 109 0 110 59 72 67 109 97 1 59 72 67 109 61 01 3b 48 43 6d (hex)