2 ms·

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 atta

by pbsd 11y ago

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. Below is the prime number corresponding to the interpretation of the byte array I was speaking of: 3c6d8e07b9ec437a4177a6c5efbc95994aaf1246780e7d17 4d7f75538ecebfabf5af04f66d4f37f086734a0b046928ac bdbb8f7a43c8d38df5f890a8d66dfc00c6058e9908c6609b 03bff987e840bc0ecbbfc857cbc822bf941c9259255f5b22 cea945a2d8a91694b3bfa7bcc1cee388550cb8263e0e46c5 59a496dff2dccc17

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 ago
  You'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 ago
    I 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.

by pbsd 11y ago

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 ago
You'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 ago
  I 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.