Month: April 2026

Crafting unusable public-keys [part II]

Games with prime factors

A different avenue opens up if we focus on a different aspect of RSA keys: the relationship between the public and private exponents:

e × d = 1 mod ɸ(N)

That is e and d are multiplicative inverses modulo ɸ. Since e is usually fixed by convention to a small prime, one can ask: does such an inverse always exist?

Surprisingly the answer is no. Multiplicative inverse exists if and only if e is relatively prime to ɸ. We can estimate how often that condition fails. Recalling that ɸ is a large number, and e is prime, there is only one way they could fail to be “relatively prime: e divides ɸ. Since ɸ = (p – 1)(q – 1) that would also imply e divides at least one (possibly both) of the factors.

When p and q are generated independently as random primes, p-1 and q-1 are also effectively random. We can approximate the probability of the product being divisible by e as 1/e + 1/e = 2/e. (Ignoring the highly improbable case where it divides both of them) For e = 65537, this is less than one in thirty thousand— unlikely to be encountered unless one is generating a lot of RSA keys.

Now what happens if we deliberately choose one of the primes to trigger this condition? In that case e is no longer invertible modulo ɸ and there is no “private key” in the traditional sense. This is a necessary but not sufficient condition to render the key unusable.

Root cause

To see why traditional “private key” does not completely neutralize a public key, let’s review the mechanics of RSA encryption.

The ciphertext C is obtained from the source plaintext P as:

C = Pe mod N

So encryption involves raising the ciphertext to the e-th power modulo N. Inverting the relationship we can say the plaintext is the e-th root of ciphertext modulo N. This is the important observation: decryption involves computing e-th roots.

In the case of signatures, a signature S is related to the original message M as:

M = Se mod N

Note the similar relationship: obtaining the signature S involves taking an e-th root.

In “standard” RSA, computing e-th roots is straightforward: we raise the input to the d-th power, where d is the private exponent. For efficiency reason, this is actually done as two separate calculations: first computing the root modulo p and later modulo q, then combining the results.

This gets more complicated in our version where no such d exists, because one or both of the primes were deliberately chosen such that e divides p-1.

Here we need to distinguish between two issues:

  1. Lack of unique roots. When e divides p-1, the structure of the group changes. It is no longer the case that every element has a unique e-th root. In fact most elements do not have e-th roots. Some minority— exactly fraction 1/e in fact— have an abundance of them, exactly e for each such element.
  2. Computing those roots when they exist is no longer a straightforward process of raising the input to some suitable exponent.

If a root does not exist, that message can not be signed or that ciphertext can not be decrypted (This latter case is less likely to be encountered in practice; no such ciphertext would be generated by a valid encryption process.) That is a mathematical constraint, not a computational limitation. No future quantum-computer or theoretical Zeno machine changes that.

On the other hands, the existence of multiple roots messes with the semantics of RSA. For example ciphertexts become ambiguous. They can decrypt into different plaintexts, each of the a valid root. The recipient can not determine which one the sender had in mind. Interestingly signatures are impacted in the a different way. There will be multiple valid signature corresponding to a given message. This is no different intrinsically probabilistic signatures such as ECDSA. An adversary would be considered to have defeated the system if they can find any one of those roots to forge a signature.

That becomes a computational problem for which well-known algorithms exist. For example Tonelli-Shanks algorithm computes square roots in a prime modulus. That corresponds to the special case e=2. Since p is prime, 2 will always divide p-1 so there can not be a “private exponent” to calculate roots in the general case. Adleman-Manders-Miller algorithm generalizes that to work for any e.

Deliberately mangled RSA keys

Revisiting the problem that started this blog post, suppose we generate a deliberately malformed platform key (PK) as described in the previous section. Can users be confident that it can not be used to updated the KEK? Recall that UEFI specification requires KEK updates to be signed by the KEK, so this comes down to asking what it would take to create a valid signature using the mangled key.

Let’s posit that the “attacker” already knows the factorization of the modulus. This is a realistic assumption since the OEM generating the modulus is part of the threat model.

Recall that even with knowledge of the modulus, there are two obstacles to signing:

  1. Finding a “signable” message. Not every message can be signed because some elements have no e-th roots. However attackers are usually not limited to targeting a single message. Often they can generate variations of a message that have cosmetic differences but carry the same semantics. In the case of UEFI variable updates, an attacker can generate different KEKs in the hopes that one of them results in a signable message. In other cases the hashing scheme is probabilistic, as with PSS so it is sufficient to keep the same message and vary some random padding to generate variants. This problem lends itself to brute-force after trying roughly e steps. Each step consists of generating a candidate message, hashing it and checking the order of the resulting group element. Desired roots exist if and only if the element order is divisible by e.
  2. Computing any e-th root once a suitable message is located. Time complexity of the AMM algorithm is linear in e and polynomial in bits of the prime.

