Because I am lazy and easily sidetracked, the promised update to the "Hacker challenge" (part 1, part 2) is now over seven months late. So I might as well post the solution to part 2, which was solved by three individuals on reddit (bobdole, c0dep0et, and xahtep).
Part 2 used DSA, which was fairly obvious; as before I made no effort to hide it. Instead of decrypting to a particular value, it verifies a message signature hash of 12345678 with various "random per-message values" or nonces.
The parameters for the algorithm were encoded in 32-bit chunks. The nice thing about DSA is that you can use huge p and y values (see Wikipedia for the terminology) without making the license key any bigger; unfortunately that doesn't buy you a lot, because the underlying group order is only q, so that's how big the search space theoretically is -- it doesn't increase security, it just makes it marginally slower to factor.
So I chose p, y, and g to be on the order of 384 bits, but q and x are only on the order of 64 bits. In fact p is just a 64-bit number shifted left 320 bits and then incremented.
The security of DSA derives from the difficulty of determining x from y = gx mod p, which is known as the discrete logarithm problem, which is harder than factoring primes.
So after you reconstruct the parameters from the hexadecimal encoding you find:
p = 12026070341127085754893097835098576041235013569186796331441953314639277634647572425804266039236571162321832835547137
g = 54659936461116297034410364232325768273521088000551606899
39983550682370032756410525809260221877924847568552733696072
y = 27434965696578515868290246727046666462183462061939529180
41150093730722092239431092724025892380242699544101134561292
You can plug these numbers into a discrete log solver and find x (it will also deduce q as the subgroup size after a few seconds). This takes about three hours on my MacBook Pro, IIRC.
Once you have x the challenge collapses into reimplementing DSA (with a small twist: s is inverted in the generator, not in the validator; I can't see any reason this would affect security and it makes the validator simpler):
let H = 12345678 (the supposed message hash) choose a nonce k compute r = (gk mod p) mod q compute k-1 (mod q) using the modular multiplicative inverse (mpz_invert with GMP) compute s = (k-1(H + x r)) mod q let w = s-1 (mod q) combine (r,w) into K = r q + w convert K into a base32-ish key stringI think this scheme is actually pretty good, as it's non-trivial to solve, but it's still crackable with the newest discrete log solver methods. It did confound some dedicated redditors for a couple days, at least, with all the details laid bare.
The obvious next step is to move on to elliptic curve cryptography, and that is the reason this post is so late. When I started writing the first hacker challenge I was completely ignorant of ECC. Immediately after writing the previous post, I bought a book on the subject, and while I understand the basics now I still don't understand it well enough to write a toy implementation suitable for a "Hacker Challenge". So I will leave that for another day, or perhaps for another person.
Source code for the DSA private key generator and license generator:
keydecode2.cpp - the challenge code from the last post (for reference)bn.h - quick and dirty bignum template
dl_genpriv.c - discrete log private/public key pair generator
dsa_genlic.c - license generator (key parameters hardcoded)