Cryptology by Discovery: An Introduction to Conjecture and Proof

1.

This message has word breaks preserved.

OBR GC WH PSUWBG.

2.

This message has been grouped into blocks of 5 letters; thus, spaces do not indicate spaces between words. (After all, the first was really too easy, right?)

DRODB YELVO SCIYE DRSXU IYERK FODSW OLENN RK

3.

Another blocked message.

PNUPK XAPDA NWEJX KSEJO KIAKJ AOYHK QZIWU WWJCA HKQ

4.

What are your strategies for breaking these ciphers?

1.

Determine if the following statements are true or false.

1. \(\displaystyle 100 \equiv 22 \pmod{26}\)
2. \(\displaystyle -3 \equiv 17 \pmod{26}\)
3. \(\displaystyle -3 \equiv 23 \pmod{26}\)
4. \(\displaystyle 123 \equiv 58 \pmod{26}\)
5. \(\displaystyle 24 \equiv -2 \pmod{26}\)

2.

Determine if the following statements are true or false.

1. \(\displaystyle 17 \equiv 77 \pmod{10}\)
2. \(\displaystyle 138 \equiv 225 \pmod{3}\)
3. \(\displaystyle 5 \equiv -1 \pmod{4}\)
4. \(\displaystyle 16 \equiv 4 \pmod{12}\)
5. \(\displaystyle 100 \equiv 301 \pmod{25}\)

3.

Reduce each of the following numbers mod 10. (Reduce means to find the smallest positive integer that is congruent to the given number mod 10.) 139,65,-290,-77,201

4.

Reduce each of the following numbers mod 26. (Reduce means to find the smallest positive integer that is congruent to the given number mod 26.) 139,65,-290,-77,201.

5.

List at least seven solutions (some positive and some negative) to the equation \(x \equiv 6 \pmod{10}\text{.}\) Then find a way to describe all solutions to the equation.

6.

Take a pair of numbers in your above list (of solutions to the equation \(x \equiv 6 \pmod{10}\)) and subtract them. Repeat until you notice a pattern. Make a conjecture.

7.

List at least seven solutions (some positive and some negative) to the equation \(x \equiv 6 \pmod{11}\text{.}\) Then find a way to describe all solutions to the equation.

8.

Take a pair of numbers in your above list and subtract them. Repeat until you notice a pattern. Make a conjecture.

1.

Click evaluate to run the code as is. What happens with the ciphertext that is bad for a monoalphabetic cipher? Why?

2.

Change the entries on the second and third line inside the first box. That is, change the values for plaintext and shift. (Remember to click evaluate after you have changed the code to run it with the new code.) What happens?

3.

What is the code doing? That is, what do the variables ASCII, numbers, shifted, asciishift, and ciphertext represent?

4.

Let's fix the problem in question 1. Change the code as follows. In the 5th line change ASCII=[ord(c) for c in plaintext]   to   ASCII=[ord(c) for c in plaintext.upper()]    Then click evaluate to run the new code. What changed?

5.

What would you need to change to encrypt more than just the 26 (capital) letters of the alphabet?

6.

Refresh the browser to go back to the original code. Then make the following changes to the code and explain what happens. (Remember to click evaluate after making both changes below.)

1. Change line 9 from shifted=[(c+shift) %26 for c in numbers]   to   shifted=[(c+shift) for c in ASCII]   . That is, remove the %26 AND change numbers to ASCII.

2. Change line 11 from asciishift=[c+65 for c in shifted]    to   asciishift=[c %128 for c in shifted] . That is, change the c+65 to c%128.

1.

Find a mathematical formula \(CT=f(PT)\) for the decimation cipher by 3. The standard numbering for the alphabet has been added to help you. Fill in the corresponding numbers in the bottom row for the ciphertext to help you find the mathematical formula. For example, your function \(f(x)\) should satisfy \(f(0)=0\) and \(f(1)=9\text{.}\)

2.

Decrypt the message USK SXKAE.

3.

Fill out the table for the decimation by 5 and decrypt OJTAUVGTTK.

4.

Find the formula for \(CT=f(PT)\) for the decimation cipher by 5.

5.

Fill out a table and find a formula for the decimation by 4 instead of by 3. What goes wrong and why?

6.

Going back to your original formula for \(CT=f(PT)\) for a decimation by 3. Can you find a decryption formula? That is, find a function \(g\) such that \(PT=f(CT)\text{.}\)

7.

What if the starting location of A is changed? What would the encrypting formula be if the A started out under the C and then continued filling in the cipher text by skipping every two letters?

1.

Encrypt the plaintext USE CODE B with formula \(CT \equiv 2 * PT \pmod{26}.\) What goes wrong?

2.

Let's return to exploring with Sage. Alter the shift program we used before to change it from a shift cipher to a multiplicative cipher. Then try all the possible multiplicative ciphers and make some conjectures about which multipliers are good and which are bad.

1.

Find multiplicative inverses for each of 1,3,5,7,9,11,15,17,19,21,23 and 25 mod 26. (Remember you are solving the equation \(3x \equiv 1 \pmod{26}\) to find the multiplicative inverse of 3 mod 26.)

