麻省理工密码学讲义：深入浅出的加密知识宝典

3星 · 超过75%的资源需积分: 0 167 浏览量更新于2024-07-27 2 收藏 1.61MB PDF 举报

"麻省理工密码学讲义是麻省理工大学提供的密码学教学材料，内容丰富，讲解深入浅出，适合学习者参考。该讲义可能涵盖了密码学的基础理论、加密算法、安全协议等方面，旨在帮助读者理解密码学在信息安全中的重要作用。讲义可能来自于数缘社区，一个由山东大学数学院研究生创办的高等数学和密码学技术论坛。社区提供了丰富的数学电子书和密码学论文资源，包括欧密会、美密会、亚密会等国际知名会议的论文。此外，社区还设有专门的讨论区，如数学综合讨论区和密码学与网络安全版块，供会员交流学习。社区还提供了一个网络公式编辑器，方便用户使用LaTeX语言编辑公式。" 这篇摘要提到了几个关键知识点： 1. 密码学基础：麻省理工的密码学讲义可能会包含密码学的基本概念，如对称加密、非对称加密、哈希函数、数字签名、公钥基础设施(PKI)等，这些都是构建安全通信的基础。 2. 加密算法：可能涉及DES、AES、RSA、ECC等经典和现代加密算法的原理和应用，这些算法在实际的网络安全中广泛使用。 3. 安全协议：可能讲解SSL/TLS协议、IPSec、PGP等用于保护网络通信的安全协议，这些协议确保了数据在传输过程中的机密性和完整性。 4. 数缘社区：这是一个数学和密码学的学习平台，提供电子书和论文库，为学习者提供了丰富的资料来源。用户可以在社区内交流讨论，寻求帮助。 5. 密码学论文库：包含了欧密会、美密会、亚密会等顶级密码学会议的论文，反映了最新的研究进展和技术动态，对于深入研究密码学的学者非常有价值。 6. 数学与信息安全：强调了数学在信息安全领域的重要性，特别是对于理解和设计密码系统来说，高等数学如代数、数论和概率论等都是必不可少的基础。 7. 网络公式编辑器：使用LaTeX语言编辑的公式工具，使得在论坛上分享复杂的数学公式变得便捷，有利于学术交流。这些知识点构成了一个全面的密码学学习框架，不仅包括理论知识，还有实践应用和学术研究的资源支持。通过学习这样的讲义，读者可以深入理解密码学原理，并了解其在网络安全中的实际应用。

Cryptography: Lecture Notes 15

4. The above properties should hold with high probability.

In short, it would be desirable for the encryption scheme to be the mathematical analogy of opaque envelopes

containing a piece of paper on which the message is written. The envelopes should be such that all legal

senders can ﬁll it, but only the legal recipient can open it.

We must answer a few questions:

• How can “opaque envelopes” be captured in a precise mathematical deﬁnition? Much of Chapters 6

and 7 is dedicated to discussing the precise deﬁnition of security in presence of a computationally

bounded adversary.

• Are “opaque envelopes” achievable mathematically? The answer is positive . We will describe the the

proposals of private (and public) encryption schemes which we prove secure under various assumptions.

We note that the simple example of a public-key encryptions system based on trapdoor function, described

in the previous section, does not satisfy the above properties. We will show later, however, probabilistic

variants of the simple system which do satisfy the new security requirements under the assumption that

trapdoor functions exist. More speciﬁcally, we will show probabilistic variants of RSA which satisfy the new

security requirement under, the assumption that the original RSA function is a trapdoor function, and are

similar in eﬃciency to the original RSA public-key encryption proposal.

1.5 The Model of Adversary

The entire discussion so far has essentially assumed that the adversary can listen to cyphertexts being

exchanged over the insecure channel, read the public-ﬁle (in the case of public-key cryptography), generate

encryptions of any message on his own (for the case of public-key encryption), and perform probabilistic

polynomial time computation. This is called a passive adversary.

One may imagine a more powerful adversary who can intercept messages being transmitted from sender

to receiver and either stop their delivery all together or alter them in some way. Even worse, suppose the

adversary can request a polynomial number of cyphertexts to be decrypted for him. We can still ask whether

there exists encryption schemes (public or secret) which are secure against such more powerful adversaries.

Indeed, such adversaries have been considered and encryption schemes which are secure against them de-

signed. The deﬁnition of security against such adversaries is more elaborate than for passive adversaries.

In Chapters 6 and 7 we consider a passive adversary who knows the probability distribution over the message

space. We will also discuss more powerful adversaries and appropriate deﬁnitions of security.

1.6 Road map to Encryption

To summarize the introduction, our challenge is to design both secure private-key and public-key encryption

systems which provably meet our deﬁnition of security and in which the operations of encryption and

decryption are as fast as possible for the sender and receiver.

Chapters 6 and 7 embark on an in depth investigation of the topic of encryption, consisting of the following

parts. For both private-key and public-key encryption, we will:

