Large Primes

[Owen Lewis]

> -----Original Message-----
> From: ukcrypto-admin@chiark.greenend.org.uk
> [mailto:ukcrypto-admin@chiark.greenend.org.uk]On Behalf Of Paul Leyland
> Sent: 16 August 2002 09:36
> To: ukcrypto@chiark.greenend.org.uk
> Subject: RE: Large Primes
>
>
>
> > From: Owen Lewis [mailto:oml@sysrx.uk.com]
> > Many thanks for the trouble taken, Paul. Every stone provides some
> > foundation for others to build on or to use as a fulcrum.
>
> Or to pick up and throw at someone, which is what the principle use of
> the AKS algorithm seems to be at the moment.  The amount of ill-informed
> blether about the demise of public key cryptography is truly amazing.

:-)

In response to another thoughtful but private mail in this thread a while
back I set my stall as follows and it seems timely to set it out now in this
forum.

Owen

=====================

My view can be summed up as follows. Short of quantum computing, there is
every reason to think that increases in the practical length of RSA keys
will stay well ahead of attempts to resolve them using the known algorithms
and computer technology.

Therefore - and leaving quantum computing to one side - if the balance of
advantage is ever to be reversed (or it should come to be known that such a
reverse was achieved X years ago by some secret group) then it is to
advances in mathematics that all should turn.

One might say with certainty that today there is no public knowledge of a
mathematical means to reduce the time required to resolve large RSA keys.
However, it would be rash to assert as certain what one cannot know, such as
what is not in the public domain or what someone may achieve at some future
time. Most advances in knowledge are not arrived at ab initio. Rather each
advance stands on stones that others erected in times before. My original
post was not to suggest that PK cryptosystems are about to crumble into dust
but to express interest in learning more about some current work with large
primes.

However, and since this is a quiet patch, may I air a concern I have in
regard to the design of PK cryptosystems such as PGP. It is that their
design is arrogant in its certitude of security. Let me explain.

These systems execute the bulk encryption of data using a symmetric cipher
(IDEA etc). For this purpose, a session key is generated when the program is
run by the originator and a copy of this key is passed to the recipient (so
the data can be deciphered) as a part of the data transferred. RSA's part is
to encipher only the session key so it is secure during transmission and
storage alongside the symmetrically enciphered bulk data.

Therefore, the content of transmissions so protected offers two different
and equally attractive foci for cryptanalysis. Recover the RSA private key
and, hence, obtain the session key or attack the bulk ciphertext directly to
recover the session keys.

It should be axiomatic that no one may know with certainty that any cipher
cannot be successfully attacked. Groups who are successful may severely
restrict the dissemination of such information. Conversely, it is certain
that history is littered with the corpses of ciphers that were once believed
to be secure. But this observation applies to any and all ciphers (pace OTP)
so why do I pick on PK cryptosystems?

As such systems are presently arranged, at best they offer their users no
more than the protection of a single cipher, the invulnerability of which
cannot be certain. Moreover, they offer two different ciphers as targets
with a failure of either, taken alone, being sufficient to destroy the
system's security. If, for the sake of simple argument, we say that the
probability (P) of a successful attack on either type of cipher is about the
same then, by arranging the work of the two ciphers in the current fashion,
the engineer increases the probability of a successful attack to P/2 where P
is less than unity.

Granted that if P is very small the significance of the increase in
probability from P to P/2 may not be critical, nevertheless it is
unnecessary and it should be poor security engineering to countenance it.
Moreover, it is arrogant since the size of P cannot ever be determined with
certainty. At any point, it is even impossible to show that P does not equal
1 i.e. there is certainty that a method of breaking one of the ciphers is
already known to some secret group.

Arguably, for each cipher, there is some value of P that is representative
of the risk to be borne by trusting it. To double that risk does seem
unnecessary. Some other cryptosystems may reduce substantially the value of
P, whatever that may be and, it seems to me, that should be the proper aim
for any cryptosystem designer.

Owen