[Cryptography] Zoom publishes draft cryptographic design for end-to-end encryption

[Weger, B.M.M. de]

> On Mon, 8 Jun 2020, Ralf Senderek wrote:

(...)

> > If I'm not mistaken then phi(n) = (p-1)*(q-1) is of roughly the same
> size
> > as n.
> > And if e*d = 1 mod phi(n) , then you *might* find a small d if e is
> large.
> > You may as well find a large d if e is large, but any small one that
> fits
> > the bill will decrypt your ossifrage.

(...)

Bart Preneel is right, but there's more to say. First this:

If p and q are of equal size (which they usually are) then phi(n) and n
are not just *roughly* the same size; actually the first half (minus 1) 
of their bits are exactly equal. If n has 2048 bits and p, q have both 
1024 bits, then the difference of n and phi(n) is n - phi(n) = p + q - 1 
which has only 1025 bits. 

And now the more important point:

Say that you first generate random e with your preferred size (small, 
large, whatever), and then compute d to fit e d = 1 (mod phi(n)). Then 
the probability distribution that d will follow is almost uniform over 
the range it will live in (which will be between phi(n)/e and phi(n)).
This is not something that I can prove mathematically, but you can do 
experiments and see it happening before your eyes.

As a consequence, the probability that d will be almost as large as
phi(n) is overwhelmingly large, whether or not e is small or large.
Roughly only 1 in a million d's will be 20 bits shorter than phi(n),
and only 1 in a million*million d's will be 40 bits shorter than phi(n).

Though I can't say it is untrue that "you *might* find a small d if e is
large", (they do exist!) it is extremely improbable. If you start doing experiments for a given n with an awful lot of random e's until you've 
found a small d (say of half the length of n, to stay well above the 
bounds Bart mentioned), and at the same time I start the Number Field 
Sieve to factor the same n, in the end (well after the sun has burnt 
down) we will find that I win.

Of course, if you want to force small d, you can do so, but then you have
to reverse the process: start choosing a small d and then compute e.
The same reasoning as above shows that with overwhelming probability now
e will be of full size.

Finally, it's even possible, and actually not that hard, to come up with
n, e, d such that both e, d are of approximately half the size of n
(or, a bit more general, e d is of approximately the size of n).
But then you have to even further reverse the process: first choose
e, d and then see if you can find primes p and q that fit your wishes. 
With a not too bad probability this works. Totally useless, but funny.

Grtz,
Benne de Weger