Find the secret key for this function

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