Tags: reversing rsa 

Rating: 5.0

## analysis
We get a binary and an full excution trace of one run of the binary. After analyzing the binary, we soon came to the conclusion, this is a handwritten RSA decryption
doing C^D mod N (C is user input number). The intresting part here: for the modular power a [square and multiply](https://en.wikipedia.org/wiki/Exponentiation_by_squaring) algorithm is used. this algorithm is left shifting the bits of the userinput and if highest bit is one it will do modular multiplication, else nothing for calculating the RSA.

## insight
so related to the fact we have an excution trace, we can look at the place in the code, where based on top most bit the decison is done, to do multiplication or not, and from that decision we can directly see the bitvalue, so all needed to do is to check every time the algo does that compare (highest bit 1 or 0) and record the bits.
those bits converted to a decimal number will be our input to get the flag

4013b6: 48 b8 00 00 00 00 00 movabs $0x8000000000000000,%rax
4013c0: 48 39 c2 cmp %rax,%rdx

4013c3: 75 40 jne 401405 <main+0x1cf> <------
401405: 8b 85 b0 f9 ff ff mov -0x650(%rbp),%eax

40140b: 48 98 cltq
40140d: 48 8d 14 c5 00 00 00 lea 0x0(,%rax,8),%rdx

## doing it with grep and other linux command line tools :-)

- grep the tracefile for the "jne 401405 <main+0x1cf>" at 4013c3 and output the following line, so we know where the execution went (-A 1)
- drop grep line separators with --no-group-separator
- drop the 4013c3 lines from the jne
- use awk printing 0 or 1 depending on next lines address
- evaluate that expression and put it into bc for converting to base 10
- avoid line breaks in bc with BC_LINE_LENGTH = 0

## solution:
echo "obase=10; ibase=2; $(grep --no-group-separator -A 1 4013c3 trace | grep -v '4013c3' | awk '{if($1 == "401405:") printf "0"; else printf "1";}') " | BC_LINE_LENGTH=0 bc

results in:

which gives us the flag, when input into challenge executable :-)

#### dam{and_1nto_d4ta_depend3ncy}