CSC 290: Cryptology: Exercises

Enigma in foreground, English bombe in background.

---

Generalities

You are encouraged to discuss general techniques and specific approaches to general problems with your fellow students, or anyone else. Unless specifically directed in an assignment, however, you are not to share code you have written, or your written solutions to specific problems. That would be a violation of The University Policy on Academic Honesty .

Don't forget the Homework Helper page.

Textbook Exercises (names: TX)

Speculations apparently the most unprofitable have almost invariably been those from which the greatest practical applications have emanated.

--John Herschel

---

These are on-paper exercises from the text (note Garrett gives answers to sample problems). Hand them in on Tuesdays during class. The spirit of the guidelines of Exercise How-To (PDF) should be observed. Legible writing, write mathematics like English prose, and so forth.

  1. T1: TextEx T1 Basics
  2. T2: TextEx T2 Classic, Vigenere
  3. T3: TextEx T3 Hill, LFSR
  4. T4: TextEx T4 DES, AES
  5. T5: TextEx T5 (Number Theory)
  6. T6: TextEx T6 (RSA)
  7. T7: TextEx T7 (discrete logs)
  8. T8: Ex T8 (Based loosely on Trappe Ch. 15)
  9. T9: Trappe: Section 10.9, Numbers 1, 2, 4, 5. Section 11.2, Numbers 1, 2, 3, 4 (Double Points), 5.
  10. T10:
  11. T11:

    Crypto Projects (names: EX) -- Generalities

    Plato thought that certain natural gifts were required for the pursuit of learning. He stressed that anyone seeking wisdom in this way should be aware `how many subjects there are to study, how much hard work theyh involve, and how indispensible it is for the project to adopt a well-ordered scheme of living.'

    --Anthony Gottlieb

    An expert problem solver must be endowed with two incompatible qualities -- a restless imagination and a patient pertinacity.

    -- Howard W. Eves

    These projects (except for E1) must be handed in through WebCT. WebCT is how we remember what came in and where we record grades.

    There is cryptological source code that comes with your book, and plenty written by other students at other universities in various languages out on the net. In fact I have imported a lot of it, and if you want to take a look it is in this source code directory . In "real life", that is, to get solutions for big problems, it is often useful to get code from elsewhere, and in fact you'd be crazy not to try it. HOWEVER these are not big problems, the fun and pedagogical point here is in developing the algorithms, not using them for research or to make a profit. Thus I expect you to write your own code. It's a lot more fun than trying to understand someone else's, and you learn more. Furthermore, plagiarism is lame, pitiful, shameful, dishonest, easy to detect, and bad for your academic record.

    However if you want to incorporate or build on some foreign source code, attribute ANY work that is not your own, including software from the text or off the web, java libraries, text cribbed from other sources, etc. You are encouraged to look for resources, but not to the extent that it negates the point of the assignment. This is sometimes a fine line, especially in programming assignments. I will try to be specific as to what I expect you to write as a minimum. If in doubt, ask. In any case, use of UN-attributed material is plagiarism, and a violation of the University Policy on Academic Honesty .

    I recommend you use the computer language you are most proficient in, given it has adequate non-numeric facilities. I like PERL and Matlab for these exercises. Both offer "one-liner" capabilities for otherwise messy operations on strings and arrays, and both have an interactive interpreter. By no means do you have to be expert at either of these languages: Matlab has particularly good on-line help, and I did all the PERL work for my versions of these assignments with the manual in my lap. Java has lots of useful libraries, including string and "infinite-precision" arithmetic.

    For Ex assignments, you should submit your source code (if any) and a ReadMe file to WebCT (see below). In all cases you should produce a well-organized report-style (see the Homework Helper page) writeup that describes in detail what you did, why you did it, and what the results were. This includes negative results. Even if you fail to crack a particular ciphertext, you can still get plenty of credit for an imaginative, well executed, and well documented approach. Scratch work, examples, computer code needed to make the write up coherent, etc. should be appended to the main writeup with appropriate pointers.

    Simply describe your work to an audience that knows the context (don't need stand-alone explanations of concepts etc.). What was the problem (the goal), What did you try, what did you learn, what technical issues arose and how did you beat them down (or vice versa?) what is original or unusual about your work? As your work gets more advanced and the techniques more difficult you may need to say more to describe them and how you orchestrated your solution. Remember: technical software documentation (describing its motivation, methods, validation and use) always takes more time and space than you think.

    Always welcome are graphs or charts.

    Examples of (term) project writeups are in The Student Projects Page . The average Ex project would take fewer pages to describe, of course.

    In particular, your WebCT submissions should contain the following (if applicable --- not all projects are computer projects).

    1. Well-organized (zipped archive, say) source code.
    2. A complete Readme file (manifest, interfaces, functionality, example sequences of operations, sample results, etc.)
    3. The main write-up, in PDF, as described above, giving your methods and results.

    Last but importantly, in some projects you are to encrypt text for use by other students, and you are to use text encrypted by other students. In your writeups, you should document to whom you gave your encryptions, AND you should document from whom you got your encryptions. You lose credit if you don't use others' encryptions and you lose credit if your encryptions aren't used.

    Crypto Projects (names: EX) -- Grading Guidelines

    Out of a possible 10 points:

    Bad Writing, spelling, or grammar; incomplete descriptions, inadequate or confusing explanations. UP TO MINUS THREE points, depending on how bad.

    No evidence of working code (no code listing, no scripts, no examples of interaction with program) MINUS FOUR POINTS

    No experimental results (code never worked or results not reported) MINUS FOUR POINTS

    Original content (new ideas, anyhing beyond what was asked in the assignment, including charts, graphs, comparisons, real data analysis) PLUS UP TO THREE POINTS.

    Unusual, surprising, informative extra references PLUS A POINT.

    Crypto Projects (names: EX) -- Specifics

    This kind of work, particularly in the early stages of a difficult cryptanalysis, is perhaps the most excruciating, exasperating, agonizing mental process known to man. Hour after hour, day after day, sometimes month after month, the cryptanalyst tortures his brain to find some relationship between the letters that hangs together, does not dead-end in self-contradiction, and leads to additional valid results. "Most of the time he is groping in the darkest night," one solver has written. "Now and again a little flicker of light gleams accross the darkness, tantalizing him with a glimpse of a path. Hopefully he dashes to it only to find himself in another labyrinth. His knowledge that night is inevitably followed by day keeps his waning courage up, and he steers his course towards where the morning sun is soon to appear. Except that sometimes he is engulfed in an interminable polar night."

    -- David Kahn

    1. E1: Aristocrat
    2. E2: Rotating Grille
    3. E3: Substitution, Vigenere
    4. E4: Recursive Key
    5. E5: Hill Cipher
    6. E6: Breaking RSA
    7. E7: El Gamal ++

    Term Projects

    Here is information about and some ideas for Term Projects . Some sample term projects from 2003 are in The Student Projects Page . Some are good, some are good examples of difficulties you can get into (if you want to know which are which, just ask!).

    ---

    This page is maintained by CB.

    Last update: 29.07.01.