Fifth Edition by William Stallings 苗付友 mfy@ustc.edu.cn 2018年11月 现代密码学理论与实践 第8章 数论入门 Fifth Edition by William Stallings 苗付友 mfy@ustc.edu.cn 2018年11月 网络视频：http://wlkt.ustc.edu.cn/video/detail_3363_0.htm

第二部分 公钥密码和散列函数 第8章：数论入门 第9章：公钥密码与RSA 第10章：密钥管理和其他公钥密码体制 第11章：消息认证和散列函数 第12章：散列和MAC算法 第13章：数字签名和认证协议

本章要点 素数是一种整数，在整除意义下，它只能被自身(正 负)和1整除。素数在数论和密码学里扮演重要角色。 在公钥密码里起重要作用的两个定理是费马定理和欧 拉定理。 许多密码算法的一个重要前提是能够选择一个大的素 数。开发有效算法判定一个随机整数是否为素数是密 码研究的重要课题。 离散对数是许多公钥算法的基础。离散对数和普通对 数类似，但是在模算术上进行运算。

本章目录 8.1 素数 8.2 单向函数 8.3 费马定理和欧拉定理 8.4 素性测试 8.5 计算乘法逆元素 8.6 求解ax mod n =b的问题 8.7 中国余数定理 8.8 离散对数问题 8.9 二次剩余问题 8.10 不经意传输

8.1 素数 Prime Numbers 素数合数最大公因数 整数p>1是素数当且仅当它只有因子±1和±p，如 2,3,5,7是素数，而4,6,8,9,10不是素数 素数不能写作其他数的乘积形式 1是素数，但是通常没有什么用 素数是数论的核心 小于200的素数如下 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199

小于2000的素数如下

合数的素因子分解 其中每个ap≥0, 对于某一整数a， 分解一个数n就是把它写成其他数的乘积形式，如 n=a×b×c 比起用乘的方法把几个因子乘起来生成合数，分解 合数通常要困难得多。 （算术基本定理）任何整数a>1, 都可以唯一地分 解为a= p1a1p2a2…ptat , 其中, p1<p2<…<pt 是素 数，所有的ai都是非负整数。如91=7x13; 3600=24x32x52; 11011=7x112x13 素因子分解就是把一个合数写成若干素数的乘积形 式，如3600=24x32x52， 其中每个ap≥0, 对于某一整数a， 其大多数指数ap为0. 2019/5/8 现代密码学理论与实践-08

合数的素因子分解 任一给定的正整数, 可通过简单列出所有后面公式中非零指数分量来说明. 两个数的乘法等同于对应指数分量的加法 Ex：12可以表示为{a2=2, a3=1}, 18可以表示为 {a2=1, a3=2}, 91可以表示为{a7=1, a13=1} 两个数的乘法等同于对应指数分量的加法 k=mn →kp = mp + np 对所有p Ex：k=12x18=(22x3)x(2x32)=216, k2=2+1=3, k3=1+2=3, ∴ 216=23x33 任何以pk形式表示的整数仅能被对应素数分量小于或等于它的另一个整数pj 整除, 其中j≤k，即有a|b →ap≤bp ，对所有素数p成立。 Ex：a=12, b=36, 12|36, 12=22x31, 36=22x32 a2=2=b2, a3=1≤2=b3

互素和最大公约数GCD 300=22x31x52, 18=21x32, gcd(18, 300)=21x31x50=6 gcd(a, b)=c, 即c是a和b的最大公约数, 当 c是a和b的因子 任何a和b的因子也是c的因子 两个整数 a, b, 如果除了1以外没有公共因子, 则称它们互 素(Relatively Prime) 8和15互素, 因为8的因子是1,2,4,8, 而15的因子是 1,3,5,15, 1是它们唯一的公共因子。 如果将整数表示为素数之积, 则容易确定两个正整数的最 大公因子 下列关系总是成立的 如果k=gcd(a, b), 则 kp=min(ap, bp), 对于任意的p∊P 例子： 300=22x31x52, 18=21x32, gcd(18, 300)=21x31x50=6

8.2 单向函数One-way Function 单向陷井门函数One-way Trapdoor Function 一函数f 若满足下列条件, 则称f 为单向函数： (1)对于所有属于f 之域的任一x, 容易计算y= f(x) (2)对于几乎所有属于f 之域的任一y, 求得x, 使y= f(x), 在计算上 不可行。 定义8.2 单向陷井门函数(One-way Trapdoor Function) 一“可逆”函数F若满足下列两条件, 则称F为单向陷井门函 数： (1)对于所有属于F之域的任一x, 容易计算F(x)=y； (2)对于几乎所有属于F之域的任一y, 除非获得暗门信息 (trapdoor), 否则求出x, 使得 x = F-1(y)在计算上不可行, F-1 为F之逆函数; 如有额外信息(暗门), 则容易求出x = F-1(y)，如 旅馆房间门。

单向函数举例 1.离散对数问题Discrete Logarithm Problem (DLP) 令素数p满足p-1含有另一大素数q (q整除p-1)及一整数g, 1<g< p-1。 若给定整数x, 求y = gx mod p, 最多需要Llog2x｣+w(x)-1次乘法, w(x)为x中所有1的个数。如x =15, 即 x =(1111)2, w(x)=4, 则g15 =((g2)g)2·g)2·g mod p, 只需要3 + 4 -1=6次乘法。 但是若给定p, g及y, 求x, 则为DLP问题, 最快方法需要L(p)=exp{(lnp) 1/3(ln(lnp)) 2/3 }次运算。 当p=512位时, L(p)约为2256≈1077, 计算上不可行, 因为2100≈1030, 计算要1016年。

