RSA Encryption | 05 | Crack Encryption

Like any encryption method, cracking RSA encryption is just a matter of time. However, with sufficiently large numbers it will take more time than is practical for any would-be data thief. With current technology, it would take approximately 1,000 years to crack the largest of keys. Of course, as technology advances this number will be reduced and even larger numbers will be required to maintain security confidence.

Import Libraries

import obj
import mmi
from time import clock
from math import sqrt

Intercept encrypted message

Intercepting an encrypted message is not trivial, but very possible given the prevalence of widespread software bugs and exploits found every year.

And, as is a trait of RSA encryption, the public key and exponent value are readily available to anyone.

# Intercept encrypted message
message_encrypted = obj.load('data/message_encrypted')

keys = obj.load('data/keys')

#Publicly known values
exponent   = keys['exponent']
key_public = keys['key_public']

#Private values are unknown
key_private = 'Unknown'

Create factoring function

Cracking RSA encryption is as simple as factoring the public key. However, although it is simple, it is not a fast process. Large enough values are impossible to crack in any useful amount of time, taking hundreds if not thousands of years.

Fortunately, our numbers are much smaller and should not take nearly as long!

# If number has non-prime factors, this function will find them, too. 
# However, it is slightly optimized assuming a single set of prime factors.
def findPrimeFactors(num):
    
    if int(num)!=num or num<=0:
        return 'ERROR: Number must be positive integer.'
    elif num<6:
        return 'ERROR: Number does not have two prime factors.'
    elif num%2==0:
        factorA = 2
        factorB = int(num/2)
        return {
            'A' : factorA,
            'B' : factorB
        }
    
    for fac in range(3, int(sqrt(num))+1, 2):
        if num % fac == 0:
            factorA = fac
            factorB = int(num/fac)
            return {
                'A' : factorA,
                'B' : factorB
            }
        
    return 'ERROR: Number does not have two prime factors.' 

Crack public key

begin = clock()
primes = findPrimeFactors(key_public)

print('Public key cracked in {:.6} seconds.'.format(clock()-begin))
print('\n')
print('The prime factors are:')
print(primes)

Public key cracked in 0.000193 seconds.


The prime factors are:
{'B': 541, 'A': 523}

Calculate private key

# Calculate phi
phi = (primes['A'] - 1) * (primes['B'] - 1)

# Generate private key
key_private = mmi.modinv(exponent, phi)

Decrypt stolen message

def decrypt(message_encrypted, key_private, key_public):
    
    # Decrypt message
    message_ascii = []
    for i in message_encrypted:
        message_ascii.append((i**key_private) % key_public)
    
    # Convert message to string
    message = []
    for i in message_ascii:
        message.append(chr(i))
    
    # Return decrypted message
    return ('').join(message)

# Decrypt message using cracked key
message_stolen = decrypt(message_encrypted, key_private, key_public)

# Compare cracked and original messages
print('Stolen message (top) vs original message (bottom):')
print('\n')
print(message_stolen)

message = obj.load('data/message')
print(message)

Stolen message (top) vs original message (bottom):


Don't tell my secrets to anyone, please!
Don't tell my secrets to anyone, please!