数学密码学基础：公钥加密原理与数学

5星 · 超过95%的资源需积分: 50 141 浏览量更新于2024-07-30 5 收藏 7.38MB PDF 举报

"An introduction to mathematical cryptography" 《数学密码学导论》是一本专注于公共密钥密码学的书籍，旨在向读者介绍加密领域的基础知识，特别是针对本科数学或计算机科学学生。书中的内容组织有序，自成一体，无需高级数学背景即可理解。作者Hoffstein、Pipher和Silverman通过丰富的例子和每章末尾的练习题，使得理论易于消化。这本书被推荐用于本科高年级或研究生课程，也适合自学。书中涵盖了经典密码学构造，如Diffie-Hellman密钥交换、基于离散对数的密码系统、RSA公钥加密系统以及数字签名。此外，它还介绍了构建和分析各种密码系统所需的数学工具，包括素性测试、因数分解算法、概率论、信息论和碰撞算法等。特别地，它深入探讨了椭圆曲线密码学、配对密码学、格密码学和NTRU密码系统等近年来的重要创新。对于希望了解数学在公共密钥密码学中应用的读者，这本书提供了完整的自学习材料。它只需要读者具备基本的线性代数知识，然后逐步引入和解释所需的各种数学概念。这使得即使是刚开始接触严谨数学证明的学生也能理解和跟随。书评家普遍认为，《数学密码学导论》是一本理想的教学用书，适合用于独立研究课程，或作为研究生课程的教材，特别是专注于公共密钥密码学的课程。无论是在数学还是计算机科学领域，这本书都为学习者提供了一个深入理解现代密码学理论的坚实基础。

Chapter 1

An Introduction to

Cryptography

1.1 Simple substitution ciphers

As Julius Caesar surveys the unfolding battle from his hilltop outpost, an

exhausted and disheveled courier bursts into his presence and hands him a

sheet of parchment containing gibberish:

jsjrdkfqqnslgfhpgwjfpymwtzlmnrrnsjsyqzhnzx

Within moments, Julius sends an order for a reserve unit of charioteers to

speed around the left ﬂank and exploit a momentary gap in the opponent’s

formation.

How did this string of seemingly random letters convey such important

information? The trick is easy, once it is explained. Simply take each letter in

the message and shift it ﬁve letters up the alphabet. Thus j in the ciphertext

becomes e in the plaintext,

because e is followed in the alphabet by f,g,h,i,j.

Applying this procedure to the entire ciphertext yields

jsjrdkfqqnslgfhpgwjfpymwtzlmnrrnsjsyqzhnzx

enemyfallingbackbreakthroughimminentlucius

The second line is the decrypted plaintext, and breaking it into words and

supplying the appropriate punctuation, Julius reads the message

Enemy falling back. Breakthrough imminent. Lucius.

There remains one minor quirk that must be addressed. What happens when

Julius ﬁnds a letter such as d? There is no letter appearing ﬁve letters before d

The plaintext is the original message in readable form and the ciphertext is the en-

crypted message.

J. Hoﬀstein et al., An Introduction to Mathematical Cryptography,

DOI: 10.1007/978-0-387-77994-2 1,

 Springer Science+Business Media, LLC 2008

2 1. An Introduction to Cryptography

in the alphabet. The answer is that he must wrap around to the end of the

alphabet. Thus d is replaced by y, since y is followed by z,a,b,c,d.

This wrap-around eﬀect may be conveniently visualized by placing the al-

phabet abcd...xyz around a circle, rather than in a line. If a second alphabet

circle is then placed within the ﬁrst circle and the inner circle is rotated ﬁve

letters, as illustrated in Figure 1.1, the resulting arrangement can be used

to easily encrypt and decrypt Caesar’s messages. To decrypt a letter, simply

ﬁnd it on the inner wheel and read the corresponding plaintext letter from

the outer wheel. To encrypt, reverse this process: ﬁnd the plaintext letter on

the outer wheel and read oﬀ the ciphertext letter from the inner wheel. And

note that if you build a cipherwheel whose inner wheel spins, then you are no

longer restricted to always shifting by exactly ﬁve letters. Cipher wheels of

this sort have been used for centuries.

Although the details of the preceding scene are entirely ﬁctional, and in

any case it is unlikely that a message to a Roman general would have been

written in modern English(!), there is evidence that Caesar employed this

early method of cryptography, which is sometimes called the Caesar cipher

in his honor. It is also sometimes referred to as a shift cipher, since each

letter in the alphabet is shifted up or down. Cryptography, the methodology of

concealing the content of messages, comes from the Greek root words kryptos,

meaning hidden,

and graphikos, meaning writing. The modern scientiﬁc study

of cryptography is sometimes referred to as cryptology.

