This message was too old and has been purged

[david123]

If you want a solution, don't raise the bounty but get your question right.

At the moment, this is not at all about finding a solution, but about guessing what
exactly you're asking for. You will only attract php-kiddies in this way.

[bitspill]

If you want a solution, don't raise the bounty but get your question right.

At the moment, this is not at all about finding a solution, but about guessing what
exactly you're asking for. You will only attract php-kiddies in this way.

When he posts test vectors we can infer the proper question.

[david123]

yeah, guessing will get a bit easier then, but I don't get why he doesnt spend the time
to make the question meaningful.. 

[ndnh]

If you want a solution, don't raise the bounty but get your question right.

At the moment, this is not at all about finding a solution, but about guessing what
exactly you're asking for. You will only attract php-kiddies in this way.

Yeah, I agree with this. My problem is I don't know exactly what the question is. I got the average idea but it is not enough. I also have to be sure it is under my capability to solve before attempting harder on it.

[Supercomputing]

Problem Description:

Being a some constant, further assume that we
are 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 values
using 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 winner:
The winner is the first person to post such formula in private. The formula must work in all cases, and be comutationally feasible (let us say calculatable in less than 24 hours).
If there are any wrong descriptions in this post at this time, they may be corrected or adjusted later on. Bounty ends on 02/15/2015.

The bounty is invalid because the problem description is ambiguous. However, it may be an attempt to solve the ECDLP based on Curve25519 for all instances:
http://en.wikipedia.org/wiki/Curve25519

[Jesse James]

The bounty is invalid because the problem description is ambiguous. However, it may be an attempt to solve the ECDLP based on Curve25519 for all instances:
http://en.wikipedia.org/wiki/Curve25519

My thoughts exactly.

Is the organizer willing to offer a consolation prize to anyone who can produce a proof that the original problem is impossible given the Elliptic Curve Discrete Logarithm assumption?

[Jesse James]

Here's my attempt to restate the original problem in a way that is less ambiguous and hopefully reveal more clearly the OP's intent.

Challenge: Optimize the 'find' function in the code below so that on average it can be computed for less than 1M USD in EC2 compute cost.

Code: (python)

# http://en.wikipedia.org/wiki/Curve25519 parameters
P = 2 ** 255 - 19
A = 486662
N = 7237005577332262213973186563042994240857116359379907606001950938285454250989

def expmod(b, e, m):
    if e == 0: return 1
    t = expmod(b, e / 2, m) ** 2 % m
    if e & 1: t = (t * b) % m
    return t

def inv(x):
    return expmod(x, P - 2, P)

# doubles a point on a montgomery curve (x-coordinate only representation)
# https://www.hyperelliptic.org/EFD/g1p/auto-montgom-xz.html#doubling-dbl-1987-m-3
def double(x1):
    xx1 = x1 * x1 % P
    x3 = (xx1 - 1) * (xx1 - 1) % P
    z3 = 4 * x1 * (xx1 * A * x1 + 1) % P
    return x3 * inv(z3) % P

def find(target, initial_point=9):
    assert 0 < target < P 
    assert 0 < initial_point < P
    x = initial_point
    i = 0
    while i < N:
        if x == target:
            return i 
        x = double(x)
        i += 1

[LiQio]

^ Jesse James/doctorevil this is so over my head.
All I can say is, you're such a cool guy  

*slightly blushes and continues to watch the thread*

[ndnh]

Here's my attempt to restate the original problem in a way that is less ambiguous and hopefully reveal more clearly the OP's intent.

Challenge: Optimize the 'find' function in the code below so that on average it can be computed for less than 1M USD in EC2 compute cost.

Code: (python)

# http://en.wikipedia.org/wiki/Curve25519 parameters
P = 2 ** 255 - 19
A = 486662
N = 7237005577332262213973186563042994240857116359379907606001950938285454250989

def expmod(b, e, m):
    if e == 0: return 1
    t = expmod(b, e / 2, m) ** 2 % m
    if e & 1: t = (t * b) % m
    return t

def inv(x):
    return expmod(x, P - 2, P)

# doubles a point on a montgomery curve (x-coordinate only representation)
# https://www.hyperelliptic.org/EFD/g1p/auto-montgom-xz.html#doubling-dbl-1987-m-3
def double(x1):
    xx1 = x1 * x1 % P
    x3 = (xx1 - 1) * (xx1 - 1) % P
    z3 = 4 * x1 * (xx1 * A * x1 + 1) % P
    return x3 * inv(z3) % P

