Previously, I described a proposed system that will both sign and encrypt code updates using an RSA private key. The goal is to derive the corresponding public key even though it is kept securely within the device.
If you delve into the details of RSA, the public key is the exponent and modulus pair (e, n) and private key is (d, n). The modulus is shared between the two keys and e is almost always 3, 17, or 65537. So in the vendor’s system, only d and n are actually secrets. If we could figure out d, we’ve broken RSA, so that’s likely a dead-end. But if we figure out e and n, we can decrypt the updates.
Let’s see how to efficiently figure out n using guesses of e and a pair of encrypted updates. The signature verification process, RSA-Verify, can be represented by the standard equation shown below in various forms.
The first step is the standard RSA-Pub-Op and the result is m, the padded hash of the message. The remaining steps in RSA-Verify (i.e., validating the signature) are not relevant to this attack. In the second equation, m is refactored to the left side. Finally, 0 mod n is described in an alternate form as k * n. The particular k value is the number of times the odometer has wrapped during exponentiation. It’s not important to us, just the modulus n.
Now, assume we’ve seen two updates and their signatures, sig1 and sig2. We can convert them to the above form by raising each signature to a guess for e and subtracting the associated message m. Note that m is still encrypted and we don’t know its contents.
This gives us two values with n as the common factor. The GCD algorithm gives us the common factors of two values very quickly. The reason there is no “=” sign above is that we actually get n times some small prime factors, not just n. Those can easily be removed by trial division by primes up to 1000 since the real factors of n (p and q) are at least 100-digit numbers. Once we have n, we can take each encrypted message and decrypt it with me mod n as usual, giving us the plaintext code updates.
I implemented this attack in python for small values of e. Try it out and let me know what you think.
Doing this attack with e = 65537 is difficult due to the fact that it would have to work with values millions of bits long. However, it is feasible and was implemented by Jaffe and Kocher in 1997 using an interesting FFT-multiply method. Perhaps they will publish it at some point. Thanks go to them for explaining this attack to me a few years ago.
Finally, I’d like to reiterate what I’ve said before. Public key cryptosystems and RSA in particular are extremely fragile. Do not use them differently than they were designed. Better yet, seek expert review or design assistance when working with any design involving crypto.
rdist 
“e is almost always 3, 17, or 65537” -> based on who’s experience?
there is not need to use this value u can use other values also.
“only d and n are actually secrets” -> there is not need for N to be secret at all its a public value as long as it big enough there isn’t a single problem.
Re: values of e — doesn’t matter for the attack if someone tried to choose a “secret” e that wasn’t one of those 3 values. It only expands the search time by 2^17 at most, even if you had to search every single reasonable value of e. And those 3 values are the highest by far in use in both software and hardware.
I agree there is no need for n to be secret. In fact, you’re missing the whole point of these articles — when using n with signatures, it NEVER CAN be kept secret, even if you wanted to. Perhaps you missed the previous article where the vendor was expecting to keep n secret and use (e, n) for encryption as well as signature verification. Here’s the link again:
https://rdist.root.org/2007/05/01/rsa-public-keys-are-not-private/
> It only expands the search time by 2^17
No, if you are going to try and keep the “public” exponent a secret, you make it the same sort of size as the private exponent and modulus, 2^1024 or larger.
This is unreasonable for normal usage, since it just makes verification pointlessly slow. And if you have to keep both halves secret at both ends of communication, why not just use a symmetric key? (In the example given, because they were trying to reuse an existing key intended only for signature, which is why it almost certainly does have a small public exponent.)
Alan, thanks for the comment. You are right in the general case, but I am discussing a specific case where that does not apply. If the system designer chose e randomly, then it would indeed be safe from brute-force guessing. But as you point out, such a system would be quite slow for both encryption and decryption, and a symmetric key would have been more appropriate.
The system I am describing chose e to be fast for signature verification (i.e., much smaller than d). (I think you get this, based on your last sentence.)This was because RSA was originally only used for signatures. Then the engineers later tried to add encryption by keeping (e, n) secret. In any case where e is not chosen randomly but is much smaller than d, it is subject to brute-force guessing and thus you can calculate n. The engineers’ mistake was in thinking that n can be kept secret in this case.
The first article in this series explained this in more detail.