3 ms·
Ahh, you were talking about the Socat modulus. I did miss that! Was it said somewhere or did you find it yourself? I'll check that later but nice finding! > Bu
by baby 11y ago
Ahh, you were talking about the Socat modulus. I did miss that! Was it said somewhere or did you find it yourself? I'll check that later but nice finding!
> But index calculus is the right way to do it, and it's not particularly difficult to exploit. P-H only puts a quadratic (at best) factor between you and an attacker; index calculus makes that gap subexponential.
Right now it just doesn't make sense to use index calculus. Method1 is to use a hidden (by the composite modulus) subgroup of small order for the generator. So for a 1024bits modulus, you would either try to do index calculus in a 512 bits modulus or do something like Pollard Rho with a small order.
For the second method you use Pohlig-Hellman on small orders as well, so it wouldn't make sense to use index calculus on a 512 bits modulus again.
Now imagine a 2048bits main modulus n=pq, the problem is now split into two 1024bits modulus p and q. There is no way you can use IC there. But the method I "explained" previously will work. The backdoor will be a NOBUS.
- pbsd 11y agoYou're misrepresenting my suggestion. The idea is to choose the factor size according to the complexity of ECM; the modulus size is irrelevant. So for a 2^80 security level, you choose factors of ~341 bits; relaxing the security to a 2^64-ish place, you can get away with 256-bit factors. This makes index calculus very quick, even on modest hardware, especially considering that the individual logarithm phase---the part you need to do in real-time---is much faster than the whole thing.
- baby 11y agoI see what you mean, but I don't see any reason to use NFS on the maximum sized group when you can reduce the size of that group (by using a generator of a "small" subgroup modulo each factor) and use a quicker Pollard Rho modulo each factors. You already have a significant advantage and you don't need any heavy pre-computations with NFS. By doing it your way, you do increase both my computation and the reverser's computation who tries to do Pollard Rho on the full subgroup size. Which is good, but what I found is that this is not necessary as doing it my way is already too hard for someone with no knowledge of the factors to use.