User:Vuara/Cyclopedia Cryptologia

From Wikibooks, open books for an open world
Jump to: navigation, search

http://www.disappearing-inc.com/

Cyclopedia Cryptologia

Welcome to Cyclopedia Cryptologia. This is an online encyclopedia of cryptographic protocols. There will be coverage of a few related topics such as encryption/decryption algorithms and a few historical references, but for the most part, the intent here is to be a reference on cryptographic protocols. Although my intent is to be as exhaustive as possible, the literature is increasingly broad and deep; the coverage I give it here will probably never be truly exhaustive.

+++

Foreword

This work is a cyclopedia, or a collection of articles relating to a particular field. In this case, the field is cryptographic protocols and protocol design.

There are many thousands of papers in the field that have been published in recent years. Each of these has been developed by a single author or small group of authors, and generally each has evolved its own terminology and notation. They are published at academic conferences held at various intervals and by various organizations, or as thesis papers by various graduate students or academic researchers from different universities.

A lot of the mental effort of reading these papers is devoted to learning the different notations and terminology preferred by each different team of writers, and a lot of the information is hard to collect and publish directly because of the diversity of the sources and of course the conflicts of copyright. The publication formats themselves range from plain text, to TeX, to HTML, to PostScript, to mere ink on paper.

The purpose of a cyclopedia such as this is to collect as much of this information as possible together, with a unified notation, in a single electronic format, and under a single copyright. Of course, I will try to concentrate on that which is most useful, since there will necessarily be omissions.

For now this cyclopedia is a work in progress. At some point in the future, when I am reasonably satisfied with it, I will probably publish it as a printed book. Regardless, the HTML version of it will remain available on the web, and work on it will most likely continue.

My purpose in writing such a work is simply this: I want people to have in their hands the means of protecting themselves from eavesdroppers, blackmailers, extortionists, embezzlers, thieves, and worse. Now that information is mainly digital and electronic, the only meaningful protection from such entities is a working knowledge of cryptographic protocols.

+++

Introduction

Cyclopedia Cryptologia is a work in progress. There are a lot of articles that need to be written, and I've written only some of them. Twice a week or so, I sit down, review the last ten "404 not found" errors the site has generated, and pick one of them to write an article about, so that that particular URL will quit generating 404 errors. So far, the articles aren't very broadly researched -- They are mainly placeholders to be replaced by later versions as I bring the whole up to professional standards.

Protocols are the heart and soul of applied cryptography. Protocols are the methods by which cryptography is used to get things done.

For many centuries, cryptography was mainly involved only in the very simplest protocol -- sending secret messages. But the fact of the matter is, cryptography is also useful for many other types of transactions. Cryptography is a general tool for the management of information. There are a lot of things that can be done with cryptography, and this site is about how to do them.

While encryption and decryption algorithms provide some of the materials of which useful structures are made, the materials have to be organized in a useful way to make useful structures. And that is what protocol designers do. We're going to cover a few encryption/decryption algorithms, but this cyclopedia is about protocols. Everyone can figure out how to make a mud hut; similarly, everyone can find the "secret message" protocol -- it's the simplest protocol in the universe. But just as a good building architect/engineer can develop a workable plan for a cathedral, a good protocol architect/engineer can develop incredibly useful complex cryptographic protocols, with surprising and subtle properties.

+++

Notation and Terminology If someone has to spend a full second thinking about what notation means, then the author has clearly made a mistake. With that simple but exacting criterion in mind, here is the complete vocabulary of mathematical primitives that this work will use.


() Parentheses denote a subexpression. Calculations inside a subexpression are to be done before the calculations outside of it. For example (2 * 3) + 5 = 11 but 2 * (3 + 5) = 16 Parentheses also enclose the arguments of a function. A, AB, A1 etc. Identifiers starting with a capital letter and including only capital letters or numbers represent strings or numbers. In this work, we do not differentiate between strings and numbers. Alice, Bob, etc. Capitalized identifiers represent actors in various protocols. Traditionally, these are alphabetic and alternate in gender, starting with Alice and Bob. Also, certain roles are traditionally associated with certain names: Trent is the trusted authority, Eve is the eavesdropper, Mallory is the active attacker, etc. These "special" names are outside and additional to the alphabetic run of names representing ordinary participants.

  • , /, +, -, %,

