Chapter 4: Number Theory and Cryptography

Convert (7345321)8 to its binary expansion and (10 1011 1011)2 to its octal expansion.

Determine whether the check digit of the ISBN-10 for this textbook (the seventh edition of Discrete Mathematics and its Applications) was computed correctly by the publisher.

Encrypt the message APPLES AND ORANGES using a shift chipper with key k=13 .

Use Dirichlet’s theorem, which states there are infinitely many primes in every arithmetic progression ak + b where gcd(a, b) =1, to show that there are infinitely many primes that have a decimal expansion ending with a 1.

The vigenere cipher is a block cipher, with a key that is a string of letters with numerical equivalents${\mathbf{k}}_{\mathbf{1}}\mathbf{,}{\mathbf{k}}_{\mathbf{2}}\mathbf{\dots }\mathbf{.}{\mathbf{k}}_{\mathbf{m}}\mathbf{,}$where for ${\mathbf{k}}_{\mathbf{i}}\mathbf{\in }{\mathbf{Z}}_{\mathbf{26}}\mathbf{}\mathbf{for}\mathbf{}\mathbf{i}\mathbf{=}\mathbf{1}\mathbf{,}\mathbf{2}\mathbf{,}\mathbf{\dots }\mathbf{,}\mathbf{m}$. Suppose that the numerical equivalents of the letters of a plain text block are ${\mathbf{p}}_{\mathbf{1}}\mathbf{,}{\mathbf{p}}_{\mathbf{2}}\mathbf{\dots }\mathbf{.}{\mathbf{p}}_{\mathbf{m}}$ . The corresponding numerical cipher text block is $\mathbf{(}{\mathbf{P}}_{\mathbf{1}}\mathbf{+}{\mathbf{K}}_{\mathbf{2}}\mathbf{)}\mathbf{mod}\mathbf{26}\mathbf{(}{\mathbf{p}}_{\mathbf{2}}\mathbf{+}{\mathbf{k}}_{\mathbf{2}}\mathbf{)}\mathbf{mod}\mathbf{26}\mathbf{\dots }\mathbf{(}{\mathbf{p}}_{\mathbf{m}}\mathbf{+}{\mathbf{k}}_{\mathbf{m}}\mathbf{)}\mathbf{mod}\mathbf{26}$. Finally, we translate back to letters. For example, suppose that the key string is RED, with numerical equivalents $\mathbf{1743}$.Then, the plain text ORANGE with numerical equivalents $\mathbf{141700130604}$is encrypted by first splitting it into twoblocks $\mathbf{141700}\mathbf{}\mathbf{and}\mathbf{}\mathbf{130604}$. Then, in each block we shift the first letter by17, the second by4and the third by3. We obtain $\mathbf{52103}\mathbf{}\mathbf{and}\mathbf{}\mathbf{041007}$. The cipher text is$\mathbf{FVDEKH}\mathbf{}$

18. Use the Vigenere cipher with key BLUEto encrypt the messageSNOWFALL

Show that if a is an integer and d is an integer greater than 1, then the quotient and remainder obtained when a is divided by d are (a/d) and a – d(a/d), respectively.

(a) Generalize the result in part (a) of exercise 16; that is, show that ifis a prime, the positive integers less than $\mathit{p}\mathbf{-}\mathbf{1}$, except 1 and , can be split into pairs$\mathbf{(}\mathit{p}\mathbf{-}\mathbf{3}\mathbf{)}\mathbf{/}\mathbf{2}$ of integers such that each pair consists of integers that are inverses of each other.[Hint: Use the result of Exercise: 17]

(b) From part (a) conclude that$\mathbf{(}\mathbf{p}\mathbf{-}\mathbf{1}\mathbf{)}\mathbf{!}\mathbf{\equiv }\mathbf{-}\mathbf{1}\mathbf{(}\mathbf{mod}\mathbf{p}\mathbf{)}$whenever is prime. This result is known as Wilson’s theorem.

(c) What can we conclude ifis a positive integer such that role="math" localid="1668689516754" $\mathbf{(}\mathbf{n}\mathbf{-}\mathbf{1}\mathbf{)}\mathbf{!}\mathbf{\not\equiv }\mathbf{-}\mathbf{1}\mathbf{(}\mathbf{mod}\mathbf{n}\mathbf{)}$?

Give a procedure for converting from the hexadecimal expansion of an integer to its octal expansion using binary notation as an intermediate step.

The United States Postal Service (USPS) sells money orders identified by an 11-digit number $\mathbf{\times }\mathbf{1}\mathbf{\times }\mathbf{2}\mathbf{\dots }\mathbf{\times }\mathbf{11}\mathbf{.}$The first ten digits identify the money order; x11 is a check digit that satisfies $\mathbf{\times }\mathbf{11}\mathbf{=}\mathbf{\times }\mathbf{1}\mathbf{+}\mathbf{\times }\mathbf{2}\mathbf{+}\mathbf{\cdots }\mathbf{+}\mathbf{\times }\mathbf{10}\mathbf{mod}\mathbf{9}$.

18. Find the check digit for the USPS money orders that have

identification number that starts with these ten digits.

a) 7555618873

b) 6966133421

c) 8018927435

d) 3289744134

(a) What is the difference between a public key and a private key cryptosystem?

(b) Explain why using shift chippers is a private key system.

(c) Explain why the RSA cryptosystem is a public key system.