信息安全协议：保障在线礼物交换的加密技术

需积分: 49 160 浏览量更新于2024-07-18 收藏 936KB PDF 举报

密码学协议是信息安全领域的重要组成部分，它在保障通信安全和隐私保护中扮演着关键角色。这些协议主要包括密钥交换、承诺协议和认证协议等核心概念。在本资料中，LectureNotes《CryptographicProtocols》（第1.32版，发布于2018年2月6日）由Berry Schoenmakers教授编写，旨在介绍在春季学期进行教学时使用的加密技术方法论，特别是针对那些对密码学原理感兴趣的学生。密钥交换协议是协议设计的基础，它确保参与通信的双方可以安全地协商并生成共享密钥，以便后续的信息加密和解密过程。例如，Diffie-Hellman密钥交换算法允许两个不信任网络的人通过公开通信来建立私密的密钥，这是现代网络安全中的基石。承诺协议用于确保一方在某种条件满足之前不会泄露某些信息。这在拍卖、选举和其他需要保密决策的情境中尤为有用。比如，可信赖承诺协议如Blind Signatures（盲签名）允许用户向银行请求签名而不暴露他们的交易细节，增强了用户隐私。认证协议则是验证通信各方身份的过程，以防止假冒和欺诈。数字签名和公钥基础设施（Public Key Infrastructure, PKI）是常见的认证机制，它们利用非对称加密技术来确认消息的真实性和发送者的身份。例如，SSL/TLS协议就是网络通信中常用的认证协议，确保数据传输的安全性。回到前述的“Sinterklaaslootjestrekken”或“Secret Santa”活动，其在线组织面临的一个关键问题是确保参与者信息的安全性，尤其是隐私和公平性。在不依赖第三方网站或服务的情况下，通过实施加密协议，比如使用安全的随机数生成器，以及可能的匿名或混淆策略，可以确保礼物分配的公正且个人信息得到保护。零知识证明是密码学协议中的一个高级概念，它允许一个人（称为证明者）向另一个接收者（称为验证者）展示他们知道某个信息，而无需透露实际的信息内容。这对于保护个人隐私和实现远程身份验证至关重要，尤其是在诸如区块链技术中的匿名交易和电子投票等领域。《CryptographicProtocols》是一份详尽的教程，涵盖了密码学协议的基础理论和实际应用，对于理解如何在现实世界中保护数据安全，维护通信的可信度，以及解决日常问题中的信息安全挑战具有重要意义。通过深入学习和实践这些协议，人们能够更好地应对数字化社会中的各种安全挑战。

1.3 Assumptions 9

1.3.3 RANDOM SELF-REDUCIBILITY

The following notion of random self-reducible problems is suﬃciently general for our purposes.

Recall that one commonly refers to the input of a problem and a corresponding output as a

(problem) instance and its solution.

DEFINITION 1.27 A problem is called (perfectly) random self-reducible if any in-

stance I of the problem can be solved by these three steps:

1. Transform instance I into a uniformly random instance I

2. Solve instance I

3. Extract the solution for I from the solution for I

Only steps 1 and 3 are required to run in polynomial time.

For cryptographic purposes, it is a good sign if a presumably hard problem is random self-

reducible. In that case, it is excluded that even though the problem is hard in the worst-case,

the problem is actually easy on the average. To see why, consider a random self-reducible

problem and suppose that the problem is easy on the average. Then there cannot be any hard

instances at all, since any such instance can be solved by solving a transformed, uniformly

random instance due to random self-reducibility.

PROPOSITION 1.28 Any random self-reducible problem that is hard in the worst-case is

also hard on the average.

It is reassuring that the standard discrete log and Diﬃe-Hellman problems are all random

self-reducible, where these problems are formulated as follows, for any group hgi of order n:

DL problem: compute x, given g

with x ∈ Z

DH problem: compute g

, given g

, g

with x, y ∈ Z

DDH problem: distinguish g

from g

, given g

, g

with x, y, z ∈ Z

, z −xy ∈ Z

∗

Note that for n prime the DDH problem corresponds to distinguishing the (disjoint) distri-

butions X

hgi

= {(g

, g

) : x, y ∈

} and Y

hgi

= {(g

, g

) : x, y, z ∈

, z 6= xy}, as

explained in Section 1.3.2.

The above problem formulations allow for arbitrary—potentially, worst-case—problem

instances. In cryptography, however, we generally need to allow for random problem instances,

