应用数学 (Cryptology 密码学)

~HeBe~_@

应用数学


        应用数学是应用目的明确的数学理论和方法的总称，研究如何应用数学知识到其它范畴（尤其是科学）的数学分枝，可以说是纯数学的相反。包括微分方程、向量分析、矩阵、傅里叶变换、复变分析、数值方法、概率论、数理统计、运筹学、控制理论、组合数学、信息论等许多数学分支，也包括从各种应用领域中提出的数学问题的研究。计算数学有时也可视为应用数学的一部分。
图论应用在网络分析，数论应用在密码学，博弈论、概率论、统计学应用在经济学，都可见数学在不同范畴的应用。



数学与应用数学专业      
                                        　　
业务培养目标：　　

　　业务培养目标：本专业培养掌握数学科学的基本理论与基本方法，具备运用数学知识、使用计算机解决实际问题的能力，受到科学研究的初步训练，能在科技、教育和经济部门从事研究、教学工作或在生产经营及管理部门从事实际应用、开发研究和管理工作的高级专门人才。
　　业务培养要求：本专业学生主要学习数学和应用数学的基础理论、基本方法，受到数学模型、计算机和数学软件方面的基本训练，具有较好的科学素养，初步具备科学研究、教学、解决实际问题及开发软件等方面的基本能力。?
　　毕业生应获得以下几方面的知识和能力：?
　　1.具有扎实的数学基础，受到比较严格的科学思维训练，初步掌握数学科学的思想方法；?
　　2.具有应用数学知识去解决实际问题，特别是建立数学模型的初步能力，了解某一应用领域的基本知识；?
　　3.能熟练使用计算机(包括常用语言、工具及一些数学软件)，具有编写简单应用程序的能力；?
　　4.了解国家科学技术等有关政策和法规；?
　　5.了解数学科学的某些新发展和应用前景；?
　　6.有较强的语言表达能力，掌握资料查询、文献检索及运用现代信息技术获取相关信息的基本方法，具有一定的科学研究和教学能力。?


现在市场需要这些应用数学者的需求越来越高了，因为随着科技的发展及需求。

[ 本帖最后由 ~HeBe~_@ 于 19-1-2008 12:35 AM 编辑 ]

~HeBe~_@

Applied mathematics is a branch of mathematics that concerns itself with the mathematical techniques typically used in the application of mathematical knowledge to other domains.

Applied Mathematics

       Divisions of applied mathematics. There is no consensus of what the various branches of applied mathematics are. Such categorizations are made difficult by the way mathematics and science change over time, and also by the way universities organize departments, courses, and degrees.

       Historically,applied mathematics consisted principally of applied analysis, most notably differential equations, approximation theory (broadly construed, to include representations, asymptotic methods, variational methods, and numerical analysis), and applied probability. These areas of mathematics were intimately tied to the development of Newtonian Physics,and in fact the distinction between mathematicians and physicists was not sharply drawn before the mid-19th century. This history left a legacy as well; until the early 20th century subjectssuch as classical mechanics were often taught in applied mathematics departments at American universities rather than in physics departments, and fluid mechanics may still be taught in applied mathematics departments.

       Today, the term applied mathematics is used in a broader sense. It includes the classical areas above, as well asother areas that have become increasingly important in applications.Even fields such as number theory that are part of pure mathematics are now important in applications (such as cryptology), though they are not generally considered to be part of the field of applied mathematics perse. Sometimes the term applicable mathematics is used to distinguish between the traditional field of applied mathematics and the many more areas of mathematics that are applicable to real-world problems.

       Mathematicians distinguish between applied mathematics, which is concerned with mathematical methods, and applications of mathematics within science and engineering. A biologist using a population model and applying known mathematics would not be doing applied mathematics, but rather using it. However, non mathematicians do not usually draw thisdistinction.

       The success of modern numerical mathematical methods and software has led to the emergence of computational mathematics,computational science, and computational engineering, which use high performance computing for the simulation of phenomena and solution of problems in the sciences and engineering. These are often considered interdisciplinary programs.

       Some mathematicians think that statistics is a part of applied mathematics. Others think it is a separate discipline. Statisticians in general regard their field as separate from mathematics, and the American Statistical Association has issued a statement to that effect. Mathematical statistics provides the theorems and proofs that justify statistical procedures and it is based on probability theory, which is in turn based on measure theory.

       The line betweenapplied mathematics and specific areas of application is often blurred.Many universities teach mathematical and statistical courses outside of the respective departments, in departments and areas including business and economics, engineering, physics, psychology, biology, computer science, and mathematical physics.Sometimes this is due to these areas having their own specialized mathematical dialects. Often this is theresult of efforts of those departments to gain more student credit hours and the funds that go with them.

       Usefulnessof applied mathematics. Historically, mathematics was most important int he natural sciences and engineering. However, in recent years, fields outside of the hard sciences have spawned the creation of new areas of mathematics, such as game theory, which grew out of economic considerations, or neural networks, which arose out of the study of the brain in neuro science.

       The advent of the computer has created newapplications, both in studying and using the new computer technology itself (computer science, which uses combinatorics, formal logic, and lattice theory), as well as using computers to study problems arising in other areas of science (computational science), and of course studying the mathematics of computation (numerical analysis).Statistics is probably the most wide spread application of mathematics in the social sciences, but other areas of math are proving increasingly useful in these disciplines, especially in economics and management science.

       Status in academic departments Academic institutions are not consistent in the way they group and label courses, programs, and degrees in applied mathematics. At some schools,there is a single mathematics department, whereas others have separate departments for Applied Mathematics and (Pure) Mathematics. It is very common for Statistics departments to be separate at schools with graduate programs, but many undergraduate-only institutions include statistics under the mathematics department.

       Many applied mathematics programs (as opposed to departments)consist of primarily cross-listed courses and jointly-appointed faculty in departments representing applications. Some Ph.D. programs in applied mathematics require little or no coursework outside of mathematics, while others require substantial coursework in a specific area of application. In some respects this difference reflects the distinction between "application of mathematics" and "applied mathematics".

       Some universities in the UK host departments of Applied Mathematics and Theoretical Physics,but it is now much less common to have separate departments of pure and applied mathematics. Schools with separate applied mathematics departments range from Brown University, which hasa well-known and large Division of Applied Mathematics that offers degrees through the doctorate, to Santa Clara University, which offers only the M.S. in applied mathematics. Research universities dividing their mathematics department into pure and applied sections include Harvard and MIT.

       At some universities there is a considerable amount of tension between applied and pure mathematics departments, or between applied and pure groups within a single department. One reason is that pure mathematics is often perceived as having a higher intellectual standing. Another reason is a different level of compensation, as applied mathematicians are often paid more. Applied mathematics also enjoys better opportunities to bring external funding from many sources, not limited to the Division of Mathematical Sciences at the National Science Foundation (NSF) like much of pure mathematics. External funding is highly valued at research universities and is often a condition for faculty advancement. Similar tensions can also exist between statistics and mathematics groups and departments.

[ 本帖最后由 ~HeBe~_@ 于 25-11-2007 08:23 PM 编辑 ]

