2011-2012研究生《密码学理论与实践》期末试题

2011-2012学年数学专业研究生《密码学理论与实践》

期末考试

年级： 2011 学号： 2011020680 姓名： 刘 海 专业（二级学科）： 应用数学 研究方向： 密码学理论与工程

一、 解释相关概念及方法（15分）

1. 计算安全与理论安全； 2. IND-CCA2； 3. 可证明安全方法。

二、 关于对称密码，完成如下问题（20分）

1. 叙述DES和AES分别采用什么乘法密码结构？试做一点比较分析； 2. 选择一个常用的轻量级分组密码与AES进行相关比较分析。 三、 关于公钥密码学，完成如下问题：（30分）

1.

简要介绍单向陷门函数的原理，解释如何利用IFP、DLP、ECDLP 三大问题构造单向陷门函数实现公钥加密方案的； 2.

对于RSA方案，试一试解释分解模n和求解n的欧拉函数?(n)的难度是一样的； 3.

设椭圆曲线y2?x3?11x?8定义在有限域F23上。

(1) 若椭圆曲线上的二点为P(9,10)、Q(14,13)，求P+Q和2P；

(2) 求如上椭圆曲线的一个基点G及它的阶，并构造一个简单的

ECC-ElGamal密码方案；

(3) 以如上的G为基点，为Alice和Bob选择一个私钥，用D-H密钥协商

方法求出共享密钥。

四、 请利用多项式h(x)?(7x2?2x?11)mod19设计一个（3, 5）Shamir门限方案来共

享密钥k=11。（10分）

五、 选择一个现代密码方法与技术论述其在某电子商务领域中的应用。（20分）

1 / 22

一、答：

1、计算安全是指满足以下的标准：

? 破译密码的代价超出密文信息的价值； ? 破译密码的时间超出密文信息的有效生命期；

理论安全是指：无论有多少可使用的密文，攻击者无论花费多少时间，

都不足以惟一的确定由密文解密得到的明文信息。

2、IND(不可区分性)：对已知给定的两个明文，加密者随机一致的选择其中一个进行加密，攻击者无法从密文中知道是对哪个明文的加密。

CCA2(适应性选择密文攻击)：敌手在得到目标密文y?前后都可询问解密

机，但不可询问目标密文y?。

IND-CCA2是指对于任意的有效CCA2敌手攻击，它的优势都是可忽略

的。

3、可证明安全方法是是一种归约方法，它通过定义适当的安全目标（一

般地，加密方案的安全目标是保密性，签名方案的安全目标是不可伪造性），然后在一定的敌手模型下证明方案或协议能够达到既定的安全目标。 二、答：

1、Shannon提出的乘积密码是指顺序地执行两个或多个基本密码系统，

使得最后结果的密码强度高于每个基本密码系统产生的结果。其示意图如下：

2 / 22

通常使用的技术是将代替密码和置换密码做乘积。

? DES采用的是Feistel乘法密码结构。其原理是采用对合密码: 一种加密函数f(x,k)，实现：F2n?F2t?F2n的映射。其中，n是分组长度，t是密钥长度。若对每个密钥取值都有f(f(x,k),k)?x，则称之为对合变换。对合加密函数在自密钥控制下对明文进行r轮迭代，后得到密文，密文在其逆序子密钥作用下，进行r轮迭代，就可恢复出明文。

Feistel网络将输入（2w位）分成相同长度的两部分Li和Ri，按如下方式进行变换：

Li位， w位Ri位， w位fLi?1位， w位Ri?1位， w位KFeistel网络的轮函数可表示为：

g(Li?1,Ri?1,Kn)?(Li,Ri)

其中：

Li?Ri?1，Ri?Li?1?f(Ri?1,ki)

函数f并不要求是可逆的，因为只要密钥给定，轮函数g一定是可逆的。具体为：

Li?1?Ri?f(Li,ki)，Ri?1?Li

3 / 22

Feistel加解密过程如下图：

Feistel网络结构的特点：

? 逆向操作和正向操作具有相同的结构唯一不同之处是轮子密钥的使用次序相反。

? 每轮只对轮输入的一半进行变换，虽然实现速度较慢，但可以不要求f函数可逆。

? AES采用的是SP（代换—置换）网络乘法密码结构。其原理是采用迭代密码：以一个简单函数，进行多次迭代。每次迭代，称为一轮，相应的迭代函数称为轮函数。

