Have you considered generating license keys using public key cryptography ? This way you can embed the program settings in your key, and sign the key with a private key. The program will only have to verify the signature with a public key, so the private key will not have to be embedded in the program.

The caveat is that classic public key algorithms like RSA cannot be used because the signature sizes are too big. Elliptic curve cryptography...