The bad news is with the default RSA public exponent of e=65537, neither of these is prohibitive. Knowledge of the prime factors allows computing roots the hard way with AMM and forging signatures. The good news is we can extend the construction to greatly increase the difficulty along two dimensions.

First, we can use large public-exponents. For example if e is selected to be 128-bits, both of the above computational problems become intractable. While it is straightforward to scale up difficulty this way, it runs into a compatibility problem: not all software implementations can handle large public exponents. (For example the Windows cryptography stack used to assume public exponents fit into 32 bits.) Some systems even mandate e=65537.

Adding primes

A different approach involves increasing the number of primes. The above example implicitly assumed the RSA modulus follows the usual rules: product of exactly two distinct primes and only p has the special structure with respect to p. Suppose q is also selected to have the property q ≡ 1 mod e.

This creates a new problem for the attacker on step #1. Recall that for a group element to have e-th roots, such roots must exist modulo p and modulo q individually Since messages are mapped to group elements by a hash function, the probability of that condition being met for each prime individually is still 1/e. But the probability that it holds for both prime at the same time is 1/e². Compared to the original design, that ratcheted up the difficulty by another factor of e.

Interestingly the difficulty level of the second step does not change. AMM still takes the same effort for each prime. It has to be done twice, once for each prime factor but that is merely doubling the effort— not a material increase in cryptographic terms. The real step-up in difficulty comes from finding a signable hash with e-th roots. With two primes and e=65537, that will now require over four billion attempts on average.

No need to stop with two primes. RSA works the same way over multiple primes. This is even defined in the standard under the heading multi-prime RSA. Meanwhile recipients can not detect how many primes went into a modulus short of successfully factoring it. It follows that our 2048-bit key can be generated as a product of three or more primes. Suppose we use eight primes of roughly 256-bits, all deliberately chosen to make e-th roots rare. Now the odds of a random group element modulo N having e-th roots goes down to 1 in 2¹²⁸. Looked another way, it would require 2¹²⁸ attempts on average to locate a valid message with a hash that can be signed.

If one is willing to use large public exponents and forego any pretense of being a valid RSA key, there is another approach in the opposite direction: use a single prime number as the RSA modulus. Unlike previous examples that look like a real RSA modulus to anyone else who can not factor the product, this case is easily detectable by running a primality test. It would also be completely insecure under ordinary circumstances; the private exponent can be computed trivially from the public exponent. But the choice of public exponent here ensure no such value exists and forging a signature is equivalent to extracting e-th roots which is intractable for large e. Surprisingly this would still maintain compatibility with existing software attempting to check for valid signatures: no major implementation checks if a peer’s alleged “public key” was generated properly as a composite number. Meanwhile the formulas for signature verification operate the same way even in a prime group. It is not possible to forge a valid signature without solving the difficult root-extraction challenge modulo that prime.

Burden of proof

The last piece of the puzzle is proving that a given RSA key was generated according to the scheme described. Since the public exponent is typically determined by convention, this comes down to demonstrating the special structure of the modulus.

The exact difficulty of the proof depends on the approach taken. Single prime is the easy case, because no proof is required. Anyone can verify that the modulus N is a prime and observe its relationship to the public exponent.

For composite modulus, the standard approach involves zero-knowledge proofs. There is work going back to Bellare and Yung [CRYPTO 1992] for proving properties about a given RSA key in zero-knowledge, specifically that it defines a valid permutation. In our case, that is false by construction: public-exponents are chosen to guarantee it is not a permutation and that many elements map to the same image under the public-key operation. More recent work such as Goldberg et. al. [2019] extends that result to construct non-interactive proofs that a given N is the product of two prime powers or that it is square-free (eg no prime factor is repeated.) Since these protocols only involve the modulus and not the public exponent, they can serve as building blocks. But there is still a missing piece around proving that for every prime p that divides the modulus, we have p = 1 mod e for the public exponent e.

For the case when the modulus consists of many small primes, there is a more direct approach around revealing the factorization. Recall that the heuristic argument for difficulty above is based on an attacker already knowing the factorization. When there are many small prime factors (to keep the public exponent at 65537 for compatibility) those factors may well be within reach of ECM anyway. Even the threat model implies the security of the scheme can not rest on difficulty of factorization, because one of the “adversaries” to defend against is the person who generated modulus and has full knowledge of the factors.

CP

Brass plate engraved with 'Master Made in USA Milwaukee, WI. No. 5'

Crafting unusable public-keys [part I]