单向函数举例(续) 2. 因数分解问题Factorization Problem 3. 背包问题Knapsack Problem 给定大素数 p和q, 求n = p×q, 只要一次乘法 给定n, 求p和q, 即为因数分解问题(FAC), 最快方法需要 T(n) = exp {c(ln n ln (ln n))½} 次运算, 其中c为大于 1的正整数。 3. 背包问题Knapsack Problem 给定有限个自然数序列集合B=(b1,b2,…bn)及二进制序列 x=(x1,x2,…xn), xi∈(0,1), 求S=∑xibi最多只需n-1次 加法；但若给定B和S, 求x则非常困难。 穷举时有2n种可能, 当n很大时为计算上不可行。 Garey和Johnson证明, 背包问题是NP问题 (Non-Polynomial)

单向函数及其交换性 单向函数的交换性(commutative property) 定义8.3 交换性 单向函数本身对近代密码学领域用处不大，但若具有交换性，则作用大。 定义8.3 交换性 令Z为一集合，F为将Z映射到Z本身的函数集合。 令 z∈Z, Fx(z)表示此函数集合之第x函数, 若Fx(Fy(z))=Fy(Fx(z))，则称此函数集合具有交换性。 例：D(E(m))=E(D(m))

指数函数(Exponentiation Function) 定义8.4 指数函数 令G为有限乘法群, g∈G, 则对于所有整数 x, Ex(g)=gx mod p ∈G, 是为指数函数。 通常, 令G={1,2,…,p-1}, p为素数, 则 Ex(g)= gx mod p为指数函数。 指数函数之特性 1. 周期性(Periodicity) 令序列<Ex(g)>={g0,g1,g2,…}为g所产生之序列。因 为G是有限群, Ex(g)不可能不重复, 故Ex(g)产生之序列 为周期序列。

指数函数之特性(续) 当存在最小正整数T, 使得ET(g)=gT=1=g0时, 称T为 g在G中的阶或序(order)。根据Fermat’s Theorem, 对于所有g, T必定整除p-1. 例：p=11, g=2, <Ex(g)>={20,21,22,…,210}={1,2,4,8,5,10,9,7,3,6 ,1} 即：20=1 mod 11 26=9 mod 11 21=2 mod 11 27=7 mod 11 22=4 mod 11 28=3 mod 11 23=8 mod 11 29=6 mod 11 24=5 mod 11 210=1 mod 11 25=10 mod 11 所以T=10=11-1=p-1

指数函数之特性(续) 2. 本原元素(素根、原根)Primitive Element (Root) 本原元：若g∈G的阶为T=p-1, 则称g为模p的本原元。 (1) 当g为mod p的本原元时, 由g产生的序列<Ex(g)>具 有最大周期(安全性较高)。 (2) 对于所有素数p, 其本原元必定存在。 (3) 当g为模p的本原元且a与p-1互素时, 即 gcd(a, p-1)=1, 则ga mod p亦必为模p之本原元素。 (4) 模p的本原元素个数为φ(p-1), 称为尤拉商数(Euler Totient Function), 表示不大于p-1, 且与p-1互素的 正整数之个数, 即φ(p-1)。

附：求本原元 求一个大素数 p 很容易，用现成的素性验证算法就 可以了。不过已知一个素数 p，求其本原根则很困 难，因为需要将 p - 1 的素因子 q1，q2，……qk-1， qk都找出来，然后分别验证 gq1 mod p， gq2 mod p， ……gqk-1 mod p， gqk mod p，如果都 不等于 1，则 g 是 p 的一个本原根。而然，如果 p 是一个很大的素数，例如 128 个 2 进制位的素 数，要分解出 p - 1 的所有素因子来则是一件很困 难的事情。

指数函数之特性(续) 本原元素举例：p=11, g=2, φ(p-1)= φ(10)=4, 即1, 3, 7, 9与 p-1互素。若 g=2为模p之本原元素, 则 21=2, 23=8, 27=7, 29 mod 11=6均为模11之本原元素。找到 一个本原元素后可以容易找到所有本原元素, 问题是如何找到第一 个本原元素。 算法如下： P1. 利用素性验证算法，生成一个大素数q； P2. 令 p = q * 2 + 1； P3. 利用素性验证算法，验证 p 是否是素数，如果否，则跳 转到P1； P4. 生成一个随机数 g，1 < g < p - 1； P5. 验证 g2 mod p 和 gq mod p 都不等于 1，否则跳转到 P4； P6. g 是大素数 p 的本原根。

指数函数之特性(续) 3. 交换性 指数函数满足交换性, 因为: Ex(Ey(g))=Ex(gy)=(gy)x=gyx Ey(Ex(g))=Ey(gx)=(gx)y=gxy ∴ Ex(Ey(g))=Ey(Ex(g))

指数函数之特性(续) 4. 非对称性(Asymmetric Property) ∵Ex(-g)=(-g)x=(-1)xgx=(-1)xEx(g) ∴若x为偶，则Ex(-g)= Ex(g) 若x为奇，则Ex(-g)= -Ex(g) 5. 乘法性(Multiplicative Property) Ex(g1)Ex(g2)=g1xg2x=(g1g2)x=Ex(g1g2)

指数函数之特性(续) 6. 乘法逆元素Multiplicative Inverse 7. 安全性 若T为g之序, 则对于所有x, 0≤x<T, Ex(g-1)=ET-X(g) g-1为g的乘法逆元素. 因为：Ex(g-1)=g-x=1•g-x= gT•g-x=gT-x= ET-x(g) 这是一种求乘法逆元素的方法, 欲求g-1时, 由于gT- 1=g-1 (这里x=1) ∵T整除p-1, ∴g-1=gT-1=gp-1-1 = gp-2 (mod p) g•g-1 mod p=1, 这是因为gxgT-x mod p=gT mod p=1 7. 安全性 给定g∈G及y∈<Ex(g)>, 求x使得y=Ex(g)=gx mod p为DLP问题。