cf. the hardness assumptions in Deﬁnitions 1.19–1.21. The following proposition implies that

these assumptions are not stronger than their worst-case cousins.

PROPOSITION 1.29 The DL, DH, and DDH problems are random self-reducible.

PROOF For the DL problem, any given instance h = g

with x ∈ Z

is solved as follows:

1. Transform h into a uniformly random instance h

= hg

with u ∈

2. Solve instance h

yielding x

= log

3. Extract the solution as x = log

h = x

− u mod n.

Clearly, h

is distributed uniformly on hgi.

For the DH problem, any given instance I = (g

, g

) with x, y ∈ Z

is solved as follows:

10 CHAPTER 1 Introduction

1. Transform I into a uniformly random I

= (g

, g

) = (g

, g

) with t, u ∈

2. Solve instance I

yielding g

= g

(x+t)(y+u)

= g

xy+xu+ty+tu

3. Extract the solution as g

= g

/((g

)

Note that indeed the pair (g

, g

) is distributed uniformly on hgi× hgi.

For the DDH problem, random self-reducibility amounts to transforming each triple given

as input to the Boolean distinguisher into a uniformly-random triple of the “same type.”

Given any instance I = (g

, g

), we do so as follows:

1. Transform I into I

= ((g

)

, g

, (g

)

) with s ∈

∗

and t, u ∈

2. Solve instance I

yielding bit b

3. Output b = b

First, note that s ∈

∗

can be generated in polynomial time by testing on average n/φ(n) =

O(log log n) uniformly random values s ∈ Z

until gcd(s, n) = 1; see also Section 1.2.1.

Next, let I

= (g

, g

). Then instances I and I

are of the same type as

− x

= zs + xsu + yt + tu −(xs + t)(y + u) = (z − xy)s,

hence z = xy if and only if z

= x

, using that s ∈ Z

∗

Furthermore, if z = xy, triple I

is uniform among all DH triples (g

, g

), indepen-

dent of I. That is, for any values v, w ∈ Z

Pr[x

= v, y

= w, z

= vw] =

Similarly, if z −xy ∈ Z

∗

, then s, t, u are determined uniquely by s = (z

−x

)/(z −xy),

t = x

−xs, and u = y

−y, implying that I

is uniform among all non-DH triples (g

, g

)

with z

− x

∈ Z

∗

, independent of I as well. That is,

Pr[x

= v, y

= w, z

= r] = Pr[s =

r − vw

z − xy

, t = v − xs, u = w − y] =

φ(n)n

for any values r, v, w ∈ Z

with r − vw ∈ Z

∗

. 

We will often use the following variants of the discrete log and Diﬃe-Hellman problems:

∗

problem: compute x, given g

with x ∈ Z

∗

problem: compute g

, given g

, g

with x ∈ Z

∗

and y ∈ Z

∗∗

problem: compute g

, given g

, g

with x, y ∈ Z

∗

DDH

∗

problem: distinguish g

from g

, given g

, g

with x ∈ Z

∗

, y, z ∈ Z

, z −xy ∈ Z

∗

DDH

∗∗

problem: distinguish g

from g

, given g

, g

with x, y, z ∈ Z

∗

, z −xy ∈ Z

∗

Since Z

∗

= Z

\{0} in the common case that the group order n is prime, the only diﬀerence

with the basic problems is that 1 ∈ hgi is not a valid input anymore in some cases. Using slig-

htly diﬀerent transformations, each of these variants can be seen to be random self-reducible

as well, except that for the DDH

∗∗

problem we need to assume that the prime factorization

of n is given.

1.3 Assumptions 11

EXAMPLE 1.30 It is easy to see that the DL

∗

problem is random self-reducible as follows.

Given any instance h = g

with x ∈ Z

∗

(hence, h ∈ hgi

∗

1. Transform h into a uniformly random instance h

= h

with u ∈

∗

2. Solve instance h

yielding x

= log

3. Extract the solution as x = log

h = x

/u mod n.

This time h

is distributed uniformly on hgi

∗

As an alternative approach, the transformation used for the DL problem in the proof

of Proposition 1.29 can also be used here. In this case, one tests in addition in step 1 if

ord(h

) = n to make sure h

is a valid input in step 2 satisfying h

∈ hgi

∗

, cf. Exercise 1.7.

However, to ensure that the test ord(h

) = n can be evaluated eﬃciently, we assume that we

know the prime factorization of n. Then, given any instance h = g

with x ∈ Z

∗

1. Transform h into a uniformly random instance h

= hg

with u ∈

until ord(h

) = n.

2. Solve instance h

yielding x

= log

3. Extract the solution as x = log

h = x

− u mod n.

In step 2, h

is distributed uniformly on hgi

∗

as required. To see that the (expected) running

time of step 1 is polynomial in the size of n, we note that on average n/φ(n) = O(log log n)

uniformly random h

∈ hgi are needed to ﬁnd one h

∈ hgi

∗

EXERCISE 1.31 Show that (a) the DH

∗

problem is random self-reducible, and (b) the DH

∗∗

problem is random self-reducible.

EXERCISE 1.32 Show that (a) the DDH

∗

problem is random self-reducible, and (b) given

the prime factorization of n, the DDH

∗∗

problem is random self-reducible. Hints: for both

parts use three random numbers for the transformation in step 1, s, t ∈

∗

and u ∈

;

for part (b), also test for invalid inputs, in the same way as at the end of Example 1.30.

EXERCISE 1.33 Show that the following problems are random self-reducible for any group

hgi of order n:

(a) given g

with x ∈ Z

, compute g

;

(b) given g

with x ∈ Z

∗

, compute g

1/x

;

, g

with x, y ∈ Z

∗

, compute g

x/y

;

(d) given g

, g

with x ∈ Z

, y ∈ Z

∗

, compute g

x/y

;

(e) given g

with x ∈ Z

∗

, compute g

;

(f) given g

, g

with x ∈ Z

, compute g

;

(g) given g

, g

with x, y ∈ Z

, compute g

(x+y)

;

(h) given g

, g

with x, y ∈ Z

, x − y ∈ Z

∗

, compute g

1/(x−y)

EXERCISE 1.34 Let m = pq be an RSA modulus, that is, p and q are large, distinct primes

of bit length k, for some integer k. Let integer e > 1 satisfy gcd(e, φ(m)) = 1, where

φ(m) = (p −1)(q −1). The RSA problem is to compute x = y

1/e

mod m given y ∈ Z

∗

. Show

that the RSA problem is random self-reducible.

12 CHAPTER 1 Introduction

EXERCISE 1.35 Let m be an RSA modulus, as in the previous exercise. Let J

= {y ∈ Z

∗

(y/m) = 1}, the set of all integers in Z

∗

with Jacobi symbol 1. The Quadratic Residuosity

(QR) problem is to decide whether a given y ∈ J

is a quadratic residue modulo m or not,

that is, whether y ∈ QR

, where QR

= {y ∈ Z

∗

: ∃

x∈Z

∗

y = x

mod m}. Show that the

QR problem is random self-reducible.

1.3.4 RANDOM ORACLE MODEL

DEFINITION 1.36 A function H : {0, 1}

∗

→ {0, 1}

, mapping bit strings of arbitrary length

to bit strings of a ﬁxed length k, k ≥ 0, is called a hash function. Function H is called a

cryptographic hash function, if it is easy to compute H(x) given any string x, and one or

more of the following requirements are satisﬁed:



preimage resistance (onewayness): given a k-bit string y, it is hard to ﬁnd a bit

string x such that H(x) = y.



2nd-preimage resistance (weak collision resistance): given a bit string x, it is

hard to ﬁnd a bit string x

6= x such that H(x

) = H(x).



collision resistance (strong collision resistance): it is hard to ﬁnd a pair of bit

strings (x, x

) with x 6= x

such that H(x) = H(x

In general, collision resistance implies 2nd-preimage resistance, but collision resistance need

not imply preimage resistance. In practice, however, cryptographic hash functions usually

satisfy all three requirements.

Practical examples of cryptographic hash functions are MD5, SHA-1, SHA-256, with

output lengths k = 128, k = 160, and k = 256, respectively.

If collision resistance is not

required, one may truncate the outputs by discarding, e.g., the last k/2 bits; the resulting

hash function is still preimage resistant.

Many protocols make use of a cryptographic hash function. In order to be able to prove

anything useful on the security of such protocols one commonly uses the so-called random

oracle model. In this model, a cryptographic hash function is viewed as a random oracle,

which when queried will behave as a black box containing a random function H : {0, 1}

∗

→

{0, 1}

, say. If the oracle is queried on an input value x, it will return the output value H(x).

As a consequence, if the oracle is queried multiple times on the same input, it will return

the same output value, as H is a function. Moreover, if one observes the distribution of the

output value for diﬀerent input values, the distribution will be uniform, as H is a random

function.

Note that the use of the random oracle model is a heuristic! If we prove a protocol secure

in the random oracle model, it does not follow that the same protocol using, e.g., SHA-256

as its hash function is secure, since SHA-256 is simply not a random function.

Thus, the practical upshot of the random oracle model is that a protocol proved secure

In August 2004, collisions for MD5 have (ﬁnally) been shown; furthermore, collisions for SHA-0 (a previous

version of SHA-1) have also been found. See this Mathematica notebook for some example collisions.

It is even possible to construct protocols that can be proved secure in the random oracle model, but are

insecure when used with some concrete hash function. Yet, these “counterexamples” are not realistic. See also

Exercise 5.22.

1.3 Assumptions 13

in it can only be broken if the attacker takes into account speciﬁc properties of the concrete

hash function used.

The following proposition conﬁrms that ﬁnding collisions is indeed easier than ﬁnding

(2nd-)preimages.

PROPOSITION 1.37 Let H be a cryptographic hash function, which we view as a random

oracle. Let E be an (unlimitedly powerful) adversary that makes at most t hash queries.

(i) Let y ∈ {0, 1}

be given. The probability that E ﬁnds a preimage x such that H(x) = y

is at most t/2

(ii) Let x ∈ {0, 1}

∗

be given. The probability that E ﬁnds a 2nd-preimage x

, x

6= x, such

that H(x

) = H(x) is at most t/2

(iii) The probability that E ﬁnds a collision (x, x

), x 6= x

, such that H(x) = H(x

) is at

most t

PROOF Without loss of generality, assume that all hash queries are distinct.

(i) For each hash query, the probability of an output equal to y is exactly 2

−k

(ii) Let y = H(x). For each hash query on inputs diﬀerent from x, the probability of an

output equal to y is again exactly 2

−k

(iii) Write N = 2

. If t ≥

√

N, then the bound is immediate. So assume t <

√

N. For hash

queries on inputs x

, . . . , x

, the probability of at least one collision is equal to

1 − N(N − 1)(N − 2) ···(N − t + 1)/N

This probability is bounded above by

1 − (1 − 1/N )(1 −2/N) ···(1 − (t −1)/N)

≤ 1 −e

−2/N

−4/N

···e

−2(t−1)/N

= 1 −e

−t(t−1)/N

≤ 1 −(1 − t(t − 1)/N )

= t(t −1)/N

≤ t

/N,

using that 1 − x ≥ e

−2x

for 0 ≤ x ≤ 3/4 and that e

≥ 1 + x for all x ∈ R.



EXERCISE 1.38 See the proof of Proposition 1.37(iii). Show that the upper bound for the

probability of ﬁnding at least one collision is almost tight by showing that this probability is

bounded below by t(t − 1)/4N, for t <

√

There are numerous further requirements that can be demanded of a cryptographic hash

function beyond what is stated in Deﬁnition 1.36. In general, any deviation from what can

be statistically expected of a random function should be absent or unlikely, and in any case it

should be infeasible to exploit such statistical weaknesses. By deﬁnition, the random oracle

model is robust w.r.t. such additional requirements. For example, partial preimage resistance

剩余90页未读，继续阅读

morgan_z

粉丝: 0
资源: 4

信息安全协议：保障在线礼物交换的加密技术

密码学协议详解：从古典到公钥加密

多方安全计算：从平均薪资到年龄对比的密码学协议

应用密码学精要：C语言实现的协议与算法

应用密码学 协议 算法与C源程序

应用密码学 协议、算法与c源程序

应用密码学 协议、算法与C源程序 第二版

应用密码学 协议、算法与C源程序 原书第2版 高清 带标签

应用密码学 协议、算法与C源程序 原书第2版 高清 带标签part2（共2部分）

应用密码学 协议、算法与C源程序 原书第2版 高清 带标签part1（共2部分）

密码学协议的设计与分析

最新资源

应用密码学协议算法与C源程序

应用密码学协议、算法与c源程序

应用密码学协议、算法与C源程序第二版

应用密码学协议、算法与C源程序原书第2版高清带标签

应用密码学协议、算法与C源程序原书第2版高清带标签part2（共2部分）

应用密码学协议、算法与C源程序原书第2版高清带标签part1（共2部分）