asterisk, slash, the plus sign, the minus sign, and the percent sign are infix operators for multiplication, division, addition, subtraction, and the modulo operator, respectively. The minus sign may also be used as a unary prefix operator for negation (subtraction from zero). , Comma is used as an infix operator for concatenation. &, |, !, << >> The Ampersand, vertical bar, exclamation point, double left-angle, and double right-angle are the infix operators for binary and, binary or, binary inversion, leftward shift, and rightward shift. trunc(), frac(), time(), pubkey(), hash(), etc. identifiers in lower case, followed by parentheses, are functions. Functions are always followed by an open-paren, their arguments if any, and a close paren. For now some of these just have to stand, but when I'm pulling together all the loose ends before publication I'll try to provide definitions for them all.

+++

Acknowledgements First of all, I need to give thanks to the many people who've contributed knowledge which I present here.

Probably first among these is Bruce Schneier of Counterpane Security Systems, who wrote a book called Applied Cryptography, which serves as a one-volume introduction to the field. But there is a sharp limit to what can really be covered in one volume, and Mr. Schneier recognized this. In order that the inevitable shortcomings of a single volume would not hinder his readers from future research, his book has an extensive bibliography. He also maintains at his website an extensive bibliography of cryptographic papers available online, which has been a great help. I cannot state often enough how great a service to a researcher a good bibliography is, particularly in a field like Cryptography. Cryptography, until the last few decades, has not been much studied in the private sector, and publications about it have tended to be rare and secret. Since the revolution in studying cryptography that started to happen in the 1970's, where it's been coming out into the open and mathematicians have been getting to sink their teeth into it and shake, there's been a fever of scholarly articles, published in small journals and circulated to a few thousand people. These articles have covered huge amounts of ground, come out with truly breathtaking insights and mathematical techniques. But these articles were mostly unknown and inaccessible to the public -- until Schneier enumerated them in his bibliography. Since Schneier's book came out, it's been ten times easier to do research in the field of cryptography than it was before. Schneier has continued to contribute to the field with his company, Counterpane Systems, and with his email newsletter, the Crypto-gram.

The second name I want to mention here is David Kahn, for his earlier work, The Code Breakers. This book purports to be a history of cryptography and cryptology throughout history, and in fact about half of it is devoted to that purpose. But the other half is mainly a history of cryptography and cryptology in the second world war. Prior to its publication in 1967, there had been nothing but a vast deep silence concerning cryptography, disturbed by the natterings of sunday-paper puzzle ciphers and occasional scandals of traitors divulging secrets and being quickly discredited and hushed up.

Kahn had a daunting task before him in researching and reporting the cryptographic history of the world, and he did an admirable job. And like Schneier did after him, he compensated for his book being just one book by including a fantastically complete bibliography, to drag all the obscure sources that people would otherwise never have heard of out into the light. It is not too much to say that Kahn's book, by bringing knowledge of ciphers to a broader audience, may be one of the primary forces (the other being the seminal paper new directions in cryptography by Diffie and Hellman in 1976) which set off the astounding revolution in the study of cryptography that Schneier had before him when he started to write his book.

The third major source of information I want to mention is not so well known as the other two: It is a book titled Advances in Cryptology 1981-1997, edited by Kevin McCurley and Claus Dieter Zeigler. The book is primarily an index to every paper published at these two conferences for 16 years, and is accompanied by a CD-ROM containing PDF copies of all the publications. While the publications of these conferences have been necessarily made in small runs and are therefore expensive and rare, this electronic document collecting sixteen highly eventful years of these publications has been a font of knowledge unsurpassed by any other single resource I have available to me and has saved me much effort in tracking down copies of publications long out of print and gathering dust in someone's attic. It turns the bibliography question on its head, taking the large data storage capacity available in an electronic format and simply putting all the papers there for perusal. And of course each paper has its own bibliography, so taken as a whole the bibliography given in this work eclipses either of the two above.

Fourth, there is a team of three authors: Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone. These gentlemen are responsible for a book called the Handbook of Applied Cryptography. This is a book strictly about the mathematics and implementation of cryptography - while there is an entire chapter on the oft-overlooked problem of key management and other trust issues, it does not concern itself much with protocols and history. It is strictly a book about engineering, implementation and analysis, and for that purpose, it excels.

I want to make a special thanks to Ronald Rivest, both for having a lot of truly neat ideas, and for taking the time and energy to make his publications available on the World Wide Web. People like Rivest realize that the march of progress is not just about ideas. It's also about access to ideas, and the general public benefits from ideas as well as the few peers in the field that receive the specialized publications in which these papers come out. So, to Rivest and other researchers like him, who take care to make their ideas available to more than just the specialists in their own disciplines, I'd like to extend a sincere and heartfelt thanks.