密码学导论˙第4章 数论基础 8学时 李卫海.

Presentation on theme: "密码学导论˙第4章 数论基础 8学时 李卫海."— Presentation transcript:

1 密码学导论˙第4章 数论基础 8学时 李卫海

2 本章目录 第四节 单向函数和单向陷门函数 第五节 有限域方程 第六节 秘密分享技术 第一节 有限域计算 第二节 素数相关问题
群、环、域、 模运算、有限域、多项式计算 欧几里德算法、扩展欧几里德算法 第二节 素数相关问题 素数、素因子分解 费马定理、欧拉函数、欧拉定理、求逆元 素性测试：WITNESS测试算法、Miller Rabin测试算法 第三节 本原元与指数方程 本原元、快速指数算法 第四节 单向函数和单向陷门函数 单向函数、单向陷门函数 离散对数 第五节 有限域方程 中国剩余问题：ax mod n =b 二次剩余问题、求解x2 mod p=a 第六节 秘密分享技术 拉格朗日插值法 6学时 密码学导论--中国科学技术大学

3 第一节 有限域计算 密码学导论--中国科学技术大学

4 一、群、环和域 群Group： 群G，记作{G, •}, 定义一个二元运算“•”的集合，G中每一个序偶(a,b)通过运算生成G中元素(a•b)，满足下列公理： (A1) 封闭性Closure：如果a和b都属于G，则a•b也属于G (A2) 结合律Associative：对G中的任意元素a，b，c，都有a•(b•c)=(a•b)•c成立 (A3) 单位元Identity element：G中存在一个元素e，对于G中任意元素a，都有a•e=e•a=a成立 (A4) 逆元Inverse element：对于G中任意元素a, G中都存在一个元素a-1，使得a•a-1=a-1•a=e成立 密码学导论--中国科学技术大学

5 有限群Finite Group和无限群Infinite Group：
如果一个群的元素是有限的，则该群称为有限群，且群的阶等于群中元素的个数；否则称为无限群 交换群（阿贝尔群）Abelian Group： 满足交换律的群 (A5) 交换律Commutative ：对于G中任意的元素a, b，都有a•b=b•a成立 循环群Cyclic Group: 如果群中的每一个元素都是一个固定的元素a(a∈G)的幂ak(k为整数)，则称群G为循环群。 元素a生成了群G，或者说a是群G的生成元。 密码学导论--中国科学技术大学

6 减法： 当群中的运算符是加法时，其单位元是0 a的逆元是-a 减法定义为：a–b=a+(-b) 密码学导论--中国科学技术大学

7 环Ring： 环R，记作{R,+,x}，定义二元运算加法“+”和乘法“×”的集合， R中任意元素a,b,c满足下列公理：
(A1-A5), R关于加法是交换群，单位元是0，a的逆元是-a (M1) 乘法封闭性：如果a和b都属于R，则ab也属于R (M2) 乘法结合律：如果a,b,c都属于R，则a(bc)=(ab)c (M3) 分配律：如果a,b,c都属于R，则a(b+c)=ab+ac或(a+b)c =ac+bc 密码学导论--中国科学技术大学

8 交换环Commutative Ring ：满足下列条件的环
(M4) 乘法交换律：对R中任意元素a,b，都有ab=ba成立 整环Integral Domain ：满足下列条件的交换环 (M5) 乘法单位元：在R中存在元素1，使得对于R中任意元素a，都有 a1=1a成立 (M6) 无零因子：若元素a,b满足ab=0，则必有a=0或b=0 密码学导论--中国科学技术大学

9 域Field： 域F，记作{F,+,×}，定义为满足下列关系的整环：
(M7) 乘法逆元Multiplicative inverse: 对F中每个元素a（除0以外），存在元素a-1满足aa-1=(a-1)a=1 除法： 对F中任意元素a和任意非零元素b，定义为a/b=a(b-1) 密码学导论--中国科学技术大学

10 约束关系 群：A1加法封闭；A2加法结合律；A3加法单位元；A4加法逆元 交换群：A5加法交换律
环：M1乘法封闭；M2乘法结合律；M3分配率 交换环：M4乘法交换律 整环：M5乘法单位元；M6无零因子 域：M7乘法逆元 密码学导论--中国科学技术大学

11 二、模运算 给定任意正整数n和a，用a除以n，得到的商q和余数r满足如下关系： a=qn + r 0≤r<n; q=a/n
x表示小于等于x的最大整数 例: 11=1×7+4, r=4; -11=(-2)×7+3, r=3 n 2n 3n qn (q+1)n 1 2 a r 密码学导论--中国科学技术大学

12 同余 (congruence) 给定整数a, b及n≠0, 当且仅当a-b=kn时，a与b是模n同余，记为 a≡b mod n
a≡b mod n当且仅当 a mod n = b mod n 若a是整数，n是正整数，定义a除以n的余数为a模n 对于任意整数a，总可写出：a=a/n×n+(a mod n) 例：11 mod 7 = 4 -11 mod 7 = 3 密码学导论--中国科学技术大学

13 因子 Divisors 如果a=mb, 其中 a,b,m 为整数，则当b≠0时，称b能整除a, b是a的一个因子，或a除以b余数为0，记为b|a 例：24的正因子有1, 2, 3, 4, 6, 8, 12和24。 以下关系成立 如果a|1, 则a=±1 如果a|b，且b|a, 则a=±b 任何b≠0能整除0 如果b|g，且b|h，则对任何整数m和n，有b|(mg+nh) 例：7|14 and 7|63，则7|(3×14 + 2×63) 如果a≡0 mod n，则n|a 密码学导论--中国科学技术大学

14 同余的性质 如果n|(a-b), 则a≡b mod n 反身性：a≡a mod n 对称性：a≡b mod n，则 b≡a mod n
证明：如果n|(a-b), 则有(a-b)=kn, k为某些整数， 所以a=b+kn。 故a mod n = (b + kn) mod n = b mod n 反身性：a≡a mod n 对称性：a≡b mod n，则 b≡a mod n 传递性：a≡b mod n 且 b≡c mod n，则a≡c mod n 密码学导论--中国科学技术大学

15 逆元 加法逆元(-w) 乘法逆元(w-1) 对每一个w∈Zn，存在一个z，使得w+z≡0 mod n，则 z即为加法逆元-w
若p为素数，对每一个w∈Zp，w与p互素，存在一个z ，使得w×z≡1 mod p。z即为乘法逆元w-1 用w乘以Zp中的所有数模p，余数将以不同次序涵盖Zp中的所 有数，其中必有一个为1。这个数就是w的乘法逆元， w-1 模数不是素数时，某些但非全部整数存在一个乘法逆 元。如果gcd(a, n)=1, 则能在Zn中找到b，使得a×b≡1 mod n。b即为乘法逆元a-1 密码学导论--中国科学技术大学

