Cryptography — CS6035

This is my experience with cryptography at Georgia Tech in my honestly least favorite class but turned most engaging and challenge course. Sorry I wrote this after I finish the assignment. To save you time, there are only some notes and hints and no answers. This is purely to remind myself.

I will only write about the public information and won’t give away any answer since it’s again school policy. You would have to work for this course.

Tools:

VSCode

Python knowledge and documentation

Understanding of RSA, AES and Cryptography

RSA Cryptography — Prerequisites

1. Basic command execution in Linux.

• Familiarity with running python scripts via command line interface.

1. Familiarity with python programming environments.

• Functions and the self keyword, parameters.
• Basic operators and loops in Python.
• Use of cryptography and hashing primitives.
• Ability to understand pseudocode and implement algorithms.

1. Familiarity with modular arithmetic and discrete math.

• Working knowledge of discrete math.
• Ability to look at pseudocode and implement Python code.
• Understand the difference between inverse and mod inverse.

1. Familiar with cryptographic and hashing functions.
2. Familiarity with unit testing scripts.
3. Working knowledge of how Python unit tests are made and possibly how to make your own.

Task 1 — Vigenere Ciphers (35 points)

def vigenere_decrypt_cipher(c: str, keyword: str) -> str:
    # TODO: Write the necessary code to get the message (m) from the cipher ©
    # using the keyword
    m = ''

This will explain vigenere well
    ## https://en.wikipedia.org/wiki/Vigen%C3%A8re_cipher
1. remember figure 1

    return m

def vigenere_encrypt_message(m: str, keyword: str) -> str:
    # TODO: Write the necessary code to create a Vigenere cipher (c) of the
    # message (m) using the provided keyword
    c = ''

1. refer to figure 1
    return c

def vigenere_dictionary_attack(c: str) -> str:
    # TODO: Write the necessary code to get the message (m) from the cipher (c)
    m = ''


    return m

figure 1

Task 2 — RSA Warmup (10 points)

Now that we’ve reviewed a symmetric key cryptographic algorithm, we can move on to the world of asymmetric key cryptography. RSA is perhaps the best known example of asymmetric cryptography. In RSA, the public key is a pair of integers (N, e), and the private key is an integer d.

Get cloudneuf’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

To encrypt integer m with public key (N, e), we use the formula:

To decrypt cipher integer c with private key d, we use the formula

In this task you will write the code to perform the encryption and decryption steps for the RSA cryptographic algorithm. Finally, you will write the code necessary to calculate the private key d when given the factors of the public key N (i.e. p and q).

def rsa_decrypt_cipher(n: int, d: int, c: int) -> int:
    # TODO: Write the necessary code to get the message (m) from the cipher (c)
    m = 0
    return m

def rsa_encrypt_message(m: int, e: int, n: int) -> int:
    # TODO: Write the necessary code to get the cipher (c) from the message (m)
    c = 0
    return c
def rsa_calculate_private_key(e: int, p: int, q: int) -> int:
    # TODO: Write the necessary code to get the private key d from
    # the public exponent e and the factors p and q
    d = 0
    return d

Task 3 — RSA Factor A 64-Bit Key (10 points)

Modern day RSA keys are sufficiently large that it is impossible for attackers to traverse the entire key space with limited resources. But in this task, you’re given a unique set of RSA public keys with a relatively small key size (64 bits).

Your goal is to get the factors (p and q) of each key. You can use whatever methodology you want. Your only deliverable is a formatted json file containing p and q. To get your unique set of keys, you must update the task.py file located in the task folder with your 9-digit GT ID, and then run it. Find the section below in the provided task_factor_64_bit_key.py file:

Task 4 — RSA Weak Key Attack (15 Points)

Read the paper “Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices”, which can be found at: https://factorable.net/weakkeys12.extended.pdf. The essay is essential to understanding this task. Do not skip it, do not skim it, read the whole of it.

You are given a unique RSA public key, but the RNG (random number generator) used in the key generation suffers from a vulnerability described in the paper above. In addition, you are given a list of public keys that were generated by the same RNG on the same system. Your goal is to write the code to get the unique private key (d) from your given public key (N, e) using only this provided information.

def rsa_weak_key_attack(given_public_key_N: int, given_public_key_e: int, public_key_list: typing.List[int]) -> int:
    # TODO: Write the necessary code to retrieve the private key d from the given public
    # key (N, e) using only the list of public keys generated using the same flawed RNG
    d = 0
    return d

Note: this assignment # https://www.geeksforgeeks.org/python-math-gcd-function/ helped

Task 5 — RSA Broadcast Attack (15 Points)

A message was encrypted with three different 1,024-bit RSA public keys N_1, N_2, and N_3, resulting in three different ciphers c_1, c_2, and c_3. All of them have the same public exponent e = 3.

You are given the three pairs of public keys and associated ciphers. Your job is to write the code to recover the original message.

def rsa_broadcast_attack(N_1: int, c_1: int, N_2: int, c_2: int, N_3: int, c_3: int) -> int:
    # TODO: Write the necessary code to retrieve the decrypted message
    # (m) using three different ciphers (c_1, c_2, and c_3) created 
    # using three different public key N's (N_1, N_2, and N_3)

    m = 0
    return m

Note: # https://gist.github.com/jl4730/47c6c88bef60ac35b9da961dc424fe82

Task 6 — RSA Parity Oracle Attack (15 Points)

By now you have seen that RSA treats messages and ciphers as ordinary integers. This means that you can perform arbitrary math with them. And in certain situations a resourceful hacker can use this to his or her advantage. This task demonstrates one of those situations.

Along with an encrypted message ©, you are given a special function that you can call — a parity oracle. This function will accept any integer value that you send to it and decrypt it with the private key corresponding to the public key that was used to encrypt the given cipher ©. The return value of the function will indicate whether this decrypted value is even (true) or odd (false). Armed with this function and a little modular arithmetic, it is possible to crack the encrypted message. Your goal is to write the code necessary to decrypt the original message (m) from the given cipher ©.

def rsa_parity_oracle_attack(c: int, N: int, e: int, oracle: Callable[[int], bool]) -> str:
    # TODO: Write the necessary code to get the plaintext message
    # from the cipher (c) using the public key (N, e) and an oracle 
    # function - oracle(chosen_c) that will give you the parity 
    # of the decrypted value of a chosen cipher
    #(chosen_c) value using the hidden private key (d)

    m = 42
    # Transform the integer value of the message into a human readable form
    message = bytes.fromhex(hex(int(m_int)).rstrip('L')[2:]).decode('utf-8')
    return message

Note: this took me a while to fully understand what it’s talking about. means the the chosen_c is odd or even. the idea is to find the odd or even with the information leak from secrets.