upb's "Keygenme Sheg"

[difficulty: 2][protection: digital logic]

Your serial number encodes instructions for a stack-based machine that has instructions for AND, XOR, and PUSH.

The VM is called 16 times and the output must match some values calculated from your username.

This is extremely similar to Malfunction's "Digital Arithmetic" (which came later). In DA, your serial encoded a circuit of NAND gates, and it was shown that NAND gates can be used to make any circuit. In sheg, you have a stack machine, so it is a little harder to produce a functioning "circuit" (the binary operations can ONLY use the two values at the top of the stack, and can ONLY put a result at the top of the stack). Since NOT(x)=XOR(x,1), we get can combine with AND to get NAND, and thus we get anything.

EDIT: upb has informed me that his machine is evaluating a Zhegalkin polynomial, which is neat view of a logic circuit as a polynomial over GF(2).

No comments:

Post a Comment

thanks for commenting!