迭代密码明确定义了一个轮函数和一个密钥编排方案，一个明文的加密

4 / 22

经过了t轮类似的过程。设k是一个确定长度的随机二元密钥，用k通过密钥编排方案来生成t个轮密钥。

一个SP网络就是一类特殊的迭代密码。设l和m都是正整数，明密文都是长为lm的二元向量，一个SP网络包含两个变换，分别记为?s和?p：

?s:{0,1}l?{0,1}l 实现l比特的代换，即S盒； ?p:{1,2,?,lm}?{1,2,?,lm} 实现lm比特的置换；

在SP网络中，前t轮都先经过非线性变换S，然后再进行P置换，而最后t?1轮中，只使用非线性变换S。

SP网络的框图结构如下：

K1K2KtKt?1 SS??SS S P S??SSP??S??P??S???S? S 在SP网络中，非线性代换S得到分组小块的混乱和扩散；再利用P置换，将S盒输出的结果实现整体扩散的效果。这样，若干轮的局部混乱、整体扩散之后，达到足够的混乱和扩散。

在SP网络结构中，常使用的基本代换有：

? 左循环移位代换：f:(x0,x1,?,xn?1)?(x1,x2,?,xn?1,x0)； ? 右循环移位代换：f:(x0,x1,?,xn?1)?(xn?1,x0,?,xn?2)； ? 模2n?1代换；

5 / 22

? 线性变换：y?Tx； ? 仿射变换：y?Tx?b； 通过上述比较，我们发现：

Feistel网络乘法密码结构，每轮对一半数据进行变换，密码变换不要求可逆，几乎没有任何数学理论的支撑。

SP网络乘法密码结构：每轮对所有输入数据进行变换，要求所有密码变换都可逆，具有良好的数学理论的支撑。

2、作为信息传递和处理的网络，全面感知、可靠传送和智能处理是物联网的核心功能。要实现可靠传送必须以密码算法为基础提供相应的安全服务。而与物联网关系密切，也需要密码算法作为基础支撑的无线传感网络也是近年来发展迅猛的领域之一。作为密码算法的使用环境，无线传感器和物联网具有共同的特征：它们的应用组件不同于传统的台式机和高性能计算机，而是计算能力相对较弱的嵌入式处理器；由于应用环境的关系，计算可使用的存储往往较小；考虑到各种设备的功能需求，能耗必须限制在某个范围内。因此传统密码无法很好的适用于这种环境中，就使得受限环境中密码算法的研究成为一个热点。适宜于资源受限环境使用的算法就是所谓的轻量级密码。

轻量级分组密码与传统分组密码相比有几个特点： ? 资源受限的应用环境通常处理的数据规模比较小。 ? RFID和传感器等应用通常对安全性要求不是很高。

? 轻量级分组密码大多采用硬件实现，追求的首要目标是实现占用的空间及实现效率。

6 / 22

现有的典型轻量级分组密码大致有以下几种：PRESENT、HIGHT、mCryoton、CGEN、DESL、MIBS、TWIS、KATAN&KTANTAN、TEA&XTEA、SEA和LBlock。

LBlock是我国学者吴文玲等人在2010年设计的一个轻量级分组密码，中文名为“鲁班锁”，LBlock是LuBan lock的缩写，也有Lightweight Blockcipher的意思。其分组长度为64bit，密钥长度为80bit，采用Fesitel类结构，每轮有一半数据进入轮函数，另一半做简单的循环移位。其加密算法由32轮迭代运算组成，对64bit的明文P?X1||X0，加密过程如下：

对i?1,2,?,33，计算

? X1?F(Xi?1,Ki?1)?(Xi?2???8) ? X32||X33?C为64bit的密文。

其中，基本模块如下定义：

? 轮函数F:{0,1}32?{0,1}32?{0,1}32，{X,Ki}?U?P(S(X?Ki))。 ? 函数S

函数S是函数F的一部分，由8个4?4的S盒并置而成，定义为：

S:{0,1}32?{0,1}32

Y?Y7||Y6||Y5||Y4||Y3||Y2||Y1||Y0?Z?Z7||Z6||Z5||Z4||Z3||Z2||Z1||Z0

Z7?s7(Y7)，Z6?s6(Y6)，Z5?s5(Y5)，Z4?s4(Y4)， Z3?s3(Y3)，Z2?s2(Y2)，Z1?s1(Y1)，Z0?s0(Y0)

