 <p>So apparently, you can't just take any temporary key and sign the APPX with it. In particular the certificate subject lines must match(the "publisher name"). I do not know of a better way of determining what the subject line much actually be so bare with me. First, try to use signtool and sign the APPX file with any temporary key. Now go to Event Viewer. Then to Applications and Services and then Microsoft and then Windows and then AppxPackaging and finally Microsoft-Windows-AppxPackages/Operational. There should be an error event that just happened from that build. Check it. It should say something like</p> <pre><code>Error 0x800700B: The app manifest publisher name (CN=random-hex-number) must match the subject name of the signing certificate (CN=MyWrongName) </code></pre> <p>So, now make sure to hang on to that random-hex-number. That needs to be the subject line of the certificate and is the cause of the error. To generate a working certificate:</p> <pre><code>makecert.exe mycert.cer -r -n "CN=random-hex-number" -$ individual -sv private.pkv -pe -cy end pvk2pfx -pvk private.pkv -spc mycert.cer -pfx mytemporarykey.pfx </code></pre> <p>Now finally, you should have a temporary key that will work with signtool!</p> <p>Hopefully this answers serves other people well. </p>