16 例：模8的运算 乘法表 加法表 逆元表 ＋ 1 2 3 4 5 6 7  1 2 3 4 5 6 7 w 1 2 3 4 5 6 7 -w
1 2 3 4 5 6 7  1 2 3 4 5 6 7 逆元表 w 1 2 3 4 5 6 7 -w w-1 -

17 模算术运算 (a1 op a2) mod n =[(a1 mod n )] op (a2 mod n)] mod n
(a+b) mod n = (a mod n + b mod n) mod n (a-b) mod n = (a mod n - b mod n) mod n (a•b) mod n = (a mod n • b mod n) mod n 如果 a=b mod n且 c=d mod n，则 a+c=(b+d) mod n a-c=(b-d) mod n a•c=(b•d) mod n 如果ac=bd mod n且c=d mod n，gcd(c,n)=1，则a=b mod n 例： 3*2=1*2 mod 4 且 2=2 mod 4, 但3≠1 mod 4 密码学导论--中国科学技术大学

18 模运算的性质 剩余类集(Residues) 例：n=10， 定义比n小的非负整数集合为Zn： Zn ={0,1,…,(n-1)}
模n的完全剩余类集(Complete Set of Residues mod n)：如果对每个整数a，在集合{r1,r2,…,rn}中恰有一个余数ri，使得 a mod n=ri，则称{r1,r2,…,rn}为模n的完全剩余类集，{0,1,…,n-1}形成模n的完全剩余类集。 模n的缩剩余类集(Reduced set of Residues mod n)：完全剩余集的子集，其中的元素都和n互素（包括1） 例：n=10， 模n的完全剩余集是{0, 1, 2,…,9} 模n的缩剩余集是 {1, 3, 7, 9} 密码学导论--中国科学技术大学

19 三、有限域GF(p) Galois Fields
有限域在密码学中扮演重要角色 有限域的元素个数是一个素数的幂pn, n 为正整数，一般记为GF(pn)，即Galois fields, 模pn. 关注两种特殊情形 n=1时的有限域，即GF(p) p为2时的有限域，即GF(2n) 最简单的有限域是GF(2)，代数运算简述如下：  w -w w-1 加 乘 求逆 密码学导论--中国科学技术大学

20 （1）伽罗瓦域 GF(p) 例，GF(7)上的运算
当模数是素数p，每个整数a∈[1,p-1]与p互素，因而都有唯一的模p的乘法逆。这一组模p的整数，加上算术运算，被称为有限域—伽罗瓦域 GF(p) 的空间是模p的完全剩余类Zp：{0,1, … , p-1} 例，GF(7)上的运算 加法表 乘法表 逆元表 ＋ 1 2 3 4 5 6  1 2 3 4 5 6 w 1 2 3 4 5 6 -w w-1 - 密码学导论--中国科学技术大学

21 （2）伽罗瓦域 GF(2n) 系数是二进制0和1的多项式，最高不超过n-1次项
一个元素a可被表示成一个位矢量，长度为n，(an-1,…,a1, a0)，每一个长度为n的矢量都对应着GF(2n)中的不同元素 例如二进制数110012在GF(25)中可以记作x4+x3+1 如何计算？ 密码学导论--中国科学技术大学

22 四、多项式计算 多项式 三种多项式运算： 使用代数基本规则的普通多项式运算； 系数在Zp中的多项式运算；
系数在GF(2)中，且多项式被定义为模一个n次多项式m(x)：有限域GF(2n)上的计算 密码学导论--中国科学技术大学

23 普通多项式运算 加法和减法规则：对应项系数的加或减 乘法规则：各项相乘
例：令f(x) = x3 + x2 + 2和g(x) = x2 - x + 1 f(x) + g(x) = x3 + 2x2 - x + 3 f(x) - g(x) = x3 + x + 1 f(x) ×g(x) = x5 + 3x2 - 2x + 2 f(x) / g(x) = x + 2 ……x 密码学导论--中国科学技术大学

24

25 系数在Zp中的多项式运算 系数进行模p运算 模可以是任意素数，一般取2，此时 所有系数为0或1
例：令 f(x) = x3 + x2 + 1和 g(x) = x2 + x + 1 f(x) + g(x) = x3 + x f(x) ×g(x) = x5 + x + 1 密码学导论--中国科学技术大学

26

27 有限域GF(2n)上的多项式计算 有助于二进制计算机实现 有限域GF(2n) 非零元素有逆 系数对2取模运算 最高次数小于n
可以用扩展Euclidean算法求逆 密码学导论--中国科学技术大学

28 素多项式 任何多项式可以写为：f(x)=q(x)g(x)+r(x) 若不存在余式，则称g(x)整除f(x)，g(x)|f(x)
r(x)=f(x) mod g(x) 若不存在余式，则称g(x)整除f(x)，g(x)|f(x) 若f(x)除了它本身和1外，不存在其它因式，则称f(x)是不可约多项式，或既约多项式、素多项式 系数在GF(p)中，以素多项式取模的多项式构成一个域 密码学导论--中国科学技术大学

29 例：以(x3+x+1)为模的多项式运算 + 1 x x+1 x2 x2+1 x2+x x2+x+1  1 x x+1 x2 x2+1
1 x x+1 x2 x2+1 x2+x x2+x+1  1 x x+1 x2 x2+1 x2+x x2+x+1

30 计算上的考虑 系数是0或1，多项式可以用一个比特串表示 例：在GF(23)中， 加法即比特串的异或运算 乘法即比特串的移位及异或运算
多项式取模的运算：重复用既约多项式减掉最高次项 例：在GF(23)中， (x2+1)可以表示为1012 ，(x2+x+1)可以表示为1112 加法：(x2+1) + (x2+x+1) = x ； 1012⊕1112 = 0102 乘法：(x+1)×(x2+1) = x3+x2+x+1 ； 0112×1012 = (1012)<<1⊕(1012)<<0 =11112 多项式取模：(x3+x2+x+1) mod (x3+x+1) = x2 11112 mod = 11112⊕10112= 1002 密码学导论--中国科学技术大学

31 例：在GF(23)中计算d=ab, a=1112, b=1002, p=10112
例：在GF(23)中计算d=a2, a=1012, p=10112 aa = 1012×1012 = ⊕1012 =100012 d = a2 mod p = ⊕ mod = 1112 例：在GF(23)中计算d=ab, a=1112, b=1002, p=10112 ab=1112  1002 = ab模p： mod = 0012 即1112  1002 mod = 0012，在模10112时a与b互逆。

