3 ms·

> And the first factor - get a load of this - is 231. Which... yes, 231 = 3 * 77. Why isn't the first factor just 3 then?

ColinWright 11y ago
When you use factoring algorithms other than simple trial division - things like Pollard rho and its ilk - you are not guaranteed to get the smallest factor(s) first. Sometimes you get bigger factors, or combinations of factors, because those are what happen to pop out of the algebraic structure you're running over. But any "primes" being used should have some serious factorisation algorithms run over them before being used, so this is really embarrassing. EDIT And to answer contravariant's question[0]: Also, shouldn't it only have 2 prime factors? It's possible that one of the "primes" it found was in fact composite, and it's that "prime" that has these factors. So you generate two large primes and multiply them together, not realising that one of your "primes" wasn't. [0] https://news.ycombinator.com/item?id=9561051 https://news.ycombinator.com/item?id=9561051
- jugad 11y ago
  Large pseudo prime generators usually check for divisibility by numbers upto a million or so, then follow it with Rabin-Miller or more sophisticated non-deterministic tests to verify primes. These primes could not have been generated by any reputable prime generation algos that I can imagine.
contravariant 11y ago
Also, shouldn't it only have 2 prime factors?
- detaro 11y ago
  Should. Obviously something went very wrong and the "primes" weren't properly checked to actually be primes.
  - contravariant 11y ago
    Well, obviously something went wrong. But the way I understand it RSA shouldn't work at all if you used a composite factor, decrypting a message will just give a wrong result. Unless, by some incredible fluke, they managed to find a carmichael number.
    - deleted 11y ago
      [deleted]
    - dfox 11y ago
      RSA without CRT optimization of private operations will work regardless of how many factors modulus has, if key was generated correctly. With "correctly" meaning using correct value of phi(n), which is not (p-1)*(q-1) when either of p or q are composite (which in effect means that it will not work at all with essentially all interesting implementations). IIRC PKCS#1 even supports more than two modulus factors in it's private key format (not that it is particularly useful for anything).
jugad 11y ago
They used the GCD (greatest common divisor) algo to find any common divisors between 2 large keys. 231 was such a number. This signals to me that both the keys are corrupted/bad to have really small prime factors (3, 7 and 11). I have taken courses on discrete math, cryptography and read a few prime generation algos. Its a standard first step to check numbers against primes upto a million or so (nowadays, a billion). No prime generation algo I can imagine generated these keys.

ColinWright 11y ago

When you use factoring algorithms other than simple trial division - things like Pollard rho and its ilk - you are not guaranteed to get the smallest factor(s) first. Sometimes you get bigger factors, or combinations of factors, because those are what happen to pop out of the algebraic structure you're running over. But any "primes" being used should have some serious factorisation algorithms run over them before being used, so this is really embarrassing. EDIT And to answer contravariant's question[0]: Also, shouldn't it only have 2 prime factors? It's possible that one of the "primes" it found was in fact composite, and it's that "prime" that has these factors. So you generate two large primes and multiply them together, not realising that one of your "primes" wasn't. [0] https://news.ycombinator.com/item?id=9561051 https://news.ycombinator.com/item?id=9561051

jugad 11y ago
Large pseudo prime generators usually check for divisibility by numbers upto a million or so, then follow it with Rabin-Miller or more sophisticated non-deterministic tests to verify primes. These primes could not have been generated by any reputable prime generation algos that I can imagine.

contravariant 11y ago

Also, shouldn't it only have 2 prime factors?

detaro 11y ago
Should. Obviously something went very wrong and the "primes" weren't properly checked to actually be primes.
- contravariant 11y ago
  Well, obviously something went wrong. But the way I understand it RSA shouldn't work at all if you used a composite factor, decrypting a message will just give a wrong result. Unless, by some incredible fluke, they managed to find a carmichael number.
  - deleted 11y ago
    [deleted]
  - dfox 11y ago
    RSA without CRT optimization of private operations will work regardless of how many factors modulus has, if key was generated correctly. With "correctly" meaning using correct value of phi(n), which is not (p-1)*(q-1) when either of p or q are composite (which in effect means that it will not work at all with essentially all interesting implementations). IIRC PKCS#1 even supports more than two modulus factors in it's private key format (not that it is particularly useful for anything).

jugad 11y ago

They used the GCD (greatest common divisor) algo to find any common divisors between 2 large keys. 231 was such a number. This signals to me that both the keys are corrupted/bad to have really small prime factors (3, 7 and 11). I have taken courses on discrete math, cryptography and read a few prime generation algos. Its a standard first step to check numbers against primes upto a million or so (nowadays, a billion). No prime generation algo I can imagine generated these keys.