~HeBe~_@

http://www.math.nus.edu.sg/~matleesl/leesl.htm

Prof Lee Seng Luan

密码学是以什么为基础？Number theory吗?比如RSA...

除了number theory还需要什么知识？

~HeBe~_@

密码学是需要Number theory和Abstract Algebra.
RSA 是由三个人发明cryptology ，(Ronald L. Rivest, Adi Shamir, and Leonard Adleman)
据说他们是用基本的Number theory和Abstract Algebra的知识发明cryptology。。。


[ 本帖最后由 ~HeBe~_@ 于 25-11-2007 01:12 PM 编辑 ]

~HeBe~_@

这本书的内容不是以下的内容



这里有一些有关于，cryptology的资料。。。

Generally, Cryptology 可以分为 Cryptography and Cryptanalysis

Cryptology: the theory of data security and data integrity.
Cryptology splits up into:

Cryptography - the design of secure data and communication systems, and
Cryptanalysis - the breaking of such systems

Table of Contents
-----------------

1. Overview

2. Net Etiquette
2.1. What groups are around? What's a FAQ? Who am I? Why am I here?
2.2. Do political discussions belong in sci.crypt?
2.3. How do I present a new encryption scheme in sci.crypt?

3. Basic Cryptology
3.1. What is cryptology? Cryptography? Plaintext? Ciphertext? Encryption? Key?
3.2. What references can I start with to learn cryptology?
3.3. How does one go about cryptanalysis?
3.4. What is a brute-force search and what is its cryptographic relevance?
3.5. What are some properties satisfied by every strong cryptosystem?
3.6. If a cryptosystem is theoretically unbreakable, then is it
  guaranteed analysis-proof in practice?
3.7. Why are many people still using cryptosystems that are
  relatively easy to break?
3.8. What are the basic types of cryptanalytic `attacks'?

4. Mathematical Cryptology
4.1. In mathematical terms, what is a private-key cryptosystem?
4.2. What is an attack?
4.3. What's the advantage of formulating all this mathematically?
4.4. Why is the one-time pad secure?
4.5. What's a ciphertext-only attack?
4.6. What's a known-plaintext attack?
4.7. What's a chosen-plaintext attack?
4.8. In mathematical terms, what can you say about brute-force attacks?
4.9. What's a key-guessing attack? What's entropy?

5. Product Ciphers
5.1. What is a product cipher?
5.2. What makes a product cipher secure?
5.3. What are some group-theoretic properties of product ciphers?
5.4. What can be proven about the security of a product cipher?
5.5. How are block ciphers used to encrypt data longer than the block size?
5.6. Can symmetric block ciphers be used for message authentication?
5.7. What exactly is DES?
5.8. What is triple DES?
5.9. What is differential cryptanalysis?
5.10. How was NSA involved in the design of DES?
5.11. Is DES available in software?
5.12. Is DES available in hardware?
5.13. Can DES be used to protect classified information?
5.14. What are ECB, CBC, CFB, and OFB encryption?

6. Public-Key Cryptography
6.1. What is public-key cryptography?
6.2. How does public-key cryptography solve cryptography's Catch-22?
6.3. What is the role of the `trapdoor function' in public key schemes?
6.4. What is the role of the `session key' in public key schemes?
6.5. What's RSA?
6.6. Is RSA secure?
6.7. What's the difference between the RSA and Diffie-Hellman schemes?
6.8. What is `authentication' and the `key distribution problem'?
6.9. How fast can people factor numbers?
6.10. What about other public-key cryptosystems?
6.11. What is the `RSA Factoring Challenge?'

7. Digital Signatures
7.1. What is a one-way hash function?
7.2. What is the difference between public, private, secret, shared, etc.?
7.3. What are MD4 and MD5?
7.4. What is Snefru?

8. Technical Miscellany
8.1. How do I recover from lost passwords in WordPerfect?
8.2. How do I break a Vigenere (repeated-key) cipher?
8.3. How do I send encrypted mail under UNIX? [PGP, RIPEM, PEM, ...]
8.4. Is the UNIX crypt command secure?
8.5. How do I use compression with encryption?
8.6. Is there an unbreakable cipher?
8.7. What does ``random'' mean in cryptography?
8.8. What is the unicity point (a.k.a. unicity distance)?
8.9. What is key management and why is it important?
8.10. Can I use pseudo-random or chaotic numbers as a key stream?
8.11. What is the correct frequency list for English letters?
8.12. What is the Enigma?
8.13. How do I shuffle cards?
8.14. Can I foil S/W pirates by encrypting my CD-ROM?
8.15. Can you do automatic cryptanalysis of simple ciphers?
8.16. What is the coding system used by VCR+?

9. Other Miscellany
9.1. What is the National Security Agency (NSA)?
9.2. What are the US export regulations?
9.3. What is TEMPEST?
9.4. What are the Beale Ciphers, and are they a hoax?
9.5. What is the American Cryptogram Association, and how do I get in touch?
9.6. Is RSA patented?
9.7. What about the Voynich manuscript?

10. References
10.1. Books on history and classical methods
10.2. Books on modern methods
10.3. Survey articles
10.4. Reference articles
10.5. Journals, conference proceedings
10.6. Other
10.7. How may one obtain copies of FIPS and ANSI standards cited herein?
10.8. Electronic sources
10.9. RFCs (available from [FTPRF])
10.10. Related newsgroups

[ 本帖最后由 ~HeBe~_@ 于 27-1-2008 07:42 PM 编辑 ]

flash

原帖由 ~HeBe~_@ 于 25-11-2007 01:40 AM 发表
这里有一些有关于，cryptology的资料。。。

Generally, Cryptology 可以分为 Cryptography and Cryptanalysis

Cryptology: the theory of data security and data integrity.
Cryptology splits up into ...

看起来蛮有趣的，有没有相关的内容呢？

这好像是一本书哦...

书名是什么？

~HeBe~_@

Contents:

2.1. What groups are around? What's a FAQ? Who am I? Why am I here?
2.2. Do political discussions belong in sci.crypt?
2.3. How do I present a new encryption scheme in sci.crypt?


2.1. What groups are around? What's a FAQ? Who am I? Why am I here?

  Read news.announce.newusers and news.answers for a few weeks. Always
  make sure to read a newsgroup for some time before you post to it.
  You'll be amazed how often the same question can be asked in the same
  newsgroup. After a month you'll have a much better sense of what the
  readers want to see.

2.2. Do political discussions belong in sci.crypt?

  No. In fact some newsgroups (notably misc.legal.computing) were
  created exactly so that political questions like ``Should RSA be
  patented?'' don't get in the way of technical discussions. Many
  sci.crypt readers also read misc.legal.computing, comp.org.eff.talk,
  comp.patents, sci.math, comp.compression, talk.politics.crypto,
  et al.; for the benefit of people who don't care about those other
  topics, try to put your postings in the right group.

  Questions about microfilm and smuggling and other non-cryptographic
  ``spy stuff'' don't belong in sci.crypt either.

2.3. How do I present a new encryption scheme in sci.crypt?

  ``I just came up with this neat method of encryption. Here's some
  ciphertext: FHDSIJOYW^&%$*#@OGBUJHKFSYUIRE. Is it strong?'' Without a
  doubt questions like this are the most annoying traffic on sci.crypt.

  If you have come up with an encryption scheme, providing some
  ciphertext from it is not adequate. Nobody has ever been impressed by
  random gibberish. Any new algorithm should be secure even if the
  opponent knows the full algorithm (including how any message key is
  distributed) and only the private key is kept secret. There are some
  systematic and unsystematic ways to take reasonably long ciphertexts
  and decrypt them even without prior knowledge of the algorithm, but
  this is a time-consuming and possibly fruitless exercise which most
  sci.crypt readers won't bother with.

  So what do you do if you have a new encryption scheme? First of all,
  find out if it's really new. Look through this FAQ for references and
  related methods. Familiarize yourself with the literature and the
  introductory textbooks.

  When you can appreciate how your cryptosystem fits into the world at
  large, try to break it yourself! You shouldn't waste the time of tens
  of thousands of readers asking a question which you could have easily
  answered on your own.

  If you really think your system is secure, and you want to get some
  reassurance from experts, you might try posting full details of your
  system, including working code and a solid theoretical explanation, to
  sci.crypt. (Keep in mind that the export of cryptography is regulated
  in some areas.)

  If you're lucky an expert might take some interest in what you posted.
  You can encourage this by offering cash rewards---for instance, noted
  cryptographer Ralph Merkle is offering $1000 to anyone who can break
  Snefru-4---but there are no guarantees. If you don't have enough
  experience, then most likely any experts who look at your system will
  be able to find a flaw. If this happens, it's your responsibility to
  consider the flaw and learn from it, rather than just add one more
  layer of complication and come back for another round.

  A different way to get your cryptosystem reviewed is to have the NSA
  look at it. A full discussion of this procedure is outside the scope
  of this FAQ.

  Among professionals, a common rule of thumb is that if you want to
  design a cryptosystem, you have to have experience as a cryptanalyst.

~HeBe~_@

是蛮有趣的。。。
有的。。我一个一个放上来。。

~HeBe~_@

这不是一本书。。。。

flash

原帖由 ~HeBe~_@ 于 25-11-2007 09:04 PM 发表
是蛮有趣的。。。
有的。。我一个一个放上来。。

先谢谢你的分享。。。。。。

~HeBe~_@

原帖由 flash 于 26-11-2007 09:06 AM 发表




先谢谢你的分享。。。。。。

不用客气。。。分享资料是想让更多的人学习。。。获益无穷。。。

~HeBe~_@

Contents:

3.1. What is cryptology? Cryptography? Plaintext? Ciphertext? Encryption? Key?
3.2. What references can I start with to learn cryptology?
3.3. How does one go about cryptanalysis?
3.4. What is a brute-force search and what is its cryptographic relevance?
3.5. What are some properties satisfied by every strong cryptosystem?
3.6. If a cryptosystem is theoretically unbreakable, then is it
  guaranteed analysis-proof in practice?
3.7. Why are many people still using cryptosystems that are
  relatively easy to break?
3.8. What are the basic types of cryptanalytic `attacks'?


