RSA: Detecting period of unconcealed messages

Referencing: Project Euler Problem 182 Clarification

I'm trying to determine the (minimum) period for a given value of $(p, q)$.

For a simple case where $p=19,q=23$ the period of repeating order is 132 (which I assume is from 2x2x3x11, the prime factors of 18 and 22). It's trivial to explore the number-space of 132 to see where $\gcd(e,\phi)=1$ and $\gcd(e,p-1)=2$ and $\gcd(e,q-1)=2$. Same goes for when $p=1009$ and $q=3643$ and I calculate the period to be 152964.

But what about for larger values for $p$ and $q$, like $p=232919$, $q=233117$?

Given that $\phi = 54296912488$, and the prime factors of $p-1$ are 2, 7, 127, 131 and the prime factors of $q-1$ are 2, 13, 4483 then I calculate the period is 27148456244 (is there any possibility of reducing this number-space?) Is there any other order/period that can be used to my advantage in order to drastically reduce the number of gcd calcs that I have to perform?

• How do you define 'the period of unconcealed messages'? Sep 20 '17 at 18:38
• Interesting question! @poncho I think he is using the definition of a period as the repeating part of the decimal. 19/23 has a repeating cycle of 132 digits. Paul, please correct me if I'm incorrect. Sep 20 '17 at 20:14
• By period (or is order a better word?) I mean the repeating sequence. For example, with p=19,q=23, the period is 132 such that the minimal number of unconcealed messages occur at e = 35,47,59,71,83,95, 107,119,131 and then repeat at 167,179,191,203,215,227,239,251,263. Or stated differently, There is a minimal unconcealed messages at e=35+(n*132) and 47+(n*132) [...] Sep 20 '17 at 20:41
• Are you sure? My calculations show that e=5, 17, 29, 41, 53, 65, 101, 113, 137, ... (in addition to the ones you have listed) also achieve the minimum. And, the period would appear to be 66... Sep 20 '17 at 21:12
• I also calculated 152964 as the repeating number of decimal digits for the expanded fraction 1009/3643. Sep 20 '17 at 21:28

The diagram below may help. The upper left is my inputs, P, Q, and e, with the corresponding calculations. Below this is a table showing the 9 quines and how they relate to P and Q. Upper center shows quine calculation. Upper right shows multiples of P and Q are quines.

Then we get into the bigger table. Down the first column are messages. Across the top is 0 to lambda, with increasing multiples (k) as these rows go up. I've included a short note above some of the e values. Near the middle are the number of quines (in red) for each e, when it meets certain conditions. The red cells are 1 (multiplicative identity). The blue cells are when the values equal the original message (quine). The other colors are when number match P, Q, and e, or match a quine.

Notice that $0 < e < \lambda$, as well as d' (based on $\lambda$), where d (based on $\phi$) is d' + a multiple of $\lambda$ (47 = 17 + 30). As $\lambda$ divides $\phi$. Also, the second column of 1's is the start of the period. And column 3 is $ed \equiv 1 \pmod{n}$, the multiplicative identity. Therefore, any number raised to the power of 1 is itself, which is my RSA works.

Looking at RSA in two dimensions allows us to see some symmetry in both axis. The second table shows the 9 quines (blue) along the vertical axis and the formula to calculate each. Along the right side of this table shows a few of thes symmetries. Along the horizontal axis, where e=15 is $\lambda/2$. We can see the e values which meet those conditions mirror each other. I'm not certain of the exact pattern yet, but these are $6n \pm 1$ (where n is a multiple and not the product of PQ).

