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

[Ron Garret]

On Feb 19, 2017, at 4:46 PM, Bertrand Mollinier Toublet <crypto-metzdowd at bmt-online.org> wrote:

> 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. 

See:

https://en.wikipedia.org/wiki/Carmichael_function

The section on “lower bounds” is towards the bottom.

rg