Playing with simple encryption math in Python

Probably every real programmer absorbed this decades ago in CS101. I learned it from an episode of NOVA I watched with my son last night, “The Rise of the Hackers“: The basis for most public/private key encryption, which we use for practically all internet data privacy these days, is a simple mathematical fact discovered (I think) by the RSA mathematicians:

It’s really, really hard to find the factors of a semi-prime, the product of two prime numbers. That is, it’s easy to multiply two primes together but hard to reverse engineer, such as you need to do when you hack encryption keys. Computers can start trying to compute the factors of a large semi-prime, but it will take them a long time—”thousands of computers millions of years” for the types of semi-primes we’re talking about. Factorable factors like 20000 x 350400, easy. Primes as factors, like 547 x 953, computationally too intensive for hackers, even with the latest hardware. So the semi-prime becomes the public key and its factors the private keys.

This fact seemed so irresistible and elegant to me (a teachable moment for my son! Something I could dust the old Python off for) that I got my laptop out and, as we watched the segment on quantum cryptography, created a little test program:

import time
def factor(sp):
    start = time.time()
    for p1 in range(1,sp):
        for p2 in range(1, sp):
            if p1 * p2 == sp:
                print "factors:", p1, p2
    print "time:", time.time() - start, '\n'

factor(15)
factor(15*71)
factor(229*101)
factor(307*89)
# factor(487*691)
# factor(997*991)
factor(900*200)

So the factor function uses nested loops to compute the factors of a given number, and it uses the time module to figure out how long each computation takes from start to finish. There are better ways to do this function, like with reduce code or using set to remove x/y y/x dupes, but it works and it’s legible. The bottom part tests the function by supplying semi-primes (via multiplication, so factor(229*101) is equivalent to factor(23129) because of the rules of precedence) and other numbers, and prints the resulting times.

Check it out! (I put the results below.) When you start getting into the semi-primes, it can thousands of times longer to factor, and these are low numbers. I commented out the 487*691 and 997*991 tests because they wouldn’t complete after like 10 minutes!

It’s so great to see mathematical principles applied in this way, to see the simple origins of complex systems like cryptography, and to noodle with code to get how things are working.

"""
factors: 3 5
factors: 5 3
time: 0.0390000343323 

factors: 3 355
factors: 5 213
factors: 15 71
factors: 71 15
factors: 213 5
factors: 355 3
time: 0.213999986649 

factors: 101 229
factors: 229 101
time: 65.7490000725 

factors: 89 307
factors: 307 89
time: 81.3059999943 

factors: 2 90000
factors: 3 60000
factors: 4 45000
factors: 5 36000
factors: 6 30000
factors: 8 22500
factors: 9 20000
factors: 10 18000
factors: 12 15000
factors: 15
etc etc
"""