2.

Find the decryption formula (that is, find \(a\) in the decryption formula \(PT=aCT \pmod{26}\)) and decrypt the following message which was enciphered with a multiplicative cipher.

ZQYI XCV AXXQNI

3.

Find the decryption formula (that is, find \(a\) in the decryption formula \(PT=aCT \pmod{26}\)) and decrypt the following message which was enciphered with a multiplicative cipher.

RIU SANK SEXJMDXMQAJMZG QMDRGTO

1.

Decrypt the following message (you'll have to figure out the correct starting point): UFJHCFR

2.

Find the mathematical formula for encryption that corresponds to the decryption setting for the previous problem, that is, find the function \(f\) such that \(f(PT)=CT\) using our usual numerical representation for letters, A=0, B=1, etc.

3.

Find the decryption formula. What do you notice?

4.

Find a generic encryption formula for this wheel (for all the different initial settings.).

5.

Find the general decryption formula that goes with your above encryption formula.

6.

What are the pros and cons of this cipher wheel versus the first one you made?

7.

For which shifts, will letters be enciphered as themselves with this cipher wheel? How many letters will there be? Explain why using modular arithmetic.

1.

Decrypt the ciphertext message RXBDSYZYHFJDQPGHJFZKFMXSFGAFHSDRGNDCYFDGA using the values of multiplier \((a)=15\) and additive \((b)=7\text{.}\)

2.

Solve for the decryption formula for an affine cipher given the information below. That is, solve for \(a\) and \(b\) where \(PT= aCT+b\) mod 26. Which \(a\) and \(b\) correspond to a valid affine cipher (i.e., one that can be decrypted uniquely)?

1. H is encrypted as X and G is encrypted as K.

2. A is encrypted as O and I is encrypted as U.

3. B is encrypted as O and I is encrypted as U.

4. B is encrypted as O and J is encrypted as V.

3.

Let's put all of this together to break some affine ciphertexts! Use the Sage code to break the Affine Ciphers below. Use the frequency information to help match plaintext and ciphertext to solve for \(a\) and \(b\text{.}\) Note you should solve for the decryption formula \(PT= aCT+b\) mod 26.

1. NTUJL XEOBW HDZJC LQEJV BRGCR DJNTG HFUNB FJWHU CLKBG CELNB QVBRW DJEJV BRGCD BGBUX HDEJC LCUKK HZJLK BRKBQ NTXHW CJUJW LVNBW JVHNO J

2. JSLWR SFGEL VCRTA REJIR GLETL HRGLE HLGNL HAJWF IRSRA KLWRC IKRAT FNKZN KLISZ WRILG ZWCLX IBKJI KZTGX IXERK LSCTK ZTARE TLWJS ATFNK ZNJCM ZTLEI RSSTK ZHFLX JERVL ZWVIL HRRIJ YRJXI ZGXSF LXWVV ZESBK LBZSS BJWII LDWLB RMREF IKZWV JYLXI FLXIK RGELV ZTIKE ZSSRC JWCTJ FTIKZ TZTVE RJIBK RERBZ SSZHR RIKRE JIBLE DJIJA JEIFW LTJFT IKRAT FNKZN ZWJYZ LSLVF NSJTT

3. CTCWY DQITW IDAGF CHVAA PFYVA NPCZY PMCDD EYPZA NIPAV ACSZY TSDGB NYPMW INPYP MZFAQ EIKAS BZFAT CZFAN WIDAG ZSOKF YGFAC HISZI TZFAF IDACP HDIIK AHCNI SPHWI ZFANW IDAFA OCDDA HVCOK HIEPZ FAFID AOIWA SBFAN AYGWA DDFIP AQTNA GFWCH AFIPA QZFAW IZFAN WIDAN CPSBC PHGUS AAJAH YPPAX ZZIFY WZFCZ GPIZF IPAQZ FCZGW CBDAG QNSBY GWADD WCBDA GQNSB ZFAVC VQWID AGZYD DHIEP YPZFA FIDAE CGGSD KYPMY OCPZG WADDC PQZFY PMHIE PFANA VSZWI DCGGA G

1.

Both messages below were encrypted with keyword columnar substitutions. One uses the word PIRATE and the other SAILOR. Decrypt them!

GKYBNVSYQGVYPTNVYSTSULYHSJA

FJYVYTOULBNVTYQFVYSONVY

2.

A general monoalphabetic cipher is just a random permutation of the alphabet. (No keyword, no formula.) The general monoalphabetic cipher below has the word WEATHER in it somewhere. Use that clue combined with the given frequency information to determine the location of the plaintext WEATHER and then decrypt the message.

AJUGB UJLBG IPZPH GIPCU XUPGP UGIRJ EGIPY PJYQP LJVQA UGRGH CGHLJ UKPCR HGXJU XEXGA XAUGL IHUTP JULPX UHZIX QPBXU IVWWH CA

The frequency count for single letters that occur at least twice:

The frequency count for digraphs that occur at least three times:

The frequency count for trigraphs that occur at least twice: