anonymousking123 Posted January 29, 2015 Share Posted January 29, 2015 Problem Description:Being a some constant, further assume that weare in a factor ring (basically all operations modulo some sumber p). Note, that the division below is a multiplication by the modular inverse.You always have to start with x=9.Consider the following recursive formula: Code: new_x = (x²-1)² / (4*x*(x²+a*x+1)) How often do you have to perform this operation to get a specific x (basically getting the new_x and feeding it back into the formula to get another new_x, and so on)?Note: You can start multiple such chains beginning at x=9, and add the resulting x valuesusing the addition algorithm from http://en.wikipedia.org/wiki/Montgomery_curve (Montgomery arithmetic section).Note, that the x value, is the value you get at the end of such calculation-chain, and the z value is always 1.The answer:The formula must work in all cases, and be computationally feasible (let us say calculable in less than 24 hours). NOTES: For the record, this is the posted solution: Code: <script>var equation= "(x²-1)² / (4*x*(x²+a*x+1))";var a=0;var b=10;while(a<b){var equation = equation.replace("x", "(x²-1)² / (4*x*(x²+a*x+1))");a=a+1;}document.write(equation);</script>Where b is the specific new_x you are looking for so for new_x=10(((((((((((x²-1)² / (4*x*(x²+a*x+1))²-1)² / (4*x*(x²+a*x+1))²-1)² / (4*x*(x²+a*x+1))²-1)² / (4*x*(x²+a*x+1))²-1)² / (4*x*(x²+a*x+1))²-1)² / (4*x*(x²+a*x+1))²-1)² / (4*x*(x²+a*x+1))²-1)² / (4*x*(x²+a*x+1))²-1)² / (4*x*(x²+a*x+1))²-1)² / (4*x*(x²+a*x+1))²-1)² / (4*x*(x²+a*x+1))where x=9 By no means the formula evaluates to 10, when I insert 9.Also, additionally to that, the division must be a multiplication with the modular inverse modulo p (just as a hint for future tries). @MODS: Also, this has nothing to do with homework, this to solve a complex problem with some suspect code ive been writing and i need a science formula or math formula expert and it needs to be correct *-ring[edit]In mathematics, a *-ring is a ring with a map * : A → A that is an antiautomorphism and an involution.More precisely, * is required to satisfy the following properties:[1](x + y)* = x* + y*(x y)* = y* x*1* = 1(x*)* = xfor all x, y in A. Link to comment Share on other sites More sharing options...

Phi for All Posted January 29, 2015 Share Posted January 29, 2015 @MODS: Also, this has nothing to do with homework, this to solve a complex problem with some suspect code ive been writing and i need a science formula or math formula expert and it needs to be correct ! Moderator Note OK, not homework, and a public posting of answers. We're good. Link to comment Share on other sites More sharing options...

anonymousking123 Posted January 29, 2015 Author Share Posted January 29, 2015 ! Moderator Note OK, not homework, and a public posting of answers. We're good. so do you have any idea how to solve this issue? Link to comment Share on other sites More sharing options...

anonymousking123 Posted February 7, 2015 Author Share Posted February 7, 2015 could be easily done, by actually using the x-coordinate only. Right now the Montgomery Curve 25519 is transformed to Kolbitz Representation with full (x,y) instead of only the (x) coordinate. Also, addition is not made using montgomery-steps but by simple mathematic arithmetic. Should be doable. Link to comment Share on other sites More sharing options...

fiveworlds Posted February 7, 2015 Share Posted February 7, 2015 (edited) here var equation = equation.replace("x", "(x²-1)² / (4*x*(x²+a*x+1))"); should read var equation = equation.replace(/x/gi, "(x²-1)² / (4*x*(x²+a*x+1))"); which I already tested for you <script> var equation= "(x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))"; var a=0;var b=1;var x=9; document.write(equation+"</br>"); while(a<b) { var equation = equation.replace(/x/gi, "(x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))"); document.write(equation+"</br>"); a=a+1; } var x2=x*x; var answer=(x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1)); document.write(answer+"</br>"); var answer=((x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))*x-1)*(x*x-1) / (4*x*(x*x+a*x+1)); document.write(answer+"</br>"); var x=9; var answer=(x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1)); document.write(answer+"</br>"); var x=answer; var answer=(x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1)); document.write(answer+"</br>"); var x=9; var answer=((x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))*(x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))-1)*((x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))*(x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))-1) / (4*(x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))*((x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))*(x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))+a*(x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))+1)) document.write(answer+"</br>"); </script> I also changed (x²-1)² / (4*x*(x²+a*x+1)) and used (x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1)) instead because javascript can directly evaluate it. Just for demonstation purposes I left var x=9; var answer=(x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1)); document.write(answer+"</br>"); var x=answer; var answer=(x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1)); document.write(answer+"</br>"); which is evaluation by recursion. Find the answer plug it back into the equation etc. Compared with the created equation var x=9; var answer=((x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))*(x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))-1)*((x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))*(x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))-1) / (4*(x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))*((x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))*(x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))+a*(x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))+1)) document.write(answer+"</br>"); both of which return the same answer so the code in the end is <script> var equation= "(x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))";var a=0;var b=6;var x=9;var c=0;document.write(eval(equation)+"</br>"); while(c<b){var equation = equation.replace(/x/gi, "(x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))"); document.write(equation+"</br></br>");document.write(eval(equation)+"</br>");c=c+1;} </script> This will give you just the answers minus the equations <script> var equation= "(x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))";var a=0;var b=6;var x=9;var c=0;document.write(eval(equation)+"</br>"); while(c<b){var equation = equation.replace(/x/gi, "(x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))"); document.write(eval(equation)+"</br>");c=c+1;} </script> Edited February 7, 2015 by fiveworlds Link to comment Share on other sites More sharing options...

