Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

This question is broken into two sections really:

Symmetry in RSA

I have been analyzing raw RSA and I have noticed some interesting symmetrical properties of the algorithm.

Assume that $M$ is a positive integer between $2$ and $N\over2$, ($N$ is the RSA modulus). Then:

$$ M_s = N - M \\ C = M^e \pmod N \\ C_s = M_s^e \pmod N $$

This means that $C + C_s = N$, $M + M_s = N$, $C - M = C_s - M_s$ and therefore $C_s = N - C$. Also, $$(N-M)^e \mod N = N - (M^e \mod N)$$

Let the RSA modulus ($N$) be the circumference of a circle radius $r$. Converting each $M$ value from $1$ through to $N - 1$ into segments of the circumference, each with an equal angle between segments, then it will be possible to convert each $M$ and its corresponding $C$ into Cartesian coordinates ($X, Y$) using the formula:

$$ (X,Y)= \left(r \cdot \cos({M\over360}) , r \cdot \sin({M\over360}) \right) $$

Using $X$ and $Y$ to plot a line across the circle from $M$ to its corresponding $C$ value. In some cases when calculating $C$, $C$ will be equal to $M$ (for example when $M = 1$). In these cases draw a loop back to $M$.

In all cases the end diagram will be symmetrical through the diameter of the circle from 0 to 180 degrees.


Example: RSA using $P=11 and Q=7$

(These small numbers were chosen deliberately in order to show the symmetrical pattern. The symmetrical property is the same with large primes, but because there are so many more $M$ values the image becomes a blur of lines, which are indistiguishable from one another. It is also impossible to spot the loop backs (see below)).

RSA with P=11 and Q=7

This also means the one can accurately predict the cipher text of a symmetric partner of $M$.


Inherently weak primes and RSA

Some prime numbers are very weak with regards to RSA. Examples include $P = 257$ or $Q = 193$. This is because $P-1$ is smooth, e.g. $P-1$ is smooth to $2$ ($2^8$), $Q-1$ is smooth to $3$ ($2^6, 3^1$). When these two primes are combined as $N=PQ=49601$, this produces $16705$ “loop backs” (where $C = M$). The interesting thing about this is the value of $M$ when the “loop back” occurs. For this combination the first ten loop backs are: $$1, 3, 8, 9, 11, 13, 14, 20, 23, 24$$

Why is this significant?

If $Z = C \pmod M$ then in most cases $Z = M$. Where this doesn’t happen we can say that:

If $Z = 0$ then $T_1 = C$ else $T_1 = Z$

This means that in most cases $T_1 = M$. Thus we can say:

  • If $T_1 \neq M$ then $T_2 = \gcd(T_1, N)$
  • If $T_2 = 1$ then $T_3 = M – C$

In most cases $T_3 = P$ or $Q$. When $T_3 \neq P$ and $T_3\neq Q$: - $T_4 = GCD(T_3, N)$ - $T_4$ will be either $P$ or $Q$.

$T_5 = {T_3 \over T_4}$.

The value of $T_5$ will always be one of the loop back $M$ values, e.g. $1, 3, 8, 9, 11, 13, 14, 20, 23, 24, \dots$

Although this is easy to demonstrate with small value weak prime numbers, the same case is applicable to large value RSA with strong primes. These are harder and more time consuming to calculate because of the vast size of the data to be collected. To perform this analysis one must iterate over every $M$ value between $2$ and $N – 1$.


Example: Loop back image for $P=257, Q= 193$

RSA Loopbacks for P=257, Q=193


My question:

Is it possible to use any of this information to form a cryptanalytic attack against RSA?

share|improve this question
    
Why should $C+C_s=N$? –  DrLecter Dec 17 '13 at 11:13
    
This is because all $C$ values are $mod N$. As $C_s$ is the symmetric partner of $C$ the two added are N. E.G. If $P=11$ and $Q=7$, then $N=77$. If $E=3$ and $M=2$ then $C=8$ ( $2^3 mod 77 = 8$ ). $C_s = (N-M)^e mod N = (77-2)^3 mod 77 = 69$. This means $C + C_s = 8 + 69 = 77$. Also $M_s = N - M = 75$ and therefore $|M_s - C_s| = |M - C| = |75 - 69| = |2 - 8| = 6$. –  NRCocker Dec 17 '13 at 11:26
    
Ah didnt read carefully...ok, its obvious. –  DrLecter Dec 17 '13 at 11:39
1  
You wrote $C-M=C_s-M_s$. Pretty sure this isn't true, and I cant see a way to deduct this from the other formulas. If anything, it should be $C-M=M_s-C_s$ (or take the absolute values) –  tylo Dec 17 '13 at 14:26

1 Answer 1

The first observation in the question boils down to: in textbook RSA, the encryption of $N-M$ instead of $M$ yields $N-C$ instead of $C$.

This is a special case of a more general property of textbook RSA, that the encryption of $M\cdot M'\bmod N$ yield $C\cdot C'\bmod N$, whenever enciphering $M$ yields $C$ and enciphering $M'$ yields $C'$; combined with the elementary fact that enciphering $M'=N-1$ yields $C'=N-1$.

These properties are the basis of numerous attacks on textbook RSA, including some of these (and of attacks on real RSA signature schemes with ad-hoc padding, such as on ISO/IEC 9796-2 scheme 1). This is why textbook RSA should not be directly used for anything else than random messages, or messages sufficiently close to that.


A second observation in the question considers the case of $N=P\cdot Q$ with $P-1$ smooth.

The worst thing if that happens is that it is easy to factor such $N$, using Pollard's p-1 factoring algorithm (giving a total break, making the considerations in the question of secondary importance). However this is not a serious weakness of RSA, for the odds of accidentally selecting such a $P$ are vanishingly small for usual order of magnitude of $P$; see the Dickman function for a numerical estimate.

Further, we can avoid such $P$ with relative ease; this remains standard practice at least for $P$ up to 512 bits (see appendix B.3 in FIPS 186-4, and in particular the requirement in B.3.1 A: "p and q with lengths of 512 bits shall be generated using the conditions based on auxiliary primes"). The only case when this might matter (there is not quite a consensus here) is when one generates ziiillions of keys, with $\log_2P$ below or close to 512, and a marginal risk that even one public key is vulnerable to Pollard's p-1 factoring is unacceptable (the adversary's best use of CPU time might be to attack each key with Pollard's p-1, rather than a few keys with other factoring methods).

share|improve this answer
4  
FIPS.186-4 is long. You should reference the relevant section(s). –  CodesInChaos Dec 17 '13 at 17:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.