指数函数之特性(续) 8. 可逆性 若T为g∈G之序, x-­1为x在模T时的乘法逆元素, 即 xx-1=1 mod T, 则Ex(Ex-1(g)) = Ex-1(Ex(g))=gxx-1 mod p = g mod p 这是因为Ex(g)满足交换性, 所以 Ex(Ex-1(g))=Ex-1(Ex(g))。 另一种证明方法： ∵ x-1x = 1 mod T = kT+1 ∴Ex(Ex-1(g))=gxx-1=gkT+1=(gT)k•g=1kg=g mod p 这实际上是利用费马定理对RSA算法正确性的证明

快速指数运算法—平方再乘法 快速指数运算法—平方再乘法(Square and multiply) 当x为n位时即x=(xn-1, xn-2,…,x1, x0) Ex(g)=gx=(…(1•gxn-1)2•gxn-2)2•gxn-3…)2•gx0 此算法共需要n-1次平方及w(x)-1次乘法, 平均而言w(x)=n/2, x在二进制表示时有n/2个”0”及n/2个”1”。因此，当x为n位时, 平均需要1.5n-2个乘法(平方算一次乘)。 注：如果x为k进制数，即变为k次方再乘法，效率更高？ (需要提前计算并存储g2,g3,…,gk-1)

快速指数运算法—平方再乘法 Algorithm fastexp(a, z, n) begin “return x=az mod n” a1:= a; z1:=z; x:=1 while z1≠0 do “x(a1z1 mod n)= az mod n” begin while z1 mod 2 = 0 do begin “square a1 while z1 is even” z1:=z1 div 2 a1:=(a1*a1) mod n end; z1:=z1-1 x:= (x*a1) mod n “multiply” fastexp:=x end

8.3 费马定理和欧拉定理 定理8.1 费马定理 Fermat’s Theorem 证明： 若p是素数, a是正整数且不能被p整除, 则ap-1 mod p=1 证明： 因为{a mod p, 2a mod p, ..., (p-1)a mod p}是{1, 2, ..., (p-1)}的置换形, 所以, (aｘ2aｘ ... ｘ (p-1)a)≡(1ｘ2ｘ ... ｘ(p-1)) (mod p)≡ (p-1)! mod p. 但是, aｘ2aｘ...ｘ(p-1)a=(p-1)!ap-1, 因此(p-1)!ap-1≡(p-1)! mod p, 两边去掉(p-1)!, 即得ap-1mod p = 1 证毕 例如：a=7, p=19, ap-1mod p=718 mod 19=? 72=49≡11 mod 19 74=121≡7 mod 19 78=49≡11 mod 19 716=121≡7 mod 19 ap-1=718=716x72≡7x11≡1 mod 19

费马定理的等价形式 费马定理等价形式 ap≡a mod p, p是素数，a是任意正整数 p=5, a=10, 105=100000≡10 mod 5≡0 mod 5

欧拉函数：Euler’s Totient Function φ(n) φ(n)是比n小且与n互素的正整数的个数，即模n 的缩剩余集中元素之个数，习惯上φ(1)=1。 2019/5/8 现代密码学理论与实践-08

欧拉函数φ(n)的证明 定理8.2 p和q是素数, n=p*q, φ(n)= φ(p)φ(q)=(p- 1)(q-1) 证明：考虑余数集合{0, 1, …, (pq-1)}中不与n互素的余 数集合是{p, 2p, …, (q-1)p}, {q, 2q, …, (p-1)q}和0, 所以 φ(n)= pq-[(q-1)+(p-1)+1]=pq-(p+q)+1= (p-1)(q- 1)=φ(p)φ(q) 一般说来, 对任意n, φ(n)由下式给出： φ(n)= (pi-1), n= ... Pi 均为素数。 或 φ(n)= n(1-1/p1)(1-1/p2)…(1-1/pt)

n=24=23x31, φ(n)=φ(24)=22(2-1)30(3-1)=8 φ(MN)= φ(M) φ(N) gcd(M,N)=1

欧拉定理 Euler’s Theorem 定理8.3 欧拉定理 Euler’s Theorem (欧拉产生式 Euler’s Generalization) 对任意互素的a和n (gcd(a,n)=1), 有aφ(n) mod n=1 证明：令{ r1, …, rφ(n) }是模n的缩剩余集, 0<ri<n, 1≤ i ≤ φ(n), 则{ ar1 mod n, …, arφ(n) mod n } 是 { r1, …, rφ(n) }的置换形集合。因此 (ari mod n)= ri, ari ≡ ri (mod n) aφ(n)[ ri ]≡ ri (mod n), 即得aφ(n) mod n ≡ 1 也可由此证明费马定理：ap-1 mod p = 1

欧拉定理的等价形式及推论 欧拉定理的等价形式 欧拉定理的推论 mφ(n)+1 = m(p-1)(q-1)+1 ≡ m mod n aφ(n)+1 ≡ a (mod n) 欧拉定理的推论 mφ(n)+1 = m(p-1)(q-1)+1 ≡ m mod n mkφ(n)+1≡[(mφ(n))k×m] mod n ≡[(1)k×m] mod n ≡ m mod n 例：[1, 3, 5, 7]为模8之缩剩余集, [3x1, 3x3, 3x5, 3x7]亦为模8之一个缩剩余集。因此, 3x1x3x3x3x5x3x7=1x3x5x7 mod 8, 得 34(1x3x5x7) = 1x3x5x7 mod 8, 34=3φ(n)=1 mod 8 所以, 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

