Radu - Oh the righteous indignation of public discussion! Stomp stomp. Do you feel better? Go have a teary elsewhere.
>Dear Grabriel, > >To be honest, I didn't have the motivation to understand the attack. >However, the way you handle the disclosure bothers me. >Instead of spamming in a "bug" openbsd mailing list and Reddit, do the >following: >1) contact a "crypto mathematician expert" from the closest >university/google/.../etc and convince him that you are right; >2) he will certainly help you write a research paper and submit to a >well known crypto conference; >3) wait for other experts around the world to find flaws in your reasoning. >If it occurs that you are right, people will react. > >Sincerely, >Radu > >On 02/02/2018 09:25 PM, Gabriel Withington wrote: >> 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.) >> >> 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 > > >
