Mailman 3 November 2000 - Edu-sig

Another Forth remark
by Dirk-Ulrich Heise Dec. 8, 2000

Dec. 8, 2000

Funnyly i stumbled across this: One of the original aims of Forth was to erase the boundary between user and programmer - to give all possible power to anyone who had occasion to use a computer. Nothing in the above labeling or remarks should be construed to mean that this goal has been abandoned. at http://www.taygeta.com/forth/dpansa15.htm (end of the first paragraph) Seems to be commonplace amongst language inventors ;-) Maybe they're all on a mission... Dipl.Inform. Dirk-Ulrich Heise hei(a)adtranzsig.de dheise(a)debitel.net

2 4

More permutation madness [Cryptonomicon]
by Daniel Yoo Nov. 30, 2000

Nov. 30, 2000

There was a question about ways of generating permutations: is there an easy way to show that these two functions: ### def permuteRestricted(L): 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 def permuteUnrestricted(L): newlist = L[:] # shallow copy for i in range(len(L)): 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 ### act differently? I tried to prove this difference by brute force: the attached program generates the whole space of permutations, given these two methods. I have to apologize for the code's uglyness and sluggishness, and if anyone can simplify or optimize it, I'd be very happy. I hope this helps!

2 1

Re: [Edu-sig] More permutation madness [Cryptonomicon]
by Kirby Urner Nov. 30, 2000

Nov. 30, 2000

At 03:33 AM 11/30/2000 -0800, Daniel Yoo wrote: > >There was a question about ways of generating permutations: is there an >easy way to show that these two functions: <<SNIP>> >act differently? They have different properties. There's only one possible route to ABCD...WXYZ in the restricted method (all letters self-identified) through a narrowing set of options at each turn, for 26 turns. But the unrestricted method gives a great many pathways to this same terminus in 26 iterations, by presenting a non-narrowing set of options at each turn. The restricted method is your classic decision tree with fanning branches, terminating in 26! equally probable outcomes. Every iteration forces you to the next level, towards the final outcome level. The unrestricted method allows you to retrace your steps, back towards the beginning. Without trying to compute a lot of specific probabilities, I think you can see that the two methods, while confined to the same "state space" of 26! letter sequences, are not isomorphic (i.e. are not simply two ways of doing the exact same thing). Kirby

1 0

Re: Cryptonomicon
by Dethe Elza Nov. 29, 2000

Nov. 29, 2000

Bruce Schneier, who wrote the Solitaire algorithm (called Pontifex in Cryptonomicon) has an excellent page describing how and why it works: http://www.counterpane.com/solitaire.html One of the cool things about it is that it's designed to use playing cards, so you can have students encrypt and decrypt messages with cards, getting a tactile feel for encryption, then implement the code. There's python code up on the site, too, though they make no claims about its reliability: http://www.counterpane.com/pysol.zip Anyway, it's much more realistic from an encryption point of view, without being much more complicated than a clubhouse algorithm. Win-win. --Dethe edu-sig-request(a)python.org wrote: > Send Edu-sig mailing list submissions to > edu-sig(a)python.org > > To subscribe or unsubscribe via the World Wide Web, visit > http://www.python.org/mailman/listinfo/edu-sig > or, via email, send a message with subject or body 'help' to > edu-sig-request(a)python.org > > You can reach the person managing the list at > edu-sig-admin(a)python.org > > When replying, please edit your Subject line so it is more specific > than "Re: Contents of Edu-sig digest..." > > > Today's Topics: > > 1. Re: Cryptonomicon (Kirby Urner) > > --__--__-- > > Message: 1 > Date: Sat, 25 Nov 2000 10:09:40 -0800 > To: edu-sig(a)python.org > From: Kirby Urner <pdx4d(a)teleport.com> > Subject: Re: [Edu-sig] Cryptonomicon > > > I've added some links to my Python-based > http://www.inetarena.com/~pdx4d/ocn/clubhouse.html > including to an URL where Windows users can > download GUI simulators of Enigma machines. > > The Sale essay on deciphering the Enigma mentions > how "no letter my encipher to itself" was actually > a weakness of the German system, along with its > bidirectionality, i.e. if A enciphered to J, then > J enciphered to A. > > The difference between simple random substitution > ala my clubhouse code algorithm (which allows > self-substitution) and something like Enigma, is > the latter changes the substitution key with each > press of a letter (in the Enigma using a complicate > system of rotors which, like a car odometer, > knocked successive wheels one notch with each > complete revolution of the one before). > > Here's some example plaintext and corresponding > ciphertext, from one of the Enigma simulators: > > Input (note 5-letter chunking): > > AQUIC KBROW NFOXJ UMPED OVERT HELAZ YDOGW WWWWW > WWWWW WWWWW WWWWW WWWWW WWWWW WWWWW WW > > Output (note how repeated Ws in the input > nevertheless enciphers to different letters > below): > > UVWFP ALDFF FMNML SHZLI GTMXM CISQU EIYED FJORN > OMNRA CZVXL MRBAO JRGRO ZKCAJ NMMLP AO > > Also in the news: an Enigma machine stolen from > the Bletchy Park museum was recently recovered, > along with the internal rotors (found separately, > according to newspaper accounts). > > Another link shows contains some scans of Turing's > original typed manuscript re the Enigma, plus > there's a virtual tour of Bletchy Park -- all > very reinforcing of the storyline developed by > Neal Stephenson's 'Cryptonomicon', the novel which > originally inspired me to launch this thread. > > It's be high feasible to write an Enigma simulator > in Python of course, including with a GUI front > end. But in accordance with my "cave painting" > analogy, I think what's important from a pedagogical > point of view is, on first pass, to give just the > flavor, the essential gist, and then move on to > linked topics (e.g. digital circuit design and > the evolution of computing hardware). > > Kirby > > > > > --__--__-- > > _______________________________________________ > Edu-sig mailing list > Edu-sig(a)python.org > http://www.python.org/mailman/listinfo/edu-sig > > > End of Edu-sig Digest