g = gcd(p − 1, q − 1). Then a(p−1)(q−1)/g ≡ 1 (mod pq) Theorem 3.1 (Euler’s Formula for pq). Let p and q be distinct primes and let g = gcd(p − 1, q − 1). Then a(p−1)(q−1)/g ≡ 1 (mod pq) for all a satisfying gcd(a, pq) = 1. lcm(p-1,q-1)=(p−1)(q−1)/gcd(p-1,q-1) In particular, if p and q are odd primes, then a(p−1)(q−1)/2 ≡ 1 (mod pq) Since a(p−1)(q−1)/g = a(p−1){ (q−1)/g }≡ 1(q−1)/g (mod p) ≡ 1 (mod p) Similarly, a(p−1)(q−1)/g ≡ 1 (mod q) Therefore, a(p−1)(q−1)/g ≡ 1 (mod pq)

Proposition 3.4. Let p and q be distinct primes and let e ≥ 1 satisfy gcd(e, (p − 1)(q − 1)) = 1. e has an inverse modulo (p − 1)(q − 1), say de ≡ 1 (mod (p − 1)(q − 1)). Then the congruence xe ≡ c (mod pq) has the unique solution x ≡ cd (mod pq). Proof: (cd)e ≡ cde (mod pq)≡ c1+k(p−1)(q-1) (mod pq) ≡ c · (c(p−1)(q-1))k (mod pq) ≡ c · 1k (mod pq)≡ c (mod pq). Uniqueness:

(cd)e ≡ cde (mod p)≡ c1+k(p−1) (mod p) ≡ c · (cp−1)k (mod p) ≡ c · 1k (mod p)≡ c (mod p).

8.4 素性测试 密码学中常常需要寻找大素数 传统的方法是用测试除法来过滤非素数 可以采用基于素数特性的统计素性测试方法 即依次除小于该数平方根的所有素数 这种方法只对较小的数有用 可以采用基于素数特性的统计素性测试方法 其中所有的素数都满足素数特性 但是有一些被称为伪素数的合数也满足素数特性 可以使用一种较慢的确定性素性测试方法

8.4.1 Miller-Rabin算法测试素性 这是一种基于费马定理的方法 引理8.1：对于候选奇整数n≥3, 偶数(n-1)可表示为 假设n是素数an-1 = 1 mod n； 如果an-1 ≠1 mod n n是合数； 如果对于很多a都满足an-1 = 1 mod n则n可能为素数。 引理8.1：对于候选奇整数n≥3, 偶数(n-1)可表示为 n-1 = 2kq k>0, q是奇数 证明：用2去除偶数(n-1)，直至所得结果为奇数q，此处共做k次除法；如果n是二进制数，则将该数右移，直到最右边的比特为1，共移动了k次。

素数的两个性质之一 引理8.2：如果p是素数, a是小于p的正整数, 则a2 mod p=1, 当且仅当a mod p=1或者a mod p= - 1 mod p=p-1 证明： 根据(a mod p)(a mod p)=a2 mod p, 如果a mod p =1 或a mod p = -1, 则有a2 mod p=1 反之, 如果a2 mod p=1, 则(a2 -1 ) mod p =0, 则 (a-1) mod p=0或者(a+1) mod p =0, 即a mod p =1或a mod p = -1 （p为合数也成立，比如p=4 a=1, 3 a2mod p=1）

素数的两个性质之二 引理8.3：设p是大于2的素数, 有p-1=2kq, k>0, q 是奇数。设a是整数且1<a<p-1, 则以下两个条件之 一成立： aq mod p =1, 或aq ≡ 1(mod p) 在整数aq, a2q, a4q, …, a2k-1q中存在一个数, 模p时和-1 同余, 即存在一个j(1 ≤ j ≤ k), 满足 a2j-1q mod p=(-1) mod p=p-1, 或a2j-1q ≡ -1 (mod p) 证明：若n是素数, 由费马定理可知an-1≡1(mod n). 由于p-1=2kq, 则ap-1 mod p= a2kq mod p=1。则数列 aq mod p, a2q mod p, a4q mod p, …, a2k-1q mod p, a2kq mod p, 最后的数为1, 且每一个数都是前一个数的平方。因此下面两条必有一条是正确的： 数列中的第一个数, 以及其后的所有数都是1 数列中有的数不为1, 但它们的平方模p后为1, 根据性质1满足这 个条件的唯一整数是p-1, 因此数列中必有一个数为p-1

因为： n-1 = 2kq, 计算aq, a2q, …, a2k-1q, a2kq模n的余数 若n是素数，则由费马定理可知， a2kq mod n= an-1 mod n = 1. 可以把aq, a2q, …, a2k-1q, a2kq写作{aq, a2q, …, a2j-1q, a2jq, 0≤j≤k}；若n是素数, 则有某最小的j 使得 a2jq mod n=1 j=0: aq -1 mod n =0, 或n整除(aq -1) 1≤j≤k: (a2jq -1) mod n =(a2j-1q -1)(a2j-1q +1) mod n=0, 即n整除(a2j-1q -1)或(a2j-1q +1) 。根据假设, j是使n整除(a2jq -1)的最小整数, 所以n不能整除(a2j-1q -1), 因此n整除(a2j-1q +1), 即a2j-1q mod n=(-1) mod n = n -1

Miller-Rabin算法测试素性 所以, 若n是素数, 要么余数序列(aq, a2q, …, a2k-1q, a2kq)的第一个元素为1, 要么该序列前k个元素中的某 个元素为n-1；否则n是合数。这样可以测试某个整 数是否具有素性。 然而条件成立也并不意味着n一定是素数，例如： n=2047, 则n-1=2x1023; 计算21023 mod 2047=1, 2047满足条件， 但2047不是素数，因为n=2047=23x89 。

Miller-Rabin算法测试素性 输入整数n, 如果n不是素数，则返回合数的结果；如果n可能是素数也可能不是，则返回不确定 TEST (n) 1. Find integers k, q, k > 0, q odd, so that (n–1)=2kq 2. Select a random integer 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")

