Hw09: Modular Arithmetic

Due 04.Apr.06 (Tue) 17:00.

Before you tackle the homework, remind yourself of our general hw policies (includes proof-by-induction tips).

Reading: Rosen 2.4-2.6.

1. (3pts) Section 2.4, #4 (p.166). (4ed: p.126 #4.) (| transitive)
2. (1pt) Section 2.4, #16 (p.167). (4ed: p.126 #14.) (relative primes of 12.)
3. (1pt) Section 2.4, #38 (p.167). (4ed: p.126 #30.) (congruences to 4, mod 12.)
4. (4pts) Section 2.4, #42 (p.168). (4ed: p.126 #34.) ((a ≡ b ∧ c ≡ d;) ⇒ (a-c ≡ b-d).)
   If m=1, is this true? (Does it even make sense?) Explain why or why not, in one sentence.

5. (5pts) Write a function to encode messages by the shift-cipher, as described in Rosen.

   ;; shift: string/lowercase, number → string/lowercase
   ;; (Where "string/lowercase" means "{a,...,z}*".)
   ;; Encode lower-case strings by the shift cipher, as sketched in Rosen.
   ;; Output not specified for other inputs, e.g. upper case, spaces, punctuation.
   ;;
   (define (shift msg offset) ...)
   
   ;Examples:
   (shift "pizza"  1) = "qjaab"
   (shift "bialy" -2) = "zgyjw"
   (shift "pez"   52) = "pez"
   (shift (shift "indecipherable" 17) -17) = "indecipherable"
   

   What are some other, more trivial, test-cases? You may use any language, though your solution should be well-written in any language. Clarify for future years: Turn in your hardcopy, including test cases. Of course, if your solution involves two distinct tasks, then clear code will have a distinct function for each task (plus any helpers). (The solution set's version is 8 lines, plus comments and test cases). If using scheme, you may use the provided teachpack, which also mentions scheme string- and character- processing functions.

   Note that in ASCII, unlike Rosen, the numeric value corresponding to the character #\a isn't 0 or 1, but some positive integer constant. (As always in your programs, don't use magic numbers.)

6. (3pts) For the preceding program, write a first-order logic formula expressing the general concept hinted at in the final test-case. Also, write another formula specifying some other property of the problem. For each, give a short sentence about whether this property is (a) necessary, or (b) good for a cipher system to have?
7. (3pts) Section 2.4, #56 (p.168). (4ed: p.127, #48) (ISBN check-sum)
8. (3pts) Section 2.5, #20 (p.180). (4ed: let me know) (123¹⁰⁰¹ mod 101)
   You may find it more intuitive to proceed top-down, rather than the book's bottom-up approach:
   123¹⁰⁰¹ ≡ 123*(123²)⁵⁰⁰ ≡ ... (mod 101).
   Do this by hand (perhaps with a machine for intermediate calculations), though presumably you'll double-check your final answer with mathematica or drscheme (“expt").
   You don't need to show your work.
9. (3pts) Section 2.5, #24 (p.180). (4ed: let me know) (Euclid's algorithm)
10. (4pts) Section 2.6, #48 (p.196). (4ed: let me know) (extended Euclid's algorithm)
    You'll want to first work through Example 1 (p.182), to get an intuition of what the algorithm is doing.

11. Extra credit 6 4pts) Consider the following naive public-key system given in Thursday's lecture: a message m is sent by finding the recipient's public key p,N, calculating the encrypted version x = p*m mod N, and sending x. (The recipient presumably knows the private key q, a number such that q*(p*m) mod N ≡ m (thus un-doing the encryption).) You overhear the encrypted message (number) x, and can also look up the public key p,N, but you don't know the private key q.

    (Attempt to) break the following messages. without using a high-level math program like Mathematica, Maple, or Matlab. (General purpose programming languages are okay.) Describe your approach to breaking the code; if other feasible methods also occur to you, describe them very briefly.

    In each case, the messages (strings) are converted to/from integers in the following way:

    • Identify a number in [0,100) with an individual character by taking the number, adding the ascii code for #\space, and interpreting the result as an (extended) ascii code. (Note that this allows for one funny character¹ to result: 95 maps to ascii DEL.) E.g., "A" corresponds with 33.
    • Identify a number ≥ 100 with a string, by writing it as a base-10 numeral, and taking pairs of digits as individual letters. (Pad the front with a leading 0 if necessary, to make the numeral even-length.) E.g., "AB" corresponds with 3334.
    1. (2 1pt) The encrypted message x = "=", and the public key is p=51, N=101. What was the original secret message?
    2. (2 1pt) The encrypted message x = ":.^", and the public key is p=654321, N=1000003. What was the original secret message?
    3. (2pts) The encrypted message x = "$oDST~ Kw.Y" "rs_[S$i;M<#" and the public key is p=1234567890111213141516, N=10²² + 7 9. What was the original secret message?