San Diego State University logo

Computational Linguistics Program

Linguistics 496

Language and Codes Syllabus

    Course Description

    Goals

    This course explores the relationship of cryptography --- the mathematics of hiding information --- with codes, the best human invention for transmitting it.

    Practice

    The required text is Decrypting Cryptography. Most assigned readings are from there.

    There is also some course software available from the course website. Use of the software is never required to complete assignments or exams, but it should help make some of the course concepts clearer.

    Readings, homework, discussion, midterm, term paper.

    Concepts

    Language, linguistic levels, ciphers, monoalphabetic and polyalphabetic ciphers, ciphers in other writing systems, codes, keys, public key cryptography, RSA protocol, group theory, modular arithmetic. Zero-knowledge proofs. Digital cash. Language as a code. Information-hiding and linguistic levels. Grammars as the keys to language codes.

    Office
    Hours

    Tu Th 4:00-5:30, BAM 321

    Weekly Syllabus

    WEEK
    ONE
    Sep 8
      Readings

    Chapter 1, Cryptography Decrypted.

    Privacy, Information and Anonymity in the Information Age. Basic concepts of information-hiding. Lecture.

    Ciphers. Transposition ciphers (Caesar's cipher). Encoding and encipherment. Modular arithmetic, first appearance. Lecture.

    Assignment

    NO assignment.

    WEEK
    TWO
    Sep 15
     

    Readings

    Chapters 2, Cryptography Decrypted.

    Affine ciphers. A little more modular arithmetic. Lecture.

    General substitution ciphers. The concept of a key.

    Assignment

    Shift and affine cipher problems.

    WEEK
    THREE
    Sep 22
     

    Readings

    Chapters 3, Cryptography Decrypted.

    Discussing affine cipher problem: The concept of an inverse. The concept of a valid cipher system.

    Vigenere's Cipher. Lecture.

    Answers to assignment.

    Hill's cipher. Polyalphabetic vs monoalphabetic cipher. Transposition ciphers.

    Assignment

    Vigenere assignment.

    Hill cipher decoding problem.

    WEEK
    FOUR
    Sep 29
     

    Readings

    Decryption lecture

    Decryption workbook (includes directions for using computational tools).

    Frequency lecture

    Decrypting Vigenere.

    Chapters 4,5. Cryptography. Breaking a cipher.

    Breaking substitution ciphers.

    Data Encryption Standard (DES).

    Assignment

    Decoding problem. Crack the secret cipher!

    WEEK
    FIVE
    Oct 6
      Readings

    Discussion of decoding problem. Decoding Vigenere's cipher.

    Ciphers in other writing systems. A Japanese cipher. Lecture.

    Assignment

    Hiragana and Code difficulty assignment.

    WEEK
    SIX
    Oct 11
     

    Readings

    No readings.

    Language as a code. Decoding Egyptian Hieroglyphs and Linear B. Lecture

    Speech recognition.

    Claude Shannon's Machine Translation memo.

    Assignment

    Playing with Linear B.

    WEEK
    SEVEN
    Oct 18
     

    Readings

    Chapters 7, 8 Cryptography Decrypted.

    One-way functions. Honest games. Verification and authentication. Non-repudiation. Lecture and reading.

    Assignment

    (a) Cheating at honest games. (b) Defeating public key cryptography. (c) Forging digital signatures.

    WEEK
    EIGHT
    Oct 25
     

    Readings

    Chapters 9, 10, 11 Cryptography Decrypted. Public Key Cryptography

    Diffie Hellman. Modular arithmetic: powers and roots. Inverses. A simple symmetric key code. Euclid's algorithm: a way of finding inverses.

    Assignment

    Chapter 3, Section 1Groups, Modular Arithmetic, and Cryptography.

    Modular multiplication, powers, and roots. Inverses.

    WEEK
    NINE
    Nov 1
      Readings

    An example of groups. (pdf, ps).

    Appendix A, Cryptography Decrypted. Chapter 12, Cryptography Decrypted.

    RSA. The math.

    The advantages.

    Assignment

    Take-home Midterm.

    WEEK
    TEN
    Nov 8
     

    Readings

    Chapter 2, 3.2, Groups, Modular Arithmetic, and Cryptography.

    Why it works. Part I: introduction to group theory.

    Assignment

    Assignment for Thursday, November 10: Groups and Modular arithmetic.

    WEEK
    ELEVEN
    Nov 15
     

    Readings

    Chapter 2, 3.2, Groups, Modular Arithmetic, and Cryptography.

    Part II: The theorem of La Grange. Fermat's little theorem. Euler's theorem.

    RSA: Basic computations, verification, and signatures.

    Assignment

    Group theory problems. Are Sudoku squares groups? Modular arithmetic groups under addition and multiplication.

    WEEK
    TWELVE
    Nov 22
     

    Readings

    Zero-knowledge proof. Lecture. Digital cash: The concept. Digital cash: the protocol. Lecture.

    Assignment

    Assignment.

    WEEK
    THIRTEEN
    Nov 29
     

    Readings

    Consequences. Cyberpunks and public anonymity. Crypto-Anarchy and Virtual Communities. Tim May.

    Lecture/outline for Crypto-Anarchy and Virtual Communities.

    Happy Thanksgiving.

      Assignment

    Describe how a hit man might set up shop using (a) an internet bulletin board that anyone can post publicly viewable messages to; (b) RSA cryptography; (c) digital cash.

    What's the bug? Why isn't this a huge social problem?

    WEEK
    FOURRTEEN
    Dec 6
      Readings

    Language as code. The multi-layered structure of language. Grammar as key.

      Assignment

    TBA.

    WEEK
    FIFTEEN
    Dec 13
      Readings

    Finale.

     

    Assignment

    Take home final.  

    Place and Time

    TuTh 1100-1215 Room: NE-172

    Contact

    Mailing address:
    Department of Linguistics and Oriental Languages
    San Diego State University
    5500 Campanile Drive
    San Diego, CA 92182-7727
    Telephone: (619) 594-0252
    Office location: BAM, room 321
    Office Hours: Tu Th 4:00-5:30