I was stuck on this crackme for some time, not able to recognise or figure out the math. A clue came from fuss on IRC who revealed that it was digital signature algorithm :) The serials consist of three parts: a message, and the two components of the signature, using the public key parameters stored in the crackme. I can imagine such a scheme being used in a real protection: the message could encode enabled/disabled features or a license expiration time, and the signature (only producible by the company having the private key) prevents forgeries.
DSA is interesting in its similarity to the El-Gamal scheme present in the last TMG crackme. In El-Gamal, there was only one prime, and the random K you chose had to be ensured relatively prime to P-1. DSA is more complicated. The public parameters consist of two primes, one which divides the totient of the other, and the K can be chosen freely within the number line of the smaller prime. Bruce Schneier's "Applied Cryptography" has an interesting discussion of the similarities between signature schemes based on the discrete logarithm problem at chapter 20.4 where he unifies them with generalized equations and attempts to count all possible variations.
thanks !
ReplyDelete