CEMC Banner

Grade 11/12 Math Circles
Cryptography, Part 2 - Solutions

Exercise Solutions

Exercise 1

Compute the following greatest common divisors by factoring the integers as products of primes.

  1. gcd(11,31)

  2. gcd(629,357)

  3. gcd(36652,68552)

Exercise 1 Solution

  1. Both 11 and 31 are prime numbers, so they have no prime factors in common. Note that 1 divides every number, and so 1 must be the largest number that divides both the primes 11 and 31. In other words, gcd(11,31)=1.

  2. We try to factor both of 629 and 357 into primes by trial divison. After some time, we get 629=1737357=3717. Only 17 is a prime common to both factorizations, and so gcd(629,357)=17.

  3. Again, we aim to factor both 36652 and 68552 into primes. With some trial-and-error division, we get 36652=229163=2277187=2277111768552=2228569=22211779=222111941. We see that the overlap between the two factorizations is two 2s and an 11, so gcd(36652,68552)=2211=44.

Exercise 2

Use the Euclidean algorithm to calculate the following gcds:

  1. gcd(36652,68552) (this was done in Exercise 1 in another way)

  2. gcd(4019881,10394)

Exercise 2 Solution

  1. We start by dividing 68552 by 36652 with remainder, which gives us 68552=136652+31900. Next, we take 36652 and divide it by the remainder 31900: 36552=131900+4752. Continuing, we take 31900 and divide it by the new remainder 4752: 31900=64752+3388. We now continue this process of taking the divisor from the previous step and dividing it by the remainder from the previous step, until we reach a remainder of 0. 4752=13388+13643388=21364+6601364=2660+44660=1544+0 From here, the last non-zero remainder is our gcd (in this case, 44). We conclude that gcd(36652,68552)=44, which should confirm one of your answers from Exercise 1!

  2. As above, we repeatedly perform divisions with remainder, starting with 4019881 by 10394, and then dividing the divisor from each step by the remainder from that same step. 4019881=38610394+779710394=17797+25977797=32597+62597=4326+56=15+15=51+0. The last non-zero remainder is 1, and so gcd(4019881,10394)=1.

Exercise 3

Using the Extended Euclidean algorithm, find integers x and y satisfying each of the following equations:

  1. 28x+12y=4 (Hint: We calculated gcd(28,12) using the Euclidean algorithm earlier.)

  2. 63x+91y=7

Exercise 3 Solution

  1. Earlier in the lesson, we checked that gcd(28,12)=4 using the following divisions with remainder: 28=212+412=34+0. When we ignore the last line and re-write the first one with the remainder by itself, 4=28212, we have already written 4 as a multiple of 28 plus a multiple of 12. Thus, we see that a solution to 28x+12y=4 is x=1 and y=2.

  2. Here, we must first calculate gcd(63,91) using the Euclidean algorithm. We do this with the following divisions with remainder: 91=163+2863=228+728=47+0. The last non-zero remainder is 7, so this verifies gcd(63,91)=7. Now, we ignore the last line and solve for the remainder in each of the first two equations, writing them in reverse order: 7=6322828=91163. If we substitute the second equation into the first in place of 28, we can then write 7 as a multiple of 63 plus a multiple of 91, as needed: 7=63228=632(91163)=63291+263=363291. We now see that an integer solution to 63x+91y=7 is x=3,y=2.

Exercise 4

Try this for yourself! Choose primes p and q, and calculate the public and private keys. If you have a friend to try this with, have them send you a ciphertext and try to decrypt it.

Exercise 4 Solution

Answers will vary.