? 函数P

由8个4bit字的位置变换，定义为：

P:{0,1}32?{0,1}32

7 / 22

Z?Z7||Z6||Z5||Z4||Z3||Z2||Z1||Z0?U?U7||U6||U5||U4||U3||U2||U1||U0

U7?Z6，U6?Z4，U5?Z7，U4?Z5，U3?Z2，U2?Z0，U1?Z3，U0?Z1

其解密算法是加密算法的逆。而其密钥扩展算法为将密钥K?k79k78k76?k1k0放在80bit的寄存器中，取寄存器左边的32位作为轮密钥K1，然后执行如下步骤：

对i?1,2,?,31，按如下方式更新寄存器 ? K???29。

? [k79k78k77k76]?[k79k78k77k76]，[k75k74k73k72]?[k75k74k73k72]。 ? [k50k49k48k47k46]?[i]2

? 取寄存器左边的32位作为轮密钥Ki?1。 LBlock与AES的比较：

? 在AES中，其密钥长度可以为128位、192位和256位，而LBlock其密钥长度为80bit。

? 在AES中，其分组长度为128位，而LBlock其密钥长度为80bit。 ? AES采用SP结构，每轮对所有输入数据进行变换，要求所有密码变换都可逆。而LBlock采用Feistel网络乘法密码结构，每轮对一半数据进行变换，但其密码变换也可逆。

? 在AES中，S盒被定义为16?16个字节组成的矩阵，而在LBlock中，

S盒被定义为4?4个字节组成的矩阵。

s9s8? 在硬件实现中，AES的S盒最好的实现需要200多GE，而LBlock的10个S盒都可以用大约22个GE实现。

三、答：

8 / 22

1、单向陷门函数ft(x):D?R，是一个单向函数，即对任意的x?D，容易计算，

而对几乎所有的x?D，求逆困难。但是，如果知道门限信息t，则对所有的y?R，容易计算满足y?ft(x)的x?D。

? IFP（整数分解问题）：

假设N?pq是大整数，p，q为两个素数，且p，q?2768。 输入：N。 输出：素数p，q。

这一困难问题就称为IFP（整数分解问题）。 利用IFP构造的公钥加密方案，如RSA方案：

假设M为明文，C为密文。

? 选择两个大素数p，q； ? 计算N?pq，?(N)?(p?1)(q?1)； ? 选择整数e，使得gcd(e,?(N))?1 ? 计算d?e?1mod ?(N)。 公钥KU?{e,N}，私钥KR?{d,n}

加密算法：C?Memod n； 解密算法：M?Cdmod n；

DLP（离散对数问题）：

假设p为素数，定义一个Zp的子集Z*}。 p?{a?Zp|gcd(a,p)?1* 输入：Z*p的生成元?和一个元素??Zp。

输出：x，使得?x??mod p。

这一困难问题称为DLP（离散对数问题）。

9 / 22

利用DLP构造的公钥加密方案，如ElGamal方案：

假设明文为M，密文为(C1,C2)。

密钥创建：

? 随即选择素数p；

? 计算Z*p上的一个随机生成元g； ? 随机选取x?Zp?1作为其私钥； ? 计算y?gxmod p；

? 把(p,g,y)作为其公钥公开，把x作为私钥进行保存。 加密算法：

? 随即选择k?Zp?1； ? 计算C1?gkmod p； ? 计算C2?ykMmod p； 解密算法：

? 计算M?C2modp xC1? ECDLP（椭圆曲线离散对数问题）：

假设E是定义在有限域Fp上的一个椭圆曲线，P是E(Fp)上的一个点，并且假设P的阶为素数n，令Q?dP，其中d?[1,n?1]。

输入：P,Q 输出：d

这一困难问题就称为ECDLP（椭圆曲线离散对数问题）。

利用ECDLP构造公钥加密方案，公开参数(p,E,P,n)，将d作为私钥，Q作为公钥。假设m为明文，(C1,C2)为密文：

10 / 22

加密算法：

? m?M，M是E(Fp)上的一个点； ? 选择k?[1,n?1]； ? 计算C1?kP； ? 计算C2?M?KQ; ? 输出密文(C1,C2) 解密算法：

? 计算M?C2?dC1； ? M?m； ? 输出明文m；

在上述描述中，将输出作为单向陷门信息，即私钥，而将输入作为

2、在RSA方案中，在密钥建立阶段，用户Alice要执行： 1) 随机选择两个素数p和q，满足p?q； 2) 计算n?pq；

