BigRSA

Review Show

Goal: Implement the Rivest–Shamir–Adleman public-key cryptosystem

• This is cumulative homework assignment across 4096_t and RSAinC
• Implement 4096 bit RSA.
• This is an extended homework of more than week, due after break. I recommend:

Week:	Tasks:
10 Mar	2048 bit prime generation
17 Mar	Unsigned big extended GCD
24 Mar	Finish Key Generation and File I/O
31 Mar	Implement BigRSA

• You will also probably need to manage a file structure wherein 4096_t and ops_ui are includeded into your BigRSA.
• Use header files and examples from the labs.

Primes Show

Work on week of 10 Mar

Implement Big Primality Testing

• Use, perhaps, \(6k+1\) or some other algorithms.

Implement randomization via /dev/random

• /dev/random and the more prefered but less established /dev/urandom are file-like random number generations that could plausibly be cryptographically secure on your system.
• We will not be able to implement cryptographically secure RSA, but we should follow the random number generation convention.
• Basically, we read from /dev/random as we would any other file, here is an example of reading and printing 4096 “random” bits.

BigRNG.c

#include "4096_t.h"

int main() {
        uint64_t bignum[64];
        FILE *fp = fopen("/dev/random", "r");
        fread(bignum, sizeof(uint64_t), S, fp);
        fclose(fp);
        seebig(bignum);
        return 0;
}

• You will need to use randomization to select your primes.

Implement Big Prime Generation

• Use:
  • Your primality tester
  • Your randomizer
• Generate prime numbers of about 2048 bits in size.
  • Multiply them together to get an \(n\) of about 4096 bits in size.

BigGCD Show

Work on week of 17 Mar

Implement BigGCD

• Modifying the extended Euclidean algorithm / extended gcd for use with the 4096_t ints.
• I had to do the following:
  • Change all arithmetic operations from using infix operators like \(+\) or \(/\).
  • Modifying the Euclidean algorithm to use only positive values.
  • Test extensively.
• You can also implement 4096_t to accomodate negative values (which I did not due).
  • I instead created different local values with my EEA function that tracked whether everything was positive or negative.
  • Then wrote wrapper functions around the “big” operations that tracked the sign values.

BigKey Show

Work on week of 24 Mar

Generate Keys

• Write a 4096 bit .bad and .pub file.
• Implement in a .c file called “bigkey.c”
  • It should behave identically to “keygen.c”, but generate 4096 bit keys.
  • The 4096 bit refers to how large the \(n\) value should be
  • E.g. the \(e\) value may still be (decimal) 65537
• The KeyGen description from “RSAinC” in provided below, as reference:

A Private Key in 3 Parts

• We recall that the private key minimally contains:
  • n, a modular base
  • e, an encryptor, and
  • d, a descryptor.
• Based on the KeyGen lab, it should be uncomplicated to calculate these values for 64 bit keys.
• We will use .bad instead of .pem and insecurely store these values in plaintext.
• We will then make executables to generate .bad and encrypt content provided a .bad
  • We name a .bad so helpfully we don’t use it by accident.
• We will naively print 3 lines of hexademical values, n, e, then d.
• We will write them to a 5-line file as follows:
  • The first line is the precise header text.
  • The second line is the n value in hexadecimal.
  • The third line is the e value, which is 10001.
  • The fourth line is the d value, which should be kept secret.
  • The fifth and final line is the precise footer text.

unsafe.bad

-----BEGIN UNSAFE PRIVATE KEY-----
95a61f99198bd8e9
10001
fbea5e6a3ed31e8f
-----END UNSAFE PRIVATE KEY-----

A Public Key in 2 Parts

• We recall that the public key contains, and should only contain:
  • n, a modular base, and
  • e, an encryptor
• Based on the KeyGen lab, we already have the ability to write these values to file.
• We will use .pub instead of .pem or .bad
  • Not a huge deal how these are stored, actually.
  • The key itself though, is still unsafe to use.
• We will naively print 2 lines of hexademical values, n, then e.
• We will right them to a file prefixed and suffixed as follows:

unsafe.pub

-----BEGIN UNSAFE PUBLIC KEY-----
95a61f99198bd8e9
10001
-----END UNSAFE PUBLIC KEY-----

BigRSA Show

Work on week of 31 Mar

Implement End-to-end 4096 bit RSA

• Do so in a novel file, bigrsa.c, which should:
  • Accept 3 command line arguments:
    • A flag -d or -e for decrypt or encrypt
    • The file name of an input file.
    • The file name of an output file.
  • It should:
    • Read the content of the input file.
    • Encrypt or decrypt, as specified, the file contents.
      • It should read n and d from “unsafe.bad” to decrypt.
      • It should read n and e from “unsafe.pub” to encrypt.
    • Write the encrypted or decrypted content to the output file.
• Your BigRSA should function over either “keygen.c” 32 bit keys or “bigkey.c” 4096 bit keys.

Tester Show

Under construction

Owning my failures.

• With my apologies, this is the first homework for which I was unable to complete a reference solution of which I am proud prior to releasing the assignment.
• As the testers are developed as I do the assignment, that means this assignment releases with no provided tester.
• In the interim, the “RSAinC” tests all features of “BigRSA” except ensuring that much larger chunks of information (than single characters) may be amicably encrypted.
• Adapting the RSAinC tester to work on the “15chars.txt” and “lipsum.txt” inputs to SHA256 will be sufficient, and I hope to have a grader soon.

Recognition of Student Achievement

• If you believe you have a statisfying RSA implement prior to the official release of a tester, any errors I find within the tester will be considered my errors, not yours.
• An astute student may be able to develop a high quality tester before me, and will be showered in various praises and accolades in accordance with this achievement.