2
$\begingroup$

I consider $n$-bit RSA moduli $N$ having high-order bits starting by with $k$ bits at 1, then $k$ bits at 0, then $m-2k$ bits at $1$ for as large an $m$ as possible, with $n\in\{2048,3072,4096\}$ and $k\in\{8,16,32,64\}$.

For example, with $k=32$, the hex for $N$ would be FFFFFFFF00000000FFFFFFFFFFFFFFFF...

Otherwise stated, I want $2^n-2^{n-k}+2^{n-2k}-2^{n-m}<N<2^n-2^{n-k}+2^{n-2k}$.

How large can we confidently make $m$ while having a rationale that SNFS (or optimizations of GNFS made possible by the special form of $N$, or any other technique applicable to classical computers) won't make the factorization of $N$ sizably easier than for more conventional choice of $N$?

Assume $N=p\,q$ with $p$ and $q$ below $2^{n/2}$ and otherwise essentially random primes within the constraints on $N$.

Motivation: I'm thinking of making a tiny portable (C99) RSA signature verification function, to prove it can be done (context). There's no secret manipulated, thus no need for side-channel leakage protection, which is a huge simplification. The largest remaining potential simplification is in quotient estimation for modular reduction, which I guesstimate accounts for nearly 1/3 of the code size, and a lot of the complexity. The special form of $N$ allows to cut down on that, while leaving a large choice of $p$ and $q$ of $n/2$ bits (which is desirable to maintain compatibility with classical implementations for the private-key side).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.