• Discuss formally how to deﬁne security in presence of a bounded adversary.

• Discuss current proposals of encryption systems and evaluate them respect to the security deﬁnition

chosen.

• Describe how to design encryption systems which we can prove secure under explicit assumptions such

as the existence of one-way functions, trapdoor functions, or pseudo random functions.

C h a p t e r 2

One-way and trapdoor functions

One Way functions, namely functions that are “easy” to compute and “hard” to invert, are an extremely

important cryptographic primitive. Probably the best known and simplest use of one-way functions, is for

passwords. Namely, in a time-shared computer system, instead of storing a table of login passwords, one can

store, for each password w, the value f (w). Passwords can easily be checked for correctness at login, but

even the system administrator can not deduce any user’s password by examining the stored table.

In Section 1.3 we had provided a short list of some candidate one-way functions. We now develop a theoretical

treatment of the subject of one-way and trapdoor functions, and carefully examine the candidate one-way

functions proposed in the literature. We will occasionaly refer to facts about number theory discussed in

Chapter C.

We begin by explaining why one-way functions are of fundamental importance to cryptography.

2.1 One-Way Functions: Motivation

In this section, we provide motivation to the deﬁnition of one-way functions. We argue that the existence of

one-way functions is a necessary condition to the existence of most known cryptographic primitives (including

secure encryption and digital signatures). As the current state of knowledge in complexity theory does not

allow to prove the existence of one-way function, even using more traditional assumptions as P 6= NP,

we will have to assume the existence of one-way functions. We will later try to provide evidence to the

plausibility of this assumption.

As stated in the introduction chapter, modern cryptography is based on a gap between eﬃcient algorithms

guaranteed for the legitimate user versus the unfeasibility of retrieving protected information for an adversary.

To make the following discussion more clear, let us concentrate on the cryptographic task of secure data

communication, namely encryption schemes.

In secure encryption schemes, the legitimate user is able to decipher the messages (using some private infor-

mation available to him), yet for an adversary (not having this private information) the task of decrypting

the ciphertext (i.e., “breaking” the encryption) should be infeasible. Clearly, the breaking task can be per-

formed by a non-deterministic polynomial-time machine. Yet, the security requirement states that breaking

should not be feasible, namely could not be performed by a probabilistic polynomial-time machine. Hence,

the existence of secure encryption schemes implies that there are tasks performed by non-deterministic

polynomial-time machines yet cannot be performed by deterministic (or even randomized) polynomial-time

machines. In other words, a necessary condition for the existence of secure encryption schemes is that NP

is not contained in BPP (and hence that P 6= NP).

18 Goldwasser and Bellare

However, the above mentioned necessary condition (e.g., P 6= NP) is not a suﬃcient one. P 6= NP only

implies that the encryption scheme is hard to break in the worst case. It does not rule-out the possibility

that the encryption scheme is easy to break in almost all cases. In fact, one can easily construct “encryption

schemes” for which the breaking problem is NP-complete and yet there exist an eﬃcient breaking algorithm

that succeeds on 99% of the cases. Hence, worst-case hardness is a poor measure of security. Security requires

hardness on most cases or at least average-case hardness. Hence, a necessary condition for the existence of

secure encryption schemes is the existence of languages in NP which are hard on the average. Furthermore,

P 6= NP is not known to imply the existence of languages in NP which are hard on the average.

The mere existence of problems (in NP) which are hard on the average does not suﬃce. In order to be able to

use such problems we must be able to generate such hard instances together with auxiliary information which

enable to solve these instances fast. Otherwise, the hard instances will be hard also for the legitimate users

and they gain no computational advantage over the adversary. Hence, the existence of secure encryption

schemes implies the existence of an eﬃcient way (i.e. probabilistic polynomial-time algorithm) of generating

instances with corresponding auxiliary input so that

(1) it is easy to solve these instances given the auxiliary input; and

(2) it is hard on the average to solve these instances (when not given the auxiliary input).

We avoid formulating the above “deﬁnition”. We only remark that the coin tosses used in order to generate

the instance provide suﬃcient information to allow to eﬃciently solve the instance (as in item (1) above).

Hence, without loss of generality one can replace condition (2) by requiring that these coin tosses are hard to

retrieve from the instance. The last simpliﬁcation of the above conditions essentially leads to the deﬁnition

of a one-way function.

2.2 One-Way Functions: Deﬁnitions

In this section, we present several deﬁnitions of one-way functions. The ﬁrst version, hereafter referred to

as strong one-way function (or just one-way function), is the most convenient one. We also present weak

one-way functions which may be easier to ﬁnd and yet can be used to construct strong one way functios,

and non-uniform one-way functions.

2.2.1 (Strong) One Way Functions

The most basic primitive for cryptographic applications is a one-way function. Informally, this is a function

which is “easy” to compute but “hard” to invert. Namely, any probabilistic polynomial time (PPT) algo-

rithm attempting to invert the one-way function on a element in its range, will succeed with no more than

