Skip to content

Instantly share code, notes, and snippets.

# geekman/int_divide.goSecret Created Jun 20, 2017

64-bit integer divide (also the solution to PAN CTF 2017, mobile 1)
 package main import ( "fmt" "math/big" ) func bigInt(n uint64) *big.Int { return new(big.Int).SetUint64(n) } func main() { // x * -37 == 17206538649 // trying to solve for x here // let's express that as: x * b == a big1 := bigInt(1) a := uint64(17206538649) // 91 - 42 = 49 b := int64(-37) bb := uint64(b) // re-interpret b as an unsigned 64-bit number // modulus is 64 because Longs are 64-bits N := new(big.Int).Lsh(big1, 64) // modulus is 1 << 64 Nmask := new(big.Int).Sub(N, big1) // mask is 0xFFF... (64 bits) // calculate multiplicative inverse of b using extended Euclidean algo // see https://math.stackexchange.com/questions/1583264/multiplicative-inverse-of-47-mod-64 invB := new(big.Int) gcd := new(big.Int).GCD(invB, nil, bigInt(bb), N) if gcd.Cmp(big1) != 0 { panic("GCD != 1") } // now to divide a by b // we simply rewrite it to be inv(b) * a x := new(big.Int).Mul(invB, bigInt(a)) // truncate to 64-bits x.And(x, Nmask) fmt.Printf("ans = %d signed %d", x, int64(x.Uint64())) }
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.