[Edu-sig] tomorrow's gig (some notes)

kirby urner kirby.urner at gmail.com
Tue Mar 17 06:26:08 CET 2009

Tomorrow's talk before an engineering audience, about Python in the
back office, will feature the source code below to give the flavor of
our high school curriculum, in Matsu District (AK) or Willapa Bay (WA)
for the sake of realism.

I'll also be discussing "manga code" for a FOSS project I'm involved
with, manga code being like pseudo-code except it actually runs, so
runtime gives more information than just looking at (paper printed?)
code that doesn't actually run.  I'm thinking of "manga" as in
"storyboard" and/or "comic strip" i.e. runnable code that's somewhat a
caricature or "cave painting" vis-a-vis the "real deal" (illustrative,
demonstrative, used for show & tell purposes...).

So the deal on RSA (as many of you know) is this:  you don't have the
problem of trying to sneak a private key to the other party, already
compromising, as you probably expect her to acknowledge receipt, plus
maybe the messenger photocopied it to sell on eBay.  Public key
supersedes in having the "phone number" N paired with a secret
counterpart d saved with the same person (recipient) such that only
messages encrypted with Alice's N will decode with Alice's d, and only
Alice herself needs to have d (her computer needs to know it, might be
encrypted somehow).

d = inverse(e, phi(N)) where phi(N) = (p-1)(q-1) and N = p*q, the
famous beginning of this algorithm, requires Euclid's Extended
Algorithm (EEA).

If m is message, c is ciphertext, e is exponent, then RSA.encrypt is
like c = pow(m, e, N) and RSA.decrypt is like m = pow(c, d, N).

That's what I'm testing below.

If this were a math class with Java, a CS class or whatever, we might go:

import java.math.BigInteger;
import java.security.SecureRandom;
import java.util.Random;


public class MainClass {
  public static void main(String[] unused) {
    Random prng = new SecureRandom();  // self-seeding
    System.out.println(BigInteger.probablePrime(10, prng));


So in Jython then (just installed through Synaptic, painlessly, even
if an older version i.e. 2.5b3 is just out 6 days ago).:

Jython 2.2.1 on java1.6.0_07
Type "copyright", "credits" or "license" for more information.

>>> import java.math.BigInteger as big
>>> import java.security.SecureRandom

>>> prng = java.security.SecureRandom()

>>> big.probablePrime(1000, prng)

That could be our p, then we'd need a q.

But instead I go with a famous case of a German group cracking the
challenge number RSA-640, think the realism there adds spice to the
story, saves the module from going overboard with technicalia, like we
can get into actually generating these suckers in another lesson plan
why not.  I've had my various cryptography pages at my web site for
many years, Ian working with Whit (Sun CSO) on some others for
sociality.tv seems like.

I realize there's some irony in speaking so kindly of Python on St.
Patty's day tomorrow but of course in my family we're glad to have
Celtic lore alive and well, and besides there weren't any snakes
before that so helluva job guy!  Might make some fun skits ("did you
get rid of the tigers too then?").

Note that in 2.6 you have both kinds of print, so if you want to train
your fingers for the __future__, start using those parentheses eh?

A point here is to advertise the superiority of *any*
big-integer-capable setup over a calculator, even just one laptop with
projector and Internet would be a huge step up, let kids share
projecting, teach lightning talk format, explain how, in the major
leagues, that 5 mins is taken quite seriously.

I've also mentioned about "thunder talks" which roll out a little more
slowly (the whole show is the "a [perfect] storm" (as in "to


Why calculators aren't as fun (unless yours has a bigger than
usual screen maybe?):


RSA-640 has 193 decimal digits. A cash prize of US$20,000 was
offered by RSA Security for a successful factorization.
On November 2, 2005, F. Bahr, M. Boehm, J. Franke and T. Kleinjung
of the German Federal Office for Information Security announced
that they had factorized the number using GNFS as follows:

RSA-640 = 31074182404900437213507500358885679300373460228427275457

RSA-640 = 16347336458092538484431338838650908598417836700330923121
        × 19008712816648221131268515739354139754718967899685154936

The computation took 5 months on 80 2.2 GHz AMD Opteron CPUs.

The slightly larger RSA-200 was factored in May 2005 by the same team.


N = int("31074182404900437213507500358885679300373460228427275457" +\
         "20161948823206440518081504556346829671723286782437916272" +\
         "83803341547107310850191954852900733772482278352574238645" +\

p = int("16347336458092538484431338838650908598417836700330923121"+\

q = int("19008712816648221131268515739354139754718967899685154936"+\

totient = (p - 1) * (q - 1)

These guys only work in a namespace with N, d already defined

We're setting e = 7 to keep it simple

Euler's Totient Theorem (cutting and pasting, adapting to Python)...

This theorem is one of the important keys to the RSA algorithm:

    If GCD(T, R)== 1 and T < R, then pow (T, phi(R), R) == 1

Or, in words:

    If T and R are relatively prime, with T being the smaller
    number, then when we multiply T with itself phi(R) times
    and divide the result by R, the remainder will always be 1.

from binascii import hexlify, unhexlify

def mknum(phrase):
    return eval('0x'+hexlify(phrase)+'L')

def mkphrase(num):
    return unhexlify(hex(num)[2:-1])

def gcd(a,b):
    """Return greatest common divisor using Euclid's Algorithm."""
    while b:
        a, b = b, a % b
    return a

def lcm(a,b):
    Return lowest common multiple."""
    return (a*b)/gcd(a,b)

def bingcd(a,b):
    """Extended version of Euclid's Algorithm (binary GCD)
    Returns (m,n,gcd) such that  m*a + n*b = gcd(a,b)"""
    g,u,v = [b,a],[1,0],[0,1]
    while g[1]<>0:
        y = g[0]/g[1]
        g[0],g[1] = g[1],g[0]%g[1]
        u[0],u[1] = u[1],u[0] - y*u[1]
        v[0],v[1] = v[1],v[0] - y*v[1]
    m = v[0]%b
    gcd = (m*a)%b
    n = (gcd - m*a)/b
    return (m,n,gcd)

def inverse(a,b):
    """If gcd(a,b)=1, then inverse(a,b)*a mod b = 1,
    otherwise, if gcd(a,b)!=1, return 0

    Useful in RSA encryption, for finding d such that
    e*d mod totient(n) = 1"""
    inva,n,gcd = bingcd(a,b)
    return (gcd==1)*inva

class Sender:

    def __init__(self, m):
        self.m = mknum(m)

    def encrypt(self):
        """RSA algorithm"""
        c = pow(self.m, 7, N)
        return c

class Receiver:

    def __init__(self, c):
        self.c = c

    def decrypt(self):
        """RSA algorithm"""
        d = inverse(7, totient)
        m = pow(self.c, d, N)
        return mkphrase(m)

def testing123():
    print(N == p*q)
    d = inverse(7, totient)
    print(7*d % totient)

def testingrsa():
    bob = Sender("Able was I ere I saw Elba")
    c = bob.encrypt()
    alice = Receiver(c)
    m = alice.decrypt()

if __name__ == "__main__":
    # testing123()

More information about the Edu-sig mailing list