Hacker News Reader

Comment by commandersaki | Hacker News Reader

Hm, never encountered the Carmichael function before, but I have had a cursory understanding of Carmichael number.

Given a standard 2048-bit RSA modulus, the totient is still ~2048 bits. I'm not sure and haven't done or seen analysis given the reduction in size (and search space) when replaced with a Carmichael function.

I know, I'll attempt to summon cperciva.

View on HN

This isn't used in practice because if you care about efficiency you're not calculating M^d mod N; instead you compute exponents mod p and mod q and use the CRT to combine (as mentioned in the author's link to "Garner's algorithm").

BTW the Carmichael function and Carmichael numbers have little in common aside from their author and the fact they concern whether x^b = 1 mod N for x relatively prime to N.

Thanks, I thought about this a bit more. Would the security argument for using the Carmichael function essentially be the same as RSA with totient function, as the adversary can always find d that satisfies either function (Carmichael or Euler totient) regardless of which function is used?

Correct. You could construct a weird scenario with a buggy side channel attack where using a different value for d would matter, but generally speaking the attacker doesn't know and doesn't care what value (out of the infinitely large number of options!) you're using.

The summoning worked!

And it's not even a full moon.

It worked 4 days ago, no less!

(I search on a ~daily basis for mentions of "cperciva", "Tarsnap", and "daemonology.net" to see where I and/or my work are mentioned.)

Annoyingly, while that d = e^-1 usually isn't used in practice (except in cases where you care about side-channel / fault resistance more than the 4x speedup), the Carmichael totient itself still is used in practice. At least if you want to conform to FIPS 186-5 / SP800-56B, which says that the private key includes d = e^-1 mod the Carmichael totient LCM(p-1,q-1), even if you're going to use the CRT. And that means you have to compute LCM(p-1,q-1), which also has side-channel considerations.

Reply on news.ycombinator.com