素数测试举例 例1：n=29, 有(n-1)=28=22(7)=2kq. 取a=10, 计算 107 mod 29=17, 既不为1也不为28。计算(107)2 mod 29 =28, 返 回不确定(即29可能为素数)。取a=2, 27 mod 29 =12, 214 mod 29=28, 仍返回不确定。对1到28之间的所有整数a进行测试, 都会返 回不确定, n为素数。 例2：n=221, n-1=220=22(55)= 2kq. 如果a=21, 2155 mod 221=200, (2155)2 mod 221=220, 返回不 确定, 表明221可能是素数。 取a=5, 555 mod 221 =112, 既不为1也不为220。(555)2 mod 221=168, 返回合数, 表明221肯定是合数(n=13x17)。 事实上, 2到219这218个整数中, a有4个整数会返回不确定：21, 47, 174和200

重复使用Miller-Rabin算法 如果Miller-Rabin算法返回“composite”, 这数肯定不是素数；不然是素数或者伪素数 给定一个非素奇数n和一个随机整数a, 1<a<n-1, 程序TEST返回不确定的概率< ¼ (即不能确定n不是素数) 因此, 如果选择t个不同的a, 则它们都能通过测试(返回不确定)的概率小于(¼)t 取 t=10, 则一个非素整数通过10次测试的概率小于10-6, 因此取足够大的t, 如果测试总是返回不确定, 则以很大的把握说n是素数, 其概率是1-4-t 这为决定一个奇整数n是素数且具有合理的可信度奠定了基础：对随机选取的a, 重复调用TEST(n), 如果某时刻TEST返回“合数”, 则n一定不是素数；若TEST连续t次返回“不确定”, 当t足够大时, 我们可以相信n是素数

一个确定的素性判定算法AKS 2002年以前，没有高效的方法证明一个大数的素 性，包括Miller-Rabin算法在内，所有在用算法 给出的都是概率性结果。 2002年Agrawal, Kayal和Saxena给出了一个相 对简单的确定性算法AKS，可以有效判定一个大 数是否为素数，但是看上去没有Miller-Rabin算 法快，因此没有代替古老的概率算法。

8.4.2 素数的分布 由数论中的素数定理可知，n附近的素数分布情况为平 均每ln(n)个整数中有一个素数。平均而言，在找到一 个素数之前必须测试约ln(n)个整数 因为偶数肯定不是素数，因此需要测试的整数个数为 0.5ln(n)。 例如，若要找2200左右的素数，则约需要 0.5ln(2200)= 69次测试。 这只是个平均值，在数轴上的某些位置，素数非常密集， 而在其他有些位置，素数非常稀疏。 两个相邻的奇数1,000,000,000,061和 1,000,000,000,063都是素数 而1001!+2, 1001!+3, …, 1001!+1000, 1001!+1001 这1000个连续的整数都是合数

素数的分布

8.5 计算乘法逆元素 问题：ax mod n = 1, x=a-1=? 1.利用欧拉定理 根据欧拉定理(定理8.3), aφ(n) mod n=1, 有 aa-1 mod n =1= aφ(n) mod n. 所以有a-1 = aφ(n)-1 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 如果φ(n)已知, 则a的逆元素可以用快速指数运算法求得. 特例：如果n是素数p, 则 a-1 = ap-1-1 mod p = ap-2 mod p. 2.如果φ(n)不知, 可以用Euclid’s计算最大公约数算法 的扩展来求逆.

快速指数运算法求逆元素(φ(n)已知) Algorithm fastexp(a, z, n) begin “return x=az mod n” a1:= a; z1:=z; x:=1 while z1≠0 do “x(a1z1 mod n)= az mod n” begin while z1 mod 2 = 0 do begin “square a1 while z1 is even” z1:=z1 div 2 a1:=(a1*a1) mod n end; z1:=z1-1 x:= (x*a1) mod n “multiply” fastexp:=x end

8.5.2扩展的Euclid算法求逆元素(φ(n)未知) Algorithm inv(a, n) begin g0:=n; g1:=a; u0:=1; v0:=0; u1:=0; v1:=1; i:=1 while gi≠0 do “gi = uin + via” y:=gi-1 div gi; gi+1:= gi-1 –y*gi; ui+1:= ui-1 –y*ui; vi+1:= vi-1 –y*vi; i:=i+1 end x:= vi-1 if x>=0, then inv:= x, else inv:= x+n gi = uin + via 是循环变量，当gi=0 时 gi-1=gcd(a, n)。如果gcd(a, n)=1, 则gi-1=1，并且 vi-1a –1 = ui-1n 。 因此，vi-1a mod n =1, vi-1 ＝x，就是a的逆元素。

8.5.3 在GF(2n)中求逆 在GF(2n)中的运算(模2运算是基础) 在GF(2n)中求逆 加、减运算是异或, 加无进位, 减无借位, 乘法运算是“与”, 除法运算只要位数够长即可进行。 例：计算d=a2, p(x) =x3+x+1, 在GF(23)中, a=101 a×a=101×101=10001 模p(x)：a2/p(x) =10001/1011=111, 即d. 在GF(2n)中求逆 因为除了0, 长度为n的每一个位矢量都与p(x)互素, 因此φ(p(x)) =2n-1; 所以, a×a-1 mod p(x) =1, a-1=aφ(p(x))-1 mod p(x) =a2n-2 mod p(x) 例：a=100，p(x) =1011 in GF(23)， a-1=aφ(p(x))-1 mod p(x) =a23-2 mod =10023-2 mod 1011 = (100)6 mod 1011=111 2019/5/8

8.6 求解ax mod n =b的问题 x=? 定理8.5 令g=gcd(a, n), 假如g|b (即b mod g=0), 则ax mod n=b 有g个解, 形如 x=[( )x0 + t( )] mod n, t = 0,1,…, g-1 x0是( )x mod ( )=1的解；否则无解。 证明：假如ax mod n =b 在[1, n-1]中有一个解, 则n|(ax-b). 因为g|n, g|ax, 则g|b一定成立。等式( )x mod ( )=1（*） 有唯一的解x0, x0∈[1,( )-1], （*）同乘b/g可知 x1=( )x0 mod ( )是( )x mod ( )=( )在[1, ( )-1]中的一个解。

