lanxicy.com

兰溪范文 文档专家

兰溪范文 文档专家

Substitution Cryptography

李 剑

北京邮电大学信息安全中心 E-mail: securitydoctor@163.com

010－86212346

1

Substitution Cryptography

?

?

In cryptography, a substitution cipher is a method of encryption by which units of plaintext are substituted with ciphertext according to a regular system; the "units" may be single letters (the most common), pairs of letters, triplets of letters, mixtures of the above, and so forth. The receiver deciphers the text by performing an inverse substitution.

2

Substitution Cryptography

?

?

Substitution ciphers can be compared with transposition ciphers. In a transposition cipher, units of the plaintext are rearranged in a different and usually quite complex order, but the units themselves are left unchanged. By contrast, in a substitution cipher, the units of the plaintext are retained in the same sequence in the ciphertext, but the units themselves are altered.

3

2.2.1 Simple Substitution

?

Substitution over a single letter—simple substitution—can be demonstrated by writing out the alphabet in some order to represent the substitution. This is termed a substitution alphabet.

4

2.2.1 Simple Substitution

? ?

?

? ? ?

(1) Examples Using this system, the keyword "zebras" gives us the following alphabets: Plaintext alphabet:abcdefghijklmnopqrstuvwxyzCiphertext alphabet:ZEBRASCDFGHIJKLMNOPQTUVWXYA message of flee at once. we are discovered! enciphers to SIAA ZQ LKBA. VA ZOA RFPBLUAOAR!

5

2.2.1 Simple Substitution

?

?

?

(2) Security for simple substitution ciphers A disadvantage of this method of derangement is that the last letters of the alphabet (which are mostly low frequency) tend to stay at the end. A stronger way of constructing a mixed alphabet is to perform a columnar transposition on the ordinary alphabet using the keyword, but this is not often done. (讲到这里＠＠3月13日)

6

2.2.2 Homophonic Substitution

?

An early attempt to increase the difficulty of frequency analysis attacks on substitution ciphers was to disguise plaintext letter frequencies by homophony. In these ciphers, plaintext letters map to more than one ciphertext symbol. Usually, the highest-frequency plaintext symbols are given more equivalents than lower frequency letters. In this way, the frequency distribution is flattened, making analysis more difficult. 如：密码，米马，迷吗，秘妈，觅麻，眯玛，蜜蚂….

?

?

7

2.2.3 Polyalphabetic Substitution

?

?

In a polyalphabetic cipher, multiple cipher alphabets are used. To facilitate encryption, all the alphabets are usually written out in a large table, traditionally called a tableau. （场景） The tableau is usually 26×26, so that 26 full ciphertext alphabets are available. The method of filling the tableau, and of choosing which alphabet to use next, defines the particular polyalphabetic cipher. All such ciphers are easier to break than once believed, as substitution alphabets are repeated for sufficiently large plaintexts.

8

2.2.4 Polygraphic Substitution

?

?

?

In a polygraphic substitution cipher, plaintext letters are substituted for in larger groups (typically pairs, making a digraphic cipher), instead of substituting letters individually. The advantage of this is first that the frequency distribution of digraphs is much flatter than that of individual letters (though not actually flat in real languages; for example, 'TH' is much more common than 'XQ' in English). Second, the larger number of symbols requires correspondingly more ciphertext to productively analyze letter frequencies.

9

2.2.5 Mechanical Substitution Ciphers

?

?

Between circa World War I and the widespread availability of computers (for some governments this was approximately the 1950s or 1960s; for other organizations it was a decade or more later; for individuals it was no earlier than 1975), mechanical implementations of polyalphabetic substitution ciphers were widely used. Several inventors had similar ideas about the same time, and rotor cipher machines were patented four times in 1919. The most important of the resulting machines was the Enigma, especially in the versions used by the German military from approximately 1930. The Allies also developed and used rotor machines (eg, SIGABA and Typex).

10

2.2.6 The One-time Pad

?

?

?

One type of substitution cipher, the one-time pad, is quite special. It was invented near the end of WW I by Gilbert Vernam and Joseph Mauborgne in the US. It was mathematically proved unbreakable by Claude Shannon, probably during WW II; his work was first published in the late 1940s. In its most common implementation, the one-time pad can be called a substitution cipher only from an unusual perspective; typically, the plaintext letter is combined (not substituted) in some manner (eg, XOR) with the key material character at that position.

11

2.2.7 Substitution in Modern Cryptography

?

?

Substitution ciphers as discussed above, especially the older pencil-and-paper hand ciphers, are no longer in serious use. However, the cryptographic concept of substitution carries on even today. From a sufficiently abstract perspective, modern bitoriented block ciphers (eg, DES, or AES) can be viewed as substitution ciphers on an enormously large binary alphabet. In addition, block ciphers often include smaller substitution tables called S-boxes. See also substitutionpermutation network.

12

Thanks For Attendance!

返回

13

更多相关标签: