16.8: The key exchange
- Page ID
- 40968
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)Substitution ciphers
In the questions below, if it specifies an alphabetic cipher, then the original map used letters only: ABCDEFGHIJKLMNOPQRSTUVWXYZ. If it specifies an alphanumeric cipher, then the original map used letters and numbers: ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789
1. Encrypt the message “SEND SUPPLIES” using an alphabetic Caesar cipher with shift 7 (mapping A to H).
2. Encrypt the message “CANCEL CONTRACT” using an alphanumeric Caesar cipher with shift 16 (mapping A to Q).
3. Decrypt the message “2R1 ONO 5SN OXM O“ if it was encrypted using an alphanumeric Ceasar cipher with shift 10 (mapping A to K).
4. Decrypt the message “RJJY NSAJ SNHJ“ if it was encrypted using an alphabetic Ceasar cipher with shift 5 (mapping A to F).
For questions 5-8 use this substitution mapping:
Original: \(\mathrm{ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789}\)
Maps to: \(\mathrm{HLCO2BQF5WRTZN1G4D8IJ6SUVK3A0X9YME7P}\)
5. Use the substitution mapping to encrypt the message “DEAR DIARY”
6. Use the substitution mapping to encrypt the message “ATTACK AT SUNRISE”
7. Use the substitution mapping to decrypt the message “Z2DQ 2D1N”
8. Use the substitution mapping to decrypt the message “Z22 IHI3 YX3”
Transposition ciphers
9. Encrypt the message “Meet in the library at ten” using a tabular transposition cipher with rows of length 5 characters.
10. Encrypt the message “Fly surveillance over the northern county” using a tabular transposition cipher with rows of length 8 characters.
11. Decrypt the message “THE VHI NIE SAN SHT STI MQA DAN SDR S“ if it was encrypted using a tabular transposition cipher with rows of length 7 characters.
12. Decrypt the message “DOLR UTIR INON KVEY AZ“ if it was encrypted using a tabular transposition cipher with rows of length 6 characters.
13. Encrypt the message “Buy twenty million” using a tabular transposition cipher with the encryption keyword “RENT”.
14. Encrypt the message “Attack from the northeast” using a tabular transposition cipher with the encryption keyword “POWER”.
15. Decrypt the message “RYL OEN ONI TPM IEE YTE YDH WEA HRM S” if it was encrypted using a tabular transposition cipher with the encryption keyword “READING”.
16. Decrypt the message “UYH SRT ABV HLN SEE L” if it was encrypted using a tabular transposition cipher with the encryption keyword “MAIL”.
Shifting substitution ciphers
17. Encrypt the message “SEND SUPPLIES” using an alphabetic Caesar cipher that starts with shift 7 (mapping A to H), and shifts one additional space after each character is encoded.
18. Encrypt the message “CANCEL CONTRACT” using an alphabetic Caesar cipher that starts with shift 5 (mapping A to F), and shifts one additional space after each character is encoded.
Modular arithmetic
19. Compute
- \(15 \bmod 4\)
- \(10 \bmod 5\)
- \(257 \bmod 11\)
20. Compute
- \(20 \bmod 4\)
- \(14 \bmod 3\)
- \(86 \bmod 13\)
21. Determine if 4 is a generator modulus 11
22. Determine if 2 is a generator modulus 13
23. Use the modular exponent rule to calculate \(157^{10} \bmod 5\)
24. Use the modular exponent rule to calculate \(133^{8} \bmod 6\)
Diffie-Hellman-Merkle key exchange
25. Suppose you are doing a key exchange with Marc using generator 5 and prime 23. Your secret number is 7. Marc sends you the value 3. Determine the shared secret key.
26. Suppose you are doing a key exchange with Jen using generator 5 and prime 23. Your secret number is 4. Jen sends you the value 8. Determine the shared secret key.
RSA
27. Suppose that Alice has computed \(n=33, e=7,\) and \(d=3\). Show how Bob would encrypt the message 5 and how Alice would then decrypt it.
28. Suppose that Alice has computed \(n=55, e=7,\) and \(d=13\). Show how Bob would encrypt the message 8 and how Alice would then decrypt it.
Extensions
29. To further obscure a message, sometimes the usual alphabet characters are replaced with other symbols. Design a new set of symbols, and use it to encode a message. Exchange with a friend and see if they can decode your message.
30.To make an encryption harder to break, sometimes multiple substitution and transposition ciphers are used in sequence. For example, a method might specify that the first letter of the encryption keyword be used to determine the initial shift for a Caesar cipher (perhaps with a rotating cipher), and also be used for a transposition cipher. Design your own sequence of encryption steps and encrypt a message. Exchange with a friend and see if they can follow your process to decrypt the message.
31. When using large primes, computing values like \(67^{24} \bmod 83\) can be difficult on a calculator without using additional tricks, since \(67^{24}\) is a huge number. We will explore an approach used.
- Notice that \(67^{2} \bmod 83\) is fairly easy to calculate: \(67^{2} \bmod 83=4489 \bmod 83=7\). Since \(67^{4}\) mod \(83=\left(67^{2}\right)^{2}\) mod 83 can be rewritten using the modular exponent rule as \(\left(67^{2} \bmod 83\right)^{2} \bmod 83,\) this is also easy to evaluate:\(67^{4} \bmod 83=\left(67^{2} \bmod 83\right)^{2} \bmod 83=7^{2} \bmod 83=49\) This process can be continued to find \(67^{8}\) mod 83 as \(\left(6^{4}\right)^{2}\) mod 83 . Find this value, then find \(67^{16} \bmod 83\) and \(67^{32} \bmod 83\)
- There is a rule that \((a b) \bmod n=(a \bmod n)(b \bmod n) \bmod n\) Noting that \(17000=170 \times 100\), calculate 17000 mod 83 using the rule above.
- Note that \(67^{5}=67^{4} 67 .\) Use this, along with the rule from above and the results from part \(a\) to compute \(67^{5}\) mod 83
- Note that \(67^{7}=67^{4+2+1}=67^{4} 67^{2} 67^{1} .\) Compute \(67^{7}\) mod 83.
- Write \(67^{24}\) as a product of powers of \(67,\) and use this to compute \(67^{24}\) mod 83
32. Use the process from the previous question to evaluate \(23^{34} \bmod 37\).
33. To encrypt text messages with RSA, the words are first converted into a string of numbers, and then encrypted. Several characters are usually combined together to produce a message number smaller than the modulus, but approximately the same size. Look up an ASCII table to convert the message “SCALE THE WALLS” to numbers, then encrypt it using the RSA public key \(n=10823, e=5\). Since ASCII characters are two digits, pair up characters to form four-digit numbers before encoding. For example A is 65 and B is 66, so the character pair AB could be treated as the number 6566 and encrypted as 10148
34. Explore approaches to steganography that don’t require specialized software. Attempt to hide a message using one of these techniques, and see if a fellow student can detect the message.
35. When you visit a secure website, your web browser will report that the site’s identity has been verified by a third party, called a certificate authority. This is meant to assure you that you are visiting the actual company’s website. Research how these certificates work.
