[Cryptography] Lower bound for the size of an RSA key's private exponent

Bertrand Mollinier Toublet crypto-metzdowd at bmt-online.org
Sun Feb 19 19:46:52 EST 2017


All,

On a recent project, I found myself having to serialize the private exponent of an RSA key by myself (as opposed to it being an opaque value inside, say, a standard PKCS container). 

As I was toying with it, I came to the (new for me!) understanding that the relationship between the size of that private exponent and that of the key was more tenuous than I had anticipated.

So, looking into it, it is pretty clear that the exponent is going to be no larger than the Carmichael totient of the modulus (being that it satisfies a relationship modulo that totient). It can also be as small as (roughly, worst case) that same totient value over the public exponent, which is by convention the 17 bit value 65537. 

So, I guess my question becomes: what are the upper and lower bounds of the Carmichael totient value of a modulus of size n bits? Upper value is slightly smaller than the modulus, but potentially still n bits. Lower bound, though, I'm not sure. 

Thoughts?
-- 
Bertrand Mollinier Toublet


More information about the cryptography mailing list