32 五、欧几里德算法Euclidean Algorithm
两个正整数的最大公约数(Greatest Common Divisor)：gcd(a, b) 定理：对任何整数a和b，都有gcd(a,b)=gcd(a mod b, b) 证明： 不妨设a>b，可以令a=kb+r，a mod b = r 若d是a、b的公因子，则d|kb，必然有d是r、b的公因子 若d是b、r的公因子，显然d|a，即d也是a、b的公因子 因此定理成立 若a和b只有唯一的正公因子1，则称整数a和b是互素的，即gcd(a, b)=1 密码学导论--中国科学技术大学

33 例，欧几里德算法求gcd(1970,1066) 1970 = 1 x gcd(1066, 904) 1066 = 1 x gcd(904, 162) 904 = 5 x gcd(162, 94) 162 = 1 x gcd(94, 68) 94 = 1 x gcd(68, 26) 68 = 2 x gcd(26, 16) 26 = 1 x gcd(16, 10) 16 = 1 x gcd(10, 6) 10 = 1 x gcd(6, 4) 6 = 1 x gcd(4, 2) 4 = 2 x gcd(2, 0) 1970 1066 904 162 94 68 26 16 10 6 4 2 a b a mod b … d

34 求d=gcd(a,b)，并解ax+by=d
扩展欧几里德算法： ax1+by1 (x1=1,y1=0) = a ax2+by2 (x2=0,y2=1) b a(x1-qx2)+b(y1-qy2) a mod b = a-bq … ax+by d ax'+by'

35 例：a=4864, b=3458 q x y d - 1 4864 3458 -1 1406 2 -2 3 646 5 -7 114 -27 38 76 32 -45 -91 128 注意：若b为素数，且作为模数，则等价于求解ax mod b=1 4864× ×(-45)=38 4864×(-91)+3458×128=0

36 在GF(p)中求乘法逆元 求y=b-1 mod p，即求解px+by=1 mod p 扩展欧几里德算法： by1 (y1=0) = P
b(y1-qy2) p mod b = p-bq … by 1 密码学导论--中国科学技术大学

37 例：求550在GF(1759)里的乘法逆元 q y d - 1759 1 550 3 -3 109 5 16 21 -339 4 355

38 多项式的欧几里德算法 c(x)=GCD(a(x),b(x)) c(x)是能同时整除a(x)和b(x)的次数最高的多项式
例：求GCD((x8+x4+x3+x+1),(x7+x+1)) x8+x4+x3+x+1 x7+x+1 x4+x3+x2+1 x 1 密码学导论--中国科学技术大学

39 第二节 素数相关问题 密码学导论--中国科学技术大学

40 一、素数 素数：仅能被1和它自身整除的数 素数是现代数论的核心内容 不能写成其它数字乘积的形式 1是素数?
例如：2,3,5,7是素数；4,6,8,9,10不是素数 素数是现代数论的核心内容 密码学导论--中国科学技术大学

41 素因子分解 因子分解是将数字n写为乘积形式：n=a×b×c×… 因子分解比因子相乘要困难得多 素因子分解：将整数a写为素数乘积的形式
其中p1<p2<…<pt是素数，ai是正整数 3600=24×32×52 密码学导论--中国科学技术大学

42 任一正整数可通过列出所有素因子的非零指数分量来表示
例：12可以表示为{a2=2, a3=1} 例：18可以表示为{a2=1, a3=2} 两个数的乘法等同于对应指数分量的加法： K = mn → kp = mp + np 对所有p 例：216=12×18=(22×31)×(21×32)=23×33 密码学导论--中国科学技术大学

43 整除和最大公约数GCD 整除：任何整数仅能被对应素数分量小于等于它的另一个整数整除
即a|b 对所有p，ap≤bp 例：a=12, b=36, 12|36, 12=22×31, 36=22×32 a2=2=b2, a3=1≤2=b3 最大公约数：k=gcd(a,b)所有kp=min(ap,bp) 例：300=22×31×52, 18=21× gcd(18,300)=21×31×50=6 两个数a, b互素是指它们公因子仅有1 密码学导论--中国科学技术大学

44 二、费马定理和欧拉定理 费马定理Fermat's Theorem：若p是素数，则对任意a，gcd(a,p)=1，有ap-1mod p = 1
证明： a×2a×…×((p-1)a) = (p-1)! ap-1 =[(a mod p)×(2a mod p)×…×((p-1)a mod p)] mod p =(p-1)! mod p 所以(p-1)! ap-1 = (p-1)! mod p (p-1)!与p互素，两边消去(p-1)!，得证 密码学导论--中国科学技术大学

45 费马定理等价形式：若p是素数，则 ap≡a mod p 例：a=7, p=19
72=49≡11 mod =121≡7 mod 19 78=49≡11 mod =121≡7 mod 19 ap-1=718=716×72≡7×11≡1 mod 19 ap=719=718*7=7 mod 19 密码学导论--中国科学技术大学

46 欧拉函数 欧拉函数Φ(n)：比n小且与n互素的正整数的个数，即模n的缩剩余类集中元素之个数。 若p是素数，则Φ(p)=p-1 n Φ(n)
11 10 21 12 2 4 22 3 13 23 14 6 24 8 5 15 25 20 16 26 7 17 27 18 28 9 19 29 30 密码学导论--中国科学技术大学

47 Φ(n)=Φ(p)Φ(q)=(p-1)(q-1) 证明：
若p和q是素数，n=pq，则 Φ(n)=Φ(p)Φ(q)=(p-1)(q-1) 证明： 不与n互素的数有p,2p,…,(q-1)p, q,2q,…,(p-1)q Φ(n)=pq-1-[(q-1)+(p-1)]=pq-(p+q)+1=(p-1)(q-1) 推广：只需p,q互素，即有Φ(n)=Φ(p)Φ(q) 例：Φ(35)= Φ(5)Φ(7)=4×6=24 p,q互素，则n=pq是它们的最小公倍数。在{p, 2p, …, (q-1)p, q, 2q, …, (p-1)q}中没有重复元素 密码学导论--中国科学技术大学

48 素数p，pe的完全剩余类集中共有pe个数，p的倍数有pe-1个，则Φ(pe)=pe–pe-1=pe-1(p-1)
一般说来，对任意n， Φ(n)由下式给出： 其中pi是素数 例：Φ(24)=Φ(23)Φ(3)=22(2-1)30(3-1)=8 密码学导论--中国科学技术大学

