现代密码学理论与实践 第8章 数论入门 Fourth Edition by William Stallings Slides by 杨寿保

Presentation on theme: "现代密码学理论与实践 第8章 数论入门 Fourth Edition by William Stallings Slides by 杨寿保"— Presentation transcript:

1 现代密码学理论与实践 第8章 数论入门 Fourth Edition by William Stallings Slides by 杨寿保
2012年10月 2018/11/14 现代密码学理论与实践-08

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

3 Chapter 8 Introduction to Number Theory
The Devil said to Daniel Webster: "Set me a task I can't carry out, and I'll give you anything in the world you ask for." Daniel Webster: "Fair enough. Prove that for n greater than 2, the equation an + bn = cn has no non-trivial solution in the integers." They agreed on a three-day period for the labor, and the Devil disappeared. At the end of three days, the Devil presented himself, haggard, jumpy, biting his lip. Daniel Webster said to him, "Well, how did you do at my task? Did you prove the theorem?' "Eh? No no, I haven't proved it." "Then I can have whatever I ask for? Money? The Presidency?' "What? Oh, that—of course. But listen! If we could just prove the following two lemmas—" —The Mathematical Magpie, Clifton Fadiman Opening quote. A number of concepts from number theory are essential in the design of public-key cryptographic algorithms, which this chapter will introduce. 2018/11/14 现代密码学理论与实践-08

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

5 8.1 素数 Prime Numbers 整数p>1是素数当且仅当它只有因子±1和±p，如2,3,5,7是素数，而4,6,8,9,10不是素数 素数不能写作其他数的乘积形式 1是素数，但是通常没有什么用 素数是数论的核心 小于200的素数如下 2018/11/14 现代密码学理论与实践-08

6 小于2000的素数 2018/11/14 现代密码学理论与实践-08

7 合数的素因子分解 其中每个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. 2018/11/14 现代密码学理论与实践-08

8 合数的素因子分解 任一给定的正整数, 可通过简单列出所有后面公式中非零指数分量来说明. 两个数的乘法等同于对应指数分量的加法
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 2018/11/14 现代密码学理论与实践-08

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

10 单向函数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)，如旅馆太平门。 2018/11/14 现代密码学理论与实践-08

11 单向函数举例 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, 只需要 =6次乘法。 但是若给定p, g及y, 求x, 则为DLP问题, 最快方法需要L(p)=exp{(lnpln(lnp))½}次运算。 当p=512位时, L(p)约为2256≈1077, 计算上不可行, 因为2100≈1030, 计算要1016年。 2018/11/14 现代密码学理论与实践-08

12 单向函数举例(续) 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的正整数。若p≈n, 解离散对数比因数分解难。 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) 2018/11/14 现代密码学理论与实践-08

13 单向函数及其交换性 单向函数的交换性(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)) 2018/11/14 现代密码学理论与实践-08

14 指数函数(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)产生之序列为周期序列。 2018/11/14 现代密码学理论与实践-08

15 指数函数之特性(续) 当存在最小正整数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 =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 2018/11/14 现代密码学理论与实践-08

16 指数函数之特性(续) 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)。 2018/11/14 现代密码学理论与实践-08

17 指数函数之特性(续) 本原元素举例：p=11, g=2, φ(p-1)= φ(10)=4, 即1, 3, 7, 9与p-1互素。若 g=2为模p之本原元素, 则 21=2, 23=8, 27=7, 29 =6, mod 11, 均为模11之本原元素。找到一个本原元素后可以容易找到所有本原元素, 问题是如何找到第一个本原元素。 3. 交换性 指数函数满足交换性, 因为: Ex(Ey(g))=Ex(gy)=(gy)x=gyx Ey(Ex(g))=Ey(gx)=(gx)y=gxy ∴ Ex(Ey(g))=Ey(Ex(g)) 2018/11/14 现代密码学理论与实践-08

18 指数函数之特性(续) 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) 2018/11/14 现代密码学理论与实践-08

19 指数函数之特性(续) 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问题。 2018/11/14 现代密码学理论与实践-08