3.1. What is cryptology? Cryptography? Plaintext? Ciphertext? Encryption? Key?

  The story begins: When Julius Caesar sent messages to his trusted
  acquaintances, he didn't trust the messengers. So he replaced every A
  by a D, every B by a E, and so on through the alphabet. Only someone
  who knew the ``shift by 3'' rule could decipher his messages.

  A cryptosystem or cipher system is a method of disguising messages so
  that only certain people can see through the disguise. Cryptography is
  the art of creating and using cryptosystems. Cryptanalysis is the art
  of breaking cryptosystems---seeing through the disguise even when
  you're not supposed to be able to. Cryptology is the study of both
  cryptography and cryptanalysis.

  The original message is called a plaintext. The disguised message is
  called a ciphertext. Encryption means any procedure to convert
  plaintext into ciphertext. Decryption means any procedure to convert
  ciphertext into plaintext.

  A cryptosystem is usually a whole collection of algorithms. The
  algorithms are labelled; the labels are called keys. For instance,
  Caesar probably used ``shift by n'' encryption for several different
  values of n. It's natural to say that n is the key here.

  The people who are supposed to be able to see through the disguise are
  called recipients. Other people are enemies, opponents, interlopers,
  eavesdroppers, or third parties.

3.2. What references can I start with to learn cryptology?

  For an introduction to technical matter, the survey articles given
  in part 10 are the best place to begin as they are, in general,
  concise, authored by competent people, and well written. However,
  these articles are mostly concerned with cryptology as it has
  developed in the last 50 years or so, and are more abstract and
  mathematical than historical. The Codebreakers by Kahn [KAH67] is
  encyclopedic in its history and technical detail of cryptology up
  to the mid-60's.

  Introductory cryptanalysis can be learned from Gaines [GAI44] or
  Sinkov [SIN66]. This is recommended especially for people who want
  to devise their own encryption algorithms since it is a common
  mistake to try to make a system before knowing how to break one.

  The selection of an algorithm for the DES drew the attention of
  many public researchers to problems in cryptology. Consequently
  several textbooks and books to serve as texts have appeared. The
  book of Denning [DEN82] gives a good introduction to a broad range
  of security including encryption algorithms, database security,
  access control, and formal models of security. Similar comments
  apply to the books of Price & Davies [PRI84] and Pfleeger [PFL89].

  The books of Konheim [KON81] and Meyer & Matyas [MEY82] are quite
  technical books. Both Konheim and Meyer were directly involved in
  the development of DES, and both books give a thorough analysis of
  DES. Konheim's book is quite mathematical, with detailed analyses
  of many classical cryptosystems. Meyer and Matyas concentrate on
  modern cryptographic methods, especially pertaining to key management
  and the integration of security facilities into computer systems and
  networks. For more recent documentation on related areas, try
  G. Simmons in [SIM91].

  The books of Rueppel [RUE86] and Koblitz [KOB89] concentrate on
  the application of number theory and algebra to cryptography.

3.3. How does one go about cryptanalysis?

  Classical cryptanalysis involves an interesting combination of
  analytical reasoning, application of mathematical tools, pattern
  finding, patience, determination, and luck. The best available
  textbooks on the subject are the Military Cryptanalytics series
  [FRIE1]. It is clear that proficiency in cryptanalysis is, for
  the most part, gained through the attempted solution of given
  systems. Such experience is considered so valuable that some of the
  cryptanalyses performed during WWII by the Allies are still
  classified.

  Modern public-key cryptanalysis may consist of factoring an integer,
  or taking a discrete logarithm. These are not the traditional fare
  of the cryptanalyst. Computational number theorists are some of the
  most successful cryptanalysts against public key systems.

