Find the secret key for this function

[mr.exodia]

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

from z3 import *

key = BitVec('key', 64)
solve((key * key * key * key * key * key * key) == 0x90de757572b51cd3)

Output:

[key = 16721472531635646971]
0xE80E9AAC619831FB

[dila]

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.

#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;
}

[aliali]

Originally Posted by dila

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.

#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

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;
}

Originally Posted by mr.exodia

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

from z3 import *

key = BitVec('key', 64)
solve((key * key * key * key * key * key * key) == 0x90de757572b51cd3)

Output:

[key = 16721472531635646971]
0xE80E9AAC619831FB

I still don't get it

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

[chessgod101]

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