[ais3Final2018/mama] How to know the gadget to swap 0 and p-2

[nihwkroot]

Hello,

I really appreciated for this chal. But I am a little curios about how to find the gadget to swap (k / 2 + 1) * 2 - 2 and the gadget to map to 0 and p-1.

Thanks,
Lattice

[sasdf]

Thank you for liking this challenge.

Playing with smaller p (e.g. 7, 17, 31) could help you find it. Bruteforce all possibilities is very fast even with unoptimized python code.

p4 used the gadget ((k - 2) / 2 + 1) * 2 for chal primitive. I'm lucky enough to find swapping gadget while playing with some gadgets like that before I wrote bruteforce.

For mapping gadget, it is more difficult to interpret the bruteforce result because of the multiplicative inverse. I find it when think what these two operations, add and mul, can do. I noticed that addition won't change the difference between two numbers. To change the difference to one, you have to divide the difference.

[nihwkroot]

mm, very interesting. I am wondering if there is any way to prove the gadgets are existed. let me try it.

[nihwkroot]

Here is my idea. It is very similar to the original writeup. I try to explain the behaviour.

• add op f(x,y) = (x+y) mod n
• mul op g(x,y) = (x*y) mod n+1
  The special operation in mul is if r == n, r=0. this behaviour will help us to swap 0, n-1

1. map x->y to 0 -> n-1

   • mul to expand the distance k = x - y invert((x-y)%p, p)
   • add to shift map for x,y to 0, n-1 -mx%n

2. swap 0->n-1
   This is the key point in this chal. Divide by 2 can remap the 0, n-1 to (n-1)/2, 0

   • Divide by 2 mul(invert(2, p))
     After that, we can shift the (n-1)/2, 0 to n-1, 0
     I think this is how gadget works.

If I made any mistake, just let me know.

[sasdf]

Nice analysis.
I think you also need to prove that the swapping gadget will left other numbers as it was to say that we can build a solution using these two gadgets.