3.4. What is a brute-force search and what is its cryptographic relevance?

  In a nutshell: If f(x) = y and you know y and can compute f, you can
  find x by trying every possible x. That's brute-force search.

  Example: Say a cryptanalyst has found a plaintext and a corresponding
  ciphertext, but doesn't know the key. He can simply try encrypting the
  plaintext using each possible key, until the ciphertext matches---or
  decrypting the ciphertext to match the plaintext, whichever is faster.
  Every well-designed cryptosystem has such a large key space that this
  brute-force search is impractical.
   
  Advances in technology sometimes change what is considered
  practical. For example, DES, which has been in use for over 10 years
  now, has 2^56, or about 10^17, possible keys. A computation with
  this many operations was certainly unlikely for most users in the
  mid-70's. The situation is very different today given the dramatic
  decrease in cost per processor operation. Massively parallel
  machines threaten the security of DES against brute force search.
  Some scenarios are described by Garron and Outerbridge [GAR91].

  One phase of a more sophisticated cryptanalysis may involve a
  brute-force search of some manageably small space of possibilities.

3.5. What are some properties satisfied by every strong cryptosystem?

  The security of a strong system resides with the secrecy of the key
  rather than with the supposed secrecy of the algorithm.

  A strong cryptosystem has a large keyspace, as mentioned above. It
  has a reasonably large unicity distance; see question 8.8.

  A strong cryptosystem will certainly produce ciphertext which appears
  random to all standard statistical tests (see, for example, [CAE90]).
   
  A strong cryptosystem will resist all known previous attacks. A
  system which has never been subjected to scrutiny is suspect.

  If a system passes all the tests mentioned above, is it necessarily
  strong? Certainly not. Many weak cryptosystems looked good at first.
  However, sometimes it is possible to show that a cryptosystem is
  strong by mathematical proof. ``If Joe can break this system, then
  he can also solve the well-known difficult problem of factoring
  integers.'' See part 6. Failing that, it's a crap shoot.

~HeBe~_@

3.6. If a cryptosystem is theoretically unbreakable, then is it
  guaranteed analysis-proof in practice?

  Cryptanalytic methods include what is known as ``practical
  cryptanalysis'': the enemy doesn't have to just stare at your
  ciphertext until he figures out the plaintext. For instance, he might
  assume ``cribs''---stretches of probable plaintext. If the crib is
  correct then he might be able to deduce the key and then decipher the
  rest of the message. Or he might exploit ``isologs''---the same
  plaintext enciphered in several cryptosystems or several keys. Thus
  he might obtain solutions even when cryptanalytic theory says he
  doesn't have a chance.

  Sometimes, cryptosystems malfunction or are misused. The one-time pad,
  for example, loses all security if it is used more than once! Even
  chosen-plaintext attacks, where the enemy somehow feeds plaintext into
  the encryptor until he can deduce the key, have been employed. See
  [KAH67].
  
3.7. Why are many people still using cryptosystems that are
  relatively easy to break?

  Some don't know any better. Often amateurs think they can design
  secure systems, and are not aware of what an expert cryptanalyst
  could do. And sometimes there is insufficient motivation for anybody
  to invest the work needed to crack a system.

3.8. What are the basic types of cryptanalytic `attacks'?

  A standard cryptanalytic attack is to know some plaintext matching a
  given piece of ciphertext and try to determine the key which maps one
  to the other.  This plaintext can be known because it is standard (a
  standard greeting, a known header or trailer, ...) or because it is
  guessed.  If text is guessed to be in a message, its position is probably
  not known, but a message is usually short enough that the cryptanalyst
  can assume the known plaintext is in each possible position and do
  attacks for each case in parallel.  In this case, the known plaintext can
  be something so common that it is almost guaranteed to be in a message.

  A strong encryption algorithm will be unbreakable not only under known
  plaintext (assuming the enemy knows all the plaintext for a given
  ciphertext) but also under "adaptive chosen plaintext" -- an attack
  making life much easier for the cryptanalyst.  In this attack, the enemy
  gets to choose what plaintext to use and gets to do this over and over,
  choosing the plaintext for round N+1 only after analyzing the result of
  round N.

  For example, as far as we know, DES is reasonably strong even under an
  adaptive chosen plaintext attack (the attack Biham and Shamir used).  Of
  course, we do not have access to the secrets of government cryptanalytic
  services.  Still, it is the working assumption that DES is reasonably
  strong under known plaintext and triple-DES is very strong under all
  attacks.

  To summarize, the basic types of cryptanalytic attacks in order of
  difficulty for the attacker, hardest first, are:

  cyphertext only: the attacker has only the encoded message from which
    to determine the plaintext, with no knowledge whatsoever of the
    latter.

    A cyphertext only attack is usually presumed to be possible, and
    a code's resistance to it is considered the basis of its
    cryptographic security.

  known plaintext: the attacker has the plaintext and corresponding
    cyphertext of an arbitrary message not of his choosing. The
    particular message of the sender's is said to be `compromised'.

    In some systems, one known cyphertext-plaintext pair will
    compromise the overall system, both prior and subsequent
    transmissions, and resistance to this is characteristic of a
    secure code.

  Under the following attacks, the attacker has the far less likely
  or plausible ability to `trick' the sender into encrypting or
  decrypting arbitrary plaintexts or cyphertexts. Codes that resist
  these attacks are considered to have the utmost security.

  chosen plaintext: the attacker has the capability to find the
    cyphertext corresponding to an arbitrary plaintext message of his
    choosing.

  chosen cyphertext: the attacker can choose arbitrary cyphertext and
    find the corresponding decrypted plaintext. This attack can show
    in public key systems, where it may reveal the private key.

  adaptive chosen plaintext: the attacker can determine the cyphertext
    of chosen plaintexts in an interactive or iterative process based on
    previous results. This is the general name for a method of attacking
    product ciphers called `differential cryptanalysis'.

  The next part of the FAQ gives the mathematical detail behind the
  various types of cryptoanalytic attacks.

~HeBe~_@

Contents:

4.1. In mathematical terms, what is a private-key cryptosystem?
4.2. What is an attack?
4.3. What's the advantage of formulating all this mathematically?
4.4. Why is the one-time pad secure?
4.5. What's a ciphertext-only attack?
4.6. What's a known-plaintext attack?
4.7. What's a chosen-plaintext attack?
4.8. In mathematical terms, what can you say about brute-force attacks?
4.9. What's a key-guessing attack? What's entropy?


Reader, beware: This section is highly mathematical. Well, maybe not
_highly_ mathematical, but it's got a bunch of symbols and scary-looking
formulas. You have been warned.


4.1. In mathematical terms, what is a private-key cryptosystem?

  A private-key cryptosystem consists of an encryption system E and a
  decryption system D. The encryption system E is a collection of
  functions E_K, indexed by ``keys'' K, mapping some set of
  ``plaintexts'' P to some set of ``ciphertexts'' C. Similarly the
  decryption system D is a collection of functions D_K such that
  D_K(E_K(P)) = P for every plaintext P. That is, succesful decryption
  of ciphertext into plaintext is accomplished using the same key
  (index) as was used for the corresponding encryption of plaintext
  into ciphertext. Such systems, where the same key value is used to
  encrypt and decrypt, are also known as ``symmetric'' cryptoystems.

