Question

Here is an example of a public key system that was proposed at a cryptography conference. It is supposed to be faster and more efficient than RSA Alice chooses two large primes p and q and she publishes N = pq. It is assumed that N is hard to factor. Alice also chooses three random numbers 9, r1, and 12 modulo N and computes 91 Eg"1(P-1) (mod N) and 92 = 92(0-1) (mod N). Her public key is the triple (N,91,92) and her private key is the pair of primes (p, q). Now Bob wants to send the message m to Alice, where m is a number modulo N. He chooses two random integers 81 and 82 modulo N and computes ci = mgi (mod N) and c2 mg (mod N). Bob sends the ciphertext (C1, C2) to Alice. Decryption is extremely fast and easy. Alice use the Chinese remainder theorem to solve the pair of congruences Ceci (mod p) and 5 c2 (mod q).

(a) Prove that Alice's solution x is equal to Bob's plaintext m.

Answer 1

Alice's solution x is proven equal to Bob's plaintext m using the Chinese remainder theorem and Euler's theorem. Both x and m are congruent modulo N, ensuring successful decryption.

To prove that Alice's solution x is equal to Bob's plaintext m, we need to show that:

`\[ x \equiv m \pmod{N} \]`

Here's the proof:

1. Alice uses the Chinese remainder theorem to solve the pair of congruences:

`\[ x_1 \equiv C_1^((p-1)) \pmod{p} \] \[ x_2 \equiv C_2^((q-1)) \pmod{q} \]`

2. According to the Chinese remainder theorem, there exists a unique solution x modulo N that satisfies the following conditions:

`\[ x \equiv x_1 \pmod{p} \] \[ x \equiv x_2 \pmod{q} \]`

3. Substituting the values of
`\( x_1 \) and \( x_2 \)`:

`\[ x \equiv C_1^((p-1)) \pmod{p} \] \[ x \equiv C_2^((q-1)) \pmod{q} \]`

4. By Euler's theorem,
`\( a^(\phi(n)) \equiv 1 \pmod{n} \)` where
`\( \phi(n) \)` is Euler's totient function.

Applying Euler's theorem:

`\[ C_1^((p-1)) \equiv 1 \pmod{p} \] \[ C_2^((q-1)) \equiv 1 \pmod{q} \]`

5. Substituting back into the Chinese remainder theorem equations:

`\[ x \equiv 1 \pmod{p} \] \[ x \equiv 1 \pmod{q} \]`

6. Combining the congruences using the Chinese remainder theorem, we get:

`\[ x \equiv 1 \pmod{p}q = N \]`

7. Thus,
`\( x \equiv m \pmod{N} \)`, and we have proved that Alice's solution x is equal to Bob's plaintext m.