Re: [Edu-sig] Cryptonomicon

I think this is an excellent idea. Crypto is hard to learn because (a) proving that it's hard to crack requires complex formal mathematical constructions, and (b) any real crypto uses numbers too big to write down, let alone think about.
Re big numbers: I think it really open things up for kids that we have big integers easily available now. Even though we're doing all the same ops, there's a psychological bridge that gets crossed when the numbers start taking a couple paragraphs or even pages to write down. For one thing, you really start to appreciate that we have computing machinery, and that opens up the space for a discussion of how that came to be (another thread in Cryptonomicon -- because of course Turing was involved in the war effort to break German and Japanese codes, and it was this push which led to the faster evolution of digital computing). Java also has a BigNumber class, and an op for spitting out large numbers with a percentage change that said numbers are prime (you approach a probability of 1 depending on how computationally intensive you want to get -- I haven't studied the source for this, am curious what algorithms are used (would like to see them re-expressed in Python, just for reference)). Probably the Java methods are inherited from some well-known C library and the code is in some numerical recipes book I haven't studied yet.
A clear implementation of various crypto algorithms in Python would be a great thing to have around. If we can take its bit-length down to, oh, 9, then the numbers are numbers high-schoolers can crunch in a class period with a calculator, but the computer can take care of a lot of the calculations automatically.
Plus just consider those really simple substitution codes where you make A = J, B = Z -- whatever random assignment. Also, you want to parse your messages into 5 letter chunks: ALSOY OUWAN TOPAR SEYOU RMESSA GESIN TO5LE TTERC HUNKS. You find this simple "club house" codes in books for little kids, with titles like 'I, Spy' and stuff. Of course this is nothing sophisticated, but it's a great opportunity to use Python string ops to: make the 5 letter uppercase chunks out of whatever plaintext input (could be interactive and first, then convert to file i/o); use the dictionary data structure to do the lookup/substition.
There are some *excellent* opportunities for assignments in there, too. And they're virtually impossible to cheat on :)
Dustin
The basic strategy here is to make Python a fun "toy" (in the sense that kids will want to pick it up and play with it spontaneously, not because some teacher is standing over them with a whip). The way to do this is just provide enough interactive experience to suggest a vocabulary of "tinker toys" (components), which kids while then use in synergetic ways to assemble whatever. What we want to avoid is the intimidating sense that you're not allowed to start small. Too many educational experiences include some older kids (e.g. teachers) suggesting that your work is nothing special, not interesting, because you don't know "all" of what's to know about. Crypto is a case in point. Regarding crypto, there are lots of segues to random numbers (the Standard Library book re Python keeps warning us that the randoms are "pseudo" and hence potentially an Achilles heal if you're using them as a basis for some encryption algorithm). This whole concept of random numbers generated by machines is especially rich, philosophically. We have to be clear what we mean by "random" -- what are the tests such numbers must pass? Knuth has done a lot of work in this area, and computer science has gotten a big boost from this thread -- which thinking we can recapitulate in curriculum writing geared for those relatively new to the subject. I get into random numbers some in my "Random walks through the matrix" piece, wherein a turtle swallows an n-sided die and then hops in a spatial lattice defined by n degrees of freedom at each turn to play (the so-called isotropic vector matrix features 12 spokes from every hub, to the surrounding closest packed spheres at the corners of a cuboctahedron). Kirby

