We are given a c function that does the integer division of the argument by a constant N.```clong long div(long long x) {    return x / N;}```
The constant is set at compile time```$ gcc -DN=$N -c -O2 foo.c```
Given the disassembly of the function we need to recover N```$ objdump -d foo.o
foo.o:     file format elf64-x86-64
Disassembly of section .text:0000000000000000 :   0:	48 89 f8             	mov    %rdi,%rax   3:	48 ba 01 0d 1a 82 9a 	movabs $0x49ea309a821a0d01,%rdx   a:	30 ea 49    d:	48 c1 ff 3f          	sar    $0x3f,%rdi  11:	48 f7 ea             	imul   %rdx  14:	48 c1 fa 30          	sar    $0x30,%rdx  18:	48 89 d0             	mov    %rdx,%rax  1b:	48 29 f8             	sub    %rdi,%rax  1e:	c3                   	retq   $ echo “HarekazeCTF{$N}” > /dev/null```
I tried at first to run the code in an emulator, but the movabs with a quad word immediate wasn't supported, so I rewrote the code in python.In the System V x86_64 calling convenction rdi holds the first argument of a function.  The disassembly is in the AT&T syntax, not the usual Intel syntax (e.g. mov %rdi, %rax means rax = rdi, that is move rdi to rax)```pythondef div(rdi):    rax = rdi    rdx = 0x49ea309a821a0d01    rdi = rdi >> 0x3f    rdxrax = rdx * rax    rdx, rax = rdxrax >> 64, rdxrax % (2 ** 64)    rdx = rdx >> 0x30    rax = rdx    rax = rax - rdi    return rax```
Since this function computes x / N, we have that the smallest x such that x / N = 1 is x = N.   Since x / N is a monotone function we can use binary search to efficiently find this x.
```pythonprint(div(2 ** 64 - 1))h = 2 ** 64 - 1l = 0while h - l > 1:    m = (h + l) / 2    if div(m) >= 1:        h = m    else:        l = m# we have that div(l) < 1 and l is non decreasing after each iteration# so at the end of the binary search l is the greatest x such that div(x) = 0# that in turn means that l + 1 is the smallest x such that div(x) = 1print(l + 1)print(div(l))
print(div(l + 1))```