4 ms·
A quiet change to RSA
- commandersaki 1y agoHm, 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.
- cperciva 1y agoThis 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.
- commandersaki 1y agoThanks, 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?
- cperciva 1y agoCorrect. 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.
- chc4 1y agoThe summoning worked!
- DougMerritt 1y agoAnd it's not even a full moon.
- cperciva 1y agoIt 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.)
- less_less 1y agoAnnoyingly, 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.
- jasperry 1y agoThere are a lot of people who learn and teach the RSA algorithm superficially without a sufficient grasp of the number theory to really understand what is going on. I know because I've been one of them (on both sides). The Carmichael vs. Euler totient issue confused me for a long time. Needless to say, those people should not be implementing RSA for a system that needs actual security. I'm looking for a better way to teach "real" RSA without needing the students to be math majors or to spend a whole semester on it. Does anybody have any suggestions?
- goalieca 1y agoGiven how much more favored ECDSA and ECDH is these days, i recommend teaching elliptic curves. They're actually quite simple to understand mathematically if you want a shallow comprehension.
- supernetworks_ 1y agoThe task for teaching is much harder now as these need to be combined into hybrid PQC protocols
- Krutonium 1y agoSure, but teaching the original as a fundamental building block would still be just that.
- csmantle 1y agoThe undergrad lectures I took placed almost equal emphasis on crypto over Zp and crypto over EC. For most students without deep abstract algebra backgrounds, introduction to operations and principles are more friendly and tractable over Zp.
- burnt-resistor 1y agoAnyone with an undergraduate CS background should be able to handle Dan Boneh's course: https://www.coursera.org/learn/crypto https://www.coursera.org/learn/crypto Although there are continuums of teaching delivery from muddled to clear explanations of concepts, there are no student shortcuts to escape the irreducible mental exertion to acquire familiarity towards mastery. Uncurious people shouldn't be in the field (no pun intended).
- edm0nd 1y ago[flagged]
- jdpage 1y agoA reminder, RSA (the cryptosystem) is not a product of RSA (the security company); the cryptosystem predates the company by a decade and was also independently invented by a GCHQ researcher a few years before, but it remained classified there. The only thing they really have in common is that the founders of RSA (the company) were the public inventors of RSA (the cryptosystem). The company didn't get into bed with the NSA until the turn of the century.
- foofoo12 1y ago> The company didn't get into bed with the NSA until the turn of the century You don't know what you don't know.
- tptacek 1y agoIt's not even true that the RSA authors were the founders of the company we know as RSA. The RSA founders company was acquired by Security Dynamics in the mid-1990s, which then took over the name.
- nayuki 1y agoSpecifically, the algorithm https://en.wikipedia.org/wiki/Dual_EC_DRBG https://en.wikipedia.org/wiki/Dual_EC_DRBG .
- charcircuit 1y agoThere is no evidence that it was backdoored. You should not talk as if it was a fact, when it's pure speculation.
- edm0nd 1y agoThere is however plenty of evidence the NSA does indeed purposefully backdoor and weaken encryption. Clipper Chip, the Bullrun project, etc.
- AnotherGoodName 1y agoAnother similar one is that we don't care for strong primes anymore and even though the standards for RSA specifically require it, it's not actually helpful at all, see https://eprint.iacr.org/2001/007 https://eprint.iacr.org/2001/007 Strong primes are ones where the totient (both carmichael and euler totients) have large primes in them. This happens naturally for 2048 bit and above RSA keys in any-case, they'll statistically absolutely have primes that are larger than the bits needed to factor using elliptic curve methods (>256 bits). In general it's just not that helpful, similar to trying to require carmichael rather than Euler totient. Ok you've made the 2048 bit key 3 bits stronger, great, but let's not bother right?
- less_less 1y agoDo the standards require strong primes for RSA? I think FIPS doesn't ... it gives you that option, either for the legacy reasons or to get a proof with Pocklington's theorem that (p,q) really are prime, but just choosing a random (p,q) and running enough rounds of Miller-Rabin on them is considered acceptable IIRC.
- AnotherGoodName 1y agoYeah see https://en.wikipedia.org/wiki/Strong_prime#Factoring-based_cryptosystems https://en.wikipedia.org/wiki/Strong_prime#Factoring-based_c... There is probably a newer standard superseeding that but it is there in the ansi standards
- mmastrac 1y ago"The efficiency gained from using Carmichael’s totient is minimal. More efficiency can be gained by using Garner’s algorithm." The proof of which is left to the reader?
- username223 1y agostares at the board for ten minutes disappears into the back room for fifteen minutes "Yes, it's trivial."
- jongjong 1y agoThe notation used in Euler’s totient function reminds me why I chose to study software engineering instead of maths. The same notation can be used to mean 3 different things. Illogical. It baffles me why mathematicians made the language of maths, which is supposed to be the language of logic, so ambiguous. So sloppy to reuse the mod symbol to mean different things and sloppily using an equal sign instead of congruence symbol. I will henceforth refer to software development as 'software engineering' to convey its equivalence, or perhaps superioriority over other 'engineering' disciplines which are based on ambiguous mathematical language, as opposed to rigorous, machine-verifiable, unambiguous languages.
- piskov 1y agoI expected to see CIA somewhere in the article :-)