Lab 3 – RSA Encryption & Key Cracking

#I wrote my code to be very verbose and to state every new data point. Helps me keep track of everything. Struggled on lab 2 because I had a lot of data flying around without always seeing what they all were and what I was doing with it.  

#!/usr/bin/python3
from prime import *
import math, sympy

def main():
    print("")

    #given
    C = 1315578006529763640141359009929019255795
    public_key = (3039956819131923800469303260782717053853, 65537)
    n, e = public_key

    print("public key:\t\t", n, ",", e)
    print("ciphertext:\t\t", C)
    print("")

    #factor n into p and q
    prime = sympy.primefactors(n)
    p, q = prime[0], prime[1]
    print("p:\t\t\t", p)
    print("q: \t\t\t", q)
    print("")

    #find lambda(n)
    lm = math.lcm(p - 1, q - 1)

    #find d
    d = modinv(e, lm)
    print("lambda(n):\t\t", lm)
    print("d:\t\t\t", d)
    print("")

    #decrypt
    M = dcipher(C,d,n)
    print("decrypted int:\t\t", M)

    #int to bytes
    try:
        msg = M.to_bytes((M.bit_length() + 7) // 8)
    except OverflowError:
        msg = b"(decryption failed)"
    print("decrypted message: \t", msg)
    print("")


def egcd(a, b):
    x, y, u, v = 0, 1, 1, 0
    while a != 0:
        q, r = b // a, b % a
        m, n = x - u * q, y - v * q
        b, a, x, y, u, v = a, r, u, v, m, n
    return b, x, y

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        return None
    else:
        return x % m

def cipher(m,e,n):
    i = int.from_bytes(m)
    return pow(i,e,n)

def dcipher(c,d,n):
    return pow(c,d,n)


if __name__ == "__main__":
    main()

#!/usr/bin/python3
from prime import *
import math, sympy, time, statistics, matplotlib.pyplot as plt

def main():
    print("")
    print("RSA key cracking")
    print("")

    #increment by 10, but when I hit 114, it took like 1/2 hour and nothing happened, so I decided to rewrite it to be more managable. 
    bit_sizes = [64, 74, 84, 94, 104]
    avg_times = []

    #4 tests which is 3-5
    tests = 4
    for bits in bit_sizes:
        print(f"Testing {bits}-bit primes")
        times = []

        for i in range(tests):
            start = time.time()

            p = gen_prime(bits)
            q = gen_prime(bits)
            while q == p:
                q = gen_prime(bits)
            n = p * q

            sympy.primefactors(n)

            end = time.time()
            elapsed = end - start
            times.append(elapsed)
            print(f"   Test {i+1}: {elapsed:.4f} seconds")

        avg = statistics.mean(times)
        avg_times.append(avg)
        print(f"Average for {bits}-bit")
        print(f"Time: {avg:.4f} seconds")
        print("")

    #plot
    plot_points(bit_sizes, avg_times)

    print("")
    print("Experiment complete.")
    print("Plot saved as: rsa_crack_times.png")
    print("")


def plot_points(bit_sizes, avg_times):
    plt.figure(figsize=(8, 5))
    plt.plot(bit_sizes, avg_times, marker='o', linestyle='-', linewidth=2)
    plt.title("RSA Key Cracking Time VS. Bit Size")
    plt.xlabel("bits per prime (key size component)")
    plt.ylabel("avg. time to crack (sec.)")
    plt.grid(True)
    plt.tight_layout()
    plt.savefig("rsa_crack_times.png")
    plt.show()


def egcd(a, b):
    x, y, u, v = 0, 1, 1, 0
    while a != 0:
        q, r = b // a, b % a
        m, n = x - u * q, y - v * q
        b, a, x, y, u, v = a, r, u, v, m, n
    return b, x, y


def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        return None
    else:
        return x % m


if __name__ == "__main__":
    main()

#!/usr/bin/python3
# Retrieved from: http://en.literateprograms.org/Miller-Rabin_primality_test_(Python)?oldid=17104

import random, sys

def miller_rabin_pass(a, s, d, n):
    a_to_power = pow(a, d, n)
    if a_to_power == 1:
        return True
    for i in range(s-1):
        if a_to_power == n - 1:
            return True
        a_to_power = (a_to_power * a_to_power) % n
    return a_to_power == n - 1


def miller_rabin(n):
    d = n - 1
    s = 0
    while d % 2 == 0:
        d >>= 1
        s += 1
    for repeat in range(20):
        a = 0
        while a == 0:
            a = random.randrange(n)
        if not miller_rabin_pass(a, s, d, n):
            return False
    return True

def test_num(num):
    n = int(num)
    return (miller_rabin(n) and "PRIME" or "COMPOSITE")

def gen_prime(nbits):
        while True:
            p = random.getrandbits(nbits)
            p |= 2**nbits | 1
            if miller_rabin(p):
                return p

def main():
    if sys.argv[1] == "test":
        print(test_num(sys.argv[2]))
    elif sys.argv[1] == "genprime":
        print(gen_prime(int(sys.argv[2])))

if __name__ == "__main__":
    main()