Return to Answer

The method of using (part of) the private key is actually already used by EdDSA for example to deterministically generate a secret nonce, whose disclosure would allow for private key material recovery.

The method of using (part of) the private key is actually already used by EdDSA for example to deterministically generate a secret nonce, whose disclosure would allow for private key material recovery.

Now, if you have another way to the blind, which also blinds the exponent, it might work, but amongst those, the ones I'm aware of are blindings using the Euler's theorem, doing the same as the previous one, but taking also a random $s$ value and doing: $(rc)^{d+s\cdot \phi(n)} \bmod n$ instead and multiplying the result by $r^{-1}$, but notice again that if both $r$ and $s$ can be fixed for a given message $m$, then an attack could recover $d+s\cdot \phi(n)$, which would allow him to decrypt anything as well, since $a^{s\cdot \phi(n)}= (a^s)^{\phi(n)}\equiv 1 \bmod n$, by Euler's theorem... So in the end, you really want to have a different blind for each computation.

Now, if you have another way to blind, which also blinds the exponent, it might work, but amongst those, the ones I'm aware of are blindings using the Euler's theorem, doing the same as the previous one, but taking also a random $s$ value and doing: $(rc)^{d+s\cdot \phi(n)} \bmod n$ instead and multiplying the result by $r^{-1}$, but notice again that if both $r$ and $s$ can be fixed for a given message $m$, then an attack could recover $d+s\cdot \phi(n)$, which would allow him to decrypt anything as well, since $a^{s\cdot \phi(n)}= (a^s)^{\phi(n)}\equiv 1 \bmod n$, by Euler's theorem... So in the end, you really want to have a different blind for each computation.

• The rsa_private operation is the operation requiring knowledge of the secret RSA key. This operation is required by one of the following process:

Now, you're asking about how you could be generating your randomness without entropy, and you mentioned a PRNG, the key and $m^d$, so I'll assume you only need randomness for RSA decryption, and to blind it.

Remark that it is not the same kind of properties that one would expected from a PRNG used in a masking scheme and a PRNG used for keys generation. When you are masking something, the PRNG mainly requires uniform distribution, and other such good statistical properties. But it does not necessarily requires to be a cryptographically secure PRNG. This is due to the fact that all generated values are supposed to be a secret, so you mostly require a good initial entropy source... Which could contradict your current requirements.

And as I tried to explain, the private key can be consider as a good entropy source, but this is only a one-time entropy source, so if you simply seeds your PRNG using the private key, and there is a way to reset the device so that it would get seeded again with that same private key, then there would be a way to get every new RSA operations to be conducted using the same random values, which actually means that you could not rely on your random values as being nonces, and the same mask would always get generated after $x$ calls to the just seeded PRNG...

Now, it all depends on how you actually do the blinding, if you perform simple blinding by tacking a random $r$ value, computing $r^e\bmod n$ and then decrypting the message $m^e=c$ by doing $(r^ec)^d \bmod n$ and multiplying your result by $r^{-1} \bmod n$, then you really want to take a different $r$ for each computation, even of the same message, since otherwise you would leak the secret value $d$, since the attacks target recovery of the exponent used.

Now, if you have another way to blind, which also blinds the exponent, it might work, but amongst those, the ones I'm aware of are blindings using the Euler's theorem, doing the same as the previous one, but taking also a random $s$ value and doing: $(rc)^{d+s\cdot \phi(n)} \bmod n$ instead and multiplying the result by $r^{-1}$, but notice again that if both $r$ and $s$ can be fixed for a given message $m$, then an attack could recover $d+s\cdot \phi(n)$, which would allow him to decrypt anything as well, since $a^{s\cdot \phi(n)}= (a^s)^{\phi(n)}\equiv 1 \bmod n$, by Euler's theorem... So in the end, you really want to have a different blind for each computation.

Finally let me add a word regarding side-channels such as SPA and DPA: if you are using a vulnerable exponentiation algorithm (e.g. plain square and multiply, see maybe this paper for more info), SPA cannot be prevented using just masking, it depends more on your exponentiation algorithm. Timing attacks and DPA are both working if the attacker is able to gather enough traces which are correlated, so they should be defeated by using masking, as long as you avoid fixed masks.

• The rsa_private operation is the operation requiring knowledge of the secret RSA key. This operation is required by one of the following processes:

Now, you're asking about how you could be generating your randomness without entropy, and you mentioned a PRNG, the key, and $m^d$, so I'll assume you only need randomness for RSA decryption, and to blind it.

Remark that it is not the same kind of properties that one would expect from a PRNG used in a masking scheme and a PRNG used for keys generation. When you are masking something, the PRNG mainly requires uniform distribution and other such good statistical properties. But it does not necessarily require to be a cryptographically secure PRNG. This is due to the fact that all generated values are supposed to be a secret, so you mostly require a good initial entropy source... Which could contradict your current requirements.

And as I tried to explain, the private key can be considered as a good entropy source, but this is only a one-time entropy source, so if you simply seed your PRNG using the private key, and there is a way to reset the device so that it would get seeded again with that same private key, then there would be a way to get every new RSA operations to be conducted using the same random values, which actually means that you could not rely on your random values as being nonces, and the same mask would always get generated after $x$ calls to the just seeded PRNG...

Now, it all depends on how you actually do the blinding, if you perform simple blinding by tacking a random $r$ value, computing $r^e\bmod n$ and then decrypting the message $m^e=c$ by doing $(r^ec)^d \bmod n$ and multiplying your result by $r^{-1} \bmod n$, then you really want to take a different $r$ for each computation, even of the same message, since otherwise, you would leak the secret value $d$, since the attacks target recovery of the exponent used.

Now, if you have another way to the blind, which also blinds the exponent, it might work, but amongst those, the ones I'm aware of are blindings using the Euler's theorem, doing the same as the previous one, but taking also a random $s$ value and doing: $(rc)^{d+s\cdot \phi(n)} \bmod n$ instead and multiplying the result by $r^{-1}$, but notice again that if both $r$ and $s$ can be fixed for a given message $m$, then an attack could recover $d+s\cdot \phi(n)$, which would allow him to decrypt anything as well, since $a^{s\cdot \phi(n)}= (a^s)^{\phi(n)}\equiv 1 \bmod n$, by Euler's theorem... So in the end, you really want to have a different blind for each computation.

Finally, let me add a word regarding side-channels such as SPA and DPA: if you are using a vulnerable exponentiation algorithm (e.g. plain square and multiply, see maybe this paper for more info), SPA cannot be prevented using just masking, it depends more on your exponentiation algorithm. Timing attacks and DPA are both working if the attacker is able to gather enough traces which are correlated, so they should be defeated by using masking, as long as you avoid fixed masks.