Exetools - Find the secret key for this function

Exetools (https://forum.exetools.com/index.php)

- General Discussion (https://forum.exetools.com/forumdisplay.php?f=2)

- - Find the secret key for this function (https://forum.exetools.com/showthread.php?t=17619)

My code for solving (see here on how to install z3py):

Code:

from z3 import *



key = BitVec('key', 64)

solve((key * key * key * key * key * key * key) == 0x90de757572b51cd3)

Output:

Code:

[key = 16721472531635646971]

0xE80E9AAC619831FB

Here is my solution based on solving it as an RSA problem:

key^7 = x (mod 2^64)
x^d = key (mod 2^64)

Where d is the private exponent, calculated by finding the multiplicative inverse of 7 modulo phi(2^64) = 2^63, which turns out to be 0x6db6db6db6db6db7.

Raising the magic constant to this private exponent, and taking modulo 2^64, produces the seret key 0xe80e9aac619831fb, as found by Kerlingen, UniSoft, and mr.exodia.

Code:

#include <iostream>

#include <stdint.h>

 

uint64_t modexp(uint64_t a, uint64_t b) {

  uint64_t y = 1;

  uint64_t tmp = a;

  for (int i = 0; i < 64; ++i) {

    uint64_t mask = uint64_t(1) << i;

    if (b & mask) {

      y *= tmp;

    }

    tmp *= tmp;

  }

  return y;

}

 

int main() {

  uint64_t in = 0x90de757572b51cd3;

  uint64_t tmp = modexp(in, 0x6db6db6db6db6db7);

  uint64_t out = modexp(tmp, 7);

  if (in == out) {

    std::cout << "Success: " << std::hex << tmp << std::endl;

  } else {

    std::cout << "Error" << std::endl;

  }

  return 0;

}

Quote:

Originally Posted by dila (Post 105628)

Here is my solution based on solving it as an RSA problem:

key^7 = x (mod 2^64)
x^d = key (mod 2^64)

Code:

#include <iostream>

#include <stdint.h>

 

uint64_t modexp(uint64_t a, uint64_t b) {

  uint64_t y = 1;

  uint64_t tmp = a;

  for (int i = 0; i < 64; ++i) {

    uint64_t mask = uint64_t(1) << i;

    if (b & mask) {

      y *= tmp;

    }

    tmp *= tmp;

  }

  return y;

}

 

int main() {

  uint64_t in = 0x90de757572b51cd3;

  uint64_t tmp = modexp(in, 0x6db6db6db6db6db7);

  uint64_t out = modexp(tmp, 7);

  if (in == out) {

    std::cout << "Success: " << std::hex << tmp << std::endl;

  } else {

    std::cout << "Error" << std::endl;

  }

  return 0;

}

An enhanced version of modexp function

Code:

uint64_t modexp(uint64_t a, uint64_t b)

{

        uint64_t y = 1;

        uint64_t tmp = a;

        while( b )

        {

                if( b & 1 )

                        y *= tmp;

                tmp *= tmp;

                b >>= 1;

        }

        return y;

}

Quote:

Originally Posted by mr.exodia (Post 105626)

My code for solving (see here on how to install z3py):

Code:

from z3 import *



key = BitVec('key', 64)

solve((key * key * key * key * key * key * key) == 0x90de757572b51cd3)

Output:

Code:

[key = 16721472531635646971]

0xE80E9AAC619831FB

I still don't get it :confused:

Can anyone explain me the mathematical way to calculate this ?

I always come up to a different result.

Like:

0xE80E9AAC619831FB ^7 = 0x80BE33B7E7E4CB02B42B9C6FDF0D774CC0645D8992D29738EC470B848F80CFA482BA62D01E70C65E397E7EFE6F190D1990DE757572B51CD3

or something like that

Where is my "think failure" ?

- Seth

We are calculating this with a 64 bit precision constraint. Since you overload the numerical capacity of 64 bits, the rest of the information is lost as a result. Since you are calculating this with full precision, you need to and your result by 0xFFFFFFFFFFFFFFFF.
0x80BE33B7E7E4CB02B42B9C6FDF0D774CC0645D8992D29738EC470B848F80CFA482BA62D01E70C65E397E7EFE6F190D1990DE757572B51CD3 <- 64 bit value