20 指数函数之特性(续) 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算法正确性的证明 2018/11/14 现代密码学理论与实践-08

21 快速指数运算法—平方再乘法 快速指数运算法—平方再乘法(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个乘法(平方算一次乘)。 2018/11/14 现代密码学理论与实践-08

22 快速指数运算法—平方再乘法 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 2018/11/14 现代密码学理论与实践-08

23 8.2 费马定理和欧拉定理 定理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 = 证毕 例如：a=7, p=19, ap-1mod p=718 mod 19=? 72=49≡11 mod =121≡7 mod 19 78=49≡11 mod =121≡7 mod 19 ap-1=718=716x72≡7x11≡1 mod 19 2018/11/14 现代密码学理论与实践-08

24 费马定理的等价形式 费马定理等价形式 ap≡a mod p, p是素数，a是任意正整数
p=5, a=10, 105=100000≡10 mod 5≡0 mod 5 2018/11/14 现代密码学理论与实践-08

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

26 欧拉函数φ(n)的证明 φ(n)= (pi-1), n= ... Pi 均为素数。
定理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) 例：φ(35)=24=φ(5)φ(7)=4x6=24 一般说来, 对任意n, φ(n)由下式给出： φ(n)= (pi-1), n= Pi 均为素数。 例：n=24=23x31, φ(n)=φ(24)=22(2-1)30(3-1)=8 2018/11/14 现代密码学理论与实践-08

27 欧拉定理 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 2018/11/14 现代密码学理论与实践-08

28 欧拉定理的等价形式及推论 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 2018/11/14 现代密码学理论与实践-08

29 8.3 素性测试 密码学中常常需要寻找大素数 传统的方法是用测试除法来过滤非素数,即依次除小于该数平方根的所有素数,这种方法只对较小的数有用
可以采用基于素数特性的统计素性测试方法 其中所有的素数都满足素数特性 但是有一些被称为伪素数的合数也满足素数特性 也可使用一种较慢的确定性素性测试方法 2018/11/14 现代密码学理论与实践-08

30 8.3.1 Miller-Rabin算法测试素性 这是一种基于费马定理的方法 假设n是素数, 则有an-1 = 1 mod n
n-1 = 2kq k>0, q是奇数 为证明这一点，用2去除偶数(n-1)，直至所得结果为奇数q，此处共做k次除法；如果n是二进制数，则将该数右移，直到最右边的比特为1，共移动了k次。 2018/11/14 现代密码学理论与实践-08

31 素数的两个性质之一 如果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, 则(a mod p)2 =1成立的条件是a mod p=1或者a mod p = -1 （p为合数也成立，比如p=4 a=1, 3 a2mod p=1） 2018/11/14 现代密码学理论与实践-08

32 素数的两个性质之二 设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 2018/11/14 现代密码学理论与实践-08

33 详细的算法 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 想一想性质1：如果p是素数, a是小于p的正整数, 则 a2 mod p=1, 当且仅当a mod p=1或者a mod p= -1 mod p=p-1 2018/11/14 现代密码学理论与实践-08

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

35 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") 2018/11/14 现代密码学理论与实践-08

