In October 2020 I pointed Ubuntu's pyecm at RSA-260, a 260-digit number nobody has ever factored. I knew it would not succeed. I did not expect it to crash. After about two and a half hours of searching, it died with a Python TypeError. I reported it on Launchpad, and a week later it was reproduced on Ubuntu and marked Confirmed as bug #1899312. This post is the story of that bug and what it taught me about testing.
TL;DR#
- The input: RSA-260, an unfactored 260-digit semiprime from the RSA Factoring Challenge.
- The tool:
pyecm, a Python implementation of the elliptic curve method (ECM) packaged in Ubuntu. - The crash:
TypeError: unsupported operand type(s) for >>: 'float' and 'int', raised inside the curve arithmetic after roughly 150 minutes. - The outcome: reported with the exact command, output and traceback; reproduced with pyecm 2.0.3 on Ubuntu and marked Confirmed.
What is RSA-260, and why try to factor it?#
RSA-260 is one of the numbers from the RSA Factoring Challenge: a product of two large primes, published so researchers could measure how hard factoring really is. Smaller numbers from the same list have been factored with huge distributed efforts; RSA-260 has not. Nobody factors it on a laptop, and that was never the point. I wanted to see how a general-purpose factoring tool behaves when you hand it a number far beyond what it was built for.
How does pyecm try to factor a number?#
The elliptic curve method looks for factors by doing arithmetic on randomly chosen elliptic curves modulo the number. It is good at finding small factors quickly, so pyecm searches in stages, raising the target factor size as it goes. On RSA-260 its progress looked like this:
Searching for primes around 15 digits
Searching for primes around 20 digits
Searching for primes around 25 digits
Searching for primes around 30 digits
Searching for primes around 35 digits
Each stage takes longer than the last. RSA-260's two factors are each about 130 digits long, so none of these stages could ever succeed. What I was really testing was how long the program would keep going.
What exactly crashed?#
During the 35-digit stage, pyecm stopped with this traceback (trimmed to the last frames):
File "/usr/bin/pyecm", line 927, in mainloop
pgiant_step = multiply(p1, big_multiple, n)
File "/usr/bin/pyecm", line 1134, in multiply
if (d >> pos) & 1:
TypeError: unsupported operand type(s) for >>: 'float' and 'int'
real 149m54.131s
The multiply function walks the bits of a multiplier with a right shift, d >> pos. That only works on integers. By the time execution reached it, d had become a Python float, and Python refuses to bit-shift a float. So a value that should have stayed an integer was silently turned into a float earlier in the computation, and nothing caught it until the shift.
Why didn't anyone hit this before?#
Because nobody runs that code path with these numbers. Factoring small inputs finishes in the early stages, long before the multipliers grow large enough to reach the failing branch. The bug only shows up deep into a long search, which is exactly where ordinary tests never go.
How do you write a bug report that gets confirmed?#
I gave the maintainers everything they needed to reproduce it without asking me a single question:
- The exact command, including the full 260-digit number.
- The full output, so they could see which stage it reached.
- The complete traceback and the elapsed time.
A week later the report was reproduced with pyecm 2.0.3 on Ubuntu and marked Confirmed. A report that can be reproduced by copy and paste is one people can actually act on.
Frequently asked questions#
Can pyecm factor RSA-260?#
No. ECM is designed to find relatively small factors. RSA-260's factors are each around 130 digits, which is far beyond what ECM can realistically find. Numbers of this kind are attacked with the general number field sieve and enormous amounts of compute.
Is this a security problem?#
No. It is a correctness bug in a factoring tool: the program crashes instead of continuing to search. It does not affect RSA keys or anything that relies on them.
Where is the bug report?#
On Launchpad as bug #1899312, including the full command and traceback.
Key takeaways#
- Extreme inputs reach code paths that normal tests never touch.
- In Python, an integer that quietly becomes a float can travel a long way before something fails.
- A good bug report is half the fix: exact command, exact output, exact version.
- Running tools far outside their comfort zone is a cheap way to find real bugs.
Have you found a bug just by pushing a tool further than intended? Tell me about it. I'm @khaledalam on GitHub.
Comments
No comments yet — be the first.