3) 计算?(n)?(p?1)(q?1)；

如果已知n的分解n?pq，则易求出?(n)?(p?1)(q?1)。 如果已知n和?(n)的值，则由n?pq和?(n)?(p?1)(q?1)得到：

?(n)?(p?1)(q?1)?pq?(p?q)?1?n?(p?q)?1

即：

p?q?n??(n)?1

?p和q是一元二次方程x2?(n??(n)?1)x?n?0的两个根。

综上所述：

11 / 22

对于RSA方案，分解模n和求解n的欧拉函数?(n)的难度是一样的。 3、(1) 依题意，得：a?11 ，b?8

? 4a3?27b2?4?113?27?82?7052?14?0(mod27) ? F23上的方程E：y2?x3?11x?8定义了一个椭圆曲线群。

设P(x1,y1)?Q(x2,y2)?R(x3,y3)

P(x1,y1)?P(x1,y1)?2P(x1,y1)?R?(x4,y4)

?y1?y2??x?x ? ???122?3x1?a??2y1x1?x2

x1?x2,y1?y2?0 ? ?1?y1?y210?1333?23?4????19(mod23) x1?x29?14553x12?a3?92?11254254?23?2 ?2?????15(mod23)

2y12?1020202 ? x3??1?x1?x2?192?9?14?16(mod23)

y3??1(x1?x3)?y1?19?(9?16)?10?18(mod23)

2x4??2) 2?x1?x2?15?9?9?0(mod23 y4??1(x1?x4)?y1?15?9?10?10(mod23) 即：P(9,10)?Q(14,13)?R(16,18)，2P(9,10)?R?(0,10)

(2) F23上的方程E：y2?x3?11x?8的一个基点为：G?(0,10)

? 2G?(16,18)；3G?(13,18)；4G?(18,9)；5G?(17,5)；6G?(15,12)；

7G?(16,5)；?；10G?(14,10)；11G?(9,13)；12G?(9,10)；?； 20G?(13,5)；21G?(16,5)；22G?(0,13)；23G?O

? G?23

则ECC?ElGamal密码方案为：

12 / 22

a) 加密算法

输入参数(23,E23(11,8),(0,10),23)，公钥Q?(16,18)，明文m?(17,5)； 输出：密文((13,18),(9,13))；

? 选择k?3?[1,22]； ? 计算C1?3(0,10)?(13,18)；

? 计算C2?m?3Q?(17,5)?3(16,18)?(9,13) ? 返回(C1,C2)?((13,18),(9,13)) b) 解密算法

输入参数(23,E23(11,8),(0,10),23)，私钥d?2，密文(C1,C2)?((13,18),(9,13))； 输出：明文m?(17,5)；

? 计算m?C2?dC1?(9,13)?2(13,18)?(17,5)； ? 返回m?(17,5)；

（3）F23上的方程E：y2?x3?11x?8的一个基点为：G?(0,10)

? 公开参数(23,E23(11,8),(0,10),23)；

e的公钥为? Alice，Bob分别选择自己的私钥NA?5，NB?7；则AlicPA?5(0,10)?(17,5)，Bob的公钥为PB?7(0,10)?(16,5)； ? Alice将PA发给Bob； ? Bob将PB发给Alice；

? Alice和Bob分别计算PAB?NAPB?NBPA?5(16,5)?7(17,5)?(9,10)； 则共享密钥为PAB?(9,10)。

四、答：假设秘密分发者为P0，参与者集合为P?{P1,P2,P3,P4,P5}。 秘密分发者P0，对于x1?1，x2?2，x3?3，x4?4，x5?5，分别计算：

y1?h(x1)?h(1)?1 (mod 19)；

13 / 22

y2?h(x2)?h(2)?5 (mod 19)；

y3?h(x3)?h(3)?4 (mod 19)；

y4?h(x4)?h(4)?17 (mod 19)；

y5?h(x5)?h(5)?6 (mod 19)；

然后P0分别单独的将子密钥信息(xi,yi)秘密地发送给Pi，1?i?5。随后将多项式h(x)销毁。

依题意，参与者集合P中的任意3人联合可恢复出主密钥。不妨设

A?{P1,P2,P3}，于是A中参与者掌握的全部子密钥信息为：