49 欧拉定理 Euler’s Theorem 欧拉定理 Euler's Theorem：对满足gcd(a,n)=1的任意a和n，有aΦ(n) mod n=1 证明： 令{r1, …, rΦ(n)}是模n的缩剩余集 则{ari mod n}是{ri}的置换形集合 因此， 即得aΦ(n) mod n = 1 费马定理是欧拉定理的特例 密码学导论--中国科学技术大学

50 欧拉定理的等价形式：aΦ(n)+1 ≡ a (mod n) 推论：akΦ(n)+1 ≡ a mod n
若ax mod n =1, gcd(a,n)=1，则x=aΦ(n)-1 mod n 证明： ax mod n = 1 = aΦ(n) mod n 两边同除a，即同乘a的逆，得x=aΦ(n)-1 mod n 密码学导论--中国科学技术大学

51 计算乘法逆元 可以用扩展Euclidean算法求逆 可以根据Euler’s定理求逆：a-1 = aΦ(n)-1 mod n
如果Φ(n)已知，则a的逆元素可用快速指数运算法解 设z=z020+z121+z222+…，zi=0或1 az=(…((1•azn-1)2•azn-2)2•azn-3…)2•az0 如果p是素数, a-1 = ap-2 mod p 密码学导论--中国科学技术大学

52 在GF(2n)中求逆 除了0，长度为n每一个多项式都与p(x)互素，因此，Φ(p(x))=2n-1
a-1 = aΦ(p(x))-1 mod p(x) = a2n-2 mod p(x) 例：GF(23)，a=100，p(x) =1011 Φ(p(x))=23-1=7 a-1 = aΦ(p(x))-1 mod p(x) = mod 1011 = (100)6 mod 1011 = 111 密码学导论--中国科学技术大学

53 三、素性测试 寻找大素数是密码学中的一个常见操作 传统方法是逐个尝试除法寻找因子 或者用基于素数性质的统计素性测试
用小于等于该数平方根的所有素数去除 只适合找小素数 或者用基于素数性质的统计素性测试 所有的素数都满足相应性质 存在一些合数（称为伪素数）也满足相应性质 或者使用慢一些的确定性素性测试AKS 密码学导论--中国科学技术大学