36 素数测试举例 例1：n=29, 有(n-1)=28=22(7)=2kq. 取a=10, 计算 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=25(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 2018/11/14 现代密码学理论与实践-08

37 重复使用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是素数 2018/11/14 现代密码学理论与实践-08

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

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

40 计算乘法逆元素 ax mod n =1, x=? 问题：ax mod n = 1, x=a-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. 如果φ(n)不知, 可以用Euclid’s计算最大公约数算法的扩展来求逆. 2018/11/14 现代密码学理论与实践-08

41 快速指数运算法求逆元素(φ(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 2018/11/14 现代密码学理论与实践-08

42 扩展的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的逆元素。 2018/11/14 现代密码学理论与实践-08

43 在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 = mod 1011 = (100)6 mod 1011=111 2018/11/14 现代密码学理论与实践-08

44 求解 ax mod n = b 的问题 定理8.5 令g=gcd(a, n), 假如g|b (即b mod g=0), 则ax 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的解；否则无解。 证明：假如ax mod n =b 在[1, n-1]中有一个解, 则n|(ax-b) 因为g|n, g|ax, 则g|b一定成立。 等式(a/g)x mod (n/g)=1有唯一的解x0, x0∈[1,(n/g)-1], x1=(b/g)x0 mod (n/g)是(a/g)x mod (n/g)=(b/g)在[1, (n/g)-1]中的一个解。 2018/11/14 现代密码学理论与实践-08

45 求解ax mod n =b的问题 所以, (a/g)x1 - (b/g)=k(n/g), 被g乘, 得ax1 - b =kn.
这就是说x1是ax mod n =b的一个解。 因此, 任何x∈[1, n-1], x=x1 mod(n/g)也是 ax mod n =b的一个解。 a(x1+kn/g) mod n=b 等价于ax1 mod n=b ∵ak(n/g)= sn (k, s 均为整数) 所有解由下式给出： x = x1 + t(n/g), t=0,1, …, g-1 2018/11/14 现代密码学理论与实践-08

46 求解ax mod n =b的问题 例：6x mod 10=4 ∵g=gcd(6,10)=2, 2|4, ∴应该有两个解。
先求x0, (a/g)x mod (n/g)=1 → (6/2)x mod (10/2)=1, → 3x mod 5=1, x0=2 根据x=[(b/g)x0 + t(n/g)] mod n, t=0,1,…, g-1 x=[(4/2)2 +0] mod 10 =4, t=0 x=[(4/2)2 +(10/2)] mod 10 =9, t=1 或者：x1=(b/g)x0 mod (n/g)=(4/2)2 mod (10/2)=4 x= x1 + t(10/2)=4, t=0 x= x1 + t(10/2)=9, t=1 2018/11/14 现代密码学理论与实践-08

47 用定理8.6求解ax mod n=b 定理8.6 证明：∵di两两互素, 令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的解。 2018/11/14 现代密码学理论与实践-08

48 8.4 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 (两个断言证明略) 2018/11/14 现代密码学理论与实践-08

49 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=[ (n/di)yi xi] mod n. (事实上,x=xi+kdi, 1≤i≤t, k为正整数) ∵ x mod di = (n/di)yixi mod di = xi, ((n/di)yi mod di =1) ∴ x是x mod di=xi (1≤i≤t)的公共解。 2018/11/14 现代密码学理论与实践-08

50 中国余数定理的算法 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((n/di) mod di); x:=0; x:=[x + (n/di)yi xi] mod n; crt:=x end 2018/11/14 现代密码学理论与实践-08

51 例：求解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 根据(n/di)yi mod di=1计算 (10/2)y1 mod 2=1 (10/5)y2 mod 5=1 得y1=1, y2=3. 根据x=[ (n/di)yi xi] mod n 求x ∴ x=[(10/2)y1 x1 + (10/5)y2 x2] mod 10 =(5*1*1 + 2*3*2) mod 10 =7 2018/11/14 现代密码学理论与实践-08

52 孙子定理(孙子算经, 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，(n/di)yi mod di=1 (105/3)y1 mod 3=1 (105/5)y2 mod 5=1 (105/7)y3 mod 7=1 得： 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 2018/11/14 现代密码学理论与实践-08

53 8.5 离散对数问题(discrete logarithm)
幂运算的求逆问题就是找到一个数模p的离散对数, 也就是找到x, 满足ax = b mod p, 写作 x=loga b mod p 或 x = inda, p (b) 如果a是素根, 则x总是存在, 否则不一定存在 x = log3 4 mod (3x =4 mod 13无解, 因为3不是模13的素根) x = log2 3 mod 13 = 4 (24 = 3 mod 13) 幂运算是相对容易的, 幂运算的求逆问题即求解离散对数通常是难解问题，称为DLP 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. 2018/11/14 现代密码学理论与实践-08

54 Discrete Logarithms 模n的整数幂 7模19的各次幂
根据欧拉定理(定理8.3), aφ(n) mod n= 考虑欧拉定理更一般的形式：am mod n =1, gcd (a, n)=1, 至少有一个整数m满足am mod n =1, 即m=φ(n)， 使其成立的最小正幂m为下列之一： a(模n)的阶 a所属的模n的指数 a所产生的周期长度 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; 76=3432=1 mod 19 因为73=1 mod 19, 可得73＋j= 737J=7J mod 19, 这说明若7的两个指数相差3或3的倍数，则以它们为指数的7模19幂是相同的，即该序列是周期性的，且其周期长是使7m=1 mod 19成立的最小正幂m，此例m=3。 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. 2018/11/14 现代密码学理论与实践-08

55 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是任何奇素数, α是正整数。 2018/11/14 现代密码学理论与实践-08

56 模19的整数幂 2018/11/14 现代密码学理论与实践-08

57 离散对数的计算 考虑方程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, 只需要 =6次乘法。 但是若给定p, g及y, 求x, 则为DLP问题, 最快方法需要L(p)=exp{(lnpln(lnp))½}次运算。 当p=512位时, L(p)约为2256≈1077, 计算上不可行。因为2100≈1030, 计算要1016年。 2018/11/14 现代密码学理论与实践-08

58 2018/11/14 现代密码学理论与实践-08

59 求解 x2 mod n = a 二次剩余或平方剩余问题(Quadratic Residues)
若正整数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的一个平方根。 2018/11/14 现代密码学理论与实践-08

60 二次剩余问题 例：若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的特性。 2018/11/14 现代密码学理论与实践-08

61 二次剩余问题 证明：如果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 2018/11/14 现代密码学理论与实践-08

62 首先求解 x2 mod p=a 定理8.9 定理8.10 证明：假如a∈R2, 至少有一个解x1, 满足x12 mod p=a, 但是
对于素数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]之中. 2018/11/14 现代密码学理论与实践-08

63 求解 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个等式无解, 非平方剩余。 2018/11/14 现代密码学理论与实践-08

64 求解 x2 mod p=a的问题 定理8.11 例：如果p=7, 在[1, 6]中是平方剩余的a只有三个, 即{1, 2, 4}.
如果p=11, 12 mod 11 = mod 11 = 3 22 mod 11 = mod 11 = 5 32 mod 11 = mod 11 = 9 42 mod 11 = mod 11 = 4 52 mod 11 = 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. 2018/11/14 现代密码学理论与实践-08

65 求解 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的解。 2018/11/14 现代密码学理论与实践-08

66 不经意传输协议求解x2 mod n = a Rabin的Oblivious Transfer不经意传输
Alice可以0.5的概率给Bob传递了秘密 Bob可以0.5的概率得到Alice的秘密 Bob可以0.5的概率什么也得不到 Alice对Bob是否获得秘密一无所知 Oblivious Transfer 求解x2 mod n = a 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什么也得不到。 2018/11/14 现代密码学理论与实践-08

67 不经意传输协议求解x2 mod n = a 根据定理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 2018/11/14 现代密码学理论与实践-08

68 不经意传输求解x2 mod n = a 如果p+1和q+1可以被4整除, 则容易计算x2 mod p = a
和x2 mod q = a的解： 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什么也得不到 2018/11/14 现代密码学理论与实践-08

69 第8章习题 Chapter 8: 3, 4, 5, 6, 8, 9 Chapter 8: 19, 20
第一部分作业 (Due: Oct. 30, 2012) Chapter 8: , 4, 5, 6, 8, 9 第二部分作业 (Due: Nov. 6, 2012) Chapter 8: 19, 20 加上补充4题: 分别用费马定理和Euclid算法求22x mod 37=1的逆x 找出 6x mod 21 = 9 的所有解. 见下页 2018/11/14 现代密码学理论与实践-08

70 第8章习题 (续) 3. 考虑如下等式 x mod p = x1 or p – x1 x mod q = x2 or q – x2
n = pq，p和q为素数. 这样，有4个解如下： 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) 证明： z4 = n –z1 and z3 = n –z2 4. 求x2 mod 77 = 4 的4个解，提示：首先找出x2 mod 7 = 4 和x2 mod 11 = 4的解. 2018/11/14 现代密码学理论与实践-08