You are probably mistaking encrypting for signing!
Being able to decrypt something does not imply that the encrypted data comes from a trusted source, which is what you likely want from a licensing software.
Rather, what you should do is to sign the license key, and allow the client to verify the license. This can be done using public-key cryptography. Your server would contain the private key, with the ability to sign data, and your clients would contain the public key, with the ability to verify a signature.
... it should be noted that what you are trying to do is a DRM scheme, and theses schemes are impossible to do with any reasonable guarantee of security, at least if all the "interesting" bits happening on the client.
Your program, in essence, looks like this:
You can make this more complicated and throw some obfuscation at it, but it won't change the fundamental nature of the approach. And an attacker, eager to circumvent your licensing, will find a way to execute
startTheCoolStuff() without a valid license.