# Context

• An unknown modulus N with 8 unknown prime factors $$p_1, p_2, p_3, p_4, p_5, p_6, p_7, p_8$$
• a plaintext $$m$$ is encrypted with the formula $$c = 2^m \mod N$$
• the only things the attacker know are $$c$$ and $$\sum_{i=1}^{8}(a|p_i)$$ for any integer $$a$$ with $$(a|p)$$ being the Legendre Symbol of $$a$$ and $$p$$

# Attempts

Observation:

• $$\sum_{i=1}^{8}(a|p_i) = 0$$ if $$a = N$$
• $$\sum_{i=1}^{8}(a|p_i) \in \{-8, -6, -4, -2, 0, 2, 4, 6, 8\}$$ if $$a$$ is not a multiple of one of the prime factors of $$N$$
• $$\sum_{i=1}^{8}(a|p_i) \in \{-7, -5, -3, -1, 0, 1, 3, 5, 7\}$$ if $$a$$ is a multiple of one of the prime factors of $$N$$ since $$(p|p) = 0$$
• From the definition of Legendre Symbols, if $$a$$ is a perfect square and not a multiple of the prime factors of $$N$$, $$\sum_{i=1}^{8}(a|p_i) = 8$$
• The multiplication property of a Legendre Symbol applies

# Question

1. What Cryptosystem is this?
2. How can we retrieve the plaintext?
• Are you sure the question asks to retrieve the plaintext, rather than retrieve information about the plaintext (or select among few possible plaintexts, which is not trivial since we do not know $N$, apparently)? Half-baked idea: if you obtain the values of $\displaystyle\sum_{i=1}^8\left(\frac a {p_i}\right)$ for $a=2$ (e.g. $2$) and $a=c$ (e.g. $8$), can that reveal something about $m$? Can asking for another $a$ (e.g. $a=c^2$) reveal more? What are the odds that you can't use this strategy to get any sure information about $m$? What if you make a single query?
– fgrieu
Commented Nov 8, 2023 at 12:23

1. The system bears some similarity to the Maurer-Yacobi non-interactive public key scheme (an early approximation to identifier-based encryption) with $$\alpha=2$$, $$r=8$$. However, the M-Y system does not require disclosure of the sum of the Legendre symbols.

2. Note that if we can recover plaintexts, then we can solve discrete logarithms modulo each of the $$p_i$$ in the multiplicative subgroup generated by 2. One could do this by choosing each of the $$p_i$$ to be a prime of around, say, 512-bits. With some precomputation it should be possible to solve discrete logarithms modulo these primes in roughly 36-core minutes each and thus learn $$m\mod {p_i-1}$$. The Chinese remainder theorem can then be used to recover $$m$$.

To attack the system the first thought would be to factor the 4096-bit number $$N$$, though this is beyond the scale of the general number field sieve for which the largest number factored is 829-bits. Alternatively, one might hope that the elliptic curve method could identify the factors more cheaply. However the largest prime identified by ECM to date is 274-bits in size.

No effective method using knowledge of Legendre symbol information has been found to significantly improve factoring methods. In particular, when factoring numbers of the form $$p^2q$$ (such as are used in the Okamoto-Uchiyama cryptosystem) where the adversary can know compute Legendre symbols modulo $$q$$, we do not know of a superior factoring method.

• I wonder if this oracle giving $\sum_{i=1}^{8}(a|p_i)$ for any input $a$ could help factorization of $N=\prod p_i$ or the DLP modulo $N$ (but I do not immediately see how; also, we do not know $N$, apparently).
– fgrieu
Commented Nov 8, 2023 at 12:09
• @fgrieu One feels that the strongest information comes when the sum (for non-square $a$) is $\pm 8$ so that we know that $a$ is a (non-)residue for all of the primes dividing $N$. Even given a stronger oracle that returns all of the Legendre information for all of the primes, I'm not aware of how to exploit that. Commented Nov 8, 2023 at 14:18
• I see how we can use the oracle to recover one bit of $m$ with certainty, for all except <0.4% choices of $N$ (and test against that edge case). For the rest, I pass. Indeed, even knowing $\left(\frac a p\right)$ for any desired $a$ does not seem to allow finding large $p$.
– fgrieu
Commented Nov 8, 2023 at 15:54