54 素数的性质 素数的性质1（ WITNESS测试算法）： 算法：测试n是否为素数：
若n是素数，a是正整数，a<n，则a2 mod n=1当且仅当a mod n=1或a=-1=n-1 mod n 算法：测试n是否为素数： 1. 任选随机整数a，1<a<n–1 2. if a2 mod n = 1 then return (“composite"); 3. else return ("maybe prime") 密码学导论--中国科学技术大学

55 素数的性质2（Miller Rabin测试算法）：
对奇数n≥3， (n-1)可表示为n-1=2kq，k>0，q是奇数 若n是素数，则序列(aq, a2q, …, a2k-1q)mod n中或者第一个元素为1，或者某个元素为n-1；否则n是合数。 证明： 考察序列aq, a2q, …, a2k-1q, a2kq 若n是素数，则由费马定理可知，an-1 mod n=a2kq mod n=1 。即此序列中至少会有一个1 序列的后一项是前一项的平方，则第一个1或者是第一项，或 者其前面一项为-1 条件成立，并不意味着n一定是素数。 密码学导论--中国科学技术大学

56 Miller Rabin测试算法 测试n是否为素数： 1. 计算奇数q和整数k，使得(n-1)=2kq
2. 任选随机整数a，1<a<n-1 3. if aq mod n = 1 then return ("maybe prime"); 4. for j = 0 to k-1 do 5. if (a2jq mod n = n-1) then return("maybe prime") 6. return ("composite") 密码学导论--中国科学技术大学

57 检测概率 若Miller-Rabin算法返回“合数”，则该数确定不是素数 伪素数检测结果为“不确定”的概率小于1/4
否则可能是素数，可能是伪素数 伪素数检测结果为“不确定”的概率小于1/4 若随机选择a，重复测试t次都返回不确定，则n为素数的概率1-4-t 例，t=10，则此概率> 取足够大的t，若检测结果均不确定，则可以相信n是素数 密码学导论--中国科学技术大学

58 n=29 (n-1)=28=22(7)=2kq 取a=10, 计算107 mod 29=17, 既不为1也不为28。计算(107)2 mod 29=28, 测试算法返回不确定 取a=2, 27 mod 29=12, 214 mod 29=28, 返回不确定 对1到28之间的所有整数a进行测试，都会返回不确定。判定n为素数 n=13x17=221 n-1=220=22(55)= 2kq 取a=5, 555 mod 221 =112,既不为1也不为220。(555)2 mod 221=168, 返回合数 如果a=21, 2155 mod 221=200, (2155)2 mod 221=220, 返回不确定，表明221可能是素数 事实上，1到220这220个整数中，a有6个整数会返回不确定：1, 21, 47, 174, 200和220 对于221，11%的概率会返回不确定 密码学导论--中国科学技术大学

59 素数的分布 数论给出： 偶数和5的倍数无需测试，实际确定一个素数只需测试0.4 ln(n)个数字。
第n个素数pn位于n·ln(n)<pn<n[ln(n)+ln(ln(n))], n≥6 偶数和5的倍数无需测试，实际确定一个素数只需测试0.4 ln(n)个数字。 例：若寻找大小约2200的素数，需要测试0.4 ln(2200) ≈55次 这仅是平均统计结果。素数有时会离得很近，有时会离得很远 1,000,000,000,061和1,000,000,000,063都是素数 1001!+2, 1001!+3, …, 1001!+1000, 1001!+1001是1000个连续的合数 密码学导论--中国科学技术大学

60 第三节 本原元与指数函数 密码学导论--中国科学技术大学

61 一、本原元 根据欧拉定理，aΦ(n) mod n=1，则至少有一个整数m满足：am mod n =1, 即m=Φ(n)
一般地，Φ(n)是一个数模n的可能的最高指数 如果数g满足gi mod n（0<i<n）各不相同，则称g为n的本原元（ Primitive Element、本原根、素根、原根、生成元） 若a是n的本原元，则a,a2,…,aΦ(n)是模n各不相同的，且均与n互素 密码学导论--中国科学技术大学

62 例：试找出模19的所有本原元 本原元 可以发现，对于素数p，非本原元的元素的周期都是p-1的因子。 a a2 a3 a4 a5 a6 a7
8 16 13 7 14 9 18 17 15 11 3 6 12 5 10 本原元 可以发现，对于素数p，非本原元的元素的周期都是p-1的因子。 密码学导论--中国科学技术大学

63 本原元的寻找 本原元：对模素数p， 例：p=11,Φ(p-1)=Φ(10)=4, 即有4个本原元
当g为本原元且a与p-1互素时，ga mod p也是本原元 模p的本原元素个数为欧拉函数Φ(p-1) 例：p=11,Φ(p-1)=Φ(10)=4, 即有4个本原元 若已知g=2为模p的本原元，且1, 3, 7, 9与p-1互素 则21=2，23=8，27=7，29=6 mod 11均为模11之本原元素 找到一个本原元素后很容易找到所有本原元素，问题是如何找到第一个本原元素 密码学导论--中国科学技术大学

64 本原元的判定 本原元的存在性：如果n不为2,4，也不具有pe,2pe 的形式，p是奇素数，e是正整数，则不存在模n的本原元
本原元的判定：对素数p，整数b为模p的本原元，当且仅当对所有能整除p-1的素数q，有 b(p-1)/q ≠ 1 mod p 本原多项式的判定：设P是模p[x]中的n次多项式。令N=pn-1，则P是本原的，当且仅当xN=1 mod P，且对任何能整除N的素数q，xN/q≠1 mod P 密码学导论--中国科学技术大学

65 二、生成元表示的有限域 定义有限域GF(2n)的另一种等价形式 有限域GF(2n) 中前n+1个元素为0,g0,g1,…,gn-1
设有限域GF(2n)的既约多项式为f(x)，则生成元g满足f(g)=0 阶为q=2n的有限域中，生成元g的幂：g0,g1,…,gq-2构成有限域的所有非零元素 有限域GF(2n) 中前n+1个元素为0,g0,g1,…,gn-1 gn = f(g)-(f(g)-gn) = f(g)-gn gn+1到gq-2需要计算 gq-1 = 1 乘法运算简化为指数相加 gk = gk mod (q-1) 密码学导论--中国科学技术大学

66 例：模x3+x+1的域GF(23)的生成元及运算
指数表示 多项式表示 二进制表示 十进制表示 000 g0(=g7) 1 001 g1 g 010 2 g2 100 4 g3 g+1 011 3 g4 g2+g 110 6 g5 g2+g+1 111 7 g6 g2+1 101 5

67 + 1 g g2 g3 g4 g5 g6 g+1 g2+g g2+g+1 g2+1 x2  1 g g2 g3 g4 g5 g6 g+1 g2+g g2+g+1 g2+1

68 三、指数函数 定义：令G为有限乘法群，g∈G，则对于所有整数x，E(x,g)=gx∈G，为指数函数
通常，令G={1,…,p-1}, p为素数，则E(x,g)=gx mod p为指数函数 特性1：周期性（Periodicity） 令序列<E(x,g)>={g0,g1,g2,…}为g所产生之序列。因为G是有限群，故E(x,g)产生之序列为周期序列 存在最小正整数T，使得E(T,g)=gT=1=g0，称T为g在G中的序(order)。对于所有g，T必定整除p-1 密码学导论--中国科学技术大学

69 例：p=11, g=2, <E(x,g)>={20,21,…,210}={1,2,4,8,5,10,9,7,3,6,1} 即：20=1 mod =9 mod 11 21=2 mod =7 mod 11 22=4 mod =3 mod 11 23=8 mod =6 mod 11 24=5 mod =1 mod 11 25=10 mod 11 所以T=10=11-1=p-1

70 特性4：乘法性(Multiplicative Property)
特性2：本原元问题 若找到一个本原元，容易找到其它本原元。问题是如何找到第一个本原元。 特性3：交换性 指数函数满足交换性，因为： E(x,E(y,g))=E(x,gy)=(gy)x=gyx E(y,E(x,g))=E(y,gx)=(gx)y=gxy ∴ E(x,E(y,g))=E(y,E(x,g)) 特性4：乘法性(Multiplicative Property) E(x,g1)E(x,g2)=g1xg2x=(g1g2)x=E(x,g1g2) 密码学导论--中国科学技术大学

71 特性5：非对称性(Asymmetric Property)
∵E(x,-g)=(-g)x=(-1)xgx=(-1)x E(x,g) ∴若x为偶，则满足偶对称；若x为奇，则满足奇对称 特性6：乘法逆元素(Multiplicative Inverse) 若T为g之序，则对于所有x，0≤x<T, E(x,g-1)=E(T-x,g) 因为：E(x,g-1)=g-x=1•g-x= gT•g-x=gT-x= E(T-x,g) 这是一种求乘法逆元素的方法，g-1=gT-1 (这里x=1) 特性7：可逆性 若T为g∈G之序，x­-1为x在模T时的乘法逆元素， 即xx-1=1 mod T = kT+1 则E(x,E(x-1,g))=E(x-1,E(x,g))= gxx-1 mod p =gkT+1=(gT)k•g=1kg=g mod p 密码学导论--中国科学技术大学

72 特性8：快速指数运算法 gx 设x为n比特(xn-1, xn-2,…,x1, x0)2
4 3 8 6 5 1 10 11 100 101 110 1000 1001 1010 1100 111 12 10 9 7 设x为n比特(xn-1, xn-2,…,x1, x0)2 gx=g^[(…(xn-1×2)+xn-2)×2…+x1)×2+x0] =(…(gxn-1)2*gxn-2)2˙gxn-3…)2˙gx0 共需n-1次平方及w(x)-1次乘法。w(x)是x中1的个数，平均而言w(x)=n/2。因此平均需要1.5n-2次乘法(平方算一次乘) 密码学导论--中国科学技术大学

73 f=ab mod n b=bkbk-1…b1b0 例：7560 mod 561

74 第四节 单向函数与单向陷门函数 密码学导论--中国科学技术大学

75 一、离散对数 离散对数问题DLP(Discrete Logarithms Problem) 若a是本原根，则离散对数一定存在，否则未必
指数运算的逆运算： 求解ax = b mod p，记为x=logab mod p或x=loga,p(b) 若a是本原根，则离散对数一定存在，否则未必 log3 4 mod 13 (x满足3x = 4 mod 13) 无解 log2 3 mod 13 = 4 指数运算是简单的，而离散对数是困难的 离散对数运算与大数分解同等困难 密码学导论--中国科学技术大学

76 离散对数的计算 考虑方程y = gx mod p 若给定整数g, x和p，可以直接用快速指数算法求出y
但是若给定p, g及y, 求x，则为DLP问题 最快方法的难度阶为L(p)=exp{(ln p)1/3(ln(ln p))2/3} 例：模19的离散对数 a 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 log2a mod 19 log3a mod 19 log10a mod 19 log13a mod 19 log14a mod 19 log15a mod 19 密码学导论--中国科学技术大学

