The common complaint that I've received about my attack is that it doesn't work on real keys in real time on my laptop. Now, this is a silly bar to set. The real question is what happens on a fast computer. (If I can break a 1024 bit key in 1000 years on my computer, this is a significant improvement over current methods and will put keys at risk on a supercomputer. I don't have 1000 years or a supercomputer.)

## Advertising

But I take the point and I've been working on it. And I think I've got it. What we're looking for is a loop exponent 'k' for message 'm' and semiprime 'n' such that m^k % n = 1. In order for this to be true m^k - 1 = a*n for some integer 'a'. And if we can stick to m=2 for a moment then 2^k - 1 is going to be of a known form - a binary number with every digit equal to 1. Which means that if we can find an integer 'a' such that a*n is all 1s in binary then we can easily find 'k'. And this is actually really straightforward. In fact, ignoring the nasty underflow problem Perl has with their bignum arbitrary precision package which gives faulty values for really small values of 'n', I'm able to quickly find the smallest loop exponent for 2 and a given semiprime. And it takes 'k' operations. (I've attached my proof of concept code. It's messy and uncommented but it works for values that don't fail due to underflow). I haven't tried to extend this to other messages yet but it seems like it could be straightforward - m^k - 1 expressed in base 'm' will always be a string of digits which equal m-1. It's easy to find the values in binary, in other bases it will be given by a*b % m = m-1 (or something like that). But even if this approach is somehow unusable in other bases, it gives the minimum loop exponent for m=2 and that is worth quite a lot. The loop exponent for 2 can then be fed into my original search to scale the exponents and greatly accelerate things. And the loop exponent will also work for lots of other messages. So I'm still working on this but I'm getting close to making this run very fast. Which was really my bigger point all along. It's not that I thought I found the fastest method, I simply saw the existence of a vulnerability which allowed for decryption without factoring as a point for serious concern. The concern being that somebody could look at what I had done so far and come up with a really fast method to break keys. Which might be exactly where I am. Let me know if your people have any thoughts or questions. Thanks! Gabriel

**
backfill.pl**

*Description:* Perl program