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

[Bertrand Mollinier Toublet]

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

> On Feb 27, 2017, at 5:52 PM, Jon Callas <jon at callas.org> wrote:
> 
> It's 3.
> 
> Here's my Gordian Knot construction:
> 
> Create an RSA key with a public exponent of 3. Make sure it's actually secure. Swap the public and private keys, publishing the formerly private key as the public key and keeping the formerly public key as the private one. 
> 
> The private exponent is now 3.
> 
> 
> 
> On Feb 20, 2017, at 9:46 AM, Ron Garret <ron at flownet.com> wrote:
> 
> See:
> 
> https://en.wikipedia.org/wiki/Carmichael_function
> 
> The section on “lower bounds” is towards the bottom.

Jon and Ron,

thank you for keeping this thread going. You are both literally addressing my question, and yet not quite addressing it: yes, there is a computable lower bound for the Carmichael function for arbitrary values. But when creating an RSA key, the modulus value is not arbitrary. Rather, it is the product of two large primes.

So the question really is not “What is the lower bound of the Carmichael function over all integers?", but “What is the lower bound for the Carmichael function over the values represented on exactly n bits (the modulus size) *and* that are the product of two large primes?".


Similarly, yes, you could contrive that you’d use the private exponent as the public value and vice-versa. By doing so, however, you’d ruin the security properties of RSA, a use case I am not interested in. Rather, the question is “For a non-compromised key generator, attempting its damn best to produce an RSA key of size n, what is the lower bound on the Carmichael totient of the produced modulus?"



I guess this veers into quality of implementation territory a little, too. Are p and q actually primes? Or are they statistically likely to be prime, depending on the algorithm used to generate them. Are certain relationships between p and q enforced. Wikipedia (https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Key_generation) mentions that “p and q […] should be similar in magnitude but 'differ in length by a few digits’”, citing the 1978 RSA whitepaper. This is rather vague. I can conceive than from an implementation to the other, different decisions as to what “a few digits” constitute will be made, and that might in turn impact the answer to my question.



With these constraints in mind (but violating the p and q length relationship constraint), I can contrive an example where the totient length is half that of the modulus (explicitly: by imposing p == q). I know this is not a realistic case, and I want to imagine that the actual answer is much larger than half the size of the modulus.


I can spend a few hundred/thousand dollars worth of EC2 time and generate a couple million RSA keys with my implementation of choice and get an experimental reading of some value. But before I do so, I was wondering if there exists theoretical research on the topic that can provide the start of an answer to the question.


For what it’s worth, I’ve spent a weekend’s worth of my home server’s CPU time, and generated about 60,000 2048-bit keypairs. I found that the private exponent size varied from 2033 bits to 2048 bits. About 1/3rd of the generated private exponents had a length of exactly 2048 bits. Another 1/3rd had a length of exactly 2047 bits. The rest of the lengths seemed, on this small data set, to exhibit a geometric progression, halving at every step as the bit length went down.


So, back to the theoretical question: any takers? Any hints? Any known research on the topic that I was unable to uncover myself?
-— 
Bertrand