求解ax mod n =b的问题 所以, ( )x1 - ( )=k(n/g), 被g乘, 得ax1 - b =kn. 这 就是说 x1是ax mod n =b的一个解。因此, 任何x∈[1, n-1], x=x1 mod( )也是ax mod n =b的一个解。 a(x1+kn/g) mod n=b 等价于ax1 mod n=b ∵akn/g= sn (k,s 均为整数) 所有解由下式给出：x = x1 + t( ), t=0,1, …, g-1 例：6x mod 10=4 ∵g=gcd(6,10)=2, 2|4, ∴应该有两个解。 先求x0，( )x mod ( )=1 → ( )x mod ( )=1, → 3x mod 5=1, x0=2 根据x=[( )x0 + t( )] mod n，t=0,1,…,g-1 x=[( )2 +0] mod 10 =4, t=0 x=[( )2 +( )] mod 10 =9, t=1

也可以用扩展欧几里得算法直接求解 例：6x mod 10=4 10 0 1 6 1 0 1 4 -1 1 x0=-1 mod 10=9 x1= x0 –t(10/2)=4 t=1

求解ax mod n =b的问题 定理8.6 证明：∵di两两互素, 或者：x1=( )x0 mod ( )=( )2 mod ( )=4 x= x1 + t( )=4, t=0 x= x1 + t( )=9, t=1 定理8.6 令d1,…,dt两两互素, n=d1d2…dt, 则 f(x) mod n=0, 当且仅当f(x) mod di=0, (1≤i≤t) 证明：∵di两两互素, ∴n|f(x), 当且仅当di|f(x), i=1,…,t 用定理8.6来求解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 mod di=xi，i=1,…,t，xi是f(x) mod di=0的解。 (x=a-1b mod n xi=a-1b mod di i=1,2,…,t)

总结：求解ax mod n =b一般过程 方法1： 方法2： 求g=gcd(a,n) .(欧几里得算法) 判断g|b,若真则有g个解 利用 （a/g）x mod (n/g) =1求出x0.(扩展欧几里得算法) 则xt= (b/g)x0 +t(n/g) t=0,2,…,g-1 方法2： 假如n=p*q. p,q为素数 ax mod n =bax mod p=b, ax mod q=bx mod p=x1, x mod q= x2 (Extended Euclid) CRT: (x1,x2)x 例：5x mod 21=4 ; 21=p*q=3*7 ; 5x mod 3=4 mod 3=1; 5x mod 7=4 x1=2; x2=5 x=CRT(x1,x2) 2019/5/8 现代密码学理论与实践-08

8.7 Chinese Remainder Theorem 中国余数定理 中国余数定理CRT说明某一范围内的整数可通过它对两 两互素的整数取模所得的余数来重构 Z10(0,1,…,9)中的10个整数可通过它们对2和5(10的素 因子)取模所得的两个余数来重构. 假设数x的余数r2=0 且r5=3, 即x mod 2=0, x mod 5=3, 则x是Z10中的偶 数且被5除余3, 唯一解x=8. 一种CRT的表示形式 令m= mi, 其中mi两两互素, 1<=i, j<=k, i≠j, gcd(mi, mj)=1 将Zm中的任一整数对应一个k元组, 该k元组的元素均在 Zmi中, 对应关系为a↔(a1,a2,…,ak), 其中a∈Zm, 对 1<=i<=k, ai∈Zmi, 且ai = a mod mi (两个断言证明 略)

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, )=1, 存在yi, 使得 ( )yi mod di=1; 进一步地, ( )yi mod dj=0, j≠i, (因为dj是( )的一个 因数) 令x=[ ( )yi xi] mod n. (事实上,x=xi+kdi, 1≤i≤t, k 为正整数) ∵ x mod di = ( )yixi mod di = xi, (( )yi mod di =1) ∴ x是x mod di=xi (1≤i≤t)的公共解。

中国余数定理的算法 Algorithm CRT (n, d1,…, dt, x1,…, xt) begin “return x∈[0, n-1] such that x mod di=xi， (1≤i≤t)” for i:=1 to t do yi:=inv(( ) mod di); x:=0; x:=[x + ( )yi xi] mod n; crt:=x end

孙子定理(孙子算经, 3-5世纪) 今有物不知其数, 三三数之剩二, 五五数之剩三, 七七数之剩二, 问物几何。 今有物不知其数, 三三数之剩二, 五五数之剩三, 七七数之剩二, 问物几何。 x mod 3=2 n=3*5*7=105 x mod 5=3 d1=3, d2=5, d3=7 x mod 7=2 x1=2, x2=3, x3=2 (1) 求yi，( )yi mod di=1 ( )y1 mod 3=1 ( )y2 mod 5=1 ( )y3 mod 7=1 得： 35 y1 mod 3=1 y1=2 21 y2 mod 5=1 y2=1 15 y3 mod 7=1 y3=1 (2) x = (35×2×2＋21×1×3＋15×1×2) mod 105=23

例：求解3x mod 10=1 3x mod 10=1, 10=2*5, d1=2, d2=5 所以：3x mod 2=1 x1=1 应用CRT找x mod di=xi的公共解： x mod 2=1 x mod 5=2 根据( )yi mod di=1计算 ( )y1 mod 2=1 ( )y2 mod 5=1 得y1=1, y2=3. 根据x=[ ( )yi xi] mod n 求x ∴ x=[( )y1 x1 + ( )y2 x2] mod 10 =(5*1*1 + 2*3*2) mod 10 =7