4.2. What is an attack?

  In intuitive terms a (passive) attack on a cryptosystem is any method
  of starting with some information about plaintexts and their
  corresponding ciphertexts under some (unknown) key, and figuring out
  more information about the plaintexts. It's possible to state
  mathematically what this means. Here we go.

  Fix functions F, G, and H of n variables. Fix an encryption system E,
  and fix a distribution of plaintexts and keys.

  An attack on E using G assuming F giving H with probability p is an
  algorithm A with a pair f, g of inputs and one output h, such that
  there is probability p of computing h = H(P_1,...,P_n), if we have
  f = F(P_1,...,P_n) and g = G(E_K(P_1),...,E_K(P_n)). Note that this
  probability depends on the distribution of the vector (K,P_1,...,P_n).

  The attack is trivial (or ``pointless'') if there is probability at
  least p of computing h = H(P_1,...,P_n) if f = F(P_1,...,P_n) and
  g = G(C_1,...,C_n). Here C_1,...,C_n range uniformly over the possible
  ciphertexts, and have no particular relation to P_1,...,P_n. In other
  words, an attack is trivial if it doesn't actually use the encryptions
  E_K(P_1),...,E_K(P_n).

  An attack is called ``one-ciphertext'' if n = 1, ``two-ciphertext'' if
  n = 2, and so on.

4.3. What's the advantage of formulating all this mathematically?

  In basic cryptology you can never prove that a cryptosystem is secure.
  Read part 3: we keep saying ``a strong cryptosystem must have this
  property, but having this property is no guarantee that a cryptosystem
  is strong!''

  In contrast, the purpose of mathematical cryptology is to precisely
  formulate and, if possible, prove the statement that a cryptosystem is
  strong. We say, for example, that a cryptosystem is secure against
  all (passive) attacks if any nontrivial attack against the system (as
  defined above) is too slow to be practical. If we can prove this
  statement then we have confidence that our cryptosystem will resist
  any (passive) cryptanalytic technique. If we can reduce this statement
  to some well-known unsolved problem then we still have confidence that
  the cryptosystem isn't easy to break.

  Other parts of cryptology are also amenable to mathematical
  definition. Again the point is to explicitly identify what assumptions
  we're making and prove that they produce the desired results. We can
  figure out what it means for a particular cryptosystem to be used
  properly: it just means that the assumptions are valid.

  The same methodology is useful for cryptanalysis too. The cryptanalyst
  can take advantage of incorrect assumptions. Often he can try to
  construct a proof of security for a system, see where the proof fails,
  and use these failures as the starting points for his analysis.
  
