3
$\begingroup$

Can we define an RSA variant in which the public key with $n$-bit public modulus $N$ has a compact representation of $\kappa\ll n/2$ bits, with a security argument that it is as safe as regular RSA for a given $n$ (e.g. $n=2048$), and the constraint that the two prime factors $p$ and $q$ of $N$ have (about) equal bit size?


If we remove the constraint $\log_2 p\approx\log_2 q$, we are back to this question, and, with plausible hypothesis about hardness of factoring bi-primes with asymmetric factor size, we get to $\kappa\approx n/4$ bit by the method in this answer.

With the constraint, there are several methods with a security argument to reach $\kappa\approx n/2$, some outlined in said question and in this other answer.

Marc Joye discuses the problem in RSA Moduli with a Predetermined Portion: Techniques and Applications (published in proceedings of ISPEC 2008). He proposes a method to reach $\kappa\approx n/3$: Algorithm 3, with $n_0\approx n/2$. But I do not see a clear argument that it does not weaken $N$ against some dedicated factoring algorithm.

$\endgroup$

1 Answer 1

1
$\begingroup$

Marc Joye's method to achieve $2n/3$ prescribed bits is essentially a streamlined version of the following. Bernstein attributes this method to Coppersmith (2003), but it's not clear whether Coppersmith ever published this method anywhere, or what the exact details of it were.

Let $n_0$ be the $2n/3$ prescribed most significant bits1. First, we find integers $p_0$ and $q_0$ such that $p_0q_0$ shares the $n/2$ most significant bits with $n_0$ by the usual method:

\begin{align} p_0 &\xleftarrow{\\\$} \left\{2^{n/2-1},\dots,2^{n/2}-1\right\}\,, \\ q_0 &= \left\lfloor\frac{n_0 2^{n/3}}{p_0}\right\rfloor\,. \end{align}

Now we hope that there are $p_1, q_1$ such that $(p_0 + p_1)(q_0 + q_1)$ is within a distance of at most $2^{n/3}$ of $n_02^{n/3} + 2^{n/3-1}$, in which case we have a candidate. To find them we turn to lattices. First, expand $(p_0 + p_1)(q_0 + q_1)$ into $$ p_0q_0 + p_0q_1 + p_1q_0 + p_1q_1 - \left(n_02^{n/3} + 2^{n/3-1}\right)\,. $$

Here we know $p_0q_0$ and $(n_02^{n/3} + 2^{n/3-1})$. However, $p_1q_1$ is unknown and we will have to take it into account as "error". Our goal is to find a point in the lattice spanned by the rows of $$ \begin{pmatrix} 2^{n/6} & p_0 \\ 0 & q_0 \end{pmatrix} $$ that is close to $(0, -(p_0q_0 - (n_02^{n/3} + 2^{n/3-1})))$. Using Kannan's embedding method, we can do that by finding a reduced basis of $$ \begin{pmatrix} 2^{n/6} & 0 & p_0 \\ 0 & 2^{n/3} & p_0q_0 - (n_02^{n/3} + 2^{n/3-1}) \\ 0 & 0 & q_0 \end{pmatrix} $$ and hope that one of the basis vectors has $2^{n/3}$ as its second element. Such a vector has the form $$ (2^{n/6}q_1, 2^{n/3}, q_1p_0 + p_1q_0 + p_0q_0 - \left(n_02^{n/3} + 2^{n/3-1}\right)\,. $$ The determinant of this lattice is at most $2^{n/6+n/3+n/2}$ and thus we expect shortest vectors to have length $\approx 2^{n/3}$, the approximate size of our error factor $p_1q_1$. So there's a good chance one of the 3 short vectors in the reduced basis is suitable. If so, recover $q_1$ and $p_1$ and test the primality of $p_0 + p_1$ and $q_0 + q_1$. Otherwise try again.

Here's an example replicating Joye's, finding a modulus matching the $1360$ most significant bits of the RSA-2048 challenge modulus:

n0 = 19619729042726075400928645234852108528127742528324495984210433970626973301838930917338140458111874216165019978095006438056189208714616362497368912877106434098033690744728107611196785018573785580653162016039972648338245044951355017127253514717288554503205967212528679357994195654527397700550196928365337114189575668964036187012738785361099417950233895619867184429437252674090375127581342502936419901606286707480
p0 = 162620115500125368557687896928679096076908630298961784944773841878432815950937985137049518325985583561089182509760251450429614807568377754003778301141692379940218567172817531161997378841364446146265934214297104659609840388161517843790631904512214725292690512053343507989384594958586019285500800377487422431944
q0 = n0*2^688 // p0
assert(2^1023 < q0 < 2^1024)
assert(n0*2^688 - p0*q0 < 2^1024) # ensure p0q0 shares 1024 MSBs with n0
M = Matrix(ZZ, 3, 3, [2^344,     0, p0, 
                          0, 2^683, p0*q0-(n0*2^688 + 2^687),
                          0,     0, q0])
B = M.LLL()
assert(B[0][1] == 2^683)
q1 = B[0][0]//2^344
p1 = (B[0][2] - p0*q1 - (p0*q0-((n0*2^688 + 2^687))))//q0
p = p0 + p1
q = q0 + q1
assert(p.is_prime() and q.is_prime())
assert(p*q >> 688 == n0)
print(hex(n0*2^688))
print(hex(p*q))

Now, is this method secure? This seems to be the case. Bernstein (Section 10) claims that it provably preserves security against attacks. The argument is that if $n_0$ is randomly chosen, an RSA key chosen by the above method is indistinguishable from an RSA key chosen by the standard method. In the usual $n/2$ compression method, this is obvious: a random $p, n_0$ pair completely determines $q$, and thus has the same distribution as a regular RSA key. In this case, and assuming the method succeeds, $p$ and $q$ are similarly determined by random $p_0$ and $n_0$.

In the case where $n_0$ is not random the above argument obviously does not apply, and there are certain values of $n_0$ that definitely make the modulus easier to factor (e.g., RSA-HP). But in the case where $n_0$ is picked in an unstructured "nothing up my sleeve" manner there appears to be no specialized attack that improves on any attack on a general RSA modulus. If many moduli sharing the same prescribed bits made it easier to break, the attacker could produce many such extra moduli themselves without the user's help. One might argue that because keys are obtained by finding a small $p_1$ added to $p_0$, there could be a ROCA-style attack hiding in there. However, because $p_0$ is random and not fixed, this attack strategy is not successful.


  1. There is an analogous method to prescribe the least significant bits, but it's worse for exposition.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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