8.8 离散对数问题(discrete logarithm) 幂运算的求逆问题就是找到一个数模p的离散对 数, 也就是找到x, 满足ax = b mod p, 写作 x=loga b mod p 或 x = inda, p (b) 如果a是素根, 则x总是存在, 否则不一定存在 x = log3 4 mod 13 (3x = 4 mod 13 无 解 ) x = log2 3 mod 13 = 4 (24 = 3 mod 13) 幂运算是相对容易的, 求解离散对数通常是难解 问题 Discrete logs (or indices) share the properties of normal logarithms, and are quite useful. However whilst exponentiation is relatively easy, finding discrete logs is not, in fact is as hard as factoring a number. It is the inverse problem to exponentiation, and is an example of a problem thats "easy" one way (raising a number to a power), but "hard" the other (finding what power a number is raised to giving the desired answer). Problems with this type of asymmetry are very rare, but are of critical usefulness in modern cryptography.

Discrete Logarithms 模n的整数幂 根据欧拉定理(定理8.3), aφ(n) mod n=1. 考虑欧拉定理更一般的形式：am mod n =1, gcd (a, n)=1, 至少有一个整数m满足am mod n =1, 即m=φ(n), 使其成立的最小正幂m为下列之一： a(模n)的阶 a(模n)的阶的整数倍 7模19的各次幂 71=7 mod 19; 72=49=2x19+11=11 mod 19 73=343=18x19+1=1 mod 19; 74=2401=126x19+7=7 mod 19 75=16807=884x19+11=11 mod 19 因为73=1 mod 19, 可得73＋j= 737j=7j mod 19, 这说明若7的两个指数相差3或3的倍数，则以它们为指数的7的模19幂是相同的，即该序列是周期性的，且其周期长是使7m=1 mod 19成立的最小正幂m。 Discrete logs (or indices) share the properties of normal logarithms, and are quite useful. However whilst exponentiation is relatively easy, finding discrete logs is not, in fact is as hard as factoring a number. It is the inverse problem to exponentiation, and is an example of a problem thats "easy" one way (raising a number to a power), but "hard" the other (finding what power a number is raised to giving the desired answer). Problems with this type of asymmetry are very rare, but are of critical usefulness in modern cryptography.

Discrete Logarithms 更一般地, φ(n)是一个数所属的模n的可能的最高指数, 如果一个数的阶是φ(n), 则称之为n的本原根。 若a是n的本原根, 则其幂a,a2,…,aφ(n)是模n各不相同的, 且均与n互素; 若a是素数p的本原根, 则a,a2,…,ap-1是模p各不相同的。素数19的本原根为2,3,10,13,14和15。 不是所有的整数都有本原根，只有形为2, 4, pα和2pα的整数才有本原根，这里p是任何奇素数，α是正整数。

模19的整数幂

离散对数的计算 考虑方程y = gx mod p,若给定整数g, x和p, 可以直 接求出y, 最多需要[log2x]+w(x)-1次乘法, w(x)为x 中所有1的个数。如x =15, 即 x =(1111)2, w(x)=4, 则g15 =((g2)g)2·g)2·g mod p, 只需要3 + 4 -1=6次乘法。 但是若给定p, g及y, 求x, 则为DLP问题, 最快方法需 要L(p)=exp{(lnpln(lnp))½}次运算。 当p=512位时, L(p)约为2256≈1077, 计算上不可 行。因为2100≈1030, 计算要1016年。

8.9 二次剩余问题(Quadratic Residues) 求解 x2 mod n = a x=? 二次剩余或平方剩余 若正整数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称为a模n的一个平方根。

二次剩余问题 例：若n=7, 模n的完全剩余集合为{1, 2, 3, 4, 5, 6}, 其 中, {1, 2, 4}是QRn, 即1, 2, 4为模7的二次剩余, 因为： 12 mod 7=1 42 mod 7=2 22 mod 7=4 而{3, 5, 6}为模7的非平方剩余, 因为无法找到整数 解满足 x2 = a mod 7, a∈{3, 5, 6} 定理8.8 给定 a, 0<a<n, a∈R2, 当且仅当Ek(a)=ae mod n ∈R2, k=(e, n)。即, 如果消息m=a, a∈R2, 加密/解 密m, 结果仍保留属于R2的特性。

二次剩余问题 证明：如果a∈R2, 则对某些x, 有x2 mod n = a. ∵ Ek(a)=ae mod n = (x2)e mod n = (xe)2 mod n ∴ Ek(a)∈R2 如果Ek(a)∈R2, ∵解密等同加密, ∴ (Ek(a))d mod n =a, a∈R2 例： n=11, 3∈R2 模11, ∵ 52 mod 11=3 If e=4, 34 mod 11=4 ∈R2, ∵ 22 mod 11=4 5 ∈R2 mod 11, ∵ 42 mod 11=5 e=3, 53 mod 11=4 ∈R2, ∵ 22 mod 11=4 e=4, 54 mod 11=9 ∈R2, ∵ 32 mod 11=9

求解 x2 mod p=a的问题 定理8.9 对于素数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 = (p2–2px1 + x12) mod p = x12 mod p = a p-x1≠x1, 所以这两个解是可以区分的, 除非p可被2整除。 定理8.10 对于素数p, p>2, 有(p-1)/2个模p的二次剩余, (p-1)/2个非二次剩余。 证明：显然, (p-1)/2个余数12, 22, …, ((p-1)/2)2 mod p为R2. 不可能有更多的二次剩余了, 因为对每一个a∈R2, 至少它的一个平方根 x1或者p-x1必定落在[1, (p-1)/2]之中. 或者:对于 [1, (p-1)/2]之中的任何x，必有p-x使得 x2=(p-x)2=a mod p,故只有(p-1)/2个模p的二次剩余。

