Solving discrete logarithms
in [Cryptography]
|
From: JSH on 29 Jun 2010 18:37 I've noted a fundamental result in modular arithmetic around studying the simple system of equations: f_1 = a_1*k mod N thru f_m = a_m*k mod N Specifically by noting that multiplying them together gives: f_1*...*f_m = a_1*...*a_m*k^m mod N, but ADDING them together gives: f_1+...+f_m = (a_1 + ...+ a_m)k mod N Note that the a's are what I call control variables, which can be set to ANY non-zero value. Remarkably enough that simple result allows one to handle k^m = q mod N through integer factorization. You can solve for k, when m, q and N are known, or for m, when k, q and N are known, and it is the latter I'll consider in more detail in this post. Since the a's are control variables their value can be set to some extent, with m degrees of freedom. To handle discrete logarithms entirely, over any m, I need to remove less than m of those degrees of freedom and do so with the following equations: a_1*...*a_m = q mod N and a_1+...+a_m = m mod N Then k^m = q mod N, and f_1*...*f_m = a_1*...*a_m*k^m mod N, with substitutions gives me: f_1*...*f_m = q^2 mod N and f_1+...+f_m = (a_1 + ...+ a_m)k mod N with substitution gives: f_1+...+f_m = mk mod N But so far I've removed only 2 degrees of freedom from the a's, so assume that for some unknown number m-c of the f's that the a's are simply the modular inverse of k, then for that number the f's simply equal 1, giving me: f_1+...+f_c + m - c = mk mod N Which allows me to solve for m, with: m = (k-1)^{-1}(f_1+...+f_c - c) mod N (If k-1 is not coprime to N, then factors in common would be divided off before the modular inverse operation, which actually gives another check for finding useable factors.) Notice that finding factors then becomes just a matter of considering solutions: f_1*...*f_m = q^2 mod N where m-c of the factors have been set to 1. So the reasons for that substitution is clear. Notice that c is found dynamically from the count of non-unit factors of q^2 mod N. Here's an example, solve for m, where: 2^m = 13 mod 23 so k = 2, and f_1*...*f_m = q^2 mod N = 13^2 mod 23 = 8 mod 23. And I found a solution with f_1*...*f_m = 54, and f_1 = 2, f_2 = 3, f_3 = 3, f_4 = 3 so c=4, and m = (k-1)^{-1}(f_1 +...+ f_c - c) mod N = 2+3+3+3 - 4 = 7 And 2^7 = 128 = 13 mod 23. Notice that the method then gives you the number c from factoring numbers q^2 mod N. The means mathematically that c of the a's have been set by the algebra itself to cancel out k, with the modular inverse, which is how this approach eliminates the advantage of a large m--the math simply handles it for you. And that is the basic research showing how a simple set of modular equations can lead to an approach to solving discrete logarithms through integer factorization. It is not clear at this time how practical it can be made to be. However, I would assume that it is a method that cannot simply be ignored as the idiot mutterings of some "crackpot". But if any of you do, I hope you pay the appropriate consequences if it turns out to be important. Paying as high a price as your world requires of you. No matter what the price might be. James Harris
From: Pubkeybreaker on 29 Jun 2010 18:51 On Jun 29, 6:37 pm, JSH <jst...(a)gmail.com> wrote: > > But if any of you do, I hope you pay the appropriate consequences if > it turns out to be important. Paying as high a price as your world > requires of you. No matter what the price might be. > > James Harris When are you going to tell us the year when you got your claimed degree at Vanderbilt??? You can also tell us why Vanderbilt will not confirm that you ever got a degree there. Doing so would put to rest the suspicions of many people who suspect that you are lying when you claim to have a degree in physics.
From: Noob on 30 Jun 2010 08:11 [ Reposted verbatim to sci.math ] From: JSH <jstevh(a)gmail.com> Newsgroups: sci.crypt Subject: Solving discrete logarithms Date: Tue, 29 Jun 2010 15:37:32 -0700 (PDT) Lines: 106 Message-ID: <42159356-d941-4d2d-a3ee-44ec63b7d487(a)k1g2000prl.googlegroups.com> I've noted a fundamental result in modular arithmetic around studying the simple system of equations: f_1 = a_1*k mod N thru f_m = a_m*k mod N Specifically by noting that multiplying them together gives: f_1*...*f_m = a_1*...*a_m*k^m mod N, but ADDING them together gives: f_1+...+f_m = (a_1 + ...+ a_m)k mod N Note that the a's are what I call control variables, which can be set to ANY non-zero value. Remarkably enough that simple result allows one to handle k^m = q mod N through integer factorization. You can solve for k, when m, q and N are known, or for m, when k, q and N are known, and it is the latter I'll consider in more detail in this post. Since the a's are control variables their value can be set to some extent, with m degrees of freedom. To handle discrete logarithms entirely, over any m, I need to remove less than m of those degrees of freedom and do so with the following equations: a_1*...*a_m = q mod N and a_1+...+a_m = m mod N Then k^m = q mod N, and f_1*...*f_m = a_1*...*a_m*k^m mod N, with substitutions gives me: f_1*...*f_m = q^2 mod N and f_1+...+f_m = (a_1 + ...+ a_m)k mod N with substitution gives: f_1+...+f_m = mk mod N But so far I've removed only 2 degrees of freedom from the a's, so assume that for some unknown number m-c of the f's that the a's are simply the modular inverse of k, then for that number the f's simply equal 1, giving me: f_1+...+f_c + m - c = mk mod N Which allows me to solve for m, with: m = (k-1)^{-1}(f_1+...+f_c - c) mod N (If k-1 is not coprime to N, then factors in common would be divided off before the modular inverse operation, which actually gives another check for finding useable factors.) Notice that finding factors then becomes just a matter of considering solutions: f_1*...*f_m = q^2 mod N where m-c of the factors have been set to 1. So the reasons for that substitution is clear. Notice that c is found dynamically from the count of non-unit factors of q^2 mod N. Here's an example, solve for m, where: 2^m = 13 mod 23 so k = 2, and f_1*...*f_m = q^2 mod N = 13^2 mod 23 = 8 mod 23. And I found a solution with f_1*...*f_m = 54, and f_1 = 2, f_2 = 3, f_3 = 3, f_4 = 3 so c=4, and m = (k-1)^{-1}(f_1 +...+ f_c - c) mod N = 2+3+3+3 - 4 = 7 And 2^7 = 128 = 13 mod 23. Notice that the method then gives you the number c from factoring numbers q^2 mod N. The means mathematically that c of the a's have been set by the algebra itself to cancel out k, with the modular inverse, which is how this approach eliminates the advantage of a large m--the math simply handles it for you. And that is the basic research showing how a simple set of modular equations can lead to an approach to solving discrete logarithms through integer factorization. It is not clear at this time how practical it can be made to be. However, I would assume that it is a method that cannot simply be ignored as the idiot mutterings of some "crackpot". But if any of you do, I hope you pay the appropriate consequences if it turns out to be important. Paying as high a price as your world requires of you. No matter what the price might be. James Harris
From: JSH on 30 Jun 2010 09:52 On Jun 30, 5:11 am, Noob <r...(a)127.0.0.1> wrote: > [ Reposted verbatim to sci.math ] <deleted> Yeah, if I try to post only to sci.crypt then sci.math regulars will follow over. They will often fill up a thread with insults and do it FAST. However, I'm also MORE likely to get replies on sci.math than on sci.crypt, and I'd like feedback, so the simple solution was to post the same thing on both newsgroups. The sci.math regulars who like to stalk my postings can post happily there and not feel a need to post here. Working well so far. Otherwise your cross-posting attempt would have been filled with replies. No need to cross post! I'm running discussions on this same topic on two newsgroups but without cross posting. James Harris
|
Pages: 1 Prev: Cryptanalyis by Cloning Definitions (Badly) from Regular Words. Next: JSH: So why do they lie? |