Earlier I wrote:
Plus just consider those really simple substitution codes where you make A = J, B = Z -- whatever random assignment. Also, you want to parse your messages into 5 letter chunks: ALSOY OUWAN TOPAR SEYOU RMESSA GESIN TO5LE TTERC HUNKS. You find this simple "club house" codes in books for little kids, with titles like 'I, Spy' and stuff. Of course this is nothing sophisticated, but it's a great opportunity to use Python string ops to: make the 5 letter uppercase chunks out of whatever plaintext input (could be interactive and first, then convert to file i/o); use the dictionary data structure to do the lookup/substition.
I've played around with the above, so far minus the 5-letter chunking, to develop a simple "clubhouse" substitution scheme in Python. Here's the kind of file it produces: RUFWVEUWB PLS VBJBL QBPWV PAU UFW RPTGBWV HWUFAGT RUWTG UL TGNV EULTNLBLT P LBY LPTNUL, EULEBNJBS NL CNHBWTQ PLS SBSNEPTBS TU TGB OWUOUVNTNUL TGPT PCC MBL PWB EWBPTBS BIFPC. LUY YB PWB BLAPABS NL P AWBPT ENJNC YPW, TBVTNLA YGBTGBW TGPT LPTNUL UW PLQ LPTNUL VU EULEBNJBS PLS VU SBSNEPTBS EPL CULA BLSFWB. YB PWB MBT UL P AWBPT HPTTCBRNBCS UR TGPT YPW. YB GPJB EUMB TU SBSNEPTB P OUWTNUL UR TGPT RNBCS PV P RNLPC WBVTNLA-OCPEB RUW TGUVB YGU GBWB APJB TGBNW CNJBV TGPT TGPT LPTNUL MNAGT CNJB. NT NV PCTUABTGBW RNTTNLA PLS OWUOBW TGPT YB VGUFCS SU TGNV. HFT NL P CPWABW VBLVB, YB EPLLUT SBSNEPTB, YB EPLLUT EULVBEWPTB, YB EPLLUT GPCCUY TGNV AWUFLS. TGB HWPJB MBL, CNJNLA PLS SBPS YGU VTWFAACBS GBWB GPJB EULVBEWPTBS NT RPW PHUJB UFW OUUW OUYBW TU PSS UW SBTWPET. TGB YUWCS YNCC CNTTCB LUTB LUW CULA WBMBMHBW YGPT YB VPQ GBWB, HFT NT EPL LBJBW RUWABT YGPT TGBQ SNS GBWB. ... along with the all-important key file, saved separately: D=Z Z=X Q=Y J=V ... and so on -- all 26 letters have their random substitutes. When you bring the key file and encrypted text back together, the original text (except capitalized). Notice: this primitive scheme keeps punctuation and whitespace as is, simply substitutes for the 26 uppercase alpha letters. But it's still a useful exercise for learning various aspects of Python, as well as starting to think like a cryptographer. For example, coming up with a substitution key is automatic and involves pseudo-randomly choosing from a grab-bag of alpha characters, removing the chosen letter, and choosing again, until all 26 have been chosen at pseudo-random. You then build a dictionary with this, i.e. pair 'A' with the first letter chose, 'B' with the next, and so on. There's no rule which says you can't pair a letter with itself -- could happen. Here's some code: import string, random def permute(): """ Randomly permute the uppercase alphabet by choosing its letters pseudo-randomly """ alphalist = list(string.uppercase) newlist = [] for i in range(len(alphalist)): randchar = random.choice(alphalist) alphalist.remove(randchar) newlist.append(randchar) return newlist def mkdict(): """ Pair uppercase alphabet with randomly permuted version of same """ tuples = zip(string.uppercase,permute()) codedict = {} for pair in tuples: codedict[pair[0]]=pair[1] return codedict The rest of clubhouse.py is about file i/o. You feed it filename.txt and get back filename.cpt and filename.key, the encrypted text and deciphering key. Then you reverse the process, getting filename.dcp (decrypted) back out. Looks like this in IDLE:
clubhouse.encrypt(r"./ocn/sample.txt") Writing to ./ocn/sample.cpt Saving key as ./ocn/sample.key
clubhouse.decrypt(r"./ocn/sample.cpt") Reading from ./ocn/sample.cpt Writing to ./ocn/sample.dcp Using key ./ocn/sample.key
FOURSCORE AND SEVEN YEARS AGO OUR FATHERS BROUGHT FORTH ON THIS CONTINENT A NEW NATION, CONCEIVED IN LIBERTY AND DEDICATED TO THE PROPOSITION THAT ALL MEN ARE CREATED EQUAL. NOW WE ARE ENGAGED IN A GREAT CIVIL WAR, TESTING WHETHER THAT NATION OR ANY NATION SO CONCEIVED AND SO DEDICATED CAN LONG ENDURE. WE ARE MET ON A GREAT BATTLEFIELD OF THAT WAR. WE HAVE COME TO DEDICATE A PORTION OF THAT FIELD AS A FINAL RESTING-PLACE FOR THOSE WHO HERE GAVE THEIR LIVES THAT THAT NATION MIGHT LIVE. IT IS ALTOGETHER FITTING AND PROPER THAT WE SHOULD DO THIS. BUT IN A LARGER SENSE, WE CANNOT DEDICATE, WE CANNOT CONSECRATE, WE CANNOT HALLOW THIS GROUND. THE BRAVE MEN, LIVING AND DEAD WHO STRUGGLED HERE HAVE CONSECRATED IT FAR ABOVE OUR POOR POWER TO ADD OR DETRACT. THE WORLD WILL LITTLE NOTE NOR LONG REMEMBER WHAT WE SAY HERE, BUT IT CAN NEVER FORGET WHAT THEY DID HERE. I've put the colorized (HTMLized) code for my clubhouse.py (version 1.0) at http://www.inetarena.com/~pdx4d/ocn/clubhouse.html with non-HTMLized (plaintext) source code at: http://www.inetarena.com/~pdx4d/ocn/python/clubhouse.py The html file has tie-backs to some of our posts in this thread on edu-sig (including this one). Kirby

def permute(): """ Randomly permute the uppercase alphabet by choosing its letters pseudo-randomly """ alphalist = list(string.uppercase) newlist = [] for i in range(len(alphalist)): randchar = random.choice(alphalist) alphalist.remove(randchar) newlist.append(randchar) return newlist
This looks nice! It might be nice to show another approach to shuffling the alphabet: ### from string import uppercase from random import randint def permute(L): """ Permute a list by swapping elements randomly. """ newlist = L[:] # shallow copy for i in range(len(L)): rand_i = randint(i, len(L)-1) newlist[i], newlist[rand_i] = newlist[rand_i], newlist[i] return newlist if __name__ == '__main__': print permute(list(uppercase)) ###

On Sun, 19 Nov 2000, Daniel Yoo wrote:
This looks nice! It might be nice to show another approach to shuffling the alphabet:
### from string import uppercase from random import randint def permute(L): """ Permute a list by swapping elements randomly. """ newlist = L[:] # shallow copy for i in range(len(L)): rand_i = randint(i, len(L)-1) newlist[i], newlist[rand_i] = newlist[rand_i], newlist[i] return newlist
if __name__ == '__main__': print permute(list(uppercase)) ###
It takes a bit more thought to see that this acheives the same amount of permutation as the original. For instance, if we merely swapped random elements L times, the result would be different, because unchanged elements would be much more common. That is: ### from string import uppercase from random import randint def permute(L): """ Permute a list by swapping elements randomly. """ newlist = L[:] # shallow copy for i in range(len(L)/2+1): rand_i = randint(0, len(L)-1) rand_j = randint(0, len(L)-1) newlist[rand_j], newlist[rand_i] = newlist[rand_i], newlist[rand_j] return newlist if __name__ == '__main__': print permute(list(uppercase)) ### I can see some interesting discussions about what it means to be random, and what sorts of characteristics we might want from a 'random' activity in different situations. --------------------------------------------------------------------- | Connection - in an isolating age )O( | ---------------------------------------------------------------------
participants (3)
-
Daniel Yoo
-
Dustin Mitchell
-
Kirby Urner