77 Index Calculus求离散对数 求解ax=b (mod p)，p是大素数，a是本原元
任选m个“小”素数做基底S={p1,p2,…,pm} 构建同余方程组并求解：随机选取m个随机整数kj(0≤kj≤p,1≤j≤m)，计算 解上述m个线性方程，求得logapi (mod p-1) 随机选取整数r，计算 密码学导论--中国科学技术大学

78 例，求x=log2108 (mod 269) 解： 选取S={2,3,7,11} 构建同余方程 求解上述三个方程，得 随机取r=188，得

79 例，求x=log2108 (mod 269) 解： 事实上，108= 2 2 × 3 3 ，log108=2+3 log 2 3。因此，只需知道3的对数值即可。 21~28模268均不含因子3，尝试 2 9 =512=243= 3 5 mod268，很巧，仅含有素因子3 只需求解5 log 2 3=9 mod 268 通过求逆元，易得 log 2 3=161×9=109 mod268 因此，log2108=2+3×109=329=61 mod268

80 二、单向函数和单向陷门函数 定义：单向函数(One-way Function) 一函数f若满足下列条件，则称f为单向函数：
(1)对于所有属于f之域的任一x，容易计算y=f(x)； (2)对于几乎所有属于f之域的任一y，求得x，使y=f(x), 则在计算上不可行。 定义：单向陷门函数(One-way Trapdoor Function) “可逆”函数F若满足下列二条件，则称F为单向陷门函数： (1)对于所有属于F之域的任一x，容易计算F(x)=y； (2)对于几乎所有属于F之域的任一y，如果获得暗门信息(trapdoor)，则容易求出x=F-1(y)；否则求解x=F-1 (y)在计算上不可行。F-1为F之逆函数。 密码学导论--中国科学技术大学

81 单向函数举例 离散对数问题DLP(Discrete Logarithm Problem)
令素数p满足p-1含有另一大质数q (q整除p-1)，及一整数g, 1<g<p-1。 若给定整数x，求y=gx mod p是简单的 但是若给定p, g及y，求x，则为DLP问题，是困难的。 因数分解问题(Factorization Problem) 给定大素数 p和q，求n=p×q , 只要一次乘法 给定n，求p和q，即为因数分解问题FAC，最快方法需要T(n)=exp{c(ln n ln(ln n))½} 次运算，其中c为大于1的正整数。若p≈n，解离散对数比因数分解难 密码学导论--中国科学技术大学

82 背包问题(Knapsack Problem)
给定有限个自然数序列集合B=(b1,b2,…bn)及二进制序列x=(x1,x2,…xn), xi∈(0,1), 求S＝∑xibi最多只需n-1次加法； 但若给定B和S，求x则非常困难。 穷举时有2n种可能，当n很大时为计算上不可行。 密码学导论--中国科学技术大学

83 第五节 有限域方程 密码学导论--中国科学技术大学

84 一、一元一次方程 求解ax mod n = b问题 考虑方程ax mod n = b，令g=gcd(a, n)，则
当g|b时，方程a·x mod n=b 有g个解， 解形如x=[(b/g)x0+t(n/g)] mod n，t=0,1,…,g-1， 其中，x0是(a/g)x mod (n/g)=1的解。 密码学导论--中国科学技术大学

85 证明： 假如a·x mod n = b 在[1, n-1]中有一个解，则n|(ax-b)。 因为g|n，g|ax，则g|b一定成立。否则等式无解。 gcd(a/g,n/g)=1, 即等式(a/g)x mod (n/g)=1有唯一的解x0：x0∈[1,(n/g)-1] 则(a/g)x mod (n/g)=(b/g)在[1,(n/g)-1]中的一个解是 x1=(b/g)x0 mod (n/g) 上式被g乘，即x1是ax mod n =b的一个解。 对任何x∈[1, n-1], x=x1 mod (n/g)都是ax mod n =b的解。 所有解由下式给出：x = x1 + t(n/g)，t=0,1,…,g-1 密码学导论--中国科学技术大学

86 先求x0：(a/g)x mod (n/g)=1  3x mod 5=1, x0=2
解： g=gcd(6,10)=2，2|4，应该有两个解 先求x0：(a/g)x mod (n/g)=1  3x mod 5=1, x0=2 根据x=[( b/g)x0 + t(n/g)] mod n，t=0,1,…,g-1 =[2x0 + 5t] mod 10，t=0,1,…,g-1 =[4 + 5t] mod 10，t=0,1,…,g-1 则 x=4, t=0； x=9, t=1 密码学导论--中国科学技术大学

87 令n=d1d2…dt，di两两互素，则f(x) mod n=0，当且仅当f(x) mod di=0 (1≤i≤t)
解决ax mod n=b的问题： 等价于为联立方程组(ax-b) mod di=0找一个公共解，即ax mod di=b mod di (1≤i≤t) 从一组独立解x1,…,xt(xi是f(x) mod di=0的解)，为f(x) mod di=0 构造一个公共解x，x就是f(x) mod n=0的解 若x是f(x) mod n=0的解 令xi = x mod di，i=1,…,t，则f(xi) mod di=0 f(x)=kn=kd1d2…dt, 两侧对di取模，则有f(x) mod di=f(x mod di) mod di=f(xi) mod di=0 密码学导论--中国科学技术大学

88 整数的CRT表示 某一范围内的整数可通过它对两两互素的整数取模所得的余数来重构
例：Z10=(0,1,…,9)，对2和5(10=25)取模重构 假设数x的余数r2=0且r5=3，则唯一解x=8. 整数的CRT表示形式： M=m1×m2×…×mk，mi两两互素 ZM中任一整数A对应一个k元组，元素均在Zmi中，对应关系为A↔(a1,a2,…,ak), ai = A mod mi, 1≤i≤k 将整数A映射为k维空间中的一个点 密码学导论--中国科学技术大学

89 CRT 中国余数定理(Chinese Remainder Theorem) 证明：
令d1,…,dt两两互素，n=d1d2…dt，则x mod di=xi，i=1,…,t 在[0,n-1]中有一个公共解x。 证明： 对每一个i，i=1,…,t,有gcd(di,n/di)=1，存在yi满足 (n/di)yi mod di=1 (n/di)yi mod dj=0,j≠i (因为dj是(n/di)的一个因数) 令x=[∑i(n/di)yixi] mod n. 则x mod di=(n/di)yixi mod di=xi 密码学导论--中国科学技术大学

90 向量表示： m1 m2 m3 A a1 a2 a3 整数的CRT M=m1m2…mk 密码学导论--中国科学技术大学

