RESIDUE NUMBER SYSTEM & CHINESE REMAINDER THEOREM
The Chinese Remainder Theorem (CRT) is used in various cryptographic applications in order to speed up calculations, for instance in the RSA algorithm. The goal of this task is to understand the discrete mathematics that form the basis of modern cryptography by using Euler's Theorem, Fermat Little Theorem, CRT and by solving linear congruent relationships.
Task 1: The Residue Number System (RNS) [2] allows for parallel computations by splitting a number into residues of smaller moduli. You are given the number N = (5619; 181876; 5608477) in RNS format with base elements (198247; 427363; 8125766).
- Is this a proper RNS basis?
- What is this number in binary format?
Task 2: Compute the two least significant digits of "by hand" without help of a mathematical software tool. Hint: Recall Euler's theorem: If gcd(a; n) = 1 then a‑(n) ≡1 (mod n).
Task 3: Suppose that Alice wants to send the same secret message m to Bob, Chris and Dona. The public modulus of these three people is given by the numbers = 699; = 3205 and = 8309, and they all have the same public exponent e = 13. If the transmitted cipher texts are = 670, = 2574, = 5380 respectively, and the message m (with the help of the Chinese Remainder Theorem).