D. J. Bernstein
Fall 2006 course at the Fields Institute
I'm writing a book called ``High-speed cryptography.''
I'm also teaching a
block course on the topic
at the Fields Institute in Toronto in Fall 2006.
Why is high-speed cryptography important?
Anyone with access to the Internet
can intercept mail messages and web pages and other packets of data
to see what they say.
He can also send fake messages that look like real messages.
Cryptography protects messages sent through the Internet.
Cryptography scrambles and unscrambles packets
to protect against forgery and against espionage.
An attacker who forges a message won't be able to scramble it in the right way,
so when we unscramble it we'll see that it's a forgery
and that we should throw it away.
An attacker who intercepts a scrambled credit-card number
won't be able to figure out the original number.
High-speed cryptography is important for busy network servers.
here's a quote from Cricket Liu,
author of several books on the Internet's Domain Name System:
``Verifying signed resource records
[i.e., performing cryptographic operations]
is computationally intensive
[i.e., is painfully slow].
This has slowed deployment of DNS security.''
As a practical matter, DNS security still doesn't exist;
attackers can seize control over incoming mail
and outgoing web pages by forging DNS records.
The users need faster software to scramble DNS records.
What does this book cover?
The book focuses on the four fundamental tasks in cryptography:
For each task,
the book explains a state-of-the-art function solving the task,
explains what is known and what is believed about the security of the function,
explains state-of-the-art methods to compute the function
on several common computer architectures,
and surveys the alternative functions discussed in the literature.
- using a long shared secret to protect a long series of private messages;
- expanding a short shared secret into a long shared secret;
- sharing a secret through a public conversation; and
- using a sender secret, with no shared secrets,
to protect a long series of public messages.
The book takes the attitude of the practical cryptographer.
Security is essential,
so unnecessarily risky cryptographic functions are rejected.
Speed is often essential,
so unnecessarily slow cryptographic functions are rejected.
There are many books surveying a broad spectrum of
potential cryptographic solutions to the fundamental cryptographic problems;
this book highlights the best solutions available,
minimizing risk while maximizing speed.
What do readers need to know before reading this book?
Readers are expected to have some experience with algorithm analysis
(figuring out why a computer hasn't finished a computation yet)
and algorithm improvement
(making the computer finish the computation more quickly).
A typical reader will have studied some chapters
of a textbook by Cormen, Leiserson, Rivest, and Stein;
will have heard that heapsort
``takes time n log n times, um, some constant'';
and will have seen many algorithm improvements
incorrectly described as ``optimizations.''
The most obvious difference in flavor between this book
and a typical algorithms book
is that this book pays attention to constants.
this book explains how a state-of-the-art function
takes half a millisecond on my laptop
to compute a high-security shared secret from a public conversation.
Ignoring constant factors would remove all content from this statement.
Of course, these constants depend on the choice of computer.
Sometimes one computer
takes 10 clock cycles for an operation
while another computer takes just 1 clock cycle;
this affects the time for any algorithm built on top of that operation.
Readers might have seen some computer-dependent algorithm analysis
and algorithm improvement in books on
architecture, assembly language, ``optimizing'' compilers, supercomputing, etc.
None of those topics are prerequisites;
this book includes a detailed introduction to the speed of real computers.
Many higher-level speedups are also constant-factor speedups.
In fact, most of the speedups in the algorithms literature
are constant-factor speedups.
However, readers are not presumed to have any previous experience
handling constant factors in algorithm analysis.
The other obvious difference in flavor
between this book and typical books
is the choice of functions being computed.
A typical book spends time on sorting,
for example, and on various graph operations such as shortest paths.
This book instead focuses on a few critical cryptographic operations.
Those operations rely on some mathematics
that readers might have seen
in other books on algebra, number theory, or cryptography.
None of those are prerequisites;
this book includes an introduction to the relevant mathematics.
In more detail, what does the book cover?
From a cryptographer's perspective,
here are the main topics of the book
(linked here to more than 200 pages already available in the form of papers):
- Using a long shared secret to protect a long series of private messages:
specifically univariate polynomial-evaluation MACs,
combined with additive stream encryption.
More broadly, includes a
structural framework for MAC constructions
and a complete
- Expanding a short shared secret into a long shared secret:
parallelized stream generation,
specifically block hashing by constant-time operations,
with additional material on Bolero20.
Includes extensive discussion of
multiple-target brute-force attacks,
cache-timing attacks on AES,
and what went wrong with MD5 and SHA-1.
- Sharing a secret through a public conversation:
the Diffie-Hellman system,
specifically elliptic-curve Diffie-Hellman,
Includes extensive discussion of
Pippenger's exponentiation algorithm,
Montgomery's exponentiation algorithms,
- Using a sender secret, with no shared secrets,
to protect a long series of public messages:
specifically RSA-Rabin-Williams public-key signatures,
the latest signature-compression and key-compression techniques,
against generic attacks,
and discussion of
the difficulty of integer factorization.
At a lower level,
the book contains extensive coverage
of computer architecture and microarchitecture,
new programming tools aimed at high-speed computations,
and many specific speedups,
with special attention paid to floating-point arithmetic.
This material is of interest outside cryptography
in applications ranging from video games to weather simulation.
Are any similar books already available?
I like Practical Cryptography, by Ferguson and Schneier.
This book does a great job of
explaining how to select low-risk cryptographic functions.
But it doesn't pay much attention to speed;
it doesn't explain
how careful design and implementation of cryptographic functions
can improve performance by a factor of ten or more.