Score:1

What is here the security parameter $1^\kappa$?

tv flag

Let it be $K$ a key generation algorithm which takes $(k,d)$ as input with $k$ as the bit length for $n=pq$ with $p,q \in \mathbb{P}$ and $d=|p-q|$ as the minimum distance between $p$ and $q$ (RSA). What would be the security parameter $1^\kappa$?

Would it be $\kappa=k+d$ or only $\kappa=k$ and if it were the case on what would it depends?

I searched the following links and could not find an answer to my question:

What does the expression $1^n$ mean as a function argument? Why does key generation take an input $1^k$, and how do I represent it in practice?

fgrieu avatar
ng flag
For RSA key generation per [FIPS 186-4](https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf#page=62), $k$ could be $3072$ (for security comparable to a 128-bit symmetric key), and $d$ could be $2^{k/2-100}=2^{1436}$. Adding such wildly different quantities makes no sense. Also $d$ has a standard meaning in RSA. What about $|p-q|>2^δ$? Independently: I know no mathematically justified reason why enforcing a minimum $|p-q|$ in RSA key generation would improve security comparing to not doing so. And over-increasing $δ$ (say to $8n/9$) _decreases_ security. So why would $κ=k+δ$ make sense?
marius avatar
tv flag
The question if this makes sense or what other security requirements would be I especially asked in another post. But it may be, for example, that someone starts with $int(\sqrt(n))$ when bruteforcing the factorization of $n$. Then such a distance would probably make sense. The question at this point would be whether it affects the definition of $\kappa$.
Score:1
ng flag

For reasons in my comment I'll asume we change the question to define $δ$ with $2^\delta<\lvert p-q\rvert$, and $\kappa=k+\delta$. FIPS 186-4 key generation would for example use $k=3072$ and $\delta=k/2-100=1436$.

I can't find any reference discussing asymptotic RSA security with a notation like $1^k$ that specify a minimum $\lvert p-q\rvert$. That's because:

  • Increasing $\delta$ past some point demonstrably decreases security. E.g. for $k=3072$ (which would give about 128-bit symmetric security) and $δ=1912$ we'd have $\min(p,q)<2^{161}$ and Lentra's ECM would likely allow to pull that factor of $n$.
  • Simple arguments that increasing $\delta$ improves security are flawed.
  • $\delta=0$ is believed fine.
  • The historical reason to introduce a lower bound for $\lvert p-q\rvert$ is that Fermat factorization has cost about proportional to $(p-q)^2/n$ times some polynomial in $k$, thus $\lvert p-q\rvert$ must not be too small. It was jumped from that fact to the conclusion that it's needed to specify an explicit minimum $\lvert p-q\rvert$, even though it's demonstrably enough to specify that $p$ and $q$ are chosen independently and roughly uniformly among primes in some interval like $[2^{(k-1)/2},2^{k/2})$ to insure Fermat factorization is hopeless, whenever $k$ is large enough to resist GNFS (or PPMPQS, which was long known in 1998 when the disputable decision was inked in ANS X9.31).

As requested in comment I'll nevertheless assume there's some reason to specify $\delta$, and that increasing $\delta$ increases security in some domain. In order not to contradict the fact in the first bullet point above, I'll assume $0\le\delta\le\alpha\,k+\beta$ for some reals $\alpha$ and $\beta$ with $\alpha\in[0,1)$. Under such hypothesis, it makes sense to define $\kappa=k+\delta$, and use that as the security parameter.

We could define RSA key generation for constant odd integer $e>1$ as: on input $1^\kappa$

  1. In polynomial time, choose integers $k$ and $\delta$ with $\kappa=k+\delta$ and $0\le\delta\le\alpha k+\beta$ (fail if that's impossible); suitable ways include $\delta\gets\left\lfloor\frac\alpha2\kappa\right\rfloor$ and $k\gets\kappa-\delta$.
  2. Choose $p$ uniformly randomly among primes $p$ in $[2^{(k-1)/2},2^{k/2})$ with $\gcd(p-1,e)=1$
  3. Choose $q$ uniformly randomly among primes $q$ in $[2^{(k-1)/2},2^{k/2})$ with $\gcd(q-1,e)=1$ and $2^\delta<\lvert p-q\rvert$.
  4. Compute $n\gets p\,q$ and $d\gets e^{-1}\bmod\operatorname{lcm}(p-1,q-1)$, output public key $(n,e)$ and private key $(n,d)$.

It's believable that: for any valid choice of $e$ in this key generation algorithm, for any polynomial $P$, there exists no Probabilistic Polynomial Time algorithm that when $\kappa$ grows breaks RSA encryption with non-vanishing probability within time $P(\kappa)$.

That plausible conjecture is demonstrably¹ implied by a commonly held and simpler form of the RSA conjecture for fixed/small public exponent, which removes step (1.), replaces the condition $2^\delta<\lvert p-q\rvert$ with $p\ne q$ in step (3.), and uses $k$ where there's $\kappa$. We have no proof the conjectures are equivalent, but no compelling reason to believe otherwise, thus many practitioners and most theoreticians use the simpler conjecture².


¹ Proof sketch: we assume there exists an $e$ and algorithm $\mathcal A$ that breaks RSA encryption with non-vanishing probability within time $P(\kappa)$ when using the RSA key generation with $2^\delta<\lvert p-q\rvert$. We use $\mathcal A$ to build an algorithm $\mathcal A'$ invoking $\mathcal A$ as a subprogram, which for the same $e$ breaks RSA encryption with some probability within time $P'(k)$ when using the RSA key generation with $p\ne q$. The probability is non-vanishing because $p$ and $q$ meet the condition insuring $\mathcal A$ works with a probability that we can lower-bound and is non-vanishing. We can establish $P'$ from $P$, $\alpha$ and $\beta$, and that $P'$ is still a polynomial. $\alpha<1$ comes into play.

² Often the condition $p\ne q$ is removed too, which introduces the possibility that decryption fails. That occurs for a vanishing proportion of generated keys, but some definitions of a cipher have no exclusion for such corner case, which is why we keep $p\ne q$.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.