| Welcome to Crypto. We hope you enjoy your visit. You're currently viewing our forum as a guest. This means you are limited to certain areas of the board and there are some features you can't use. If you join our community, you'll be able to access member-only sections, and use many member-only features such as customizing your profile, sending personal messages, and voting in polls. Registration is simple, fast, and completely free. Join our community! If you're already a member please log in to your account to access all of our features: |
- Pages:
- 1
- 2
| Writing tutorials on "programming for cryptanalysts"; Looking for comments and ideas | |
|---|---|
| Topic Started: Jul 7 2009, 03:11 AM (398 Views) | |
| mosher | Jul 7 2009, 03:11 AM Post #1 |
|
Member
  ![]](http://209.85.122.85/static/1/pip_r.png)
|
A few days ago I posted an entry on my blog "Jerusalem Mosaics" entitled "Serious about cryptanalysis? Learn a programming language!". The point of the entry was that a cryptanalyst today must know the rudiments of computer programming and must be able to write small programs to reduce the task of analyzing a cipher. I believe I'm preaching to the converted on this forum -- many algorithmic and software engineering issues are posted here. I recently received a comment to the aforementioned blog entry:
My reply was that I had been caught unprepared and did not have pre-written tutorials to complement my blog entry. My answer to the commenter was that I would seriously consider writing such a tutorial, possibly posting it on The Crypto Forum. My intention is taking a programming language (e.g., C, C++, Perl) and teaching the rudiments needed to open a file, parse the text, iterate over the characters, take a frequency count, outputting to standard output or a file, and a handful of other concepts. I don't intend on teaching the language in its entirety; rather teaching the minimal number of concepts with emphasis on cryptanalysis. The tutorials would impart the hands-on experience and tips I've learned over the years, and would be accompanied by real-working examples. In parallel I'd like to provide an ever-growing collection of programming snippets in that language for copying-and-pasting My questions to the learned group are:
Regards, Moshe Edited by mosher, Jul 7 2009, 03:12 AM.
|
 |
 
|
| osric | Jul 7 2009, 09:42 AM Post #2 |
|
Advanced Member
|
I think your project is well worth while. I have written a tutorial to teach beginners to program in Python ( see it at http://web.me.com/mikejcowan/Ciphers/1._Introduction.html) and I know from many responses that this was welcomed. I used examples from solving cryptograms as the basis of teaching and this seems to have gone down well. I don't claim that my effort is either complete for Python or that knowledge of Python programming is sufficient for all interests and so I welcome your initiative, which I think will be very useful. Here are my responses to the questions you pose: * What is your opinion of this venture? A very good move. * Am I reinventing the wheel? Has this been done to date? If so, where? Yes there are tutorials available on the Web for Java and Python with the Freeware downloads, and I'm sure for some other languages. But they tend to take a 'broad brush' approach and try to teach all aspects of the language. For the beginner this can be confusing. there is nothing worse than 'expert speak' for the person who knows nothing or very little. I see a need for teaching that is focussed at a particular application -- like solving cryptograms, or something else concrete and useful. * My programming languages include C, C++, Java, Perl, and AWK. I'm especially partial to scripting languages because of the quick turn-around and high ratio of power-to-code-written. I thought I'd begin with Perl, but it would be great to have tutorials for Python, Ruby, and other state-of-the-art languages? Would anyone be willing to produce tutorials for other languages? Personally I would welcome a tutorial on Perl, a language I don't know! In general, I would suggest Java should be high on the list for these reasons: the software is free, the language is state of the art, there is great flexibility (applications can be run as GUI, as monitor, run on the internet), the tutorials provided with the software are too 'geeky' and not easy for beginners. * What should these tutorials cover? I'm going top pass on this one. My ideas are demonstrated at my website. * Should the different language tutorials be synchronized, handling the same programming tasks? Or should they be independent? If you tackle several languages, my suggestion is to do one language at a time because a beginner is going to find it hard enough to learn one language, let alone two or three. However i realize that my suggestion demands that you pick the 'right' language to cover first, and this will be an impossible choice to meet all folk who are interested in getting started. On the other hand if several people are going to be involved, each tackling a different language, then it would be useful for synchronization -- but I doubt this is practical. My experience is that people have their own creative ideas and like to do their own thing at their own pace. This means synchronization is not welcomed. * Any other comments and ideas you may have. Keep out the geeky stuff -- that can come later. Focus on teaching by doing rather than theory. Be simple, not smart. Oh and Good Luck with the venture. |
|
|
|
| jdege | Jul 7 2009, 01:12 PM Post #3 |
Elite member
|
Personally, I'm a strong believer in using the simplest tool for the job. For a simple substitution cipher, the language you need is tr. Which is so simple as to hardly be worth considering as a programming language. As an example, to implement the basic rot-13 cipher in tr is:
Or, if you prefer to upper case:
Or, if you want to eliminate spaces and group in fives (patristocrats):
|
| When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl. | |
|
|
| osric | Jul 7 2009, 11:28 PM Post #4 |
|
Advanced Member
|
OK, but it's got to be fit for purpose. Where do I download the app to write and run programs in this language? Will a program in this language solve a Patristocrat? a Playfair? a Quagmire 4? Can you give us an example of such a solving program so we can see its simplicity? |
|
|
|
| jdege | Jul 8 2009, 02:13 AM Post #5 |
|
Elite member
|
tr is one of the standard Unix text-processing tools. It takes two arguments, the first is a list of characters to be substituted, the second is a list of characters to substitute for them. It's very easy to use it to implement a simple substitution cipher, but it's very quickly out of its depth doing anything more. You can do a fair bit of crypto work with the Unix toolset, tr, grep, sed, awk, et al. With sh tying them all together, of course. The scripts I use to do frequency counts, calculate IC's, etc., use them. The following converts all alphabetic characters to upper case, then removes all non-uppercase letters, then prints the remaining characters one per line, then sorts the lines, then counts the number of times each unique line appears. If you're familiar with the toolset, it's very quick to throw something like this together.
Still, the closest thing to a real programming language in the bunch is awk, and its data structure capabilities are primitive. The tools I use for solving Quags are done in Python. Though I'll usually write such tools to take a specific input format and then use the Unix text-processing tools to preprocess the input to create that format. I find it more flexible and easier to adapt. A week or so ago I wrote a command-line calculator, based on the example in the bison manual, that did matrix math to a modular base. With some simple text processing I convert plaintext into matrix and vector multiplication, and then convert the results into ciiphertext, and I had a tool that implemented the Hill Cipher. Use each tool for its best purpose, and if you don't have tool that works, write one in such a way that it works with the others. I agree that Python is a very good choice as an introductory programming language, It has the sophisticated data structures that awk lacks. And it's performant enough for everything a novice is likely to try, until they start getting their feet wet in hillclimbers, etc. And it has a pretty good cross-platform GUI capability, which can help with visualization in some problem areas. But I still can't help thinking that we do novice programmers a disservice by this "write a program to solve your problem" approach that has been so prevalent in the PC era. It's a lot easier to write a simple program that handles one part of a tool chain, where all of the other parts came off-the-shelf, that to write a program that handles the problem in its entirety, (BTW - These tools are available on Windows: http://gnuwin32.sourceforge.net/. And as for the Mac, the Mac is Unix - they're already there.) |
| When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl. | |
|
|
|
| mosher | Jul 8 2009, 07:20 AM Post #6 |
|
Member
|
First off, i owe osric and apology -- your article "Tutorial on how to program in python -- for programming novices" is exactly what I had in mind, and you fulfilled what I intended to do -- well done. Therefore, I'd like to do something similar for Perl, my scripting language of choice for writing both "quick-and-dirty" and more permanent cryptanalytic programs. Regarding jdege's comments about Unix-type tools, I agree wholeheartedly. The philosophy of chaining many small tools together has always been especially appealing to me. Over time the Unix OS world itself started writing bloated, oversized Swiss knife tools, but the concept is an excellent one. These tools are especially suited for repetitive, known tasks like inputting and cleaning data, taking frequency counts, finding repetitions, etc. as jdege demonstrated. My point of learning a programming language is for the less repetitive tasks required while doing original research. The latest example that comes to mind is my recent work on Chaocipher. I wrote scores of both small and larger programs for performing non-standard operations: interval frequency counts, looking for non-standard interrupted patterns and coincidences through the PT / CT, simulating numerous encryption models, and much more. Obviously one cannot write tools for these very specific tasks, and expanding existing tools to handle them might be overkill. Over the years I've thought about developing a programming language specifically for cryptanalysis. I vividly remember in the 70's trying to track down a copy of the Project MAC document entitled "OCAS - ON-LINE CRYPTANALYTIC AID SYSTEM", by Daniel J. Edwards, MIT (1966). Edwards's idea was a SNOBOL-like language designed specifically for cryptanalysis. In my opinion, such an approach (i.e., a dedicated language) is no longer necessary. Modern-day languages, both scripting and otherwise, have the programming concepts needed for the work (e.g., looping constructs, subroutines, object-oriented support, sophisticated input/output). In addition, they can be extended by writing libraries for them (e.g., CPAN for Perl). One can invest time and energy writing a cryptanalysis-dedicated library that can greatly ease the programmer's life, practically inventing a new domain-specific language dedicated to cryptanalysis. Regarding jdege's idea of tools, I can imagine an extension library for one's language of choice that allows one-line calling to an ever-growing list of cryptanalytic tasks:
The library can simulate known cipher entities like:
Also one-stop complete emulations of known cipher systems like:
Standardizing the interfaces between the functions will help introduce order and will enable chaining such function calls together, not unlike the Unix tool chaining concept. One other point, not relevant to this posting, is the need to standardize ciphertext input files. Currently, ciphertext files are simple text files with nothing other than the ciphertext characters. No hint of what the cipher is, where it originated, what is known about it, possible cipher systems, possible cribs, and much more. If cryptanalysts world-wide are to pool their collective work together, there should be a standard format for archiving ciphertext messages on a long-term basis. I envision developing an XML DTD/schema specifically for ciphertext messages. I'm just touching upon the idea here: I hope to begin another thread dedicated to this recommendation. Moshe |
|
|
|
| osric | Jul 8 2009, 10:35 AM Post #7 |
|
Advanced Member
|
Moshe -- your last posting develops the theme very nicely, in my view, and I agree with it all. No apologies needed to me -- I'm delighted that you will be producing a 'vade mecum' on Perl. jdege -- as always, interesting input, though I do have a different point of view on some items.
For this reason I feel that tr is not a suitable language to teach to beginners. It’s just not useful enough. In my book it falls into the ‘geeky’ category – of interest to the ‘cognoscienti’ like yourself, but to be avoided by the beginner. The same goes for the other languages you mention. They are obviously fun for you but I can’t imagine that being so for someone who wants to learn an understandable, extendable, well-supported and useful language. The code you quoted as an example is to me a total horror for a beginner! Not intuitive, no relation to any high-level language and thus a dead end. As an indicator, a survey in the ACA a few years ago did not find these languages in use. We have to be careful with definitions in this discussion. When I asked you : “Will a program in this language solve a Patristocrat? a Playfair? a Quagmire 4?”, I meant will it automatically solve. In other words, given the ciphertext, will the program be capable enough to find the solution on its own, without human inputs? There is no way that the languages you mention are sufficiently capable. If you disagree, then please show me a program that will give a complete solution for a Playfair.
Python is perfectly capable of solving using a stochastic algorithm – be it hillclimbing, a genetic algorithm, Simulated Annealing or my Churn algorithm. I suggest you have a good look at my tutorial and try the programs that come with it! Where Python is weak is in its speed, because it’s not compiled. So for complex auto solvers it’s not the best choice. When a beginner who initially learns Python gets to the complex level (which very few in the ACA have reached) then they need to progress to Pascal (yes there are still keen adherents), C/C++ or Java.
You are right that there is a spectrum of potential computer users, ranging from those who just want to program a tool to take the ‘grunt work’ out of pencil and paper solving all the way up to the enthusiasts who want an ‘automatic’ solve. This came out clearly in an ACA working group on which I served some 5 years ago. And I agree that it would be useful to cater for as many needs as is practical. But I think you are wrong to criticize an approach of “write a program to solve your problem”. In my experience, people don’t want to learn to program as an academic exercise, or to increase their erudition. They want to acquire programming skills in order to do something useful with them. This may just be, as you have intimated, to write an interactive Aristo solver. Or it may be at the difficult end of the spectrum. Both are worthy and neither is a disservice. The way forward is to teach the basic programming skills (and we all know what they are) and to illustrate their use through examples of increasing complexity. This is the normal approach, allowing the learner to go as far as he/she is interested. The novel aspect of Moshe’s project is to construct such a tutorial especially for the beginner, and that in my view will be an improvement over the generality of what’s available on the net. There are, of course, some very good books for beginners, but they don’t come free!
Again I have to say that these are designed for people who know what they are doing, and are not suitable for the beginner --- and I’m talking about both the interface and the instructions. The beginner needs a ‘friendly’ interface and not the stripped-down, professional version to which you refer. Suitable versions in my experience are: Python, Net Beans for Java on the Mac, Borland or equivalent MS for C++ (unfortunately not free), Visual Basic (available with Office). There may well be others known to you or other Forum members. Edited by osric, Jul 8 2009, 10:38 AM.
|
|
|
|
| jdege | Jul 8 2009, 12:34 PM Post #8 |
|
Elite member
|
That was my point. When you're writing a program that is going to run through millions of trial keys, you'll need a compiled language. And if you're using objects, you want a language in which you can create arrays of objects, and not just arrays of references to objects. The level of indirection that is unavoidable in Java or C# can be a performance killer, in certain problems.
I don't mean to criticize you. My point was that the general assumption in most programming texts is that you are writing a program - a stand-alone application that will be used by other people over a period of time. This is a very different problem than that of using a computer to solve a particular technical problem of your own. You said, above, "They want to acquire programming skills in order to do something useful with them." And that is exactly the point. There is a reason that so many people turn to spreadsheets, rather than to programming languages. Or MatLab. (Or, for the old farts, APL.) They don't want a program, they want a problem solved. And the fastest way to do that is to leverage programs that already exist. It's not language, so much as mindset. What we're not providing, by focusing too quickly on particular languages, is guidance in what program to write. |
| When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl. | |
|
|
|
| osric | Jul 8 2009, 06:36 PM Post #9 |
|
Advanced Member
|
This is pure speculation on your part. The FACT is that cipher solving programs written in Delphi, Pascal, C++ and Java not only solve programs extremely effectively, but without peer. Just look at the performance of people who use these languages: THE RAT, NUCULAR, GIZMO and BION not to mention SCRYER and myself. We don’t have ‘killer hangups’ with the languages we use, nor are we so stupid as to choose languages that are unsuitable. As for Python, it’s perfectly good for most cipher solving applications. Otherwise BION and I wouldn’t recommend it!
Moshe has floated the idea of writing a tutorial to help people learn a programming language. To do this he’s got to choose a suitable language. This is not ‘focussing too quickly’ but an essential part of his task. I have no doubt he will choose useful programs to illustrate the teaching and that in itself is guidance of the sort you claim is lacking. There’s oodles of guidance in other quarters on what programs to write. The problem I see is too little action. Good for Moshe for taking the initiative to do something, other than talk! |
|
|
|
| jdege | Jul 9 2009, 02:45 AM Post #10 |
|
Elite member
|
You seem to have taken my remarks on programming languages as some sort of personal attack on you and other ACA members who have been, until now, no part of the conversation, and I'm at a loss to understand why. Similarly, my remarks on Python have been generally favorable, yet you are responding as if I had belittled it. This confuses me. I am not a language bigot. As I said at the first, I believe in using the simplest tool for the job. Which is the simplest tool? The one that will meet the requirements with the least effort, The pipestream I posted earlier outputs the frequency count of the input text, one line per letter, with the count for a letter and the letter on each line, separated by whitespace. To calculate the IC for the text, we simply pipe the frequency count through a simple awk script:
Awk is designed around processing lines of text with white-space-separated fields. For this problem, there is no language that can provide a simpler solution. Does this mean that awk is the only choice, or even the best choice? Of course not. Which is the best choice depends upon the problem, environment, and the experience of the programmer. If the programmer is familiar with python, and not with awk, the idea that the programmer should waste his time learning awk rather than use python is absurd. True, python doesn't have the built-in line looping and parsing that awk does, but implementing would take at most a dozen lines of code. Weighing that trivial effort against that of learning another programming language yields only one rational conclusion. Of course, a python programmer who was writing a program for calculating the IC of a text would be unlikely to write one that took as input a frequency count. He'd be more likely to write one program that did the whole thing - case collapsing, filtering out irrelevant characters, frequency counting, and calculation of the IC. That whole exercise might take 30 lines of code, or maybe 50 if you were conscientious about error handling. But what would you have? A program that could calculate monogram ICs of english telegraph text. If you were working with a Danish xenocrypt, with its extra vowels, or a cipher in which ciphertext was represented by pairs of digits, you'd have to start over from scratch. When we're teaching novices to write programs to solve their own problems, we need to teach them to modularize - to build pieces that are each responsible for doing just one thing, and to define standardized communication mechanisms so that they can be easily plugged together to solve a wide range of problems. And that's what's not taught in typical intro to programming books. In fact, I can't think of many books that were written to teach programmers how to write programs for their own use since "Software Tools" and "Programming Pearls". The form these modules take is dependent on the toolset you're using. I knew programmers back in the day who had bookshelves full of punch-cards that they could pull out and drop in a deck, whenever they needed a routine in their program. Python modules, static link libraries, DLLs, COM objects, .NET assemblies, whatever is appropriate for the environment, we need to be teaching the novices that what they're doing isn't writing a program to solve a particular problem, but developing a repository of tools that they can easily customize to solve a wide range of problems in their particular domain. |
| When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl. | |
|
|
|
| osric | Jul 9 2009, 08:00 AM Post #11 |
|
Advanced Member
|
jdege -- we have very different points of view. So be it, that's what discussions are about. Just to be facetious for a moment, my approach is:"Never mind the theory, will it work in practice?" while I get the impression yours is the other way around! I doubt we can find much common ground. However I respect your expertise and your point of view and I really have nothing more to add. I'm very happy to leave it to Moshe to decide the best way forward, armed with his own ideas and our differing views, and look forward in the future to learning Perl. It would be really interesting to hear comments on Moshe's proposed project from other members of the Forum, and especially from those who are interested in learning to program. May I encourage you to post your own views and suggestions on this valuable project? |
|
|
|
| nullsole | Jul 21 2009, 07:04 PM Post #12 |
Just registered
|
First hello all, I have been lurking here for a very, very long time and have learned from postings, and tutorials found here. This topic is quite timely for me so it felt like time to come out of lurkdom. As a non-programmer, or maybe I can say, as someone just beginning to learn to program I can say I would for sure be interested in anything that would help in my endeavor. MOSHER: I recently came to the realization about the importance of learning to program to make any sort of serious headway in cryptanalysis, even with strictly classical ACA type ciphers. It just makes sense in this day and age to use the tools around us. With that in mind, and a search on programming, cryptanalysis, and classical cipher types - osric's site came up in my list. A hit on a book, and probing around the Python.org site and I decided on my language. I am now about two weeks into my journey and loving it! osric: It was your site that got me started! The approach you presented was EXACTLY what I was looking for, and could not find anywhere. That is was specific to cryptology was the grab! There are many good and free tutorials and ebooks out there, but none on crypto. I wanted to learn to program specifically for classical crypto. As a non programmer, with only very limited experience with rbase (back in the day), and DOS bat, and Linux scrips to keep a BBS running -- that was it. After database programming, I was into graphics and 3D with Lightwave but that didn't involve programming and now I am strictly a traditional artist using the computer as a most, a composition/layout tool (Photoshop). I was interested in programming kind of the same way - as a tool for crypto. Except, I do find it almost as much fun as breaking into a cipher so they have almost become one and the same. I am just learning the many types of ciphers from the ACA as I am learning Python to help (in the future) with the breaking and solving of them. So, you can, consider me your test subject! Hopefully there are more of us lurking about in the shadows ... enough so more folks with this wonderful knowledge can mentor us that a bit behind but anxious to be a part of something more. I find any explanation or description of how to approach a type cipher extremely useful and I think as MOSHER presented, anyone regardless of specific language could take that and apply it. Of course, specifics to the language would be great, but at least knowing there was a forum where one could freely ask about problem solving on various crypto techniques would be wonderful. I'll be watching this Forum as I have been for anything anyone is willing to share! Thanks, nullsole |
|
|
|
| jdege | Jul 22 2009, 12:33 AM Post #13 |
|
Elite member
|
I am glad to know there are people interested in this. Since our discussion last week, I've been working on a tutorial, myself, in using Python in cryptography. Not recapitulating what Osric has done, but trying to touch on the areas I had brought up in our earlier discussions. It's nearly done, but things have been so quiet around here I was worried that nobody would be interested. Give me a couple of days... |
| When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl. | |
|
|
|
| mosher | Jul 27 2009, 05:05 AM Post #14 |
|
Member
|
Hi nullsole, Many thanks for your encouraging input! I've been a lurker for many years, and came out of it about a year ago when I established The Chaocipher Clearing House. Since then I have joined The Crypto Forum and haunted sci.crypt. No doubt about it: since doing so I have come in contact with so many talented and knowledgeable cryptographers on this and other forums. "The more one shares, the more one gets" was never truer. osric's excellent Python site was the first of its kid that I had encountered, and jdege has now added his wonderful site, too. These tutorials are not one-time efforts; they will remain on the Web for years to come as a great source of programming education. I hope to free up soon to add my modest contribution (probably in Perl). It might be a nice idea to have a programming language "snippets" area for each language. For example, there might be a place on this site that collects short, standalone sequences of Python code for doing important functions such as:
I use a program called CodeBank to store code snippets in all the programming languages I use (there are many other excellent programs like it on the Web). I have built up code sequences of 5, 10 or more lines of Perl, AWK, sed, C++, Java, MS-DOS batch code, Xerces (XML), and grep for functions I've used a zillion times. Today, when I need to copy-and-paste some tried-and-true lines of code, I dip into my 'tool box' for it. And if I write some new code that I believe will have value in the future, I place the snippet in the DB. I envision something similar for cryptographic script programming. Regards, Moshe |
|
|
|
| jdege | Jul 27 2009, 03:05 PM Post #15 |
|
Elite member
|
I like the idea of having a store of common coding idioms you've found useful. I've found myself, quite often, searching through code to find how I, or others on the team, have done something before, just so that we maintain the pattern of always doing things the same way. I'd never considered maintaining a database of these idioms - it's something I'll bring up at our next dev team meeting. But still, that's only a first step. Cut-and-paste reuse has significant shortcomings. A number of the areas you've cited, normalizing text, taking frequency counts, etc., are well-suited to being implemented in a class hierarchy. Create a text class to handle plain text. Extend it, or inherit from it, to create a class to handle digram ciphertexts, or other variants, as the need arises. Make them all implement a common interface, and write your frequency count class to work against that common interface. In other words, don't solve the immediate problem, create tools to help you solve the problem more easily. The specifics of Kernighan and Plauger's "Software Tools" may not apply to your situation, but the mindset most definitely does. Over time, you will increase your effectiveness by increasing your tool set. 
Edited by jdege, Jul 27 2009, 03:06 PM.
|
| When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl. | |
|
|
|
| 1 user reading this topic (1 Guest and 0 Anonymous) | |
| Go to Next Page | |
| « Previous Topic · General · Next Topic » |
- Pages:
- 1
- 2
5:57 AM Nov 28