anonymousking123 Posted February 7, 2015 Author Share Posted February 7, 2015 (edited) thats wrong it is not correct If you have a generator element b of an additive group of order N, and you know it takes x repeated doubling operations (squaring operations in the context of a multiplicative group) on this element in order to reach q then you have effectively solved [multiplicative group notation]: q = b^{2x}for x.What we really want to do is crack the discrete logarithm, which means finding x in the context of: q = b^{x}So the question becomes: if we can solve the first equation can we solve the second? The answer is yes. The reason is that the exponent of b is itself an element of it's own multiplicative group ℤ_{N}^{×} of which 2 is a generator since N is prime (at least in the context of Curve25519 or secp256k1).So if you find x that satisfies: q = b^{2x}then you can use your solution to solve the discrete log easy peasy lemon squeezy.: log_{b}(q) = 2^{x} mod N Edited February 7, 2015 by anonymousking123 Link to comment Share on other sites More sharing options...

Strange Posted February 7, 2015 Share Posted February 7, 2015 thats wrong it is not correct You will soon learn to ignore 99% of fiveworld's posts. Link to comment Share on other sites More sharing options...

imatfaal Posted February 7, 2015 Share Posted February 7, 2015 ! Moderator Note anonymousking123 please don't swear or use foul language - even in frustration Link to comment Share on other sites More sharing options...

John Posted February 7, 2015 Share Posted February 7, 2015 (edited) I'm not entirely sure what you're asking here, but a couple of things popped into my mind while reading:1. Using the formula for new_x presented in your OP, if we have to start with x = 9, then we have (x^{2} - 1)^{2} = 6400, which means the formula will never reach 10 for any p where 6400 = 0 (mod p), or for which (6400^{2} - 1)^{2} = 1677721518080001 = 0 (mod p), etc. 2. Though you possibly qualified it by saying "at least in the context of...", I just thought I'd note that 2 is not necessarily a generator of ℤ_{p}^{×} where p is prime. Consider, for example, p = 7.Of course, I may be misunderstanding entirely what you're wanting to do. Edited February 7, 2015 by John Link to comment Share on other sites More sharing options...

anonymousking123 Posted February 7, 2015 Author Share Posted February 7, 2015 (edited) The 'p' in (mod p) is 2^255 - 19 and I'm not searching for 10 but rather some arbitrarily large number such as83402281777707715381485212681368749158073214888176003645002923212220704930559 Edited February 7, 2015 by anonymousking123 Link to comment Share on other sites More sharing options...

John Posted February 8, 2015 Share Posted February 8, 2015 Alright, though you did say any formula we produce should work "in all cases," which I take to mean for general p and general x. Having re-read the thread, I noticed a few things I missed earlier. Are you essentially trying to find a general method for quickly finding the discrete logarithm? Are you looking to break elliptic curve cryptography? Link to comment Share on other sites More sharing options...

anonymousking123 Posted February 8, 2015 Author Share Posted February 8, 2015 (edited) pm sent so take that as a yes and as far as anyone else can make out of this, were looking to prevent this vulnerability we found somewhere from happening so anyone with any advice would and could be potentially rewarded if they'd like as a prize! Edited February 8, 2015 by anonymousking123 Link to comment Share on other sites More sharing options...

anonymousking123 Posted February 8, 2015 Author Share Posted February 8, 2015 Well, this is the point,let us say you have the following parameters:a = 486662modulus = 2^255 - 19Then you are right, to look for new_x=10 cannot be obtained by the formula, that means there is no "point doubling possible" that will result in new_x = 10 from any starting point.But you can use montgomery point addition to add x=9 to the desired new_10 = 10, but this point can be maybe obtained by looking for different points than newx_10, which then (added by montgomery rules) will result in new_x = 10.This is the essential task here. Link to comment Share on other sites More sharing options...

anonymousking123 Posted February 8, 2015 Author Share Posted February 8, 2015 An approach idea.Take an arbitrary x value (the one that is looked for, and find the point, that caused that value when inserted into the formula.In Mathematica that would be:Solve[(x*x - 1)^2/(4*x*(x*x + 486662*x + 1)) == THEVALUETOLOOKFOR, Modulus -> 2^255 - 19]Then go back the whole chain, unti you reach x=9.This can sometimes be tricky, that is why you probably have to think about it further. Link to comment Share on other sites More sharing options...

## Recommended Posts

## Create an account or sign in to comment

You need to be a member in order to leave a comment

## Create an account

Sign up for a new account in our community. It's easy!

Register a new account## Sign in

Already have an account? Sign in here.

Sign In Now