“negligible” probability, where the probability is taken over the elements in the domain of the function and

the coin tosses of the PPT attempting the inversion.

This informal deﬁnition introduces a couple of measures that are prevalent in complexity theoretic cryptog-

raphy. An easy computation is one which can be carried out by a PPT algorithm; and a function ν: N → R

is negligible if it vanishes faster than the inverse of any polynomial. More formally,

Deﬁnition 2.1 ν is negligible if for every constant c ≥ 0 there exists an integer k

such that ν(k) < k

−c

for

all k ≥ k

Another way to think of it is ν(k) = k

−ω(1)

A few words, concerning the notion of negligible probability, are in place. The above deﬁnition and discussion

considers the success probability of an algorithm to be negligible if as a function of the input length the suc-

cess probability is bounded by any polynomial fraction. It follows that repeating the algorithm polynomially

(in the input length) many times yields a new algorithm that also has a negligible success probability. In

other words, events which occur with negligible (in n) probability remain negligible even if the experiment

Cryptography: Lecture Notes 19

is repeated for polynomially (in k) many times. Hence, deﬁning negligible success as “occurring with proba-

bility smaller than any polynomial fraction” is naturally coupled with deﬁning feasible as “computed within

polynomial time”. A “strong negation” of the notion of a negligible fraction/probability is the notion of a

non-negligible fraction/probability. we say that a function ν is non-negligible if there exists a polynomial p

such that for all suﬃciently large k’s it holds that ν(k) >

p(k)

. Note that functions may be neither negligible

nor non-negligible.

Deﬁnition 2.2 A function f: {0, 1}

∗

→ {0, 1}

∗

is one-way if:

(1) there exists a PPT that on input x output f(x);

(2) For every PPT algorithm A there is a negligible function ν

such that for suﬃciently large k,

f(z) = y : x

← {0, 1}

; y ← f (x) ; z ← A(1

, y)

≤ ν

(k)

Remark 2.3 The guarantee is probabilistic. The adversary is not unable to invert the function, but has

a low probability of doing so where the probability distribution is taken over the input x to the one-way

function where x if of length k, and the possible coin tosses of the adversary. Namely, x is chosen at random

and y is set to f(x).

Remark 2.4 The advsersary is not asked to ﬁnd x; that would be pretty near impossible. It is asked to

ﬁnd some inverse of y. Naturally, if the function is 1-1 then the only inverse is x.

Remark 2.5 Note that the adversary algorithm takes as input f(x) and the security parameter 1

(expressed

in unary notatin) which corresponds to the binary length of x. This represents the fact the adversary can

work in time polynomial in |x|, even if f(x) happends to be much shorter. This rules out the possibility that

a function is considered one-way merely because the inverting algorithm does not have enough time to print

the output. Consider for example the function deﬁned as f(x) = y where y is the log k least signiﬁcant bits

of x where |x| = k. Since the |f (x)| = log |x| no algorithm can invert f in time polynomial in |f(x)|, yet

there exists an obvious algorithm which ﬁnds an inverse of f(x) in time polynomial in |x|. Note that in the

special case of length preserving functions f (i.e., |f(x)| = |x| for all x’s), the auxiliary input is redundant.

Remark 2.6 By this deﬁnition it trivially follows that the size of the output of f is bounded by a polynomial

in k, since f (x) is a poly-time computable.

Remark 2.7 The deﬁnition which is typical to deﬁnitions from computational complexity theory, works

with asymptotic complexity—what happens as the size of the problem becomes large. Security is only asked

to hold for large enough input lengths, namely as k goes to inﬁnity. Per this deﬁnition, it may be entirely

feasible to invert f on, say, 512 bit inputs. Thus such deﬁnitions are less directly relevant to practice, but

useful for studying things on a basic level. To apply this deﬁnition to practice in cryptography we must

typically envisage not a single one-way function but a family of them, parameterized by a security parameter

k. That is, for each value of the security parameter k there is be a speciﬁc function f : {0, 1}

→ {0, 1}

∗

Or, there may be a family of functions (or cryptosystems) for each value of k. We shall deﬁne such familes

in subsequent section.

The next two sections discuss variants of the strong one-way function deﬁnition. The ﬁrst time reader is

encouraged to directly go to Section 2.2.4.

剩余283页未读，继续阅读

tb_418

粉丝: 0
资源: 4

麻省理工密码学讲义：深入浅出的加密知识宝典

麻省理工学院密码学讲义

Lecture Notes on Cryptography麻省理工学院密码学讲义

Lecture Notes on Cryptography (麻省理工学院密码学讲义)

密码学讲义Lecture Notes on Cryptography

密码学讲义：Goldwasser 2008年

密码学讲义：Shafi Goldwasser & Mihir Bellare

MIT夏季课程：密码学讲义全英版

现代密码学基础与应用探索

现代密码学：理论与应用概览

现代密码学理论与实践概述：关键资源推荐

最新资源