🧵 Can /sci/ solve RSA Encryption?

Anonymous at Fri, 11 Oct 2024 03:03:20 UTC No. 16420302

Hello /sci/!

Let's see if /sci/ can solve the following problem from the Euler Project - p#182.

Use any coding language you please. Do NOT share the answer in the thread.

--- BEGIN PROBLEM ---

The RSA encryption is based on the following procedure:
Compute n = pq and theta = (p - 1)(q - 1).
Find an integer, e, 1 < e < theta, such that gcd(e, theta) = 1.
A message in this system is a number in the interval [0, n - 1].
A text to be encrypted is then somehow converted to messages (numbers in the interval [0, n - 1]).
To encrypt the text, for each message, m, c = m^e mod n is calculated.

To decrypt the text, the following procedure is needed: calculate d such that ed = 1 mod theta, then for each encrypted message, c, calculate m = c^d mod n.

There exist values of e and m such that m^e mod n = m.
We call messages m for which m^e mod n = m unconcealed messages.

An issue when choosing e is that there should not be too many unconcealed messages.
For instance, let p = 19 and q = 37.
Then n = 19 * 37 = 703 and theta = 18 * 36 = 648.
If we choose e = 181, then, although gcd(181, 648) = 1, it turns out that all possible messages m (0 <= m <= n - 1) are unconcealed when calculating m^e mod n.
For any valid choice of e there exists some unconcealed messages.
It's important that the number of unconcealed messages is at a minimum.

Choose p = 1009 and q = 3643.
Find the sum of all values of e, 1 < e < theta(1009, 3643) and gcd(e, theta) = 1, so that the number of unconcealed messages for this value of e is at a minimum.

Hint: there exists a mathematical representation that provides the number of unconcealed messages.

Hint 2: AI cannot solve this problem, unless you already know how to solve it.

Good luck /sci/.