You would have registered your product at Microsoft and your new product key would come from ... Microsoft.

It's up to you to call them.

It is that simple.
Bob