求解 x2 mod p=a的问题 设 x2 mod p = 1 x2 mod p = 2 … x2 mod p = p-1 我们可以计算(1, 2, 3, …, p-1)平方模p,即x2 mod p=a. 如果a是模p的平方剩余, 则x2 mod p = a在[1, p-1]中有两个可区分的解。所以, 在[1, p-1]中, 仅有 (p-1)/2个等式有解, 是平方剩余; 1/2个等式无解, 非 平方剩余。

求解 x2 mod p=a的问题 定理8.11 (二次剩余特点) 例：如果p=7, 在[1, 6]中是平方剩余的a只有三个, 即{1, 2, 4}. 如果p=11, 12 mod 11 = 1 62 mod 11 = 3 22 mod 11 = 4 72 mod 11 = 5 32 mod 11 = 9 82 mod 11 = 9 42 mod 11 = 5 92 mod 11 = 4 52 mod 11 = 3 102 mod 11=1 只有(p-1)/2个a∈R2, 每个a有两个解, 即x1和p-x1。 定理8.11 (二次剩余特点) For prime p>2, and 0<a<p, a(p-1)/2 mod p = 1, if a∈R2 a(p-1)/2 mod p = p-1, otherwise.

求解 x2 mod p=a的问题 证明：根据Fermat’s theorem, 即ap-1 mod p = 1, ∵ p是奇数, 因此可以因式分解ap-1–1, 得 (a(p-1)/2 + 1)(a(p-1)/2 - 1) mod p = 0, 即p可整除a(p-1)/2 +1或a(p-1)/2–1, 不能同时整除, 不然意味着p可以整除它们的差, 即2. ∴ a(p-1)/2 mod p = ±1 ∵ a∈R2, 一定存在x, x2 mod p = a. ∴ a(p-1)/2 mod p = (x2)(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的解。

8.10 不经意传输 Oblivious Transfer (1) Rabin的Oblivious Transfer Alice可以0.5的概率给Bob传递了秘密 Bob可以0.5的概率得到Alice的秘密 Bob可以0.5的概率什么也得不到 Alice对Bob是否获得秘密一无所知 Oblivious Transfer Protocol A：n=p×q →B B：a = x2 mod n →A, 0<x<n, gcd(x, n)=1 A：因为知道p和q, 则可以计算x2 mod n = a的四个根： x, n-x, y, n-y, 从中随机挑选一个送给B B：若收到y或n-y, 则可以从x, y计算p和q： gcd(x+y, n)=p 或q 若收到x或n-x, 则B什么也得不到。

不经意传输(2) 根据定理8.6, d1,d2,…,dt两两互素, n=d1d2…dt, 则 f(x) mod n=0, 当且仅当f(x) mod di =0 ∴ x2 mod n = a可以有x2 mod p = a, x2 mod q = a 根据定理8.9, p>0, p是素数, 0<a<p. x2 mod p = a有两个解, 如果a∈R2, 否则无解。 ∴ x2 mod p = a有两个解, x1和p-x1; x2 mod q = a有两个解, x2和q-x2 应用CRT, 可以求出x2 mod n = a的四个解, x mod di=xi, i=1,..t Z1 mod p = x1 Z3 mod p = p-x1 Z1 mod q = x2 Z3 mod q = x2 Z2 mod p = x1 Z4 mod p = p-x1 Z2 mod q = q-x2 Z4 mod q = q-x2

不经意传输(3) (对于a∈R2 ，令x= a(p+1)/4 mod p 这样， x 的确是α 模p 的一个平方根。) 如果p+1和q+1可以被4整除, 则容易计算x2 mod p = a 和x2 mod q = a的解： (对于a∈R2 ，令x= a(p+1)/4 mod p x2 = a(p+1)/2 mod p= a(p-1)/2 a mod p=a mod p 这样， x 的确是α 模p 的一个平方根。) x1 = a(p+1)/4 mod p, 则导出p-x1 x2 = a(q+1)/4 mod q, 则导出q-x2 例：p=3, q=7, n=21. Bob选x=5, 计算a=52 mod 21=4送给Alice. Alice计算：x1 = 4(3+1)/4 mod 3=1, 则导出p-x1=2 x2 = 4(7+1)/4 mod 7=2, 则导出q-x2=5 Z1=crt(n, p, q, x1, x2)=16, 即n-x Z2=crt(n, p, q, x1, q-x2)=19, 即y Z3=crt(n, p, q, p-x1, x2)=2, 即n-y Z4=crt(n, p, q, p-x1, q-x2)=5, 即x Alice任选一个, 如y=19给Bob, Bob计算 gcd(x+y, n)=gcd(5+19,21)=gcd(24,21)=3, 即p, q=21/p=21/3=7 若Alice选Z1=16给Bob, 则gcd(x+n-x, n)=gcd(n, n)=1, Bob什么也得不到。

第8章习题 19, 20, 21, 加上5道补充题 1, 2, 3, 4, 6, 8, 9, 12 第一部分作业 第二部分作业 ( 8.21(a)题目有误，应改为17x2 ≡10 mod 29 ) 给定p=17，g=3， 模p的阶T是什么？ 找出所有的本原元素。 分别用费马定理和Euclid算法求22x mod 37=1的逆x Find out all solutions for 6x mod 21 = 9. 见下页

补充题(续) 4. Consider the equations x mod p = x1 or p – x1 x mod q = x2 or q – x2 where n = pq for primes p and q. There are four common solutions, given by z1 = crt (n, p, q, x1, x2) z2 = crt (n, p, q, x1, q-x2) z3 = crt (n, p, q, p-x1, x2) z4 = crt (n, p, q, p-x1, q-x2) Show that z4 = n –z1 and z3 = n –z2 5. Using the result of the preceding problem, find the 4 solutions to the equation x2 mod 77 = 4 by first finding solutions to x2 mod 7 = 4 and x2 mod 11 = 4.