In the Caesar cipher, each letter is replaced by one speciﬁc substitute

letter. However, if Bob encrypts a message for Alice

using a Caesar cipher

and allows the encrypted message to fall into Eve’s hands, it will take Eve

very little time to decrypt it. All she needs to do is try each of the 26 possible

shifts.

Bob can make his message harder to attack by using a more complicated

replacement scheme. For example, he could replace every occurrence of a

by z and every occurrence of z by a, every occurrence of b by y and every

occurrence of y by b, and so on, exchanging each pair of letters c ↔ x,...,

m ↔ n.

This is an example of a simple substitution cipher, that is, a cipher in which

each letter is replaced by another letter (or some other type of symbol). The

Caesar cipher is an example of a simple substitution cipher, but there are

many simple substitution ciphers other than the Caesar cipher. In fact, a

A cipher wheel with mixed up alphabets and with encryption performed using diﬀerent

oﬀsets for diﬀerent parts of the message is featured in a 15

century monograph by Leon

Batista Alberti [58].

The word cryptic, meaning hidden or occult, appears in 1638, while crypto- as a preﬁx

for concealed or secret makes its appearance in 1760. The term cryptogram appears much

later, ﬁrst occurring in 1880.

In cryptography, it is traditional for Bob and Alice to exchange conﬁdential messages

and for their adversary Eve, the eavesdropper, to intercept and attempt to read their mes-

sages. This makes the ﬁeld of cryptography much more personal than other areas of math-

ematics and computer science, whose denizens are often X and Y !

1.1. Simple substitution ciphers 5

26 · 25 · 24 ···4 · 3 ·2 · 1 = 26! = 403291461126605635584000000.

There are thus more than 10

diﬀerent simple substitution ciphers. Each

associated encryption table is known as a key.

Suppose that Eve intercepts one of Bob’s messages and that she attempts

to decrypt it by trying every possible simple substitution cipher. The process

of decrypting a message without knowing the underlying key is called crypt-

analysis. If Eve (or her computer) is able to check one million cipher alphabets

per second, it would still take her more than 10

years to try them all.

But

the age of the universe is estimated to be on the order of 10

years. Thus Eve

has almost no chance of decrypting Bob’s message, which means that Bob’s

message is secure and he has nothing to worry about!

Or does he?

It is time for an important lesson in the practical side of the science of

cryptography:

Your opponent always uses her best strategy to defeat you,

not the strategy that you want her to use. Thus the secu-

rity of an encryption system depends on the best known

method to break it. As new and improved methods are

developed, the level of security can only get worse, never

better.

Despite the large number of possible simple substitution ciphers, they are

actually quite easy to break, and indeed many newspapers and magazines

feature them as a companion to the daily crossword puzzle. The reason that

Eve can easily cryptanalyze a simple substitution cipher is that the letters

in the English language (or any other human language) are not random. To

take an extreme example, the letter q in English is virtually always followed

by the letter u. More useful is the fact that certain letters such as e and t

appear far more frequently than other letters such as f and c. Table 1.3 lists

the letters with their typical frequencies in English text. As you can see, the

most frequent letter is e, followed by t, a, o,andn.

Thus if Eve counts the letters in Bob’s encrypted message and makes a

frequency table, it is likely that the most frequent letter will represent e,and

that t, a, o,andn will appear among the next most frequent letters. In this

way, Eve can try various possibilities and, after a certain amount of trial and

error, decrypt Bob’s message.

In the remainder of this section we illustrate how to cryptanalyze a simple

substitution cipher by decrypting the message given in Table 1.4. Of course the

end result of defeating a simple substitution cipher is not our main goal here.

Our key point is to introduce the idea of statistical analysis, which will prove to

Do you see how we got 10

years? There are 60 · 60 · 24 · 365 seconds in a year, and 26!

divided by 10

· 60 · 60 · 24 · 365 is approximately 10

13.107

The assertion that a large number of possible keys, in and of itself, makes a cryptosys-

tem secure, has appeared many times in history and has equally often been shown to be

fallacious.

剩余532页未读，继续阅读

ysoh2

粉丝: 0

数学密码学基础：公钥加密原理与数学

数学密码学基础：探索RSA与椭圆曲线加密

数学密码学基础概览

探索数学加密与Python编程实践——AITMCLab

An Introduction to Cryptography 2nd Edition

An Introduction to Cryptography - 2nd Edition - 2007

Cryptography An Introduction2nd

An Introduction to Mathematica.rar

The Princeton Companion to Mathematics

Truth Tables and Boolean Algebra: Mathematical Bridges of Logical Operations (In-depth Analysis)

AI从头到脚详解如何创建部署Azure Web App的OpenAI项目源码

最新资源