91 孙子定理（孙子算经，3－5世纪） 今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何。 x mod 3=2
n=357=105 (5*7)((5*7)-1mod3)=35*35-1mod3=35*2=70 (3*7)((3*7)-1mod5)=21*21-1mod5=21*1=21 (3*5)((3*5)-1mod7)=15*15-1mod7=15*1=15 x=2*70+3*21+2*15 mod 105=23 三人同行七十稀 五树梅花二一枝 七子团圆正月半 除零百五便可知 密码学导论--中国科学技术大学

92 例：求解3x mod 10=1 3x mod 10=1，10=25，d1=2，d2=5 3x mod 2=1，解为x1=1
应用CRT找下列方程组的公共解： x mod 2=1 x mod 5=2 5*(5-1mod2)=5*1=5 2*(2-1mod5)=2*3=6 x=5*1+6*2 mod 10=7 密码学导论--中国科学技术大学

93 二、二次剩余问题 定义：若正整数a，gcd(a,n)=1，满足x2 mod n=a，即二次方程x2=a mod n 有解，则称a为模n的二次剩余或平方剩余(Quadratic Residues, R2)；否则a是模n的非二次剩余(Quadratic Non-residues, NR2) 用QRn表示所有模n的二次剩余之集合，用QNRn表示所有模n的非二次剩余之集合。 满足x2 = a mod n的x称为模n的一个平方根。 密码学导论--中国科学技术大学

94 例：若n=7，模n的完全剩余集合为{1, 2, 3, 4, 5, 6}，QR7={1, 2, 4}，即1, 2, 4为模7的二次剩余
因为： 12 mod 7=62 mod 7=1 42 mod 7=32 mod 7=2 22 mod 7=52 mod 7=4 而{3, 5, 6}为模7的非平方剩余，因为无法找到整数解满足x2 = a mod 7，a∈{3, 5, 6} 密码学导论--中国科学技术大学

95 定理：给定a, 0<a<n，则a∈R2，当且仅当ae mod n∈R2, 其中GCD(a,n)=1,GCD(e,Φ(n))=1。
证明： 若 a∈R2, 存在x满足 x2 mod n = a ae mod n = (x2)e mod n = (xe)2 mod n 所以ae mod n∈R2 总能找到d，使得ed=1modΦ(n)，即aed=a mod n 所以(ae)d mod n =a, 若ae mod n∈R2, 可推知a∈R2 密码学导论--中国科学技术大学

96 定理：对于素数p，p>2，0<a<p, 如果a∈R2，则x2 mod p = a 有两个解，否则无解。（二次剩余解的个数）
证明： 假如a∈R2, 至少有一个解x1, 满足x12 mod p=a，同时p-x1也是一个解：(p-x1)2 mod p = x12 mod p = a p-x1≠x1（p为奇数），所以这两个解是可以区分的 密码学导论--中国科学技术大学

97 定理：对于素数p，p>2, 有(p-1)/2个模p的二次剩余，(p-1)/2个模p的非二次剩余。（二次剩余的个数）
证明： 对每个a∈R2，它的两个平方根x1或p-x1中有且仅有一个落在 [1, (p-1)/2]中 (p-1)/2个剩余12, 22, …, ((p-1)/2)2 mod p是不同的R2中的数 不存在其它二次剩余 密码学导论--中国科学技术大学

98 例： 如果p=7，在[1, 6]中是平方剩余的有三个，即{1, 2, 4} 如果p=11，在[1,10]中是平方剩余的有五个，即
12 mod 7 = mod 7 = 1 22 mod 7 = mod 7 = 4 32 mod 7 = mod 7 = 2 如果p=11，在[1,10]中是平方剩余的有五个，即 12 mod 11 = mod 11 = 1 22 mod 11 = mod 11 = 4 32 mod 11 = mod 11 = 9 42 mod 11 = mod 11 = 5 52 mod 11 = mod 11 = 3 密码学导论--中国科学技术大学

99 定理：对素数p>2, 0<a<p, 若a∈R2, 则a(p-1)/2 mod p=1；否则a(p-1)/2 mod p = p-1。（二次剩余的判定）
证明： 根据费马定理，ap-1 mod p=1, 有(ap-1–1) mod p=0 ∵ p是奇数，因此有(a(p-1)/2 +1)(a(p-1)/2 -1) mod p=0 即p|a(p-1)/2 +1或p|a(p-1)/2–1，但不同时成立，否则p|2 ∴ a(p-1)/2 mod p = ±1 若a∈R2，则其平方根x满足a(p-1)/2 mod p=xp-1 mod p=1。 共(p-1)/2个平方剩余，都是a(p-1)/2 mod p = 1的解。而不会有更多的解，因为(p-1)/2次方程最多有(p-1)/2个解。(p-1)/2个非平方剩余只能是a(p-1)/2 mod p = p-1的解 密码学导论--中国科学技术大学

100 求解x2 mod p=a，a∈R2 尚无有效的确定性算法求解模素数的平方根问题 若素数p≡3 mod 4，则存在确定性解法
a(p-1)/2 mod p=1 a(p+1)/2 mod p=a x1=a(p+1)/4 mod p x2=p-x1 在生成随机素数时，保证生成的是模4余3的素数 只需最低2个比特固定为11 密码学导论--中国科学技术大学

101 求解x2 mod n=a，a∈R2 考虑n=pq，p和q是素数
x2 mod n = a  x2 = a mod p，x2 mod q = a a∈R2，则两式必有解 x2 = a mod p有两个解，x1和p-x1 x2 = a mod q有两个解，x2和q-x2 当p、q=3 mod 4时，易解 x1 = a(p+1)/4 mod p，并导出p-x1 x2 = a(q+1)/4 mod q，并导出q-x2 应用CRT，可以求出x2 mod n = a的四个解， Z mod p = x1或 p-x1；Z mod q = x2或 q-x2 密码学导论--中国科学技术大学

102 Z1 mod p = x1 Z1 mod q = x2 GCD(Z1＋Z2,n)=q GCD(Z1＋Z3,n)=p
Z2 mod q = q-x2 Z3 mod p = p-x1 Z3 mod q = x2 Z4 mod p = p-x1 Z4 mod q = q-x2 GCD(Z1＋Z2,n)=q GCD(Z1＋Z3,n)=p GCD(Z1＋Z4,n)=n GCD(Z2＋Z3,n)=n GCD(Z2＋Z4,n)=p GCD(Z3＋Z4,n)=q 不经意传输 密码学导论--中国科学技术大学

103 第四节 秘密分享技术 密码学导论--中国科学技术大学

