Since you asked in general "Are there any other obvious flaws/issues I'm missing", I would recommend that you would take a critical look at the whole update process flow. I would not consider the quality of the PRNG at your server as an obvious weak point, as long as it is reasonably strong, since on servers you have quite a bit of choice of reasonably good routines to generate a fair PRN (note that it is quite acceptable to generate a pair of good PGP keys on a regular server or client machines).
Critical review of the update process as a whole should consider the following, by no means an exhaustive, list:
- A server that is opened to the public internet usually exhibits a fairly wide attack surface - OS, apps, services, open ports etc.
If I were an attacker, I would first try to penetrate your server, and use your private key in there to send malicious update commands out.
- You need to secure the environment of your embedded processor. I assume that you discount the possibility of direct physical acess to the embedded system (otherwise all security bets are off), but you do need to think about other issues like flooding the device's comm channel with badely signed messages generated by an attacker, thus causing DOS on your embedded system. You may possibly mitigate this with a watchdog timer that will kill the update loop after a set time.
- I concur with maeher - questioning the need to generate a key pair for each device. This will be a nighmare of a management vis a vis the chance of private key compromise: How would you remotely identify the client in order to know which private key to use for the signature going to that particular client? would you send a bunch of records for each client to test them all in order to find the one recognized sig in them? would you first send a client ID in the clear and respond with the appropriate signed message? I would also, as maeher proposed, recommend one key pair with all clients will have the same public key.
If you are really concerned about someone stealing your private keys, you may want to consider having all the keys expired after each update and regenerating a new pair for the next update cycle (the new pair will be signed by the old one before expiring). This is not as strong as a unique pair for each client, but certainly more manageable.
When you consider the above, it does make a difference if your embedded app is just an industrial controller, or a system whose failure due to a rogue update will cause a regional catastrophe.