Introduction to Cryptography: exercises

Practice (17)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

1. Encode IXLOVEXMATH using the cryptosystem in .

   Zbulo përgjigjen

   Hint:

   LAORYHAPDWK

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

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?

   Zbulo përgjigjen

   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?

   Zbulo përgjigjen

   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\).

6. Given the matrix \[\begin{aligned}\end{aligned}\], use the encryption function \(f({\mathbf p}) = A {\mathbf p} + {\mathbf b}\) to encode the message CRYPTOLOGY, where \({\mathbf b} = ( 2, 5)^\transpose\). 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\), 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\)

   Zbulo përgjigjen

   Hint:

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

8. Compute the decoding key \(D\) for each of the encoding keys in .

9. Decrypt each of the following RSA messages \(y\).

   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\)

   Zbulo përgjigjen

   Hint:

   (a) \(31\) (c) \(14\).

10. For each of the following encryption keys \((n, E)\) in the RSA cryptosystem, compute \(D\).

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

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

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

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

    Zbulo përgjigjen

    Hint:

    (a) \(n = 11 \cdot 41\); (c) \(n = 8779 \cdot 4327\).

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\), \(E\), and \(X\) such that \[\begin{aligned}\end{aligned}\]. 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.

14. A better algorithm for factoring odd positive integers is Fermat's factorization algorithm.

    1. Let \(n= ab\) be an odd composite number. Prove that \(n\) can be written as the difference of two perfect squares: \[\begin{aligned}\end{aligned}\]. Consequently, a positive odd integer can be factored exactly when we can find integers \(x\) and \(y\) such that \(n = x^2 - y^2\).

    2. Write a program to implement the following factorization algorithm based on the observation in part (a). The expression ceiling(sqrt(n)) means the smallest integer greater than or equal to the square root of \(n\). Write another program to do factorization using trial division and compare the speed of the two algorithms. Which algorithm is faster and why?

15. Recall Fermat's Little Theorem from . Let \(p\) be prime with \(\gcd(a, p) = 1\). Then \(a^{p-1} \equiv 1 \pmod{p}\). We can use Fermat's Little Theorem as a screening test for primes. For example, \(15\) cannot be prime since \[\begin{aligned}\end{aligned}\]. However, \(17\) is a potential prime since \[\begin{aligned}\end{aligned}\]. We say that an odd composite number \(n\) is a pseudoprime if \[\begin{aligned}\end{aligned}\]. Which of the following numbers are primes and which are pseudoprimes?

    1. \(342\)

    2. \(811\)

    3. \(601\)

    4. \(561\)

    5. \(771\)

    6. \(631\)

16. Let \(n\) be an odd composite number and \(b\) be a positive integer such that \(\gcd(b, n) = 1\). If \(b^{n-1} \equiv 1 \pmod{n}\), then \(n\) is a pseudoprime base \(b\). Show that \(341\) is a pseudoprime base \(2\) but not a pseudoprime base \(3\).

17. Write a program to determine all primes less than \(2000\) using trial division. Write a second program that will determine all numbers less than \(2000\) that are either primes or pseudoprimes. Compare the speed of the two programs. How many pseudoprimes are there below \(2000\)?

    There exist composite numbers that are pseudoprimes for all bases to which they are relatively prime. These numbers are called Carmichael numbers. The first Carmichael number is \(561 = 3 \cdot 11 \cdot 17\). In 1992, Alford, Granville, and Pomerance proved that there are an infinite number of Carmichael numbers [4]. However, Carmichael numbers are very rare. There are only \(2163\) Carmichael numbers less than \(25 \times 10^9\). For more sophisticated primality tests, see [1], [6], or [7].

Provo timen.

Parts of this page are adapted from Judson, Abstract Algebra: Theory and Applications (GFDL 1.3). Condensed and re-explained here; errors are ours.

Më shumë në Abstract Algebra

GroupsSubgroups, cosets and Lagrange's theoremCyclic groups and permutation groupsHomomorphisms, normal subgroups and quotient groupsRings and fieldsGalois theory: why the quintic has no formula