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.
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.
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.
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.
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).
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]:
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