第9章 密码协议(不经意传输和掷硬币协议)
- 格式：ppt
- 大小：156.00 KB
- 文档页数：20
文档推荐
-
第9章 密码协议(不经意传输和掷硬币协议)页数:20
-
安全协议期末复习页数:10
-
9公平交换协议页数:46
下载文档原格式
合集下载
chap10-2：密码协议基本理论
处理通信双方自身发生的攻击。
数字签名提供了这种能力:
验证签名者、签名的日期和时间 认证消息内容 可由第三方仲裁，以解决争执
因此，数字签名具有认证功能
数字签名应满足的条件
签名值必须依赖于所签的消息 产生签名比较容易 识别和验证签名比较容易
伪造数字签名在计算上是不可行的。包括
已知数字签名，伪造新的消息 已知消息，伪造数字签名
对用其公钥加密过的随机数进行解密；
对随机数进行签名。
为了保证安全性，认证协议的公私钥对不能在 其他应用中使用；同时，协议还应能够抵抗选 择密文攻击。
采用公钥密码技术的认证方案
简单的认证协议：
认证方 B 选择随机数 r ，计算 x=h(r) ， e=PA(r ，
B)，（其中：h 是哈希函数，PA是发起方A 的公
Alice用H将消息m进行处理，得h=H(m)。
Alice 用自己的私钥 k 对h“解密” s=D(h, k) ， s 就是对消
息m的签名值，(m，s)就是一个签名消息。
Alice将(m，s)发送给Bob。 Bob 收到 (m ， s) 后，用 Alice 的公钥 z ，将消息 m 与签名 s 做
，他有办法检验，该签名是否真的被 Alice 签名的消 息。
或许攻击者Eve截获了大量的被Alice签名的消息，但
他仍然不能伪造出一个新的，别人认可的“被 Alice 签名的消息”。
如果无论Eve截获多少被Alice签名的消息，他伪造新
的“被 Alice 签名的消息”的成功概率仍然没有丝毫 提高，则称该签名算法是零知识的。
息(m，s)进行验证。
是否只有Alice自己才能生成自己的签名消息
密码协议
第三次尝试协议
S
1. A, B
A
2. {KAB, B}KAS, {KAB, A}KBS
3. {KAB, A}KBS
B
1.4.3 重放(Replay)
▪ 安全假设4:敌手能够从以前协议运行中通过密码分 析获取会话密钥KAB.
对第三次尝试协议的攻击
C
1. A, B
2. {KAB’, B}KAS, {KAB’, A}KBS
▪数据源鉴别(Data Origin Authentication)：确保 所接收的到数据确实是来自所声明的源头。由于修 改了数据必然修改了它的起源，所以数据源鉴别包 含了数据完整性。可以通过MAC或数字签名算法来 实现。
▪ 非否认性(Non-repudiation)：防止消息的发送方 或接收方对他所发送过的消息进行抵赖。通常是通 过数字签名算法来实现。鉴别和密钥建立协议中很 少使用这一密码属性。但在电子商务协议中应用普 遍。
In recognition of his fundamental contributions to the theory of computation, including the complexity-based theory of pseudorandom number generation, cryptography, and communication complexity."
1. B, NB
A
4. {KAB, A,NB}KBS
B
▪ 对比最终协议和第四次尝试协议 ▪Key Confirmation
1.5 Dolev-Yao模型
▪ 将密码协议本身与密码协议所具体采用的密码系统 分开，在假定密码系统“完善”的基础上讨论密码 协议本身的正确性、安全性、冗余性等课题
0 密码协议(电话抛币协议)
5
南京航空航天大学网络研究室
密码协议
对协议的攻击
被动攻击 主动攻击 被动骗子 主动骗子 协议对被动欺骗来说应该是安全的 合法用户可以发觉是否有主动欺骗
Copyright Yuan Email:hello@
6
南京航空航天大学网络研究室
密码协议
所需数论定理
用到的数学结论： 只需要记住。
设有Blum整数n，满足n=pq。 分解问题等价于判断二次剩余：则分解n（即 分解问题）等价于判断x^2=a mod n 是否有解， 即判断a是否为mod n的二次剩余； 分解问题等价于求解二次根：若a是二次剩余， 上述两个难题也等价于求出a的两个二次根x1 和x2.
Copyright Yuan Email:hello@
Copyright Yuan Email:hello@
11
南京航空航天大学网络研究室
密码协议
9.6 掷硬币协议
因u是B随机选取的，A不知道u，所以要猜测u只 能是计算模n下z的4个平方根，猜中的概率是1/2。 再考虑B如何能欺骗A，如果B在A猜测完后能够 改变u的值，则A的猜测必不正确，A可通过 z≡u2 mod n 检查出B是否改变了u的值，所以B要想改 变u的值就只能在x’和y’之间进行。而B若掌握x’ 和y’，就可通过gcd{x’-y’, n}或gcd{x’+y’, n}求出p 和q，说明B的欺骗与分解n是等价的。
Copyright Yuan Email:hello@
8
南京航空航天大学网络研究室
密码协议
电话抛币协议
问题：“抛币-猜测”游戏的数字化，也即电 话抛币，或网络抛币。
Copyright Yuan Email:hello@
现代密码学之密码协议.
比特承诺
利用基于单向函数的比特承诺方案如下：
Alice和 Bob共同选定一个单向函数，如Hash函数 Alice生成两个随机数和承诺比特串，计算单向函 数值并将结果（哈希值）和其中一个随机数发送 给Bob。 当Alice向Bob出示消息时，她把承诺比特串与另 一个随机数一起发送给Bob。 Bob计算hash值，并与第②步收到的值做比较以检 验消息的有效性。
国家级精品课程
现代密码学
灾备技术国家工程实验室 北京邮电大学信息安全中心
上一讲内容回顾
有特殊性质的签名方案
盲签名 群签名与环签名 多重签名 聚合签名 代理签名 不可否认签名 一次签名 失败即停签名 „„
《现代密码学章主要内容
密码协议概念 比特承诺 公平抛币协议 安全多方计算 电子货币 电子选举 匿名协议
4
本章主要内容
密码协议概念 比特承诺 公平抛币协议 安全多方计算 电子货币 电子选举 匿名协议
5
密码协议概念
协议是一系列步骤，它包括两方或多方， 设计它的目的是要完成一项任务。一般包含 了三个方面的含义：
⑴ 协议需要二个或二个以上的主体参与。 ⑵ 参与者按照一定的次序交替地执行一系列的步 骤，在前一步尚未完成之前，后面的步骤不能被执 行。 ⑶ 参与者必须能够协同地完成某项任务，或达成某 种意向。
a 勒让德符号 p 1和
a q 1 ，若满足则计算
x 2 a(mod n) 的四个根：x1 , n x1 , x2 , n x2 ，其中 n x1 x 2 x ,x 2 。然后Alice随机猜测Bob选取的是 1 2 中的哪一个，并把猜测结果0或1发送给Bob（事先规 定大的用1表示，小的用0表示）.
第9章-密码协议(不经意传输和掷硬币协议)电子教案
南京航空航天大学网络研究室
密码协议
9.6 掷硬币பைடு நூலகம்议
④ A猜测u=x’或u=y’，或者A找出最小的i使得x’ 的第i个比特与y’的第i个比特不同，A猜测u的第 i个比特是0还是1。A将猜测发送给B。
密码协议
9.5 不经意传输协议
2. “多传一”的不经意传输协议
设A有多个秘密，想将其中一个传递给B，使得只有B 知道A传递的是哪个秘密。设A的秘密是s1,s2,…,sk， 每一秘密是一比特序列。协议如下：
① A告诉B一个单向函数f，但对f-1保密。
② 设B想得到秘密si，他在f的定义域内随机选取k个 值x1,x2,…,xk，将k元组(y1,y2,…,yk)发送给A， 其中
密码协议包含某种密码算法. 参与该协议的伙伴可能是朋友和完全信任的人，或
者也可能是敌人和互相完全不信任的人。 在协议中使用密码的目的是防止或发现偷听者和欺
骗.
Copyright Yuan Email:hello@
3
南京航空航天大学网络研究室
密码协议
协议的目的
计算一个数值想共享它们的秘密部分 共同产生随机序列 确定互相的身份 同时签署合同
由于B没有zj(j≠i)的信息，因此无法得到sj(j≠i)，而A 不知k元组(y1,y2,…,yk)中哪个是f(xi)，因此无法确 定B得到的是哪个秘密。
Copyright Yuan Email:hello@
10
南京航空航天大学网络研究室
密码协议
9.6 掷硬币协议
在某些密码协议中要求通信双方在无第三方 协助的情况下，产生一个随机序列，因为A、B之 间可能存在不信任关系，因此随机序列不能由一 方产生再通过电话或网络告诉另一方。这一问题 可通过掷硬币协议来实现，掷硬币协议有多种实 现方式，下面介绍其中的3种。
现代密码学之密码协议
百万富翁问题
假设A拥有i百万，B拥有j百万，且即1 ≤i,j ≤N。两人执行如下协议： ①A和B共同协商一种公钥加密体制。不妨设B的公钥和私钥分别为 KUB和KRB。 ②A随机选择一个大随机数x,用B的公钥加密c=EKU (x),然后将c-i发 B 送给B。 ③B首先计算N个数：yu=DKR (c-i+u),u=1,2,…,N。然后随机选择一 B 个大素数p,再计算N个数：zu=yumod p,u=1,2,…,N。接着验证对于 所有的0≤a≠b ≤N-1,是否都满足|za-zb|≥2？若不满足，则重新选择 大素数p重新验证。最后，B将以下的N+1个数串发送给 A:z1,z2,…,zj,zj+1+1,zj+2+1,…,zN+1和p。 ④设A收到N+1个数串m的第i个数是mi，若满足mi≡x mod p，则结 论是i≤j;否则i>j。 ⑤A将最终的结论告诉B。
比特承诺
利用基于单向函数的比特承诺方案如下：
Alice和 Bob共同选定一个单向函数，如Hash函数 Alice生成两个随机数和承诺比特串，计算单向函 数值并将结果（哈希值）和其中一个随机数发送 给Bob。 当Alice向Bob出示消息时，她把承诺比特串与另 一个随机数一起发送给Bob。 Bob计算hash值，并与第②步收到的值做比较以检 验消息的有效性。
本章主要内容
密码协议概念 比特承诺 公平抛币协议 安全多方计算 电子货币 电子选举 ቤተ መጻሕፍቲ ባይዱ匿名协议
20
安全多方计算
安全多方计算就是指在无可信第三方的情况下， 安全地计算一个约定的函数的值。 在一个安全多方计算协议中，参与方之间一般是 互不信任的，他们各自都有一个不想让其它任何 人了解的秘密数，但是他们要利用这些秘密数来 求得大家都信任的值或答案。确切地讲，安全多 方计算就是满足下述三个条件的密码协议：
不经意传输协议 密码学原理
不经意传输协议（Oblivious Transfer Protocol）的密码学原理是基于多重加密和随机性。
该协议使用单向函数和密码学哈希函数等数学工具，以确保信息只能在预定的接收者之间传播。
在典型的Oblivious Transfer Protocol中，通信双方分别是发送者（Sender）和接收者（Receiver）。
发送者希望向接收者传输一批敏感的数据，但并不知道接收者需要哪些数据。
接收者希望从发送者那里获取感兴趣的数据，但不想让发送者知道他实际选择了哪些数据。
协议的实现过程包括预处理阶段，发送者和接收者在事先约定好的通信安全模型下，进行一些密钥交换和初始化的操作，旨在为之后的通信建立必要的加密环境。
0 密码协议(不经意传输和掷硬币协议)
第9章 密码协议
密码协议
协议
协议是一系列步骤 它包括两方或多方 设计它的目的是要完成一项任务
Copyright Yuan Email:hello@
2
南京航空航天大学网络研究室
密码协议
协议特点
协议中的每人都必须了解协议，并且预先 知道所要完成的所有步骤。 协议中的每人都必须同意遵循它。
为模n的平方剩余与分解n是等价的。
Copyright Yuan Email:hello@
19
南京航空航天大学网络研究室
密码协议
9.6 掷硬币协议
协议如下： a ① B选择p、q，计算n=pq；再选取满足 n 1 的随 机数a，将n和a发送给A。 ② A猜测a是模n的平方剩余或非平方剩余，并将结果 告诉B。 ③ B告诉A猜测正确或不正确，并将p、q发送给A。 ④ A检查p、q都是素数且n=pq。 显然，A猜中的概率是1/2。协议执行完后，A根 据p、q可求出a mod n的4个平方根（如果a是模n的 平方剩余），以检查B是否在A猜测完后将结果做了 修改。
协议必须是不模糊的，每一步必须明确定 义，并且不会引起误解。 协议必须是完整的，对每种可能的情况必 须规定具体的动作。
Copyright Yuan Email:hello@
3
南京航空航天大学网络研究室
密码协议
密码协议
密码协议，有时也称作安全协议，是以密码学为基 础的消息交换协议，其目的是在网络环境中提供各 种安全服务。密码学是网络安全的基础，但网络安 全不能单纯依靠安全的密码算法。安全协议是网络 安全的一个重要组成部分，我们需要通过安全协议 进行实体之间的认证、在实体之间安全地分配密钥 或其它各种秘密、确认发送和接收的消息的非否认 性等。 密码协议包含某种密码算法. 参与该协议的伙伴可能是朋友和完全信任的人，或 者也可能是敌人和互相完全不信任的人。 在协议中使用密码的目的是防止或发现偷听者和欺 骗.
密码协议
协议
协议是一系列步骤 它包括两方或多方 设计它的目的是要完成一项任务
Copyright Yuan Email:hello@
2
南京航空航天大学网络研究室
密码协议
协议特点
协议中的每人都必须了解协议，并且预先 知道所要完成的所有步骤。 协议中的每人都必须同意遵循它。
为模n的平方剩余与分解n是等价的。
Copyright Yuan Email:hello@
19
南京航空航天大学网络研究室
密码协议
9.6 掷硬币协议
协议如下： a ① B选择p、q，计算n=pq；再选取满足 n 1 的随 机数a，将n和a发送给A。 ② A猜测a是模n的平方剩余或非平方剩余，并将结果 告诉B。 ③ B告诉A猜测正确或不正确，并将p、q发送给A。 ④ A检查p、q都是素数且n=pq。 显然，A猜中的概率是1/2。协议执行完后，A根 据p、q可求出a mod n的4个平方根（如果a是模n的 平方剩余），以检查B是否在A猜测完后将结果做了 修改。
协议必须是不模糊的，每一步必须明确定 义，并且不会引起误解。 协议必须是完整的，对每种可能的情况必 须规定具体的动作。
Copyright Yuan Email:hello@
3
南京航空航天大学网络研究室
密码协议
密码协议
密码协议，有时也称作安全协议，是以密码学为基 础的消息交换协议，其目的是在网络环境中提供各 种安全服务。密码学是网络安全的基础，但网络安 全不能单纯依靠安全的密码算法。安全协议是网络 安全的一个重要组成部分，我们需要通过安全协议 进行实体之间的认证、在实体之间安全地分配密钥 或其它各种秘密、确认发送和接收的消息的非否认 性等。 密码协议包含某种密码算法. 参与该协议的伙伴可能是朋友和完全信任的人，或 者也可能是敌人和互相完全不信任的人。 在协议中使用密码的目的是防止或发现偷听者和欺 骗.
7.6其他密码协议
上页
返回
下页
结束
4. 基于大数分解问题的“多传一”不经意 传输协议 设A有多个秘密，并对自己的每个秘密都 使用一个不同的RSA体制加密，A要想向B 传递其中的一个秘密，就可告诉B加密该密 钥的RSA体制的模数。协议如下： ① A构造k个RSA加密体制，使得在每个体 制中的两个素数pj和qj满足pj≡qj≡3 mod 4（ 因此可保证同一数a在模nj=pjqj下的两个平 方根有相反的Jacobi符号），将加密密钥 (ej, nj)及加密后的秘密sejj mod nj发送给B， 其中j=1, 2, …, k。
来的y得出x，即只能猜测x的奇偶性。而B若在A
做出猜测以后改变x，A可通过 y f x 检查出来
?
。
上页 返回 下页 结束
3. 利用二次剩余掷硬币 设n是两个大素数p、q的乘积，即n=pq。整 数a满足0<a<n和gcd(a, n)=1，则有一半的a 所有a中，只有一半是模n的平方剩余，而 的。
上页 返回 下页 结束
④ A猜测u=x’或u=y’，或者A找出最小的i使 得x’的第i个比特与y’的第i个比特不同，A猜 测u的第i个比特是0还是1。A将猜测发送给 B。 ⑤ B告诉A猜测正确或不正确，并将u的值 发送给A。
上页
返回
下页
结束
⑥ A公开n的因子。 因u是B随机选取的，A不知道u，所以要猜测u只 能是计算模n下z的4个平方根，猜中的概率是12 。再考虑B如何能欺骗A，如果B在A猜测完后能 够改变u的值，则A的猜测必不正确，A可通过 检查出B是否改变了u的值，所以B要想改变u的 值就只能在x’和y’之间进行。而B若掌握x’和y’，
xj j i yj f xj j i
第11章密码协议.
h( x) a0 a1 x a2 x (mod 17)
2
2019/4/12 19
二、不经意传输
“不经意传输协议”的特性
（不经意传输协议；Oblivious Transfer；OT） 设Alice欲告诉Bob 某个秘密。 Alice使用一个“不经 意传输协议”将此秘密发送给Bob。则发送/接收 过程就具有以下的性质。
2019/4/12 21
二、不经意传输
（2）发送/接收过程完结时， Alice无法确知Bob是 否得到了秘密。 换句话说，在发/收过程结束后， Alice仍然仅仅知道 ： Bob得到秘密和未得到秘密的可能性各占1/2。 除此之外， Alice得不到任何新的消息。
2019/4/12
22
二、不经意传输
( ID(1))t 1 a 0 t 1 a ( ID( 2)) 1 (mod p ) t 1 a ( ID(t )) t 1
14
一、秘密共享
这是一个关于未知系数 {a0, a1, a2, …, at-2, at-1} 的t元一次方程组（请注意，是模(modp)运算的t元一 次方程组），有t个方程，因此容易解出{a0, a1, a2, …, at-2, at-1}。 当任何t-1个人以下同时到场，每个人交出自己的身 份名（ID(k)，h(ID(k))），则获得了关于未知系数 的t元一次方程组，有t-1个以下方程，因此无法唯 一地确定h(x)。
2019/4/12 16
一、秘密共享
由于Eve难以由自己的所谓ID(k)求出对应的h(ID(k)) ，因此他的所谓身份名（ID(k)，h(ID(k))）很难成 为“配套的”。 因此， {a0, a1, a2, …, at-2, at-1}， {a0’, a1’, a2’, …, at-2’, at-1’}， {a0”, a1”, a2”, …, at-2”, at-1”}， 三个系数向量中的任何两个向量都很难相互相等。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
为模n的平方剩余与分解n是等价的。
Copyright Yuan Email:hello@
19
南京航空航天大学网络研究室
密码协议
9.6 掷硬币协议
协议如下： a ① B选择p、q，计算n=pq；再选取满足 n 1 的随 机数a，将n和a发送给A。 ② A猜测a是模n的平方剩余或非平方剩余，并将结果 告诉B。 ③ B告诉A猜测正确或不正确，并将p、q发送给A。 ④ A检查p、q都是素数且n=pq。 显然，A猜中的概率是1/2。协议执行完后，A根 据p、q可求出a mod n的4个平方根（如果a是模n的 平方剩余），以检查B是否在A猜测完后将结果做了 修改。
Copyright Yuan Email:hello@
16
南京航空航天大学网络研究室
密码协给B. ⑤ B告诉A猜测不正确，并将u=2发送给A，A检验 u=2在1和21/2之间且满足4≡22 mod 21，A知道自 己输了。 ⑥ A公开n=21的因子p=3,q=7，B检验n=pq，知道自 己赢了。
Copyright Yuan Email:hello@
11
南京航空航天大学网络研究室
密码协议
9.6 掷硬币协议
在某些密码协议中要求通信双方在无第三方 协助的情况下，产生一个随机序列，因为A、B之 间可能存在不信任关系，因此随机序列不能由一 方产生再通过电话或网络告诉另一方。这一问题 可通过掷硬币协议来实现，掷硬币协议有多种实 现方式，下面介绍其中的3种。
协议必须是不模糊的，每一步必须明确定 义，并且不会引起误解。 协议必须是完整的，对每种可能的情况必 须规定具体的动作。
Copyright Yuan Email:hello@
3
南京航空航天大学网络研究室
密码协议
密码协议
密码协议，有时也称作安全协议，是以密码学为基 础的消息交换协议，其目的是在网络环境中提供各 种安全服务。密码学是网络安全的基础，但网络安 全不能单纯依靠安全的密码算法。安全协议是网络 安全的一个重要组成部分，我们需要通过安全协议 进行实体之间的认证、在实体之间安全地分配密钥 或其它各种秘密、确认发送和接收的消息的非否认 性等。 密码协议包含某种密码算法. 参与该协议的伙伴可能是朋友和完全信任的人，或 者也可能是敌人和互相完全不信任的人。 在协议中使用密码的目的是防止或发现偷听者和欺 骗.
Copyright Yuan Email:hello@
9
南京航空航天大学网络研究室
密码协议
9.5 不经意传输协议
2. “多传一”的不经意传输协议 设A有多个秘密，想将其中一个传递给B，使得只有B 知道A传递的是哪个秘密。设A的秘密是 s1,s2,„,sk，每一秘密是一比特序列。协议如下： ① A告诉B一个单向函数f，但对f-1保密。 ② 设B想得到秘密si，他在f的定义域内随机选取k个 值x1,x2,„,xk，将k元组(y1,y2,„,yk)发送给A， 其中 j i x j yj j i f xj
Copyright Yuan Email:hello@
14
南京航空航天大学网络研究室
密码协议
9.6 掷硬币协议
因u是B随机选取的，A不知道u，所以要猜测u只 能是计算模n下z的4个平方根，猜中的概率是1/2。 再考虑B如何能欺骗A，如果B在A猜测完后能够 改变u的值，则A的猜测必不正确，A可通过 z≡u2 mod n 检查出B是否改变了u的值，所以B要想改 变u的值就只能在x’和y’之间进行。而B若掌握x’ 和y’，就可通过gcd{x’-y’, n}或gcd{x’+y’, n}求出p 和q，说明B的欺骗与分解n是等价的。
Copyright Yuan Email:hello@
8
南京航空航天大学网络研究室
密码协议
9.5 不经意传输协议
协议如下： ① B随机选一数x，将x2 mod n发送给A。 ② A（掌握n=pq的分解）计算x2 mod n的4个平方根 ±x和±y，并将其中之一发送给B。由于A只知道 x2 mod n，并不知道4个平方根中哪一个是B选的x。 ③ B检查第②步收到的数是否与±x在模n下同余， 如果是，则B没有得到任何新信息；否则B就掌握 了x2 mod n的两个不同的平方根，从而能够分解n。 而A却不知究竟是哪种情况。 显然，B得到n的分解的概率是1/2。
Copyright Yuan Email:hello@
15
南京航空航天大学网络研究室
密码协议
9.6 掷硬币协议
例9.1 ① A取p=3,q=7，将n=21发送给B。 ② B在1和21/2之间，随机选择一个整数u=2，计算z≡22 mod n≡4并将z=4发送给A。 ③ A计算模21下z=4的4个平方根x=2,-x=19,y=5,-y=16， 取x’= 2，y’= 5。
Copyright Yuan Email:hello@
20
南京航空航天大学网络研究室
Copyright Yuan Email:hello@
10
南京航空航天大学网络研究室
密码协议
9.5 不经意传输协议
③ A计算zj=f-1(yj)(j=1,2,…,k)，并将zj sj(j=1,2,…,k) 发送给B。 ④ 由于zi=f-1(yi)=f-1(f(xi))=xi，所以B知道zi，因此可 从zi si获得si。 由于B没有zj(j≠i)的信息，因此无法得到sj(j≠i)，而A 不知k元组(y1,y2,…,yk)中哪个是f(xi)，因此无法确 定B得到的是哪个秘密。
Copyright Yuan Email:hello@
13
南京航空航天大学网络研究室
密码协议
9.6 掷硬币协议
④ A猜测u=x’或u=y’，或者A找出最小的i使得x’ 的第i个比特与y’的第i个比特不同，A猜测u的第 i个比特是0还是1。A将猜测发送给B。 ⑤ B告诉A猜测正确或不正确，并将u的值发送给A。 ⑥ A公开n的因子。
Copyright Yuan Email:hello@
y f
?
x
18
检查出来。
南京航空航天大学网络研究室
密码协议
9.6 掷硬币协议
3. 利用二次剩余掷硬币
设n是两个大素数p、q的乘积，即n=pq。整数 a满足0<a<n和gcd(a,n)=1，则有一半的a，其 Jacobi符号 a 1 ，而在满足 a 1 的所有 n n a中，只有一半是模n的平方剩余，而判断a是否
Copyright Yuan Email:hello@
7
南京航空航天大学网络研究室
密码协议
9.5 不经意传输协议
1. 基于大数分解问题的不经意传输协议 设A想通过不经意传输协议传递给B的秘密是 整数n（为两个大素数之积）的因数分解。这个问 题具有普遍意义，因为任何秘密都可通过RSA加 密，得到n的因数分解就可得到这个秘密。 协议基于如下事实： 已知某数在模n下两个不 同的平方根，就可分解n。
密码协议
对协议的攻击
被动攻击 主动攻击 被动骗子 主动骗子 协议对被动欺骗来说应该是安全的 合法用户可以发觉是否有主动欺骗
Copyright Yuan Email:hello@
6
南京航空航天大学网络研究室
密码协议
9.5 不经意传输协议
设A有一个秘密，想以1/2的概率传递给B，即 B有50%的机会收到这个秘密，另外50%的机会 什么也没有收到，协议执行完后，B知道自己是 否收到了这个秘密，但A却不知B是否收到了这个 秘密。这种协议就称为不经意传输协议。 例如A是机密的出售者，A列举了很多问题， 意欲出售各个问题的答案，B想买其中一个问题 的答案，但又不想让A知道自己买的是哪个问题 的答案。
第9章 密码协议
密码协议
协议
协议是一系列步骤 它包括两方或多方 设计它的目的是要完成一项任务
Copyright Yuan Email:hello@
2
南京航空航天大学网络研究室
密码协议
协议特点
协议中的每人都必须了解协议，并且预先 知道所要完成的所有步骤。 协议中的每人都必须同意遵循它。
Copyright Yuan Email:hello@
12
南京航空航天大学网络研究室
密码协议
9.6 掷硬币协议
1. 采用平方根掷硬币 协议如下： ① A选择两个大素数p、q，将乘积n=pq发送给B。 ② B在1和n/2之间，随机选择一个整数u，计算z≡u2 mod n，并将z发送给A。 ③ A计算模n下z的4个平方根±x和±y（因A知道n 的分解，所以可做到），设x’是x mod n和-x mod n中较小者，y’是y mod n和-y mod n中较小者， 则由于1<u<n/2，所以u为x’和y’之一。
Copyright Yuan Email:hello@
17
南京航空航天大学网络研究室
密码协议
9.6 掷硬币协议
2. 利用单向函数掷硬币 设A、B都知道某一单向函数f(x)，但都不知道该函数 的逆函数，协议如下： ① B选择一个随机数x，求y=f(x)并发送给A。 ② A对x的奇偶性进行猜测，并将结果告诉B。 ③ B告诉A猜测正确或不正确，并将x发送给A。 由于A不知道f(x)的逆函数，因此无法通过B发过来的 y得出x，即只能猜测x的奇偶性。而B若在A做出猜测 以后改变x，A可通过
Copyright Yuan Email:hello@
4
南京航空航天大学网络研究室
密码协议
协议的目的
计算一个数值想共享它们的秘密部分 共同产生随机序列 确定互相的身份 同时签署合同
Copyright Yuan Email:hello@
5
南京航空航天大学网络研究室