Skip to main content
Cryptography

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

4
  • $\begingroup$ In your conditions, and for those many verification implementations that accept only one or a few discrete values of $n$, $S<pq<2^n$ should be the slightly tighter $\max(S,2^{n-1})<pq<2^n$. Make that $\max(S,2^{n-8})<pq<2^n$ where $n$ is the bit size of the bytestring $S$ for a PKCS#1-conformant implementation with no constraint on $n$. If we do not care about the security of the exhibited public key, your approach can be made computationally easy by allowing more than two factors. $\endgroup$ Commented Jul 1, 2013 at 5:40
  • 1
    $\begingroup$ @fgrieu: as for $\max(S, 2^{n-8}) < pq$, you are correct. I knew about that constraint when I was writing it; I skipped it in a (possibly poor) attempt to try to make more compact (and I forgot about the $\max$ construct, thinking of it as two separate inequalities). As for making the key out of more than two factors, I don't believe that that would make the construction significantly easier. $\endgroup$ Commented Jul 1, 2013 at 13:37
  • 1
    $\begingroup$ @fgrieu: we're attacking the problem in a completely different way; we're solving the discrete log problem $S^{e_p} \equiv Pad(M)\ (\bmod p)\ $ to give us the value $e_p$. This is feasible for large $p$, as long as $p$ is carefully chosen (that is, we make sure that $p-1$ is smooth). $\endgroup$ Commented Jul 1, 2013 at 17:07
  • $\begingroup$ Of course you first choose the primes and then find $e_p$, my mistake. I realized that just after writing my previous comment (again; I got it when you first posted). Sorry about that, my mind is warped by currently struggling with factoring. You can forget my remark about multiple primes too. $\endgroup$ Commented Jul 1, 2013 at 17:08