Department of Mathematics
National University of Singapore
(2014/2015) Semester 2 GEK1531 Introduction to Cybercrime Tutorial 2
(1) Find the smallest positive integer x that satisfies the following congruence equations.
(i) 777 ≡ x mod 11. Ans: 7
(ii) −36789 ≡ x mod 19. Ans: 14
(iii) 123935 + 2573467 ≡ x mod 321. Ans: 39
(iv) 231 × 1214 ≡ x mod 255. Ans: 189
(v) 123935 + 2573467 ≡ x mod 113. Ans: 92
(vi) 524 ≡ x mod 19. Ans: 7
First, one can compute 52 ≡ 6 mod 19, 54 ≡ (52 )2 ≡ 62 ≡ 17 mod 19. Then,
58 ≡ (54 )2 ≡ 172 ≡ 4 mod 19, 51 6 ≡ (58 )2 ≡ 16 mod 19. So, 52 4 ≡ 516+8 ≡
516 58 ≡ 16 × 4 ≡ 7 mod 19.
Note that 19 is prime. Therefore, 518 ≡ 1 mod 19. Hence, 524 ≡ 518+4+2 ≡
1 × 17 × 6 mod 7 mod 19.
(vii) 23159 ≡ x mod 79. Ans: 1
Again, 79 is prime. Hence, 2378 ≡ 1 mod 79.
23159 ≡ 23156+3 ≡ (2378 )2 × 233 ≡ 1 mod 79.
(viii) 9x ≡ 3 mod 47. Ans: 16
We first find the multiplicative inverse of 9 mod 47.
47 = 5 × 9 + 2; 9 = 2 × 4 + 1.
Therefore, we get
9 = (47 − 5 × 9) × 4 + 1 and 9 = 47 × 4 − 20 × 9 + 1.
Finally, we get 1 = 21 × 9 − 47 × 4. So, we have
1 ≡ 21 × 9 − 47 × 4 ≡ 21 × 9 mod 47.
In other words, 21 is the multiplicative inverse of 9 modulus 47. Now, multiply
21 to both sides of the equation 9x ≡ 3 mod 47, we get 21 × 9x ≡ 21 × 3 mod 47.
As 21 × 9 ≡ 1 mod 47, we get x ≡ 63 ≡ 16 mod 47.
1
(2) As in Example 14, it is known that an affine cipher with key (9, 11) is used to encrypt
a message. Decrypt the message if the cipher text is:
TOIDY (Ans: YJRCN)
(Note. The decrypted text needs not make sense.)
The encryption function is f (x) ≡ 9x + 11 mod 26. To find the inverse function,
we set y ≡ 9x + 11 mod 26.
We then get y − 11 ≡ 9x mod 26. It is easy to check that 9 × 3 ≡ 1 mod 26.
Multiply 3 to both sides of the equation y − 11 ≡ 9x mod 26 Therefore, we get
3y − 33 ≡ 3y + 19 ≡ x mod 26. So the inverse function is g(x) ≡ 3x + 19 mod 26.
Now, ‘T’ corresponds to 19, g(19) ≡ 3 × 19 + 19 ≡ 24 mod 26. So, we decrpyt it
as ‘Y’.
(3) Using the exponential cipher f (x) = x3 mod 5251 that encipher two letters each time,
encipher the message:
Easy
Note that ‘ea’ corresponds to the number 0400 and ‘sy’ corresponds to 1824.
4003 ≡ 812 mod 5251 and 18243 ≡ 2058 mod 5251. The cipher text is
Ans: 0812 2058
(4) Find all the elements in the set Z∗39 .
For each number from 1 to 38, take those numbers which are coprime with 39. It can
be easily checked that the numbers are 1, 2, 4, 5, 7, 8, 10, 11, 14, 16, 17, 19, 20, 22, 23, 25, 28, 29, 31, 3
(5) In the setting of RSA cryptosystem, we set n = 37 × 41 and the public key of Bob is
7, i.e. e = 7.
(i) Suppose Alice sent a message to Bob represented by a number 323. Find the
number that represents the ciphertext.
Note that n = 1517. 3237 ≡ 841 mod 1517. Ans: 841
(ii) Find the multiplicative inverse of 7 mod φ(n).
φ(n) = 36 × 40 = 1440. We need to use Euclidean algorthium to calculate the
multiplicative inverse. The answer is 823.
(iii) Suppose B received the ciphertext represented by the number 13. Find the
number that represent the plaintext.
To decrypt, we need to compute 13823 mod 1517. It is a bit tedious but the idea
is to compute 132 , 134 , 138 , 1316 etc. The answer is 1165.
