Question

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 task.py:
import hashlib
import json
import typing
##############################################
# Change this to your 9-digit ID!
STUDENT_ID = '123456789'
##############################################
def print_tests_for_student_id() -> None:
f = open('student_tests.json')
student_tests = json.load(f)
student_id_hash = hashlib.sha256(STUDENT_ID.encode()).hexdigest()
try:
tests = student_tests[student_id_hash]
print('The tests for ID {} are:'.format(STUDENT_ID))
print('========================================================')
for test_id, test in tests.items():
print('{} -> {}'.format(test_id, test))
print('========================================================')
except KeyError:
print('ERROR: ID {} was not found in student_tests.'.format(STUDENT_ID))
# This function is only provided for your convenience.
# You are not required to use it.
def rsa_factor_64_bit_key(N: int, e: int) -> typing.Tuple[int, int]:
p = 0
q = 0
# TODO: Write the necessary code to get the factors p and q of the public key (N, e)
return p, q
if __name__ == '__main__':
print_tests_for_student_id()

Answer 1

To find the factors (p and q) of a given RSA public key with a key size of 64 bits, you can use Fermat's factorization method.

Step-by-step explanation:

To find the factors (p and q) of a given RSA public key with a key size of 64 bits, you can use a methodology called Fermat's factorization method. This method takes advantage of the fact that RSA public keys are usually composite numbers formed by multiplying two prime numbers together.

The steps to find the factors are as follows:

1. Compute the square root of the public key N and round it up to the nearest integer.
2. Starting from this rounded square root, check if there exists an integer value X such that X^2 - N is a perfect square.
3. If such an X is found, the factors are p = X - sqrt(X^2 - N) and q = X + sqrt(X^2 - N).
4. Repeat these steps for each RSA public key to obtain the factors p and q.