Score:6

Crypto

Must RSA exponent and modulus be odd

ubiquibacon

12/30/23, 1:24 AM

I'm working on some RSA code that uses Toms Fast Math (TFM for short), and I'm trying to understand why the functions fp_exptmod (for modular exponentiation operations) and fp_invmod (for modular inverse operations) both require an odd modulus and the former also requires an odd exponent. I've written code to allow the use of evens, but TFM is built with crypto in mind, so I'm thinking maybe allowing evens isn't necessary or even desired? Still, even though my math-fu isn't as strong as it could be, I would think limiting the choices of exponent and modulus to only half (i.e. only odds) of all natural numbers would give bad actors a head start that we don't want.

Asked more generically, in the context of generating strong RSA keys, is the use of odd exponent and modulus for modular exponentiation operations and the use of an odd modulus for modular inverse operations required? If not, is there a benefit to including evens?

1396

2 + 3

modular-arithmetic

fraxinus

12/30/23, 2:49 PM

I have an idea (borrowed from the floating-point arithmetic) - not to store the first and the last bit of the RSA key ! They are always both 1, so one can have 2050-bit RSA key stored in only 2048 bits !

Peter Cordes

1/1/24, 2:06 PM

@fraxinus: BigInt math gets done in 32 or 64-bit chunks by CPUs, so a 2050 bit key is probably(?) as slow as being another whole word bigger (2112 bits). It's possible (and I had same idea, at least for an implicit low bit), but it's a poor tradeoff of performance vs. storage for most use-cases. You might make the top and bottom bits implicit in a key size that's a multiple of 64 if you have anything you can pack into that space (like how FP formats pack in an extra exponent bit in the space left by making the top mantissa bit implicit). So you'd store a 2048-bit key in 2046 bits.

fraxinus

1/1/24, 3:56 PM

Of course, the idea is really a retrocomputing cartoon. Crypto is in fact pretty much fragile in regard to ideas like this.

Score:20

Crypto

forest

12/30/23, 1:29 AM

If the modulus is even, that means one of its factors is 2. The modulus is supposed to be the product of two large prime numbers. While it's possible to use more than two prime factors (called multi-prime RSA), that's not common, and having the number 2 as one of those factors would make little sense.

The public exponent $e$ must be coprime with $\varphi(n)$, where $n$ is the public modulus. If that's not the case, then there will be multiple possible plaintexts for a given ciphertext. And actually, the Rabin cryptosystem is basically RSA with $e = 2$, which is, of course, even, but it spits out four possible plaintexts, so regular RSA decryption doesn't work in the Rabin cryptosystem (thus it's not RSA).

While $e$ can be any value as long as $\gcd(e,\varphi(n))=1$, it's usually chosen to be 65537 or 3.

As Ilmari Karonen pointed out, $\varphi(n) = (p-1)(q-1)$ is always even for a product $n = pq$ of two odd primes. $65537 = 2^{16}+1$ is one plus a power of two (and specifically a Fermat prime), and thus has the lowest possible binary Hamming weight among odd numbers of comparable size, which makes exponentiation by squaring faster. $e=3$ is faster still, but not often used for silly reasons.

+ 1

ubiquibacon

12/31/23, 1:15 AM

Good point about `(p-1)(q-1)` being even. Upon further investigation, the TFM documentation for `fp_invmod` seems incorrect, and actually doesn't even agree with the comments in the library's code.

Score:13

Crypto

yyyyyyy

12/30/23, 1:38 AM

In the context of RSA, the modulus should be a product of two large primes, and all primes $>2$ are odd — so it's not a restriction in this situation.

The reason the implementation only works with odd moduli is that it uses Montgomery multiplication internally to speed up the exponentiation, which involves calculating the inverse of the modulus modulo a power of two. This inverse exists if and only if the modulus is odd.
_{(The special role of $2$ here arises from the fact that computers work with bits, thus computations modulo powers of two are "native" in some sense: They are typically much faster than for moduli of other forms.)}

+ 1

fgrieu

1/2/24, 5:55 AM

Addition: Montgomery multiplication requires expressing the multiplicands and modulus in some base, and computing the modular inverse of the rightmost digit of the modulus expressed in that base, modulo the base. Since in RSA, the modulus is always odd, choosing a power of two as the base makes that inverse always well-defined. Any other choice of the base would introduce a restriction on the modulus. Hence the base is a power of two in practical implementations (though it can be 10 in demos).

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Must RSA exponent and modulus be odd

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.