Various features pertain to embedded key generation and provisioning systems, such as systems installed within smartphones for generating public-key/private-key pairs for use in encryption/decryption and digital signature generation. In some examples, an embedded system is provided that generates two public-key/private-key pairs—one for encryption/decryption and the other for signing/verification—where the two public-key/private-key pairs share a common modulus but are otherwise distinct or uncorrelated. This allows the two key pairs to be generated more efficiently than if two entirely separate key pairs were generated and yet, at least in the context of embedded systems, satisfactory integrity and confidentiality is achieved. Techniques for decrypting and signing messages using common modulus keys are described for use by an embedded component of a mobile device, along with techniques for encrypting and verifying messages for use by a remote system such as a key provisioning server of a partner software vendor.