Skip to main content

Discrete Mathematics · Divisibility, modular arithmetic, and elementary number theory

RSA decryption needs Euler, and Euler needs a coprime message

Problem

Discrete Mathematics practice problem

Let p=5p=5 and q=13q=13, and set n=pq=65n=pq=65. Let e=5e=5.

1. Compute φ(n)\varphi(n) from the product formula, and prove that gcd⁡(e,φ(n))=1\gcd(e,\varphi(n))=1. Find the unique dd with 1≤d<φ(n)1\le d<\varphi(n) anded≡1(modφ(n)).ed\equiv 1\pmod{\varphi(n)}.Do not invert ee modulo nn.

2. Prove Euler's theorem: if gcd⁡(a,n)=1\gcd(a,n)=1, then aφ(n)≡1(modn)a^{\varphi(n)}\equiv 1\pmod n. Your proof should use that multiplication by aa permutes (Z/nZ)×(\mathbb Z/n\mathbb Z)^\times.

3. Let mm be an integer with gcd⁡(m,n)=1\gcd(m,n)=1, and set c≡me(modn)c\equiv m^e\pmod n. Using only Euler's theorem and the congruence ed≡1(modφ(n))ed\equiv 1\pmod{\varphi(n)}, provecd≡m(modn).c^d\equiv m\pmod n.Then, for the plaintext m=11m=11, compute the ciphertext c≡11e(modn)c\equiv 11^e\pmod n and verify cd≡11(modn)c^d\equiv 11\pmod n. Record both residues in {0,1,…,n−1}\{0,1,\ldots,n-1\}.

4. Let m′=10m'=10. Compute gcd⁡(m′,n)\gcd(m',n) and prove that Euler's theorem does not apply to m′m' modulo nn, by showing (m′)φ(n)≢1(modn)(m')^{\varphi(n)}\not\equiv 1\pmod n. Explain why quoting Euler on m′m' cannot justify RSA decryption of m′m', even if some other argument (not requested here) might still recover m′m'. Also explain why the private exponent must be an inverse of ee modulo φ(n)\varphi(n) rather than modulo nn.

Do not treat nn as prime, do not replace φ(n)\varphi(n) by n−1n-1, and do not skip the coprime-message hypothesis.

Hint

Hint

φ(65)=4⋅12=48\varphi(65)=4\cdot 12=48. The inverse of 55 modulo 4848 satisfies 5d=48k+15d=48k+1; try k=3k=3.

Check your work

Work the problem yourself first. Then open it in Training to check your answer and read the full worked solution.

The answer check and full solution for this problem come with ProofAnvil Practice membership ($19 USD monthly). See membership. Or start with the free Discrete Mathematics sample problem: Try the free sample problem.

More Discrete Mathematics practice problems

Back to Discrete Mathematics

An original ProofAnvil practice problem, written for this course. ProofAnvil is a practice course, not a homework-answer service.