Problem Set Solutions

  1. Which of the following numbers are prime? For the ones that aren’t prime, factor them as a product of primes.

    1. 101

    2. 119

    3. 127

    Solution:

    1. The number 101 is prime. You can verify this using trial division – if 101 were not prime, it would have a prime factor smaller than 11. (Can you explain why?) But 101 is not divisible by any primes smaller than 11, so it must be prime.

    2. The number 119 is not prime, because it factors as 119=717.

    3. The number 127 is prime. Just as you can argue in part (a), if this number were not prime, it would have a prime factor smaller than 13. But 127 is not divisible by any primes smaller than 13.

    1. For any positive integer a, what is gcd(a,0) equal to?

    2. Calculate gcd(15,27) using the Euclidean algorithm.

    3. Calculate gcd(61783,4019881) using the Euclidean algorithm.

    Solution:

    1. For any positive integer a, gcd(a,0)=a. Indeed, a divides itself, and a divides 0 because 0=a0. Any integer larger than a cannot divide a, so a is indeed the greatest common divisor of a and 0.

    2. We perform divisions with remainder, starting with dividing 27 by 15. 27=115+1215=112+312=43+0. We see that 3 is the last non-zero remainder, so gcd(15,27)=3.

    3. Again, we perform divisions with remainder, starting with dividing 4019881 by 61783. 4019881=6561783+398661783=153986+19933986=21993+0. We see that 1993 is the last non-zero remainder, so gcd(61783,4019881)=1993.

  2. Find integers x and y solving the following equations.

    1. 15x+27y=3. (Hint: We’ve done half the work in the previous question.)

    2. 17x+31y=1.

    3. 17x+31y=4. (Hint: This requires a little more than just the Extended Euclidean algorithm. How can you work with the answer obtained in part (b) to get an answer here?)

    Solution:

    1. Starting from the Euclidean algorithm work from question 2(b), we have 27=115+1215=112+312=43+0. Leaving out the last line, solving for the remainders, and writing them in reverse order, we get 3=1511212=27115. Substituting the second equation into the first, we get 3=151123=151(27115)3=215127. This gives us the solution x=2 and y=1 to the equation 15x+27y=3.

    2. Here, we first have to run the Euclidean algorithm on 17 and 31, which gives us 31=117+1417=114+314=43+23=12+12=21+0. Removing the last line, solving for the remainders, and writing them in reverse order, we get 1=3122=14433=1711414=31117. Substituting each line one at a time, we get 1=312=31(1443)=3114+43=53114=5(17114)114=517514114=517614=5176(31117)=517631+617=1117631. This gives us the solution x=11 and y=6 to the equation 17x+31y=1.

    3. Given our work in part (b), there is just one more thing to do. We already know that 1711+31(6)=1, and if we multiply both sides by 4, we get 17(114)+31(64)=4. This gives a solution x=114=44 and y=64=24 to the equation 17x+31y=4.

  3. Compute the following values of the Euler phi function.

    1. ϕ(7)

    2. ϕ(15)

    3. ϕ(27)

    4. ϕ(30)

    5. ϕ(pk), where p is a prime number and k is a positive integer.

    Solution:

    1. Since 7 is prime, we apply the formula for ϕ(p) where p is prime from Example 5. This gives us ϕ(7)=71=6.

    2. Since 15=35 is the product of two different primes, we can use the formula for ϕ(n) in the case discussed in Example 6. This gives us ϕ(15)=(31)(51)=24=8.

    3. Since 27=33, we haven’t discussed a formula for ϕ(n) that will work here. We could try all the numbers between 1 and 27 and take gcds, but let’s be a little bit more clever.

      Since 3 is the only prime dividing 27, we get gcd(m,27)1 exactly when m is a multiple of 3. So, we just have to count the number of multiples of 3 between 0 and 26 and subtract them from 27 to get the answer. Now, there are exactly nine multiples of 3 in that range: 3,6,9,12,15,18,21,24,27. Hence ϕ(27)=279=18.

    4. Notice that 30=235, so we haven’t discussed any tricks for calculating ϕ(30) that will compute it instantly. But again, given an integer m between 1 and 30, we will have gcd(m,30)1 exactly when m is a multiple of either 2,3, or 5. So, let’s start by removing all multiples of 2 from the list of integers from 1 to 30, giving 1,3,5,7,9,11,13,15,17,19,21,23,25,27,29. From that list, we now remove the multiples of 3: 1,5,7,11,13,17,19,23,25,29. And finally, we take away the multiples of 5: 1,7,11,13,17,19,23,29. This remaining list gives all the integers m between 1 and 30 for which gcd(m,30)=1. There are eight integers on this list, so ϕ(30)=8.

    5. Here, we can use the same approach that worked for calculating ϕ(27), which was also a power of a prime number. Knowing that p is the only prime factor of pk, if we have an integer m between 1 and pk, we know that gcd(m,pk)1 exactly when m is a multiple of p.

      There are pk integers from 1 to pk, and exactly pkp=pk1 of them are multiples of p, namely all integers of the form np, where n ranges from 1 up to pk1. Subtracting off all of these multiples of p from the total, we get pkpk1 integers m between 1 and pk not divisible by p. This tells us ϕ(pk)=pkpk1. Notice that this agrees with the k=1 case worked out in Example 5, as well as the case p=3,k=3 that we solved in part (c).

  4. Modular arithmetic is good for much more than RSA. If an equation is true in the integers, we can “reduce it mod n" to get a congruence mod n that is also true. This is more useful in the other direction: if we start with an equation and prove it has no solutions mod n for some choice of n, then there are no integer solutions. This helps because we can exhaustively try every possibility for the variables mod n – there are only n different choices for each variable that would give a distinct result.

    Prove that each of the following equations has no integer solution by showing each one has no solutions mod n for a small choice of n (in each case, you can take n5.)

    1. 6x+21y=2

    2. 5y=x2+2

    3. x2+y2=31

    Solution:

    1. Here, we take the equation and reduce it modulo 3. This gives us 6x+21y2(mod3). Now, notice that both 6 and 21 are congruent to 0 mod 3. This means 6x0(mod3) and 21y0(mod3). The congruence above then simplifies to 0+02(mod3). In turn, this says 02(mod3). By definition, this means 3(02). This is impossible, as 2 is not divisible by 3. This shows that the congruence has no solution modulo 3, which means the original equation has no solution either.

    2. For this one, we take the equation and reduce it modulo 5. Since 5y0(mod5) no matter what value we take for the integer y, we find that the congruence 5yx2+2(mod5) reduces to 0x2+2(mod5). Now, there are only five “different" integers modulo 5, namely 0,1,2,3,4. Let’s try them all as possible values of x to see what x2+2 comes out to: 02+22(mod5)12+23(mod5)22+261(mod5)32+2(2)2+261(mod5)42+2(1)2+23(mod5). We just tried all possible values for x modulo 5, and none of them gave us x2+20(mod5). Therefore, the congruence has no solutions, which implies the equation 5y=x2+2 has no integer solutions.

    3. For this equation, reducing modulo 4 works. When we do this, we end up with x2+y2313(mod4).

      Since 0,1,2,3 represent all the different possible values modulo 4, we can try each of these as values for x to see what the possibilities for x2 will be: 020(mod4)121(mod4)2240(mod4)3291(mod4). Therefore, no matter what x is, we know that x20(mod4) or x21(mod4). Similarly, these are the only two possible values for y2 modulo 4. Putting that together, the possibilities for x2+y2 modulo 4 will be: 0+00(mod4)0+11(mod4)1+01(mod4)1+12(mod4) None of these possibilities gives us an answer of 3 modulo 4, so x2+y23(mod4) has no solutions. In turn, this implies x2+y2=31 has no integer solutions either.

  5. In RSA, Nick is not supposed to reveal ϕ(N), because knowing it allows everybody to calculate Nick’s private key. It’s time to put on our cryptanalysis hats and try to break the system. If we know p and q, the two factors of N, it becomes easy to calculate ϕ(N). However, as we know, finding those factors is really hard. Maybe there’s an easier way to calculate ϕ(N)? We’re going to see the answer is no.

    1. Suppose you have a magic machine that takes N and instantly calculates ϕ(N). How can you use the values of N and ϕ(N) to calculate p+q?

    2. Once you know both p+q and N=pq, how can you calculate both p and q? (Hint: Consider the quadratic formula applied to the polynomial x2(p+q)x+pq.)

    What this means is that an efficient way for calculating ϕ(N) leads to an efficient way of factoring N, and everyone believes that factorization is really hard.

    Solution:

    1. If we have the values of N=pq and ϕ(N)=(p1)(q1)=pqpq+1, the value of p+q is easy to obtain. Indeed, notice that Nϕ(N)=pq(pqpq+1)=(p+q)1.

      So, if we know N and a machine has given us the value of ϕ(N), then we can put Nϕ(N)+1 into a calculator and find the value of p+q.

    2. As suggested in the hint, let’s see what the quadratic formula says about the roots of the polynomial x2(p+q)x+pq. By that formula, the roots are x=((p+q))±((p+q))24pq2=(p+q)±p2+2pq+q24pq2=(p+q)±p22pq+q22=(p+q)±(pq)22=(p+q)±|pq|2. The absolute value makes things a little complicated, but because of the ± in the quadratic formula, in every case the two roots come out to be p and q. Therefore, if you use the known numbers N=pq and p+q, applying the quadratic formula to x2(p+q)x+pq gives the values of p and q as the answers. This may be the single coolest application of the quadratic formula ever to exist!

  6. Like any cryptosystem, the security of RSA can be compromised if used incorrectly. Suppose Nick and Bahaa have the same value of N, but different encryption exponents e1 and e2.

    1. Explain how Nick and Bahaa can work out each other’s private keys, and therefore read each other’s encrypted messages.

    2. Suppose Shefaza comes along and sends the same message M to both Nick and Bahaa (maybe it’s Shefaza’s credit card number). Suppose also that gcd(e1,e2)=1. Now, let’s say Diana comes along and reads the ciphertexts that Shefaza sent to Nick and Bahaa, say C1Me1(modN) and C2Me2(modN).

      Explain how Diana can use this information to recover Shefaza’s plaintext M.

      Hint: Running the Extended Euclidean algorithm on e1 and e2 allows Diana to find integers x and y such that e1x+e2y=1. How can this information help her recover M?

    Solution:

    1. Because Nick and Bahaa have both chosen the same value of N, both of them started by choosing the same primes p and q to create N. In particular, both Nick and Bahaa know the value of ϕ(N). Because of this, if Nick used exponent e1 and Bahaa used exponent e2, Nick could look up e2 and find Bahaa’s decryption exponent d2 by running the Extended Euclidean algorithm on ϕ(N) and e2. In the same way, Bahaa can calculate Nick’s decryption exponent d1.

    2. As mentioned in the hint for the question, since gcd(e1,e2)=1, Diana can use the known values of e1 and e2 to find integers x and y such that e1x+e2y=1, by running the Extended Euclidean algorithm.

      At this point, Diana should take the ciphertexts C1 and C2 that she intercepted and compute C1xC2y(modN). Here is what happens when she does this: C1xC2y(Me1)x(Me2)yMe1xMe2yMe1x+e2yM1(modN).

      So, if Diana calculates the unique integer M between 0 and N1 such that MC1xC2y(modN), then M will be the desired plaintext.

      Remark: There’s a minor point to mention here: we only talked about what it means to raise numbers to positive exponents mod N. Here, x or y could be negative. There’s a way to make sense of negative exponents mod N, which you can investigate if you are curious! But don’t worry: the argument given here can indeed be made valid.