[HN Gopher] A quiet change to RSA
___________________________________________________________________
A quiet change to RSA
Author : ibobev
Score : 82 points
Date : 2025-10-06 19:07 UTC (5 days ago)
(HTM) web link (www.johndcook.com)
(TXT) w3m dump (www.johndcook.com)
| commandersaki wrote:
| 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.
| cperciva wrote:
| 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.
| commandersaki wrote:
| 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?
| cperciva wrote:
| 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.
| chc4 wrote:
| The summoning worked!
| less_less wrote:
| 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.
| jasperry wrote:
| There 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 wrote:
| Given 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_ wrote:
| The task for teaching is much harder now as these need to be
| combined into hybrid PQC protocols
| Krutonium wrote:
| Sure, but teaching the original as a fundamental building
| block would still be just that.
| burnt-resistor wrote:
| Anyone with an undergraduate CS background should be able to
| handle Dan Boneh's course:
|
| 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).
| AnotherGoodName wrote:
| I wrote an article trying to give a simple overview for
| teaching. https://rubberduckmaths.com/eulers_theorem
|
| I also added plenty of inline python code blocks students can
| change and run on the fly.
|
| The reason i wrote this is the hand waving around group theory
| i saw in other explanations. Namely you shouldn't just say x^y
| always = x mod m for certain values of y (eg. x^13=x mod 35,
| even for factors of 35). You should give a detailed, intuitive
| understanding of why this occurs.
| jcalvinowens wrote:
| I use this as a teaching aid:
| https://github.com/jcalvinowens/toy-rsa
|
| It's an ugly naive implementation, but it's much simpler and
| more accessible than any real one I've ever seen, and depends
| on nothing but libc.
| f_devd wrote:
| Depending on what you're trying to teach, I would think
| something like these would be nicer to read (but with minimal
| dependencies): https://github.com/jackkolb/TinyRSA or
| https://github.com/i404788/tiny-rsa
| almostgotcaught wrote:
| > 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.
|
| RSA is math so it seems like you're trying to shove a square
| peg into a round hole here.
| LelouBil wrote:
| Yeah, learning maths for 1-2 months and then applying it to
| RSA in python at the very end was how I learned it and I
| think it was a great way. Even though it was a CS diploma we
| learned it with the maths teacher and spent the right amount
| of time on it.
| LelouBil wrote:
| During my 2-year CS degree (in France ) we learned the whole
| modular algebra with groups, and stuff (don't know the
| terminology in English sorry) and finally, we learned about RSA
| using all of this stuff and it really was a wow moment for the
| whole class!
|
| I don't know how it's taught elsewhere but I feel like I both
| have "a sufficient grasp of the number theory to really
| understand what is going on" but also I "should not be
| implementing RSA for a system that needs actual security" !
| im3w1l wrote:
| > 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?
|
| Start and end with a reminder to use padding.
|
| Actually if you want to make it not-so-mathy, talking about
| about how to be compatible with other programs could be nice.
| How do you import/export public key in pem or der? How do you
| (de)serialize ciphertext?
| AnotherGoodName wrote:
| Another 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
|
| 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 wrote:
| Do 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.
| mmastrac wrote:
| "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?
___________________________________________________________________
(page generated 2025-10-11 23:00 UTC)