A motivating example

In modern applications it is very common for access rights to be expressed in terms of control over a cryptographic key. All blockchains operate on this model: control of funds comes down to control over a private key, usually ECDSA. Someone who can create valid digital signature using that key is assumed to be owner of those assets.

There are unusual edge-cases when a system requires such a key to be defined as part of its configuration and yet it is important to prove to third-parties that one does not have control over that key. One example is creating firmware images for secure boot. The UEFI secure boot specification defines a number of keys such as platform key (PK) and key-exchange-key (KEK) that need to be set before a system can transition into secure boot mode. Interestingly PK and KEK are not used directly validate what operating systems are allowed to boot: that is controlled by a different EFI variable, labeled database or “db” for short, which contains a list of keys or hashes. The trust chain looks like this:

PK → KEK → DB

Changes to the DB must be signed by one of the KEK entries, and changes to the KEK in turn must be signed by the PK.

Now suppose a privacy-conscious PC manufacturer wants to ship an image with DB configured in a specific way. For example, include the Microsoft third-party signing key in DB to permit Ubuntu, Debian and other operating systems with a signed shim to be installed. At the same time, this manufacturer wants to prove they do not control PK or KEK. (Since either PK and KEK allow modifying the DB, it would amount to a manufacturer backdoor into every unit shipped.) This requires creating PK and KEK entries of a particular type:

  • They must look like valid keys as far as the EFI specification is concerned; otherwise the firmware could reject them, error out or ignore secure boot configuration.
  • OEM must be able to convince customers that they do not control the corresponding private key. More specifically that they can not create signed updates to alter the KEK using PK, or alter the DB using KEK. (As we will see, “not controlling the private key” is not entirely equivalent to this formulation.)

Threat model

Proving that one knows the private key corresponding to a given public key is easy: do something that requires knowledge of the private half and which can be verified with the public key, such as digitally signing a message or decrypting a random ciphertext. Proving the negative— that one does not know it— is more tricky. Intuitively, public and private-key halves of the key are generated together, typically with the public key derived from the private key. Naively that would imply for a given public key, somebody somewhere must have known the private key.

To be clear, we want to rule out some evasions that fail to fully address the trust problem:

  • Claiming that one deleted the private-half after key generation and only retained the public piece. While such “pinky-promise” approaches may be valuable for compliance purposes and appeasing auditors, a mathematical guarantee is much preferable.
  • Claiming someone else unaffiliated generated the key. For example one could pick the public-key from Google’s TLS certificate, asserting he/she does not have the corresponding private key. While that would be a plausible statement— unless the speaker is affiliated with Google— it does not side-step the trust assumption: someone still has the private key and retains a backdoor into any system where that public key is installed. It merely deflects the problem to another trusted third-party (Google) along with a dubious theory about that entity being more competent or trustworthy at key management.
  • Claiming ownership of the key is distributed among a group of trusted third-parties where some minimum quorum must collude for any successful use. Again this does not lift the assumption of good faith, only diffuses it from a single trusted third-party to a coalition of thereof. This rules out approaches such as distributed/join key generation.

The ideal solution is one where one can offer a public key and demonstrate that no person or group ever had access to the private key.

Easy case: ECDSA

If one is willing to depart from standard key generation procedures, it is not too difficult to achieve that goal for some public-key cryptosystems. For example in the case of ECDSA, we have:

  • The private key is a plain integer (called “scalar” in EC terminology) between 1 and the order of the elliptic curve
  • The public key is a point on the curve

For a properly generated key, these two have a relationship: the public key is equal to the product of the secret scalar with a fixed point on the curve, called the “generator” because every point on the curve can be reached by taking successive multiples of that point. It follows that traditional key generation works by:

  1. Randomly selecting a private scalar from the appropriate range
  2. Multiplying that with the generation point to get the public point

What if we invert this sequence? Choose a curve point in a semi-deterministic way (more on this below) without knowing the scalar. The logical next step would be working backwards towards the private key, by calculating the scalar which would yield that point when multiplied by the generator. This is an instance of the “discrete logarithm” problem, akin to an analog of division over finite groups. But that runs up against a practical yet insurmountable problem: solving discrete logs over the type of large curves used in cryptography is computationally out of reach of present systems. In fact the security of every public-key system depends on such an assumption: deriving the private-key from the public-key must be “infeasible” in the sense that requires an amount of computation far beyond what is possible given present day understanding of the mathematics and state-of-the-art technology.1

