exercises-crypt.ipynb

Kernel:

%%html
<link href="http://mathbook.pugetsound.edu/beta/mathbook-content.css" rel="stylesheet" type="text/css" />
<link href="https://aimath.org/mathbook/mathbook-add-on.css" rel="stylesheet" type="text/css" />
<style>.subtitle {font-size:medium; display:block}</style>
<link href="https://fonts.googleapis.com/css?family=Open+Sans:400,400italic,600,600italic" rel="stylesheet" type="text/css" />
<link href="https://fonts.googleapis.com/css?family=Inconsolata:400,700&subset=latin,latin-ext" rel="stylesheet" type="text/css" /><!-- Hide this cell. -->
<script>
var cell = $(".container .cell").eq(0), ia = cell.find(".input_area")
if (cell.find(".toggle-button").length == 0) {
ia.after(
    $('<button class="toggle-button">Toggle hidden code</button>').click(
        function (){ ia.toggle() }
        )
    )
ia.hide()
}
</script>

Important: to view this notebook properly you will need to execute the cell above, which assumes you have an Internet connection. It should already be selected, or place your cursor anywhere above to select. Then press the "Run" button in the menu bar above (the right-pointing arrowhead), or press Shift-Enter on your keyboard.

ParseError: KaTeX parse error: \newcommand{\lt} attempting to redefine \lt; use \renewcommand

Section7.3Exercises

¶

1

Encode IXLOVEXMATH using the cryptosystem in Example 1.

Hint

LAORYHAPDWK

2

Decode ZLOOA WKLVA EHARQ WKHA ILQDO, which was encoded using the cryptosystem in Example 1.

3

Assuming that monoalphabetic code was used to encode the following secret message, what was the original message?

APHUO EGEHP PEXOV FKEUH CKVUE CHKVE APHUO
EGEHU EXOVL EXDKT VGEFT EHFKE UHCKF TZEXO
VEZDT TVKUE XOVKV ENOHK ZFTEH TEHKQ LEROF
PVEHP PEXOV ERYKP GERYT GVKEG XDRTE RGAGA

What is the significance of this message in the history of cryptography?

Hint

Hint: V = E, E = X (also used for spaces and punctuation), K = R.

4

What is the total number of possible monoalphabetic cryptosystems? How secure are such cryptosystems?

Hint

$26! - 1$

5

Prove that a $2 \times 2$ matrix $A$ with entries in ${\mathbb Z}_{26}$ is invertible if and only if $\gcd( \det(A), 26 ) = 1\text{.}$

6

Given the matrix

$$\begin{equation*} A = \begin{pmatrix} 3 & 4 \\ 2 & 3 \end{pmatrix}, \end{equation*}$$

use the encryption function $f({\mathbf p}) = A {\mathbf p} + {\mathbf b}$ to encode the message CRYPTOLOGY, where ${\mathbf b} = ( 2, 5)^{\rm t}\text{.}$ What is the decoding function?

7

Encrypt each of the following RSA messages $x$ so that $x$ is divided into blocks of integers of length 2; that is, if $x = 142528\text{,}$ encode 14, 25, and 28 separately.

1. $n = 3551, E = 629, x = 31$

2. $n = 2257, E = 47, x = 23$

3. $n = 120979, E = 13251, x = 142371$

4. $n = 45629, E = 781, x = 231561$

Hint

(a) 2791; (c) 112135 25032 442.

8

Compute the decoding key $D$ for each of the encoding keys in Exercise 7.

9

Decrypt each of the following RSA messages $y\text{.}$

1. $n = 3551, D = 1997, y = 2791$

2. $n = 5893, D = 81, y = 34$

3. $n = 120979, D = 27331, y = 112135$

4. $n = 79403, D = 671, y = 129381$

Hint

(a) 31; (c) 14.

10

For each of the following encryption keys $(n, E)$ in the RSA cryptosystem, compute $D\text{.}$

1. $(n, E) = (451, 231)$

2. $(n, E) = (3053, 1921)$

3. $(n, E) = (37986733, 12371)$

4. $(n, E) = (16394854313, 34578451)$

Hint

(a) $n = 11 \cdot 41\text{;}$ (c) $n = 8779 \cdot 4327\text{.}$

11

Encrypted messages are often divided into blocks of $n$ letters. A message such as THE WORLD WONDERS WHY might be encrypted as JIW OCFRJ LPOEVYQ IOC but sent as JIW OCF RJL POE VYQ IOC. What are the advantages of using blocks of $n$ letters?

12

Find integers $n\text{,}$ $E\text{,}$ and $X$ such that

$$\begin{equation*} X^E \equiv X \pmod{n}. \end{equation*}$$

Is this a potential problem in the RSA cryptosystem?

13

Every person in the class should construct an RSA cryptosystem using primes that are 10 to 15 digits long. Hand in $(n, E)$ and an encoded message. Keep $D$ secret. See if you can break one another's codes.