4.4. Why is the one-time pad secure?

  By definition, the one-time pad is a cryptosystem where the
  plaintexts, ciphertexts, and keys are all strings (say byte strings)
  of some length m, and E_K(P) is just the sum (let's say the exclusive
  or) of K and P.

  It is easy to prove mathematically that there are _no_ nontrivial
  single-ciphertext attacks on the one-time pad, assuming a uniform
  distribution of keys. Note that we don't have to assume a uniform
  distribution of plaintexts. (Here's the proof: Let A be an attack,
  i.e., an algorithm taking two inputs f, g and producing one output h,
  with some probability p that h = H(P) whenever f = F(P) and
  g = G(E_K(P)) (i.e., g = G(K + P)). Then, because the distribution of
  K is uniform and independent of P, the distribution of K + P must also
  be uniform and independent of P. But also the distribution of C is
  uniform and independent of P. Hence there is probability exactly p
  that h = H(P) whenever f = F(P) and g = G(C), over all P and C. Thus
  a fortiori A is trivial.)

  On the other hand the one-time pad is _not_ secure if a key K is used
  for more than one plaintext: i.e., there are nontrivial
  multiple-ciphertext attacks. So to be properly used a key K must be
  thrown away after one encryption. The key is also called a ``pad'';
  this explains the name ``one-time pad.''

  Also, a computer-based pseudo-random number generator does _not_
  qualify as a true one-time pad because of its deterministic
  properties. See `pseudo-random number generators as key stream'.

4.5. What's a ciphertext-only attack?

  In the notation above, a ciphertext-only attack is one where F is
  constant. Given only some information G(E_K(P_1),...,E_K(P_n)) about
  n ciphertexts, the attack has to have some chance of producing some
  information H(P_1,...,P_n) about the plaintexts. The attack is trivial
  if it has just as good a chance of producing H(P_1,...,P_n) when given
  G(C_1,...,C_n) for random C_1,...,C_n.

  For example, say G(C) = C, and say H(P) is the first bit of P. We can
  easily write down an attack---the ``guessing attack,'' which simply
  guesses that H(P) is 1. This attack is trivial because it doesn't use
  the ciphertext: it has a fifty-fifty chance of guessing correctly no
  matter what. On the other hand there is an attack on RSA which
  produces one bit of information about P, with 100% success, using C.
  If it is fed a random C then the success rate drops to 50%. So this is
  a nontrivial attack.

[ 本帖最后由 ~HeBe~_@ 于 4-12-2007 05:20 PM 编辑 ]

~HeBe~_@

4.6. What's a known-plaintext attack?

  The classic known-plaintext attack has F(P_1,P_2) = P_1,
  G(C_1,C_2) = (C_1,C_2), and H(P_1,P_2) depending only on P_2.
  In other words, given two ciphertexts C_1 and C_2 and one decryption
  P_1, the known-plaintext attack should produce information about the
  other decryption P_2.

  Note that known-plaintext attacks are often defined in the literature
  as producing information about the key, but this is pointless: the
  cryptanalyst generally cares about the key only insofar as it lets him
  decrypt further messages.

4.7. What's a chosen-plaintext attack?

  A chosen-plaintext attack is the first of an increasingly impractical
  series of _active_ attacks on a cryptosystem: attacks where the
  cryptanalyst feeds data to the encryptor. These attacks don't fit into
  our model of passive attacks explained above. Anyway, a
  chosen-plaintext attack lets the cryptanalyst choose a plaintext and
  look at the corresponding ciphertext, then repeat until he has figured
  out how to decrypt any message. More absurd examples of this sort of
  attack are the ``chosen-key attack'' and ``chosen-system attack.''

  A much more important form of active attack is a message corruption
  attack, where the attacker tries to change the ciphertext in such a
  way as to make a useful change in the plaintext.

  There are many easy ways to throw kinks into all of these attacks:
  for instance, automatically encrypting any plaintext P as
  T,E_K(h(T+R+P),R,P), where T is a time-key (sequence number) chosen anew
  for each message, R is a random number, and h is a one-way hash
  function. Here comma means concatenation and plus means exclusive-or.

4.8. In mathematical terms, what can you say about brute-force attacks?

  Consider the following known-plaintext attack. We are given some
  plaintexts P_1,...,P_{n-1} and ciphertexts C_1,...,C_{n-1}. We're
  also given a ciphertext C_n. We run through every key K. When we find
  K such that E_K(P_i) = C_i for every i < n, we print D_K(C_n).

  If n is big enough that only one key works, this attack will succeed
  on valid inputs all the time, while it will produce correct results
  only once in a blue moon for random inputs. Thus this is a nontrivial
  attack. Its only problem is that it is very slow if there are many
  possible keys.

4.9. What's a key-guessing attack? What's entropy?

  Say somebody is using the one-time pad---but isn't choosing keys
  randomly and uniformly from all m-bit messages, as he was supposed to
  for our security proof. In fact say he's known to prefer keys which
  are English words. Then a cryptanalyst can run through all English
  words as possible keys. This attack will often succeed, and it's much
  faster than a brute-force search of the entire keyspace.

  We can measure how bad a key distribution is by calculating its
  entropy. This number E is the number of ``real bits of information''
  of the key: a cryptanalyst will typically happen across the key within
  2^E guesses. E is defined as the sum of -p_K log_2 p_K, where p_K is
  the probability of key K.

~HeBe~_@

Contents:

5.1. What is a product cipher?
5.2. What makes a product cipher secure?
5.3. What are some group-theoretic properties of product ciphers?
5.4. What can be proven about the security of a product cipher?
5.5. How are block ciphers used to encrypt data longer than the block size?
5.6. Can symmetric block ciphers be used for message authentication?
5.7. What exactly is DES?
5.8. What is triple DES?
5.9. What is differential cryptanalysis?
5.10. How was NSA involved in the design of DES?
5.11. Is DES available in software?
5.12. Is DES available in hardware?
5.13. Can DES be used to protect classified information?
5.14. What are ECB, CBC, CFB, OFB, and PCBC encryption?


5.1. What is a product cipher?

  A product cipher is a block cipher that iterates several weak
  operations such as substitution, transposition, modular
  addition/multiplication, and linear transformation. (A ``block
  cipher'' just means a cipher that encrypts a block of data---8 bytes,
  say---all at once, then goes on to the next block.) The notion of
  product ciphers is due to Shannon [SHA49]. Examples of modern
  product ciphers include LUCIFER [SOR84], DES [NBS77], SP-networks
  [KAM78], LOKI [BRO90], FEAL [SHI84], PES [LAI90], Khufu and Khafre
  [ME91a]. The so-called Feistel ciphers are a class of product
  ciphers which operate on one half of the ciphertext at each round,
  and then swap the ciphertext halves after each round. LUCIFER,
  DES, LOKI, and FEAL are examples of Feistel ciphers.

  The following table compares the main parameters of several product
  ciphers:

  cipher   |   block length   |   key bits   |   number of rounds
  LUCIFER          128               128                16
  DES               64                56                16
  LOKI              64                64                16
  FEAL              64               128            2^x, x >= 5
  PES               64               128                 8

5.2. What makes a product cipher secure?

  Nobody knows how to prove mathematically that a product cipher is
  completely secure. So in practice one begins by demonstrating that the
  cipher ``looks highly random''. For example, the cipher must be
  nonlinear, and it must produce ciphertext which functionally depends
  on every bit of the plaintext and the key. Meyer [MEY78] has shown
  that at least 5 rounds of DES are required to guarantee such a
  dependence. In this sense a product cipher should act as a ``mixing''
  function which combines the plaintext, key, and ciphertext in a
  complex nonlinear fashion.

  The fixed per-round substitutions of the product cipher are
  referred to as S-boxes. For example, LUCIFER has 2 S-boxes, and DES
  has 8 S-boxes. The nonlinearity of a product cipher reduces to a
  careful design of these S-boxes. A list of partial design criteria
  for the S-boxes of DES, which apply to S-boxes in general, may be
  found in Brown [BRO89] and Brickell et al. [BRI86].

5.3. What are some group-theoretic properties of product ciphers?

  Let E be a product cipher that maps N-bit blocks to N-bit blocks.
  Let E_K(X) be the encryption of X under key K. Then, for any fixed K,
  the map sending X to E_K(X) is a permutation of the set of N-bit
  blocks. Denote this permutation by P_K. The set of all N-bit
  permutations is called the symmetric group and is written S_{2^N}.
  The collection of all these permutations P_K, where K ranges over all
  possible keys, is denoted E(S_{2^N}). If E were a random mapping from
  plaintexts to ciphertexts then we would expect E(S_{2^N}) to generate
  a large subset of S_{2^N}.

  Coppersmith and Grossman [COP74] have shown that a very simple
  product cipher can generate the alternating group A_{2^N} given a
  sufficient number of rounds. (The alternating group is half of the
  symmetric group: it consists of all ``even'' permutations, i.e., all
  permutations which can be written as an even number of swaps.)
  Even and Goldreich [EVE83] were able to extend these results to show
  that Feistel ciphers can generate A_{2^N}, given a sufficient number
  of rounds.

  The security of multiple encipherment also depends on the
  group-theoretic properties of a cipher. Multiple encipherment is an
  extension over single encipherment if for keys K1, K2 there does
  not exist a third key K3 such that

  E_K2(E_K1(X)) == E_(K3)(X)                (**)

  which indicates that encrypting twice with two independent keys
  K1, K2 is equal to a single encryption under the third key K3. If
  for every K1, K2 there exists a K3 such that eq. (**) is true then
  we say that E is a group.

  This question of whether DES is a group under this definition was
  extensively studied by Sherman, Kaliski, and Rivest [SHE88]. In their
  paper they give strong evidence for the hypothesis that DES is not a
  group. In fact DES is not a group [CAM93].

5.4. What can be proven about the security of a product cipher?

  Recall from above that P_K is a permutation produced by E under
  some key K. The goal of the designer of E is to ensure that P_K
  appears to be a random element of S_{2^N}, the symmetric group.
  Let R be an element of S_{2^N} selected randomly. We will say that P_K
  and R are indistinguishable if an observer given P_K and R in some
  order cannot distinguish between these two permutations in polynomial
  time. That is, with time bounded resources, the observer cannot
  determine which of the permutations is produced by E: the optimal
  decision is no better than simply guessing.

  Luby and Rackoff [LUB88] have shown that a class of Feistel ciphers
  are secure in this sense when the round mapping is replaced by
  random boolean functions.

5.5. How are block ciphers used to encrypt data longer than the block size?

  There are four standard ``modes of operation'' (and numerous non-standard
  ones as well). The standard modes of operation are defined in the U.S.
  Department of Commerce Federal Information Processing Standard (FIPS) 81,
  published in 1980. See the question about ECB below for more details.

  Although they are defined for the DES block cipher, the ``modes of
  operation'' can be used with any block cipher.

5.6. Can symmetric block ciphers be used for message authentication?

  You may use a symmetric cryptosystem block cipher to prove to yourself
  that you generated a message, and that the message wasn't altered
  after you created it. But you cannot prove these things to anyone else
  without revealing your key. Thereafter you cannot prove anything about
  messages authenticated with that key.
  
  See ANSI X3.106-1983 and FIPS 113 (1985) for a standard method of message
  authentication using DES.

5.7. What exactly is DES?

  DES is the U.S. Government's Data Encryption Standard, a product
  cipher that operates on 64-bit blocks of data, using a 56-bit key.

  It is defined in FIPS 46-1 (1988) [which supersedes FIPS 46 (1977)].
  FIPS are Federal Information Processing Standards published by NTIS.
  DES is identical to the ANSI standard Data Encryption Algorithm (DEA)
  defined in ANSI X3.92-1981.

5.8. What is triple DES?

  Triple DES is a product cipher which, like DES, operates on 64-bit
  data blocks. There are several forms, each of which uses the DES
  cipher 3 times. Some forms use two 56-bit keys, some use three.
  The DES ``modes of operation'' may also be used with triple-DES.

  Some people refer to E(K1,D(K2,E(K1,x))) as triple-DES.

  This method is defined in chapter 7.2 of the ANSI standard X9.17-1985
  ``Financial Institution Key Management'' and is intended for use in
  encrypting DES keys and IVs for ``Automated Key Distribution''. Its
  formal name is ``Encryption and Decryption of a Single Key by a Key
  Pair'', but it is referenced in other standards documents as EDE.

  That standard says (section 7.2.1): ``Key encrypting keys may be a single
  DEA key or a DEA key pair. Key pairs shoud be used where additional
  security is needed (e.g., the data protected by the key(s) has a long
  security life). A key pair shall not be encrypted or decrypted using a
  single key.''

  Others use the term ``triple-DES'' for E(K1,D(K2,E(K3,x))) or
  E(K1,E(K2,E(K3,x))).

  All of these methods are defined only for ECB mode of operation.  The
  security of various methods of achieving other modes of operation (such as
  CBC) is under study at the moment.  For now, it should be assumed that
  other modes be defined as they are today, but with E(K1,D(K2,E(K1,x))) as
  the block cipher within the feedback mechanism creating the mode.

  One of us (Ellison) has long advocated triple DES use in the form

    E(K1, Tran( E(K2, Tran( E(K3, Compress( x )))))),

  where each DES instance has its own key and IV (for CBC mode) and Tran is
  a large-block transposition program. Tran is available from [FTPTR].  This
  claims to gain security by diffusing single bit changes over a much larger
  block (Tran's block size).  Other compositions of weak ciphers with DES
  are possible.  For example, one could use:

   E(K1, Prngxor(K4, Tran( E(K2, Tran( Prngxor(K5, E(K3, Compress( x )))))))),

  where Prngxor() [FTPPX] is a simple stream cipher driven from a long-period
  pseudo-random number generator (PRNG), to make sure that all plaintext or
  ciphertext patterns are hidden while permitting the use of ECB mode for DES
  (since there are certain weaknesses in the use of inner CBC loops for
  multiple-DES, under some attacks, and we do not yet know if these show up
  under composition with Tran()).

~HeBe~_@

5.9. What is differential cryptanalysis?

  Differential cryptanalysis is a statistical attack that can be
  applied to any iterated mapping (i.e., any mapping which is based on
  a repeated round function). The method was recently popularized by
  Biham and Shamir [BIH91], but Coppersmith has remarked that the
  S-boxes of DES were optimized against this attack some 20 years ago.
  This method has proved effective against several product ciphers,
  notably FEAL [BI91a].

  Differential cryptanalysis is based on observing a large number of
  ciphertexts Y, Y' whose corresponding plaintexts X, X' satisfy a
  known difference D = X+X', where + is componentwise XOR. In the
  basic Biham-Shamir attack, 2^{47} such plaintext pairs are required
  to determine the key for DES. Substantially fewer pairs are required
  if DES is truncated to 6 or 8 rounds. In these cases, the actual key
  can be recovered in a matter of minutes using a few thousand pairs.
  For full DES this attack is impractical because it requires so many
  known plaintexts.

  The work of Biham and Shamir on DES revealed several startling
  observations on the algorithm. Most importantly, if the key
  schedule was removed from DES and a 16*48 = 768-bit key was used,
  the key could be recovered in less than 2^{64} steps. Thus
  independent subkeys do not add substantial security to DES.
  Further, the S-boxes of DES are extremely sensitive in that
  changing even single entries in these tables yields significant
  improvement in the differential attack.

  Adi Shamir is quoted to say (NYTimes Oct 13 1991), ``I would say
  that, contrary to what some people believe, there is no evidence
  of tampering with the DES so that the basic design was weakened.''

5.10. How was NSA involved in the design of DES?

  According to Kinnucan [KIN78], Tuchman, a member of the group that
  developed DES at IBM is quoted as saying, ``We developed the DES
  algorithm entirely within IBM using IBMers. The NSA did not
  dictate a single wire!'' Tuchman and Meyer (another developer of
  DES) spent a year breaking ciphers and finding weaknesses in
  Lucifer. They then spent two years strengthening Lucifer. ``Their
  basic approach was to look for strong substitution, permutation,
  and key scheduling functions ... IBM has classified the notes
  containing the selection criteria at the request of the NSA....
  `The NSA told us we had inadvertently reinvented some of the deep
  secrets it uses to make its own algorithms,' explains Tuchman.''
  
  On the other hand, a document called ``Involvement of the NSA in
  the development of DES: unclassified summary of the United States
  Select Committee on Intelligence'', printed in the IEEE
  Communications Magazine, p53-55, 1978, states: ``In the development
  of DES, NSA convinced IBM that a reduced keysize was sufficient;
  indirectly assisted in the development of the S-box structures; and
  certified that the final DES algorithm was, to the best of their
  knowledge, free from any statistical or mathematical weakness.''

  Clearly the key size was reduced at the insistence of the NSA.
  The article further states that the NSA did not tamper with the
  algorithm itself, just the parameters, which in some sense
  resolves the apparent conflict in the remarks of Meyer and Tuchman
  presented above.