def find(target, initial_point=9):
    assert 0 < target < P 
    assert 0 < initial_point < P
    x = initial_point
    i = 0
    while i < N:
        if x == target:
            return i 
        x = double(x)
        i += 1

Dang! I don't know Python or any programming language.

But I think I can get a better idea of the question. Thanks for posting this.

[bitspill]

Here's my C++ implementation: https://github.com/bitspill/CurveBounty

The version I PM'd you the other day was ATROCIOUS that was my mind at 4am and it suffered as such, here is a revamped version. If I'm on the right path I can make some adjustments but I don't want to pursue this if I'm running in the wrong direction.

[Evil-Knievel]

This message was too old and has been purged

[bitspill]

Here's my C++ implementation: https://github.com/bitspill/CurveBounty

The version I PM'd you the other day was ATROCIOUS that was my mind at 4am and it suffered as such, here is a revamped version. If I'm on the right path I can make some adjustments but I don't want to pursue this if I'm running in the wrong direction.

It is the right direction, but it looks like a brute force approach. If it works good (and fast) for all search x, this should be fine, but at this moment an x which is not a power of two would not be found. 

Yes it is brute forcing it.

I'm not sure as to what you mean by an x can't be found if it's not a power of two, the following x is not a power of 2:

Code:

x=83402281777707715381485212681368749158073214888176003645002923212220704930560
log_2(x) = 255.5266

If you are referencing the _i's those are only printed every 256 so as to not bog down performance with constant console writes but yet often enough to know it hasn't stalled.

[Evil-Knievel]

This message was too old and has been purged

[ndnh]

Here's my C++ implementation: https://github.com/bitspill/CurveBounty

The version I PM'd you the other day was ATROCIOUS that was my mind at 4am and it suffered as such, here is a revamped version. If I'm on the right path I can make some adjustments but I don't want to pursue this if I'm running in the wrong direction.

It is the right direction, but it looks like a brute force approach. If it works good (and fast) for all search x, this should be fine, but at this moment an x which is not a power of two would not be found.  

Yes it is brute forcing it.

I'm not sure as to what you mean by an x can't be found if it's not a power of two, the following x is not a power of 2:

Code:

x=83402281777707715381485212681368749158073214888176003645002923212220704930560
log_2(x) = 255.5266

If you are referencing the _i's those are only printed every 256 so as to not bog down performance with constant console writes but yet often enough to know it hasn't stalled.

it is not a power of two, because it was calculated modulo, but the exponent is a power of two. So you have doubled "x=9" 10240 times, so basically it is 2^10240 * (x=9) where the multiplication is the montgomery curve scalar multiplication.

You could say, that 83402281777707715381485212681368749158073214888176003645002923212220704930560 is easily found,
but 83402281777707715381485212681368749158073214888176003645002923212220704930559 not. And this is the tough case, because:

- the loop iteration can either grow arbitrary large
- or: you need to create multiple such iterations with different "i" values, and add them according to the montgomery curve addition rules.

I think this ^ is right. and also brute forcing it many not be feasible if the above points are taken?

But now you know what we are searching for.

[SargeR33]

I am a programmer/developer, pretty good with maths but this thread blew my brain multiple times.

[bitspill]

I am a programmer/developer, pretty good with maths but this thread blew my brain multiple times.

The wonders of cryptography.

[david123]

I am a programmer/developer, pretty good with maths but this thread blew my brain multiple times.

The wonders of cryptography.

Rather the incompetence of the op.

So, did someone get what he is asking for and could kindly repeat it in a clear, concise way without
abusing mathematical terms too much? That would be great.

[bitspill]

I am a programmer/developer, pretty good with maths but this thread blew my brain multiple times.

The wonders of cryptography.

Rather the incompetence of the op.

So, did someone get what he is asking for and could kindly repeat it in a clear, concise way without
abusing mathematical terms too much? That would be great.

It's basically what Jesse James and I were doing but we are only doubling, you must also check addition in order to satisfy his request

[david123]

yeuh but what are you doing? are you performing calculations on an
elliptic curve?

[bitspill]

yeuh but what are you doing? are you performing calculations on an
elliptic curve?

From what I gather we are brute-forcing searching Curve25519 for a specific number not disclosed to us