So if we can prove that the public-key was selected according to a verifiable procedure, it provides high confidence that the corresponding private key is not known to anyone. There are several ways to do this in a nothing-up-my-sleeve manner starting with an English language statement or the digits of pi as the seed.

  • Use a cryptographic hash function such SHA256 to map the seed into a curve point. There are some nuances here. Curve points are ordered pairs <x, y> in a particular range satisfying the curve equation. While the hash output can be used to select x, there is no guarantee that a corresponding y exists. There may be no such point on the curve with that x-coordinate, or there will be exactly two requiring a choice between them. As such combining the hash operation with an incrementing counter may be necessary until a valid point is found.
  • Alternatively use a dedicated hash-to-curve scheme. These are designed to map inputs exactly into curve points of unknown discrete logarithms, without the awkward trial-and-error approach of using a plain hash.

It is important that the choice of seed be free of arbitrary decisions as much as possible. For example a seed containing a very specific sequence of digits with no explanation is bound to raise suspicion. Perhaps the prover “cooked” the seed: they tried trillions of variations on those digits until hitting on a curve point where the discrete logarithm problem was easier to solve by sheer chance. (To be clear: there are presently no such known shortcuts or concept of “weak keys” on ECDSA where one out of a trillion public keys is much easier to break.) By comparison the starting digits of pi are effectively a fact about the universe that no prover can influence.

Difficult case: RSA

Returning to the motivating example for this blog post, it turns out that most UEFI implementations do not handle ECDSA keys very well. RSA being the least common denominator for a portable solution, we run into a problem: RSA is not easily amenable to the previous approach of deterministically selecting a public-key without worrying about the private half. In effect there is shared structure linking the halves:

  • Private key is (N, d) where N is the modulus, a product of two large primes
  • Public key is (N, e) with N same as before and e the inverse of d modulo ɸ(N) the order of the multiplicative group.

In practice key generation proceeds as:

  1. Find two primes p and q of appropriate size to generate the modulus N = p × q
  2. Public exponent e is often fixed by standards or convention, for example 1 + 216 is a popular choice.
  3. Private exponent d is then calculated from e, using the known factorization of N.

If one generates N according to this sequence, then at some point that person knew the individual factors p and q, and could have used that knowledge to calculate the corresponding private exponent d. Meanwhile generating N naively in a deterministic way by hashing an agreed upon seed does quite provide the same security guarantee.

Recall that the security of RSA rests on the difficulty of factoring the modulus. Proper RSA moduli are generated as a product of two roughly equal size primes, and have exactly those two factors. By comparison, a random number of the same size is extremely unlikely to have such a clean structure. Suppose we were were to pick a random 2048-bit number and declare it to be an RSA modulus. What are the odds that number can be completely factored? Emphasis on complete factorization because deriving the private exponent from the public one requires full factorization of the group.

Factoring in the factors

If we interpret “random” in a strict sense, we can say that half the time, that number will be divisible 2. About a third of the time, it will be divisible by 3. More generally for a given “small” prime w, the number will be divisible by that prime 1/w of the time. Whether or not factoring such a composite is feasible depends on, well, many “factors”— specifically the size of the second largest factor.

There is mixed news here. Good news in that statistically speaking large numbers are also likely to have larger factors. More precisely, there is a measure called “smoothness:” a number is called B-smooth if all of its prime factors are less than B. For any given B, the probability of a randomly selected number being B-smooth rapidly declines with the size of that number. So it is astronomically improbable that our random 2048-bit number factors cleanly into a bunch of 32-bit integers, requiring no fancy factorization algorithm beyond trying the first few billion primes.

But there are specialized factoring algorithms for chipping away at small factors, specifically the Elliptic Curve Method or ECM which can reliably get at factors in the ~200 bit range. So the relevant question becomes:

“Given a random N bitnumber, what is the probability that its second-large factor is W bits or less?”

for various choices of N and W. It turns out this probability is not at all negligible for reasonable choices. For example if we use the common 2048 bit RSA key size and 200 bits as the threshold for ECM factoring, Claude Opus 4.6 estimates 1 in 5 chances of complete factorization. Even with key-sizes cranked up to 4096 bits, there is still non-negligible probability over 1%. Those are not at comforting odds for a cryptographic application.

There is another practical problem with this approach even if one is willing to roll the dice on probabilities: it is unclear how one could convince everyone else that the chosen modulus can not be factored easily. At best one can say “we ran ECM for X hours and it failed to find any factors.” That is a not a very reassuring statement. It offers little confidence that the next person trying a little harder with more computing resources could not successfully discover one more factor.

[continued in part II]

CP

  1. Granted both of those can advance. While the mathematics behind discrete logarithm problem have been studied for a long time with only incremental progress in attacks, it is entirely possible that the second dimension— computing technology— will experience a drastic leap with the introduction of quantum computers. ↩︎