(x1,y1)?(1, 1)；(x2,y2)?(2, 5)；(x3,y3)?(3, 4)；

依此构造方程组：

?111??k??1???????124???a1???5??139??a??4????2???

上述方程组等价于：

?111??k??1???????013 19)???a1???4? (mod?002??a???5????2???

由此解可得到：a1?2，a2?7，k?11。

即：P1，P2，P3共同重构了主密钥k?11。

而当参与重构的参与者少于3人时，不妨设参与重构的参与者集合

A??{P1,P2}，于是A?中参与者掌握的全部子密钥信息为：

(x1,y1)?(1, 1)；(x2,y2)?(2, 5)；

依此构造方程组为：

14 / 22

?k??111????1???124???a1????5?????a????2?

由于：

?1111??1111?r(A,b)???1245??~??0134???r(A)?2?3

????我们知道，该方程组有无穷多组解。

因此，P1，P2不能准确的重构出主密钥k?11。 五、答：

秘密共享最初是用于密钥管理，即将一个主密钥在多个参与者之间共

享，使得特定的参与者集合能够恢复出主密钥，而任意少于这个特定参与者集合的参与者在一起不能恢复出主密钥。秘密共享是在1979年由Shamir和Blakley分别基于拉格朗日插值和几何空间中点的性质单独提出的。随后其他学者基于中国剩余定理、矩阵、同态等构造出其他秘密共享方案。但是，在这些秘密共享方案中，Shamir的方案更为简单、实用，并且只有Shamir的秘密共享方案是完美的，因此受到更为广泛的应用。

所谓的完美秘密共享体制是指：实现存取结构AS的完美秘密共享体制

和对应的重构函数

由分配函数?:S?R?S1???SnRe?{ReA:(S1???Sn)|A?S|A?AS}构成，且满足下面的条件：

? 重构要求：对于任意的A?AS和k?N，重构函数

ReA:(S1???Sn)|A?S使得对于任意的s?S(k)(k)kPr[Re(?(s,R)|,1)?s]?1，其AkA，

中S表示安全参数为k时对应的主密钥空间，它是S的一个子集。

?

安全性要求：对于任意的B?AS(k)t,t?S和12，{?(k)(t1,R)|B}k?N和

{?(k)(t2,R)|B}k?N完全不可区分。

15 / 22

下面，我们来看看Shamir的具体方案： ? 密钥分配算法：

设Fq为q元有限域，q是素数并且q?n。为了使集合P?{P1,P2,?,Pn}中

的n个参与者共享主密钥s，s?Fq，密钥管理中心P0按下面的步骤进行工作：

步骤1：P0秘密地在Fq中随机地选取t?1个元素，记为a1,?,at?1，并取以x为变元的多项式f(x)?s?a1x?a2x2???at?1xt?1。

步骤2：对于1?i?n，P0计算f(i)，记为yi?f(i)。

步骤3：对于1?i?n，P0秘密地将(i,yi)分配给Pi，这可通过一个秘密

安全信道传输完成。Pi不得向任何人泄露yi。 ? 重构算法：

设P1,?,Pl是P中任意选定的l(l?t)个参与者，这l个参与者掌握的全部

子密钥集合为{(1,y1),?,(l,yl)}。则计算方程组：

?11?1??s??y1???????t?1?12?2??a1??y2?????????????????????12?lt?1??a??y????t?1??t?

上述方程组可以看成t个变元的线性方程组，系数矩阵的秩是t，这由1,2,?,n在Fq中两两不同和范德蒙矩阵的性质保证。事实上，它的任何不同的t行构成t?t的范德蒙矩阵，所以是秩为t的可逆矩阵。因此，当l?t时，s,a1,?,at?1是它的唯一解，于是得到主密钥s。

对于l?t，l个参与者要恢复主密钥s时，他们可得到含有t个变量的

l(l?t)个方程的线性方程组。若l?t?1，则他们就得到含有t个变量的t?1个方程。假设这t?1个参与者用他们掌握的t?1个子密钥猜的主密钥s0（不

16 / 22

管用什么方法猜）。由于将s0?f(0)和关于子密钥的t?1个方程放在一起可得到唯一解，因此对主密钥的任何假设值s0都存在唯一的多项式fs(x)，

0使得yj?fs(j)，1?j?l，和s0?fs(0)。于是，没有一个主密钥的可能值

00被排除，换句话说，t?1个参与者合谋得不到主密钥的任何信息。一般来说，对于l?t，对任意给定的s，关于(a1,?,at?1)的方程组都有相同个数的解，由此推出：从{((1,y1),?,(l,yl))}得不到主密钥s的任何信息，或者说，要得到s其工作量与穷搜索相同。

但是，在Shamir的方案中存在两个问题：即如何确保密码分发者分发给参与者的子秘密时正确的；如何确保在秘密重构阶段中各参与者出示的子秘密是正确的。正是介于上述两个问题，学者们研究出了可验证的秘密共享方案，但是在可验证的秘密共享方案中还存在一个问题，即各个参与者只能验证自己的子秘密是否正确，不能验证其他参与者的子秘密是否正确。基于此，学者们又提出了可公开验证秘密共享。

在现实生活中可以见到各种拍卖会，比如常见的是拍卖商推出要拍

卖的商品，由拍卖者根据情况叫价，最后在一定时间内再没有人叫更高的价时，商品就被拍卖给当前叫价最高的人（称为中标者）。按照拍卖的形式可以将其分为英式拍卖、荷兰式拍卖、密封式拍卖等。其中，英式拍卖和荷兰式拍卖由竞拍者公开叫价，不过前者是从低价向高价叫，后者则由高价向低价进行。在密封式拍卖中，竞拍者采取匿名投标，即将自己的出价密封上报，在一定程度上保护了竞拍者的隐私。电子拍卖是将现实生活中的拍卖行为电子化，即商品信息的公布、竞拍者投标的递交、揭标等过程都可以通过互联网进行，拍卖商以及竞拍的各位买家可

17 / 22

以身处不同的地方参加拍卖，大大方便了拍卖活动的进行。现在，电子拍卖已经为电子商务的一项基本业务，互联网上有许多电子拍卖系统，如Yahoo！，eBay.com等。我们下面介绍秘密共享体制在密封式电子拍卖中的应用。

一个密封式电子拍卖系统至少要满足下列要求：

? 公平性。即所有竞拍者的地位一样，不存在一方比其他方更有利的条件。

? 不可否认性。竞拍者上交其出价后不能否认其出价。 ? 不可伪造性。竞拍者的投标不能够被他人伪造。 ? 可证实性。可公开证明中标者标价的合法性。 ? 标价保密性。竞拍者的标价必须保密、

? 匿名性。除中标者所出标价在最后可公开验证外，其他竞拍者所出的标价是保密的，并且所有竞拍者的身份保密，不能将标价信息与竞拍者对应起来。

简单来说，一个电子拍卖系统应包含注册中心、拍卖服务器、卖主和竞拍者。注册中心负责给卖主和竞拍者颁发合法证书、进行投标注册等，它实际上相当于一个负责认证的权威机构。拍卖服务器则负责主要的拍卖工作，即竞拍者将自己的标价“密封”通过秘密信道上交给拍卖服务器，拍卖服务器打开标价后按照一定的规则，如最高价中标的原则，公布最后中标的标价。如下图所示：

18 / 22

注册认证卖主注册中心竞拍者1??竞拍者m注册中心提交标价 我们可以看到，由于拍卖服务器掌握了所有竞拍者的标价信息，一旦它被攻破，整个系统的安全就受到极大威胁。一个简单的解决方法是采用每个 竞拍者将自己的标价通过一个(t,n)门限秘密共享体制在这n个服务器，

n个拍卖服务器之间 ，使得只有至少t个拍卖服务器联合才能恢复出每个竞

拍者的标价信息。而任何少于t个拍卖服务器即使联合起来也得不到关于标价的任何信息。为了实现标价的匿名性，每个竞拍者仍然利用秘密共享体制将自己的标价分为若干份，但不是一次全交给拍卖服务器，而是分若干次上交，每次上交后拍卖服务器进行重构，知道找到最高的标价为止。具体步骤为如下：

假设共有m个竞拍者，记为B1,B2,?,Bm。 ? 系统拍卖

拍卖服务器首先发布要拍卖的物品，并公布可以接受的拍卖价pi，

1?i?n，不妨设p1?p2???pn，n?m；再选中一个大素数p满足p远远大于

pn，所有的计算都在

Zp中进行；选择一个无碰撞的单向函数H(?)并将其公布

出去。

19 / 22

? 注册

每个竞拍者Bi，1?i?m到注册中心进行注册，注册中心检查每一个竞拍者的身份和资格，如是否有经济担保等。如果合格就发放资格证书，记为Ceri。

? 投标

对于1?i?m，竞拍者Bi从公布的n个标价中选一个作为自己的将投的标价，比如第ki个标价pk，1?ki?n。同时选择一个常项数为pk，次数至多为

iin?ki次的Zp上的随即多项式fi(x)，即：

fi(x)?pki?a1x???an?kixn?ki

其中，a1,a2,an?k随机地取自Zp。然后，Bi计算yij?fi(j)，1?j?n。为了后面

i验证需要，Bi公开信息：Ceri，H(yi1),H(yi2),?,H(yin),。

接着开始第一轮的投标：对于1?i?m，Bi通过秘密信道发送给拍卖服务

器标价信息yi1。拍卖服务器在收到这一轮的所有标价信息（即y11,y21,?,ym1）后关闭这一轮标价提交。

? 揭标

首先，拍卖服务器针对接收到的y11,y21,?,ym1分别计算它们在Hash函数

H(?)下的值，并与投标前的公开信息H(yi1)，1?i?m进行比较。如果有某个

竞拍者提交的部分标价的Hash值与投标前公布的信息不符，则拒绝该竞拍者继续参加拍卖。

假设在第r(1?r?n)轮投标后，拍卖服务器得到了竞拍者Bi的部分标价信息yi1,yi2,?,yir，则拍卖服务器计算插值多项式

g(x)??yij(r)ij?1r(x?1)?(x?j?1)(x?j?1)?(x?r)

(j?1)?(j?j?1)(j?j?1)?(j?r)00

如果对于某个1?i0?m，满足gi(r)(0)?pm?r?1，则说明竞拍者Bi可能投了最

20 / 22

高价pm?r?1，于是转到下面的验证环节。

否则，即对于1?i?m，都有gi(r)(0)?pm?r?1，则进行第r?1轮的投标：竞

0标者Bi通过秘密信道发送给拍卖服务器标价信息yi(r?1)，1?i?m。

? 验证

如果gi(r)(0)?pm?r?1，则拍卖服务器要求竞拍者Bi提供yi(r?1),?,yin，Bi通

00000过秘密信道发送给拍卖服务器yi(r?1),?,yin，拍卖服务器收到后首先检验他们

00的Hash值是否与投标前公布的信息相符，然后继续检验对于r?1?j?n，是否都有等式gi(r)(j)?yij成立。如果所有条件都满足，则宣布Bi即为中标者；

000否则进行下一轮的投标。

我们可以看到，在上述的电子拍卖方案中，每个竞拍者通过一个门限秘密共享体制对自己所投的标价进行共享，每一轮投标只提交n各秘密份额（对应于秘密共享体制中的子秘密）中的一个，从而标价可以更早地被重构出来，即等式gi(r)(0)?pm?r?1成立。如果竞拍者选择标价pt，1?t?n，同时产生常数

0项为pt，次数至多为n?t次的随即多项式f(x)，也就是将pt按照(n?t?1,n)的门限产生秘密份额f(1),?,f(n)。根据门限秘密共享体制的安全性，由任意

r(r?n?t)个秘密份额得不到主密钥pt的任何信息，即设由f(1),?,f(r)计算r?1次插值多项式为g(r)(x)，则有

Pr[g(r)(0)?pt]?1 p也就是说，如果竞拍者实际投的标价是pt，那么他将不会以超过的概率在揭标环节被认为投了最高标价pn?r?1（r?n?t），从而进入验证环节。由于p远远大于pn，因此这个概率是非常小的。并且进入验证环节后，需要核对g(r)(x) 21 / 22

1p在余下的点（即尚未通过投标过程提交的）r?1,?,n上取值。由于f(x)?g(r)(x)是至多n?1次的非零多项式，因此f(x)?g(r)(x)不可能在n?1个不同点（即

0,1,?,n）上取相同的值，即该竞拍者不可能通过验证。因此，在上述的方案

中最后宣布的中标者确实就是出价最高的。不过，由于在验证环节需要提供所有的秘密份额，因此拍卖服务器自然就知道了竞拍者所投的标价。如果该竞拍者不是最后的中标者，则标价的泄露违背了密封式电子拍卖的安全性要求，但是这个概率是非常小的，不超过。

1p 22 / 22

本文来源：https://www.bwwdw.com/article/w91p.html