Join Log in
Score:6
PixelPower avatar Crypto

Difficulty of computing RSA keypair with given bits preset

us flag
PixelPower

Given a 2048-bit RSA public key physically burned into hardware, is it feasible to find a keypair where the public key could be "overlaid"? To detail, each bit in the hardware key is write-once; zeroes can be set to ones, but the write is permanent. The existing RSA public key is 2048-bit and its corresponding private key is unknown; my hunch is that this would take around 21024 guesses since on average about half of the bits would be 1 in the existing key. A brief review of the literature resulted in no obvious way to compute the Carmichael λ(n) where n is of the form 2n-1 (as in, set all bits to 1).

152
1 + 1
rsa
A. Hersean avatar
cr flag
A. Hersean
In general, write-once hardware also ensure that zeros cannot be overwritten.
0
Reply
Score:7
poncho avatar Crypto
my flag
poncho

Given a 2048-bit RSA public key physically burned into hardware, is it feasible to find a keypair where the public key could be "overlaid"?

The immediately obvious approach to attack this would be to search for a 2048 bit prime that overlays the modulus; by replacing the value with a prime, finding the private exponent is easy.

And, in that range, roughly 1 in 700 odd numbers is prime; given that there are far more than 700 ways to set some 0 bits to 1 within your modulus, that implies that there is such a prime (and it wouldn't be that hard to find - an expected 700 primality checks before you find one).

Now, such an updated modulus wouldn't be secure (I assume the attacker doesn't care about that), and it wouldn't work if the other side attempted to check on the primality of the modulus (I have yet to see an RSA implementation that bothered checking a public key for primality), however it would appear to be a workabout approach.

0 + 2
PixelPower avatar
us flag
PixelPower
You're correct; security is irrelevant here. I need this to bypass bootloader verification and I'm quite confident no checks are done on the key (merely read from e-fuses). Thank you!
0
Reply
poncho avatar
my flag
poncho
@PixelPower: I just did a quick check; $2^{2048}-1-2^{692}, 2^{2048}-1-2^{1106}, 2^{2048}-1-2^{1454}$ all appear to be prime - if one of those three bits are clear in your RSA key, you're golden...
1
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.