Public Key Cryptography

[Ian Brown]

George Foot wrote:
> In the following discussion the emphasis 
> is on operating difficulties and operating hazards which need more 
> attention than they are receiving at the present time.

You're absolutely right that operating difficulties are a big problem, but
I think your strong conclusion relies on some weak propositions.

Markus makes an important point: systems that use one public key to encrypt
all traffic to an individual are rather badly designed. Ideally,
interactive protocols (like Diffie-Hellman) should be used that use new
keys for each session. In any case, key pairs used for encryption should be
as short-lived as possible. Keys used for *authentication* will be longer
lived (and are what will be used in public-key infrastructures) but your
paper talks about encryption, not signing.

The compromise of private long-lived keys does lead to all sorts of
problems: hopefully smartcard-type systems where the private key is
supposed never to leave the card will become far more widespread (modulo
the problems with current "tamper resistant" chips that Cambridge and
others have identified.)

> A major weakness inherent in a Public Key Cryptosystem is the 
> difficulty of withdrawing a Public Key which is no longer valid 
> -- this difficulty needs emphasis because it could bring Public 
> Keys methods into disrespect.  The problem is simple to explain 
> but an effective solution does not exist and possibly is 
> impossible to find.

Well, try reading the SPKI documents. They get rid of the idea of
certificate revocation lists and instead concentrate on positive
re-authorisation. They compare this to original credit card systems, where
Visa published a list of stolen cards weekly that would be rejected, to
current systems where on-line positive authorisation of cards is used.

> However attempts to break RSA are 
> intensive and success with longer Key lengths is reported frequently.

Paul Leyland has answered this question here rather well before. 1024-bit
or higher RSA keys are absolutely *infeasible* to break with current
techniques, regardless of the computational power you throw at them. It
would need new mathematical techniques that performed hugely better than
those we have today; in which case, 2048, 4096 or however long keys would
likely be vulnerable also.

> PGP is one of the hybrid systems which employs RSA for Key creation 
> and Key exchange and then reverts to a more traditional single Key 
> cryptosystem for message transmission because less computatonal 
> capacity is required and quicker speeds can be achieved.  Examples 
> of these  secondary cryptosystems are IDEA, DES, CAST and Blowfish.
> Security in these circumstances is limited to the security provided 
> by the single key cryptosystem of which experience is limited and it 
> may be an illusion that security is equivalent to the much better 
> known and respected RSA system itself.

DES is rather better analysed than RSA, and is the default symmetric
algorithm (in its TripleDES incarnation) for the OpenPGP standard. IDEA has
also been much-analysed since its use in PGP 2.x.

> Another inherent drawback of Public Key Cryptosystems is that 
> the Public Key and the Modulus are published

In RSA, the exponent and modulus *are* the public key.

> and therefore can be 
> subjected to continuous cryptoanalysis without any limit of time 
> -- thereby greatly increasing the chance that the system will be 
> broken.

This is a fundamental part of designing a public-key cryptosystem -- those
that have survived any length of time limit this chance to an incredibly,
incredibly small size.

> In fact the published accounts of breaking Public Keys 
> are rated for efficiency by the time necessary to break a Key 
> of a specified length.

As are attempts to break symmetric keys.

> Much weight has been given to the possibility of confirming the 
> origin of an electronic transmission if double encryption

While RSA encrypts with a private key to sign data, other cryptosystems
can't be said to do this -- DSA, just for one, which doesn't *have* an
encryption function by design. This is a common misuse of terminology.

Ian.