Homework 10: Modular Arithmetic

Due 05.Apr.19 (Tue)

Before you tackle the homework, remind yourself of our general hw policies

Reading: Rosen §§ 6.2, 2.4, 2.5.

1. (3pts) Section 6.2, #6 (p.423): dit,dah1,dah2
   (Deferred from next week)
   After you set up a recurrence relation with initial conditions, I suggest you work out a few terms by hand before solving the recurrence, to get a feel for how the sequence grows.
2. (3pts) Section 6.2, #8 (p.423): average lobsters
   (Deferred from next week)
3. (3pts) Section 2.4, #4 (p.166). (| transitive)
4. (1pt) Section 2.4, #16 (p.167). (relative primes of 12.)
5. (1pt) Section 2.4, #38 (p.167). (congruences to 4, mod 12.)
6. (4pts) Section 2.4, #42 (p.168). ((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.
7. (3pts) Explain the Flash Mind Reader (or any of its variants). (Flash plug-in required).
   Your explanation shouldn't contain unsubstantiated claims about properties of sums of a numeral's digits; if you want to argue about such numerals, name the parts and show the property holds (as in lecture, about casting out 11ses).

8. (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. 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.)

9. (3pts) For the preceding program, write a first-order logic formula expressing the general concept hinted at in the final test-case above. Also, write a second formula specifying some other property of the code. For each, give a short sentence about whether you consider this a good property a a bad property for a cipher system to have?
10. (3pts) Section 2.4, #56 (p.168). (ISBN check-sum)
11. (3pts) Section 2.5, #20 (p.180). (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.
12. (3pts) Section 2.5, #24 (p.180). (Euclid's algorithm)
13. (4pts) Section 2.6, #48 (p.196). (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.

14. (Extra credit 4pts) Consider the following naive public-key system (as described 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 knows the private key q, a number such that q⋅(p⋅m) ≡ m (mod N) (thus un-doing the encryption). You overhear only the encrypted message (number) x, and you can also look up the public key ⟨p,N⟩, but you aren't directly given the private key q.

    (Attempt to) break the following messages. without using a high-level math program like Mathematica, Maple, or Matlab, since they know how to break this cipher built-in. (Any 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. ( 1pt) The encrypted message x = "=", and the public key is p=51, N=101. What was the original secret message?
    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 = "rs_[S$i;M<#" and the public key is p=1234567890111213141516, N=10²² + 9. What was the original secret message?