So to answer the original question, each message has a different period (spot the red 1's horizontally for each message), which divides $\lambda$, except for multiples of P and Q. However, $\lambda$ would probably be the smallest period you are looking for when calculating which $e$ produces the minimum number of quines.

Convention states that $P > Q$. At best, there are 9 unconcealed messages. I'll refer to these as $U_0$ through $U_8$. Here are some relationships between these.

\begin{align*} U_0&=0\\ U_1&=1\\ U_2&=kP, &&\text{where $k=1$ to $Q/2$. Test if unconcealed. Stop once you find one.} \\ U_3&=kQ, &&\text{where $k=1$ to $P/2$ (try $U_2\pm1$ before trying multiples of $Q$).} \\ U_4&=U_2+U_3 \bmod N \\ U_5&=N-U_4 &&\text{(also, $U_6+U_7 \bmod N$)} \\ U_6&=N-U_3 \\ U_7&=N-U_2 \\ U_8&=N-U_1 \\ \end{align*}

Looking at this example, there is no period for unconcealed messages. Also note $e$, $\phi$, and Carmichael values are not needed.

$P=47, Q=23, N=1081$, where $e$ results in 9 unconcealed messages.

\begin{align*} U_0&=0 \\ U_1&=1, &U_8&=1080, &U_1+U_8&=N \\ U_2&=46, &U_7&=1035, &U_2+U_7&=N \\ U_3&=47, &U_6&=1034, &U_3+U_6&=N \\ U_4&=93, &U_5&=988, &U_4+U_5&=N \\ \end{align*}

The most you'll need to test is $(P+Q)/2$ and will often be far less. This reduces the number-space you need to search.
For clarity:

$$U_0=N \bmod N, \quad \text{or 0}$$

The first pair is $U_1=N+1 \bmod N$ and $U_8=N-1 \bmod N$. Their sum equals $N$.

The second pair, $U_2$ and $U_7$ are a multiple of either $P$ or $Q$ and sum $N$. If the is a multiple of $P$, then you only need to search to $Q/2$ as these mirror each other. Once you go beyond $Q/2$ you are testing the same values against the other half of the pair.

Similarly, the third pair, $U_3$ and $U_6$, will be a multiple of the other factor with the same consideration (sum $N$ and test to $P/2$ assuming this is a multiple of $Q$). This would be $Q$ if the second pair were a multiple of $P$, and $P$ if the second pair were a multiple of $Q$. The small numbers which I've tested, $U_3$ is $U_2\pm1$. Which means $U_6$ is also $U_7\pm1$. I don't know why this is, or if this holds for larger numbers. I have yet to code this and test.

The fourth pair, $U_4$ and $U_5$, also sum $N$. This pair is calculated from pair two and three. $U_4=U_2+U_3$, you can append '$\bmod N$' for consistency, but since both are $\mathit{factor}/2$, these will always sum less than $N$. Conversely, $U_5$ is the sum of $U_6$ and $U_7$, both on the high side of $\mathit{factor}/2$ due to their relation of $U_2$ and $U_3$, therefore will sum greater than $N$ and will require '$\bmod N$'.

So, three unconcealed messages are known, $U_0$, $U_1$, and $U_8$. By discovering $U_2$ and $U_3$, the remaining four can be calculated. In the process of discovering $U_2$ and $U_3$, the multiple, $k$, ranges from $1$ to $\mathit{factor}/2$. You can stop once a factor is found because the compliment is calculated. Then test $U_3$ as $U_2\pm1$ before testing multiples of the opposite factor.

When the selection of $e$ results in more than 9 unconcealed messages, these same 9 are always the same, as they are based on $P$ and $Q$.

There are three simple formulas, $U=k*\mathit{factor}+1, U=k*\mathit{factor}, U=k*\mathit{factor}-1$, which demonstrate concisely how and why these 9 relate to each other the way they do. It was an awesome discovery and I'll share in another post.

• When I state U3=U2+/-1, clearly I don't mean U3 is both U2+1 and U2-1. It will be one or the other. The same for U6=U7+/-1 will be either U7+1 or U7-1, and not both. However, they will be opposite signs. If U3=U2+1 then U6=U7-1. Essentially U2 and U3 will have a difference of 1, and U6 and U7 will also have a difference of 1. Nov 5 '17 at 17:07
• Thanks for taking the time to write such a detailed answer Carl, it is appreciated. I will try to incorporate this into my algorithm in the next week or so, and will mark it as accepted answer if it checks out. Nov 9 '17 at 23:20
• I've had time to look at this again. Let's take the simple case where p=47,q=23. This gives a value of phi=(p-1)(q-1)=1012 enumerating through all e from 3 to phi, where gcd(e,t)==1 and gcd(e,p-1)==2 && gcd(e,q-1)==2 results in the following sequence: 3 7 15 19 27 31 35 39 43 51 59 63 71 75 79 83 87 91 95 103 107 119 123 127 131 135 147 151 159 163 167 171 175 179 183 191 195 203 211 [...] 1081 I don't see how that ties into this answer.. Nov 19 '17 at 1:28
• Try gcd(e-1,p-1)==2 && gcd(e-1,q-1)==2. See my answer in Project Euler Problem 182 Clarification. Nov 19 '17 at 4:27
• The 9 unconcealed messages are 0, 1, 1080, 46,1035,47, 1034, 93, 988. This worked exactly as described above. The period is 506, or a divisor such as 253, 46, 23, and 11. This depends on the message. Nov 19 '17 at 5:12

It turns out that finding the period is equivalent to factoring $N$.

The period divides $\operatorname{lcm}(p-1, q-1)$. So by the time you factor $N$ to get $p$ and $q$, you already have done the factoring. The other way to do this is brute force guessing of R which is not better than brute force guessing $p$, $q$, $\phi$, $d$, or any other RSA variable.

\begin{align*} N &= p \cdot q \\ R &= \operatorname{lcm}(\phi(p-1), \phi(q-1)) \end{align*}

An option might be to try $R$ as powers of 2, from $2…N-1$, as the lcm will be an even number.

• Since I know the values for p,q already (and therefore, p-1,q-1 and N) does this change the complexity of calculation? I thought that knowing the prime factors of p-1 and q-1 might be useful, which are relatively inexpensive to calculate. Oct 23 '17 at 22:05