Find the secret key for this function

[dila]

bool check(uint64_t key)
{
    return key * key * key * key * key * key * key == 0x90de757572b51cd3;
}

It returns true for the the correct key, but what is it and how do you find it?

[Conquest]

find the 7th root of the value. Any mathematics solver program should be good enough

[SmilingWolf]

Originally Posted by Conquest

find the 7th root of the value. Any mathematics solver program should be good enough

Yeah... except that the 7th root of that value is not an integer while the input to the function is.
You have to find an x such that (x^7 & 0xFFFFFFFFFFFFFFFF) == 0x90de757572b51cd3

[anon_c]

@Conquest
Not exactly. Bear in mind the Int64 precision.

Say you work in 16 bits
You want X^7 == 8680
Solve for the 7th root and you will get in decimal 4.44712��
But a valid solution would be for instance: 4A (74 dec) because the result of 4A ^ 7 is 8680 in 16bit

@Dila
I don��t see any other option than brute force

AC

[Kerlingen]

E80E9AAC619831FB

And no, I didn't bruteforce 20.000 years, it's just simple math.

Just as a small hint:
If "x^7" is supposed to end on the digit "3", could "x" ever be a multiple of "2"?
Answer: No.
You've reduced the number of possible values for "x" by 50%.

[Syoma]

It is the standard x^y mod n = c like RSA uses but with bad modulo N.

[UniSoft]

#define EXP7(x)  ((x) * (x) * (x) * (x) * (x) * (x) * (x))

uint64_t res = 0x90de757572b51cd3ULL;
uint64_t key = 0;
uint64_t mask = 1ULL;

while (mask)
{
    if ((EXP7(key) ^ res) & mask)
    {
        key |= mask;
        if ((EXP7(key) ^ res) & mask)
            break;
    }
    mask <<= 1;
}

if (mask)
    printf("not found");
else
    printf("found: 0x%llX", key);

[Kerlingen]

RSA is x^y with known x and unknown y.
This is x^y with unknown x and known y.
Two completely different things.

[niculaita]

try this 0xFFFFFFFFFFFFFE0B or this 0xFFFFFFFFFFFFFE0C

[anon_c]

@Kerlingen
��just simple math��
What is the mathematical solution then? (I know it is not a difficult key to find��)

I believe everybody knows you don��t have to try all numbers! Indeed, simple math can be used to avoid nonsense bases. But I am curious to know your definition of brute force. Do you really believe trying all possible solution is the only definition? Dictionary attack over a WPA key for instance, is still a kind of Brute-force attack��

AC

[Syoma]

Originally Posted by Kerlingen

RSA is x^y with known x and unknown y.
This is x^y with unknown x and known y.
Two completely different things.

RSA powmod primitive is
c = m^e mod N, where c is ciphertext, m - message, e - public exponent, N - modulus
m = c^d mod N, where d is private exponent

our case is
0x90de757572b51cd3 = key^7 mod (max_uint64+1)

[UniSoft]

Originally Posted by Syoma

RSA powmod primitive is
c = m^e mod N, where c is ciphertext, m - message, e - public exponent, N - modulus
m = c^d mod N, where d is private exponent

our case is
0x90de757572b51cd3 = key^7 mod (max_uint64+1)

This is not the RSA !!!
In RSA N = p * q, where p and q are prime numbers!!!
max_uint64+1 = 0x10000000000000000 is not the product of two prime numbers, therefore the equation m = (m^e mod N)^d mod N will not work (mainly because of the large number of collisions).

[Syoma]

Originally Posted by UniSoft

This is not the RSA !!!

Did you ever read the topic? I wrote
It is the standard x^y mod n = c like RSA uses but with bad modulo N.
I did not write it is RSA. My suggestion was there may be simple math solution in number theory.

Just reviewed most popular directions. Do not see any simple solution.
x^7 = 3*3*31*4129*1499933*6041353 mod 2^64

[DARKER]

0x90de757572b51cd3 = 10438910133587483859

10419912285387762041 = 521 ^7
10438910133587483859 = ~521,136 ^7 <- this is your number
10560719825892021888 = 522 ^7

but your key is uint64, so this is not possible because ~521,136 is not integer

PS: Other solution can be some another integer, it's case when you strip result to uint64 (last bytes of result are 0x90de757572b51cd3 - it's just end of some big number)

[dila]

In textbook RSA, you compute phi(n) from (p-1)(q-1), but that formula does not work if the modulus contains repeated prime factors. Here we have n = 2^64, so there are repeated 2's.

The requirement for modular exponentiation to be reversible is that gcd(e, phi(n)) = 1. If that turns out to be true, then a private exponent exists, which can "decrypt" the magic constant into the value of key.

@UniSoft: How does your solving code work??