How to create a serial key (Registration key)
I am targeting this answer at what can realistically be achieved on a PIC microprocessor.

I would generate a random number on the PIC, the common way to do this is to use the A2D as a noise generator and repeatedly sample the LSB. Once you have this, append a check digit or two and display it to the user. The check digits will allow you (on the server that receives the text) to guard against billing the user for a miss-typed code. 

On the server, take the users code, strip the check digits, run it through a Linear Feedback Shift Register that is pre-loaded with a secret value. Charge the user, if the payment clears, text back the output code.

Your PIC chip needs to know the secret too, and repeats the calculation. You might want to try Microchips CRC Generator hardware eg. AN1148 shows how to use the hardware LSFR. Load in the secret, then clock in the random challenge. Compare this to what the user keys in - a result that matches most likely means a purchase.

I'd have a supervisor mode if this is a kiosk, rather than single device, to allow the re-loading of another secret code, or pattern of LFSR taps, secured by physical access and store this in the NVRAM. This way you can at least change the encoding over time, or in response to a break. Add NVRAM counters to compare local purchases against server approvals to monitor slippage. Watch your wear-levelling though!

This is only as 'secure' as your secret and technique staying private. It would be relatively trivial for anyone who can dump a hex image from your machine to reverse the algorithm from the assembler, although presumably anyone with physical access has simpler techniques to get the product without paying. Similarly anyone willing to guess the technique, buy a code and another for validation could guess the technique and do a brute force search for the secret. 

I don't think full public key cryptography is viable on these machines, so this is a compromise. Porting OpenSSL is going to be non trivial and use up a significant portion of your developer time and code space. If it's not a missile launch code, or you need to protect users details, or guarantee votes in an election, public key cryptography is probably more than required for your revenue protection case. Caveat emptor.