2 2

Re: Intro to Crypto (Python, kid/beginner focus)
by Kirby Urner Nov. 28, 2000

Nov. 28, 2000

Kirby Urner <urner(a)alumni.princeton.edu> wrote: >A lot of the background reading is on the web pages >linked from the URL below, which contains mostly >Python source code. Actually, not any more -- I've just upgraded this page (*) to contain a better narrative:code ratio. It's actually quite readable now, with most of the source code kept in the back, for those wanting to read it (and/or copy/execute it). This is one of several web pages from the Oregon Curriculum Network, developed in part to assist homeschoolers with math-related curriculum. But I'm not exclusively so focussed (e.g. my own daughter goes to a public school, and I'm thinking of her and her peers just as much -- went over there recently to install Python for the iMac). The Python aspect wasn't part of this site at the outset -- although using *some* computer language always was. I came to Python late in my game, and quickly recognized it for having the key features I was looking for in a teaching language, chiefly a command line interface (CLI) and an easy way of implementing many of the object-oriented programming concepts (OO). Kirby * http://www.inetarena.com/~pdx4d/ocn/clubhouse.html

1 0

Re: [Edu-sig] Cryptonomicon
by Kirby Urner Nov. 25, 2000

Nov. 25, 2000

>> e.g. letter frequency, in descending order, tends towards >> ETAOINSHRDLU, plus we have commonly occuring letter combos, >> like ET EA OU. > >I thought that was 'RSTLNE'.. > >Dustin A joke, right? Something to do with the Wheel of Fortune. BTW, my source for that factoid was: http://raphael.math.uic.edu/~jeremy/crypt/freq.html Here's another post on the topic, which gives some alternatives (all starting with ET though): http://linguistlist.org/~ask-ling/archive-1998.7/msg00388.html Kirby

1 1

Re: Edu-sig digest, Vol 1 #172 - 5 msgs
by Dorothea Salo Nov. 21, 2000

Nov. 21, 2000

> 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 above algorithms, if I'm reading them correctly, allow a character to be substituted by itself. I assume this is desirable behavior (since it increases the number of permutations), but perhaps someone could comment on how often self-substitution could be expected to happen, and how likely it might be that self-substitution would cause the "encrypted" result to be easier to human-decode. (Self-substitution of "e" seems more likely to ease decryption than self-substitution of "z," but I'm just guessing.) Of course, most Cryptoquoters assume that self-substitution is explicitly disallowed, so it might actually be considered a "feature" in this context... (I can think of a couple of ways to disallow self-substitution, but I think the Python is less interesting than the problem.) Dorothea -- Dorothea Salo Impressions Book and Journal Services, Inc. phone: (608) 244-6218 fax: (608) 244-7050 http://www.impressions.com

2 1

Re: [Edu-sig] Cryptonomicon
by Kirby Urner Nov. 20, 2000

Nov. 20, 2000

>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. > Yes, always a worthwhile thread. Also fun would be to take some clubhouse crypto texts and crack them. Although permuting the 26 uppercase letters yields 403,291,461,126,605,635,584,000,000 possible arrangements (looks impressive), if we know the plaintext is in English, then we can always apply some valuable clues, e.g. letter frequency, in descending order, tends towards ETAOINSHRDLU, plus we have commonly occuring letter combos, like ET EA OU. And if the encrypted text isn't chunked (e.g. into 5-letter strings), to obscure word lengths, then we have a lot more to go on: frequent 3-letter words like AND THE would suggest substitutions. Indeed, finding the most common letter (say V) and then finding 3-letter words ending in V would give a good hypothesis for the T and H substitutions. I'd be in favor of leaving all these clues intact (e.g. not even chunking at first) and allowing students to successfully crack a few clubhouse messages. Then you could go to a next level of difficulty (e.g. add chunking). As per usual, the cryptographer and cracker share the same mind, as do computer security folks and hackers (in the popular media sense of hacker). Kirby

2 1

Re: [Edu-sig] Cryptonomicon
by Kirby Urner Nov. 19, 2000

Nov. 19, 2000

>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

3 3

Re: Programming for non-programmer IT professionals
by Dethe Elza Nov. 18, 2000

Nov. 18, 2000

Kirby & Jim, When analyzing data like you're talking about, you might want to check out Martin Fowler's "Analysis Patterns : Reusable Object Models." Many of his examples are drawn from health care, and there's a lot of good stuff. ISBN 0201895420. --Dethe Dethe Elza Antarcti.ca Client Lead http://antarcti.ca http://map.net

2 3