RSAinC

HW 0x6: Due Th, Mar 06

Review 

Goal: Public Key Encryption

Review: Newish:
- RSA - modexp
- FileIO
  • In the lab you should’ve finished key generation.
    • Otherwise, return to a complete the lab.
    • KeyGen
  • This assignment concerns two distinct executable files:
    • Write keys to files
      • keygen.c
      • Covered in the lab section.
    • Encrpyt and decrypt based those keys.
      • rsainc.c
      • Covered here, but requiring keygen.c

KeyGen 

  • This section summarizes the lab. If you completed the lab, you may move onto “ModExp”
  • Recall a sample Python implementation was provided, but was not very readable.

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

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
  • Ensure your keys are 32 bit.
    • Simply encrypt values up to 1 << 31 in size.
  • Here is a testing script:
def modexp(m, e, n):
    if e == 0:
        return 1
    if e == 1:
        return m % n
    if e % 2:
        return (m * modexp(m*m % n, e//2, n)) % n
    return  modexp(m*m % n, e//2, n) % n

make_encrypt = lambda e, n : lambda m : modexp(m,e,n)

lines = open("unsafe.bad").readlines()
n = int(lines[1], 16) 
e = int(lines[2], 16) 
d = int(lines[3], 16) 

lines = open("unsafe.pub").readlines()
if n != int(lines[1], 16) or e != int(lines[2], 16):
    print("Public key does not match private key.")
    exit()

encrypt = make_encrypt(e,n)
decrypt = make_encrypt(d,n)

if all([i == decrypt(encrypt(i)) for i in range(0x100)]):
    print("Keys work for small values.")
else:
    print("Keys failed on small values.")

if all([i == decrypt(encrypt(i)) for i in range(0,1 << 31, 1 << 29)]):
    print("Keys work for larger values.")
else:
    print("Keys failed on larger values.")

By successfully encrypting and decrypting up to 1 << 31, the key is large enough for some small tasks, such encrypting the string “hi” - a string of length 3 when including the null terminator, which therefore contains 24 bits of information.

ModExp 

  • For C language encryption and decryption, it is necessary to implement “modexp” in C.
  • Do so in a novel file, rsainc.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.
  • Here is a Python implementation.
    • It is exceptionally annoying because Python doesn’t like to treat files as holding data rather than text.
rsa_py.py
if __name__ != "__main__":
    exit()

import sys

def modexp(m, e, n):
    if e == 0:
        return 1
    if e == 1:
        return m % n
    if e % 2:
        return (m * modexp(m*m % n, e//2, n)) % n
    return  modexp(m*m % n, e//2, n) % n

if 'e' in sys.argv[1]:
    lines = open("unsafe.pub").readlines()
    n, e = int(lines[1], 16), int(lines[2], 16) 
elif 'd' in sys.argv[1]:
    lines = open("unsafe.bad").readlines()
    n, e = int(lines[1], 16), int(lines[3], 16) # have to call it e, not d
else:
    exit()
s = open(sys.argv[2], "rb").read()
m = int.from_bytes(s, byteorder=sys.byteorder, signed=False)
c = modexp(m,e,n)
s = open(sys.argv[3], "wb").write(c.to_bytes(4, byteorder=sys.byteorder))

Hint

  • You will probably want to use something like this:
fscanf(key, "-----BEGIN UNSAFE PRIVATE KEY-----\n%lx\n%lx\n-----END UNSAFE PRIVATE KEY-----\n", &n, &e);

Tester 

  • I am providing the following Containerfile, which will serve as a minimal autograder.
  • Use the tester with caution outside of containers as it deletes files you may want to preserve
Containerfile

Usage

  • I built my container via:
  • I tested my code via:
  • If the above script returns the following you are done:
    • Upload your code to your GitHub on which I am a collaborator.
  • I will review the most recent version prior to the due date.

Sketch

  • We note the tester performs no error handling, for which you as the student are responsible.
  • This assignment was essentially as follows:
    • Create a keygen.c that compiles into a keygen executable with is functionally identical to python3 keygen.py
      • Key generation should create an unsafe.bad private key and an unsafe.pub public key.
    • Create a rsainc.c that compiles into a rsainc executable with is functionally identical to python3 rsa_py.py
      • Encryption and decryption will use a created unsafe.bad private key and an unsafe.pub public key.

Tester

  • The tester:
    • Ensures the local directory contains no prior message, key, or executable files.
    • Uses curl to fetch the latest keygen.py and rsa_py.py from the instructional GitHub
    • Compiles keygen.c and rsainc.c will all flags:
    • Creates a short message file containing at most two characters.
    • Tests RSA for all permutations of C and Python for each stage:
      • Generates keys
      • Encrypts the message, and
      • Decrypts the message, then
      • Prints the output.