5.11. Is DES available in software?

  Several people have made DES code available via ftp (see part 10 for
  pathnames): Stig Ostholm [FTPSO]; BSD [FTPBK]; Eric Young [FTPEY];
  Dennis Furguson [FTPDF]; Mark Riordan [FTPMR]; Phil Karn [FTPPK].
  A Pascal listing of DES is also given in Patterson [PAT87]. Antti
  Louko <alo@kampi.hut.fi> has written a version of DES with BigNum
  packages in [FTPAL].

  FIPS 46-1 says ``The algorithm specified in this standard is to be
  implemented ... using hardware (not software) technology. ...
  Software implementations in general purpose computers are not in
  compliance with this standard.''  Despite this, software
  implementations abound, and are used by government agencies.

5.12. Is DES available in hardware?

  The following paragraphs are quoted from messages sent to the editors.
  We don't vouch for the quality or even existence of the products.

  Christian Franke, franke@informatik.rwth-aachen.de, says: ``1.
  Cryptech CRY12C102: 22.5Mbit/s according to Data Sheet, with 32 Bit
  interface. We use this one, because it was the only one available when
  we started the project. No problems !  2. Pijnenburg PCC100: 20Mbit/s
  according to Data Sheet. Address: PIJNENBURG B.V., Boxtelswweg 26,
  NL-5261 NE Vught, The Netherlands. 3. INFOSYS DES Chip (Germany):
  S-Boxes must be loaded by software. So you can modify the Algorithm.
  Sorry, I don't have the data sheet handy. Please E-Mail me if you need
  further information.''

  Marcus J Ranum, mjr@tis.com, says: ``SuperCrypt'' 100Mb/sec and faster
  DES and Proprietary Storage for 16 56-bit keys Key stream generator
  Integrated hardware DES3 procedure Extended mode with 112 bit keys;
  Computer Elektronik Infosys; 512-A Herndon Parkway,; Herndon, VA
  22070; 800-322-3464.

  Tim Hember, thember@gandalf.ca, says: Newbridge Microsystems sells
  an AM9568 compatible DES chip that operates at 25MHz, performs a
  round of encryption in 18 clocks, has a three-stage pipeline,
  supports ECB, CBC, CFB-8 and >>> CFB-1 <<<<. Further it is very
  reasonable priced as opposed to other high-end DES chips. Call
  Newbridge Microsystems, Ottawa, 613-592-0714. (... there are no
  import/export issues with Canada and the US). If you require custom
  DES or Public Key ICs then Timestep Engineering developed
  Newbridge's crypto chips and ICs for other commercial and
  educational establishments. They can be reached at 613-820-0024.

