10-08-2012, 02:17 PM
Complexity and Cryptography
Complexity_and_Cryptography_An_Introduction_-_JOHN.pdf (Size: 3.27 MB / Downloads: 28)
Basics of cryptography
The Oxford English Dictionary gives the following definition of cryptography.
‘A secret manner of writing, either by arbitrary characters, by using letters
or characters in other than their ordinary sense, or by other methods intelligible
only to those possessing the key; also anything written in this way. Generally,
the art of writing or solving ciphers.’
Cryptography is an ancient art, and until relatively recently the above definition
would have been quite adequate. However, in the last thirty years it has
expanded to encompass much more than secret messages or ciphers.
For example cryptographic protocols for securely proving your identity online
(perhaps to your bank’s website) or signing binding digital contracts are
now at least as important as ciphers.
As the scope of cryptography has broadened in recent years attempts have
been made to lay more rigorous mathematical foundations for the subject. While
cryptography has historically been seen as an art rather than a science this has
always really depended on which side of the ‘cryptographic fence’ you belong.
We distinguish between cryptographers, whose job it is to design cryptographic
systems, and cryptanalysts, whose job it is to try to break them. Cryptanalysts
have been using mathematics to break ciphers for more than a thousand years.
Indeed Mary Queen of Scots fell victim to a mathematical cryptanalyst using
statistical frequency analysis in 1586!
The development of computers from Babbage’s early designs for his
‘Difference Engines’ toTuring’s involvement in breaking the Enigma code owes
much to cryptanalysts desire to automate their mathematically based methods
for breaking ciphers. This continues with the National Security Agency (NSA)
being one of the largest single users of computing power in the world.
One could argue that cryptographers have been less scientific when designing
cryptosystems. They have often relied on intuition to guide their choice
of cipher. A common mistake that is repeated throughout the history of
Basics of cryptography
cryptography is that a ‘complicated’ cryptosystem must be secure. As we will
see those cryptosystems which are currently believed to be most secure are
really quite simple to describe.
The massive increase in the public use of cryptography, driven partly by
the advent of the Internet, has led to a large amount of work attempting to put
cryptography on a firm scientific footing. In many ways this has been extremely
successful: for example it is now possible to agree (up to a point) on what it
means to say that a cryptographic protocol is secure. However, we must caution
against complacency: the inability to prove that certain computational problems
are indeed ‘difficult’ means that almost every aspect of modern cryptography
relies on extremely plausible, but nevertheless unproven, security assumptions.
In this respect modern cryptography shares some unfortunate similarities with
the cryptography of earlier times!
Cryptographic models
When discussing cryptographic protocols we necessarily consider abstract, idealised
situations which hopefully capture the essential characteristics of the realworld
situations we are attempting to model. In order to describe the various
scenarios arising in modern cryptography it is useful to introduce a collection
of now infamous characters with specific roles.
The players
Alice and Bob are the principal characters. Usually Alice wants to send a secret
message to Bob. Bob may also want her to digitally sign the message so that
she cannot deny sending it at a later date and he can be sure that the message
is authentic. Generally Alice and Bob are the good guys, but even this cannot
always be taken for granted. Sometimes they do not simply send messages. For
example they might try to toss a coin down the telephone line!
Eve is the arch-villain of the piece, a passive eavesdropper who can listen in to
all communications between Alice and Bob. She will happily read any message
that is not securely encrypted. Although she is unable to modify messages in
transit she may be able to convince Alice and Bob to exchange messages of her
own choosing.
Fred is a forger who will attempt to forge Alice’s signature on messages to
Bob.
Modern cryptography
Modern cryptography starts from a rather different position. It is founded on
complexity theory: that is the theory of how easy or difficult problems are to
solve computationally.
Modern cryptographic security can informally be summarised by the following
statement.
It should not matter whether a cryptogram reveals information about the
message. What matters is whether this information can be efficiently
extracted by an adversary.
Obviously this point of view would be futile if we were faced with an adversary
with unbounded computational resources. So we make the following assumption.