104 为防止密钥丢失（或被毁），应建立副本备份
备份越多，越容易泄露 备份越少，越容易丢失（或被毁） 重要机构必须由数个人共同合作才能完成某件工作 例如：打开银行金库的大门，启动核导弹发射程序 秘密共享：不增加备份数量的情况下，增加可靠性 由n个用户中的t个用户相互协作，完成某些重要任务 密码学导论--中国科学技术大学

105 (t,n)门限方案 Shamir于1979年提出 当t=n时，有时又称作秘密分割
将一个秘密K分解成n个影子（shadow, 或称为共享）k1, k2, …, kn 设计一个算法，使得 只要有t个ki，计算K是容易的； 从任何少于t个ki，计算K是不可能的。 当t=n时，有时又称作秘密分割 此时，算法可以简单的用异或实现 引入n-1个随机数，将它们、以及它们与秘密的总的异或值作为影子 密码学导论--中国科学技术大学

106 拉格朗日插值多项式法 (Lagrange Interpolating Polynomial Scheme)
选择一个域GF(p)，素数p>K, p>n。每个影子由下列t-1次方的随机多项式导出: h(x) = (at-1xt-1 + … + a1x1+ a0) mod p a0即为秘密K，a0= K，是常数项。 给定h(x)，则K=h(0)，ki=h(xi)，i=1,…,n x1, x2, …, xw无需保密，通常取1,2,3,… 只需要t个点就可以唯一地重组t-1次的多项式 t-1次多项式必须要t个点才可以唯一确定 密码学导论--中国科学技术大学

107 密钥重组： 给定t个影子，k1, k2, …, kt，h(x)可由下面的Lagrange Interpolating Polynomial给出： 所有运算在GF(p)里进行，除是由乘模p的逆实现的。 则密钥为h(x)的常数项 密码学导论--中国科学技术大学

108 拉格朗日插值多项式重建公式证明 假设已有t个影子k1, k2, …, kt 设多项式为h(x)，则 密码学导论--中国科学技术大学

109 采用基分解的处理方法，先求解如下方程组 考虑第一个方程组 密码学导论--中国科学技术大学

110 类似地可以解出所有方程组 代回原同余方程组，即得证 当给出t+1个影子时 任选t个来解 用所有的t+1个来解 密码学导论--中国科学技术大学

111 代回同余方程组，可得 注意到 代入上式， 密码学导论--中国科学技术大学

112 密码学导论--中国科学技术大学

113 例：令K=13, n=5, t=3 取p = 17 h(x)＝(2x2 +10x +13) mod 17 k1 = h(1) = ( ) mod 17 = 25 mod 17 = 8 k2 = h(2) = ( ) mod 17 = 41 mod 17 = 7 k3 = h(3) = ( ) mod 17 = 61 mod 17 = 10 k4 = h(4) = ( ) mod 17 = 85 mod 17 = 0 k5 = h(5) = ( ) mod 17 = 113 mod 17 = 11 密码学导论--中国科学技术大学

114 重组h(x)，t = 3，随机选取k1，k3，k5： K = h(0) = 13
密码学导论--中国科学技术大学

115 高级门限方案 可以构造复杂的共享方案 若某人比其他人重要，可以分配给他更多的影子 设想需要在两个敌对代表团之间共享秘密
可以按各人的重要程度分配不同数量的影子 设想需要在两个敌对代表团之间共享秘密 设A代表团7人，B代表团12人，需要由来自A团的2人和来自B团的3人一起才能恢复秘密 多项式构造为一个三次多项式，它是一个一次多项式（给A团分配影子）和一个二次多项式（给B团分配影子）的乘积 密码学导论--中国科学技术大学

116 其它实现方法 矢量方案 Karnin-Greene-Hellman矩阵方案 将秘密映射为t维空间中的一个点
选择n+1个t维向量V0,V1,V2,…,Vn（公开），使得任意t个向量所构成的矩阵的秩为t。向量U是t维行向量。 秘密为U·V0，影子是乘积U·Vi (1<i<n) 任意t个影子能够用来解t元线性方程组，确定U。 密码学导论--中国科学技术大学

117 Asmuth-Bloom方案，又称中国剩余定理方案
对于(t,n)门限方案，秘密值M，选择大素数p>M，再选择n个大于p的数d1, d2, …, dn，使得 di按递增顺序排列，di<di+1 di两两互素 d1×d2×…×dt>p×dn-t+2×dn-t+3×…×dn，令L=d1×d2×…×dt 选取随机数r，使得M'=M+rp，M'<L，影子ki=M' mod di 利用中国剩余定理，由任意t个影子就能恢复M 任意t个影子对应的di乘积都大于L，因而可以构造唯一公共解M' mod (di1×di2×…×dit) = M' mod L M=M' mod p 任意t-1个影子恢复的M'之模N，L/N>p，且N与p互素，无法获得真实M'的信息 密码学导论--中国科学技术大学

118 特定情景中的秘密分享 有骗子的秘密共享 情景1：重构秘密时，合法用户故意输入错误影子 情景2：重构秘密时，非法用户在参与过程中窃取他人影子
某个拒绝总统命令不愿意发射导弹的将领，在输入影子时故意输入错误数字，使得秘密不能恢复。 普通方案无法发现究竟是谁在破坏 情景2：重构秘密时，非法用户在参与过程中窃取他人影子 非法用户可以偷看别人的影子，可以在算法中设法推演出他人影子的信息，可以当t个合法用户恢复秘密后构建自己的合法影子 恶意的，半可信的 密码学导论--中国科学技术大学

119 没有仲裁者的秘密共享 不暴露影子的秘密共享 在某种场合下，没有可信的仲裁者来制造影子
如果有人知道核弹发射的最终密码，并由他来为其他将领分配影子，则这个人有机会独自发射核弹 需要一种算法，由合法参与者来共同生成影子，但没有人知道秘密 设想秘密是在某个设备中秘密生成，参与者可以用它来计算，但不能读取秘密 不暴露影子的秘密共享 重建秘密时不直接展示各人的影子 例如，当秘密是所有人共同数字签名的私钥时，每个人独立签名后，文件就已经用共同的私钥签名了 密码学导论--中国科学技术大学

120 可验证的秘密共享 带预防的秘密共享 带除名的秘密共享 影子持有人如何知道自己的影子是正确的？ 合法参与者如何验证某个可疑对象的影子正确与否？
通过重建秘密可以验证，但那样秘密就泄露了 带预防的秘密共享 对于已构建的(t,n)方案，如果想提高为(t',n)方案，如何做？ 带除名的秘密共享 对于已构建的(t,n)方案，如果想除名一个参与者，如何做？ 密码学导论--中国科学技术大学

121