5.13. Can DES be used to protect classified information?

  DES is not intended to protect classified data. FIPS 46-1 says:
  ``This standard will be used by Federal departments and agencies for
  the cryptographic protection of computer data when the following
  conditions apply: 1. ... cryptographic protection is required; and
  2. the data is not classified according to the National Security Act
  of 1947, as amended, or the Atomic Energy Act of 1954, as amended.''

~HeBe~_@

5.14. What are ECB, CBC, CFB, OFB, and PCBC encryption?

  These are methods for using block ciphers, such as DES, to encrypt
  messages, files, and blocks of data, known as ``modes of operation.''
  Four ``modes of operation'' are defined in FIPS 81 (1980 December 2),
  and also in ANSI X3.106-1983.

  FIPS 81 specifies that when 7-bit ASCII data is sent in octets, the
  unused most-significant bit is to be set to 1.

  FIPS 81 also specifies the padding for short blocks.

  The four FIPS/ANSI standard DES modes of operation are:
        Electronic Code Book  (ECB),
        Cipher Block Chaining (CBC),
        K-bit Cipher FeedBack (CFB), and
        K-bit Output FeedBack (OFB).

  All four of the ANSI/FIPS modes have very little "error extension".
  For a single bit error in the cipherstream, none of them produce an
  error burst in the decrypted output stream of longer than 128 bits.

  A fifth mode of operation, used in Kerberos and elsewhere but not
  defined in any standard, is error-Propagating Cipher Block Chaining
  (PCBC).  Unlike the 4 standard modes, PCBC extends or propagates the
  effect of a single bit error in the cipherstream throughout remainder
  of the decrypted textstream after the point of error.

  These 5 methods are explained below in a C-language-like notation.

  Some symbols:

  P[n]  The n'th block of plaintext, input to encryption, output from
        decryption. Size of block determined by the mode.

  C[n]  The n'th block of ciphertext, output from encryption, input to
        decryption. Size of block determined by the mode.

  E(m)  The DES encryption function, performed on 64-bit block m, using
        the 16-key schedule derived from some 56-bit key.

  D(m)  The DES decryption function, performed on 64-bit block m, using
        the same key schedule as in E(m), except that the 16 keys
        in the schedule are used in the opposite order as in E(m).

  IV    A 64-bit ``initialization vector'', a secret value which, along with
        the key, is shared by both encryptor and decryptor.

  I[n]  The n'th value of a 64-bit variable, used in some modes.
  R[n]  The n'th value of a 64-bit variable, used in some modes.

  LSB(m,k) The k least significant (right-most) bits of m.
        e.g. m & ((1 << k) - 1)

  MSB(m,k) The k most significant (left-most) bits of m.
        e.g. (m >> (64-k)) & ((1 << k) - 1)

  = ^ << >> &  operators as defined in the c langage.


  Electronic Code Book (ECB):

          P[n] and C[n] are each 64-bits long.

          Encryption:                   Decryption:
          C[n] = E(P[n])                P[n] = D(C[n])


  Cipher Block Chaining (CBC):

          P[n] and C[n] are each 64-bits long.

          Encryption:                   Decryption:
          C[0] = E(P[0]^IV)             P[0] = D(C[0])^IV
  (n>0)   C[n] = E(P[n]^C[n-1])         P[n] = D(C[n])^C[n-1]


  Propagating Cipher Block Chaining (PCBC):

          P[n] and C[n] are each 64-bits long.

          Encryption:                   Decryption:
          C[0] = E(P[0]^IV)             P[0] = D(C[0])^IV
  (n>0)   C[n] = E(P[n]^P[n-1]^C[n-1])  P[n] = D(C[n])^P[n-1]^C[n-1]


  k-bit Cipher FeedBack (CFB):

          P[n] and C[n] are each k bits long, 1 <= k <= 64.

          Encryption:                   Decryption:
          I[0] = IV                     I[0] = IV
  (n>0)   I[n] = I[n-1]<<k | C[n-1]     I[n] = I[n-1]<<k | C[n-1]      
  (all n) R[n] = MSB(E(I[n]),k)         R[n] = MSB(E(I[n]),k)
  (all n) C[n] = P[n]^R[n]              P[n] = C[n]^R[n]

          Note that for k==64, this reduces to:

          I[0] = IV                     I[0] = IV
  (n>0)   I[n] = C[n-1]                 I[n] = C[n-1]   
  (all n) R[n] = E(I[n])                R[n] = E(I[n])
  (all n) C[n] = P[n]^R[n]              P[n] = C[n]^R[n]

  CFB notes: Since I[n] depends only on the plain or cipher text from the
  previous operation, the E() function can be performed in parallel with
  the reception of the text with which it is used.


  k-bit Output FeedBack (OFB):

          P[n] and C[n] are each k bits long, 1 <= k <= 64.

          Encryption:                   Decryption:
          I[0] = IV                     I[0] = IV
  (n>0)   I[n] = I[n-1]<<k | R[n-1]     I[n] = I[n-1]<<k | R[n-1]      
  (all n) R[n] = MSB(E(I[n]),k)         R[n] = MSB(E(I[n]),k)
  (all n) C[n] = P[n]^R[n]              P[n] = C[n]^R[n]

          Note that for k==64, this reduces to:

          I[0] = IV                     I[0] = IV
  (n>0)   I[n] = R[n-1]                 I[n] = R[n-1]   
  (all n) R[n] = E(I[n])                R[n] = E(I[n])
  (all n) C[n] = P[n]^R[n]              P[n] = C[n]^R[n]

  OFB notes: encryption and decryption are identical. Since I[n] is
  independent of P and C, the E() function can be performed in advance of
  the receipt of the plain/cipher text with which it is to be used.


  Additional notes on DES ``modes of operation'':

  ECB and CBC use E() to encrypt and D() to decrypt, but the feedback
  modes use E() to both encrypt and decrypt. This disproves the following
  erroneous claim: ``DES implementations which provide E() but not D()
  cannot be used for data confidentiality.''