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

[kirby urner]

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)
986024402532744041493470893465725154540167461230347296361
094920931610743969216973764051955623260076378742309845854
297301750831176718526148689979016653882056041932096046944
963620102533089175317598139585190865815470057233752762341
448040708612248660611811336839535064227491583786355872281
6236632070326659

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
brainstorm")).

Kirby

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

RSA-640

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:
[19][20][21]

RSA-640 = 31074182404900437213507500358885679300373460228427275457
          20161948823206440518081504556346829671723286782437916272
          83803341547107310850191954852900733772482278352574238645
          4014691736602477652346609

RSA-640 = 16347336458092538484431338838650908598417836700330923121
          81110852389333100104508151212118167511579
        × 19008712816648221131268515739354139754718967899685154936
          66638539088027103802104498957191261465571

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.

See:
http://en.wikipedia.org/wiki/RSA-640#RSA-640
"""

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

p = int("16347336458092538484431338838650908598417836700330923121"+\
        "81110852389333100104508151212118167511579")

q = int("19008712816648221131268515739354139754718967899685154936"+\
        "66638539088027103802104498957191261465571")

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(p)
    print(q)
    print(p*q)
    print(N)
    print(N == p*q)
    d = inverse(7, totient)
    print(d)
    print(7*d % totient)

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

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