1 清华大学宋斌恒1 Lecture 10. Number theoretic Algorithm 清华大学 宋斌恒 清华大学宋斌恒2 From useless to useful ? Number theory is regarded as a beautiful but largely useless in the past ? Today number-theoretic algorithms are used widely 清华大学宋斌恒3 Contents ? Basic concepts ? Divisibility and divisor ? Prime and composite numbers ? Division theorem ? Greatest common divisors ? Relative prime integers ? Unique factorization ? Euclid algorithm and its complexity analysis ? Modular arithmetic ? Solving modular linear equation ?孙子定理【中国剩余数定理】 ? RSA 清华大学宋斌恒4 Basic Concepts ? Z={…,-2,-1,0,1,2,…} Integers 整数 ? N={0,1,2,3…} Natural numbers 自然数 ? d|a (d divides a) d整除a，存在整数k使得 a=kd ? Divisor: 约数 ? Trivial divisor：平凡约数【举例】 ?素数【1，2，3，4那个是素数】 ?合数【1，2，3，4那个是合数】 清华大学宋斌恒5 与算法复杂度相关的概念 ?整数的表示： ?一进制 ?二进制【十进制等】的长度作为一个整数的复 杂度度量。 ? The function of “Log * of n” ? f (i) (n)=n if i==0 ? f (i) (n)=f(f (i) (n)) if i>0 ? lg* n = min{i>=0: lg (i) (n)<=1} 清华大学宋斌恒6 除法定理 ?对任意整数a和正整数n，存在唯一整数q和r使 得0≤r<n, a=qn+r ? Quotient:【q】 ? Remainder (residue 【r】) ? Z n ={[a] n : 0≤a≤n-1} ? [a] n ={a+kn: k in Z} ?【[a] n 的代表？】 2 清华大学宋斌恒7 最大公约数 ? Gcd: greatest common devisors ?定理：如果a和b是任意不等于0的整数，则 gcd(a,b)=集合{ax+by:x,y in Z}的最小整数。 【证明！】 ?互素：Relative prime integers ?如果gcd(a, b)=1称a和b互素 ?唯一分解定理 ? a=Π i=1,…n (p i ei ), p i 是素数单调升【是否可以通过 此方法计算gcd? 复杂度？】 ?？如何证明有无穷多素数？？【课堂提问】 清华大学宋斌恒8 gcd ? GCD递推定理：gcd(a,b)=gcd(b,a mod b) ?辗转相除法【如何说明其正确性？】 ?存在x和y使得gcd(a,b)=xa+yb。 ?西方人叫Euclid算法 清华大学宋斌恒9 Euclid算法 1. Euclid(a,b) 1. If b==0 return a 2. Return Euclid(b,a mod b) ? Running time: ? Steps of division: O(lg a) = O(n) n is the bit length of a. ? Lame’s theorem: 欧几里德算法迭代步数小于k，其 中F k 是第k个Fibonacci数。 ?证明提示：数学归纳法证明：如果a>b>=1而且上述 Euclid算法进行了k步递归，则a>= F k+2 and b>= F k+1 清华大学宋斌恒10 扩展欧几里德算法 ? Extended-Euclid(a,b) ? If b=0 then return (a,1,0) ? (d’,x’,y’)?Extended-Euclid(b,a mod b) ? Return (d’,y’,x’-[a/b]y’); 清华大学宋斌恒11 计算最大公约数及其线性组合表示 ab[a/b] dxy 140 91 1 7 2 -3 91 49 1 7 -1 2 x’-[a/b]y’ 49 42 1 7 1 -1 x’-[a/b]y’ 42 7 6 7 0 1 x’-[a/b]y’ 70- 710 清华大学宋斌恒12 群的概念？ ?群(S，⊕ ) 1.封闭性 2.么元 3.结合率 4.逆元 交换率：交换群＝Abelian群 3 清华大学宋斌恒13 Modular arithmetic ?＋ n 群， ?× n 群 ? (Z n ,+ n )是有限Abel群 ? (Z * n ,× n )是有限Abel群 ?其中Z * n ＝{[a] n : gcd(a,n)=1} 清华大学宋斌恒14 . 15 群 14 13 11 8 47 14 42 1 14131187421. 15 清华大学宋斌恒15 Euler’s phi function φ(n)=nΠ p|n (1-1/p) is the size of Z * n . 欧拉φ函数 ?子群，真子群， ? Lagrange’s theorem: 有限群的子群的元素个 数是原群元素个数的约数。 清华大学宋斌恒16 由一个元素生成[张成]的子群 ?幂： ? a (k) = a ⊕ a ⊕ a ⊕ a ⊕ …⊕ a ? <a>={a (k) , k>=1} ? Order of a: 使a (k) ＝e的最小k 清华大学宋斌恒17 Solving modular linear equation ? ax ≡b (mod n) ? <a> 表示由a 生成的Z n 的子群 ? d=gcd(a,n) ? ?<a>=<d> in Z n . ? |<a>|=n/d ?利用扩充欧拉算法求解上述问题，可以得到有无解，有解 时给出所有解。 ?如果d|b则有b/d个解，x 0 =x’(b/d) mod n, x’是扩展欧几理 德算法的系数 ? x 0 +i(n/d) mod n; i=0,…,d-1通解 清华大学宋斌恒18 孙子点兵【中国余数定理】 ? a ??(a 1 ,a 2 ,…,a k )， ? a in Z n , ? a i in Z n i , ? n= n 1 n 2 …n k 所有n i 两两互素 ? Z n 与Z n1 ×Z n2 ×…×Z nk .等价 ?求逆与系数。 ? a=Σ a i m i (m i -1 mod n i ), ? m i =n 1 n 2 …n i-1 n i+1 …n k ?其中m i (m i -1 mod n i )是基本解 4 清华大学宋斌恒19 鬼谷算题 ?在鬼谷算题中有这样一个著名的题目：“今有物 不知其数，三三数之剩二，五五数之剩三，七 七数之剩二，问物几何?” ?我国宋代学者对这类题目钻研已颇为精深，总 结出了“三人同行七十稀，五树梅花廿一枝，七 子团圆正半月，去百零五便得知。”这样的口 诀，意思是说“以三三数之，余数乘以七十；五 五数之，余数乘以二十一；七七数之，余数乘 十五。三者相加，如不大于一百零五，即为答 数；否则须减去一百零五或其倍数。 清华大学宋斌恒20 解答 ? 3个一排余2、 ? 5个一排余3、 ? 7个一排余2、 ?【2】×70＋【3】×21＋【2】×15－105＝ 128 ?三人同行70稀, 五树梅花廿一支, 七子团圆正半 月, 抛五去百便得知。 清华大学宋斌恒21 利用公式求基本解 ? 35×（35 －1 mod 3）＝70 ? 21×（21 －1 mod 5）＝21 ? 15×（15 －1 mod 7）＝15 ?更多内容参见论文《中国剩余定理》 ?数学研究所李文林袁向东 清华大学宋斌恒22 元素的幂 ? 3 i mod 7 ? Euler’s theorem: ? For any integer n >1. ? a φ(n) ≡1 (mod n) for all a in Z * n . ? Fermat’s theorem: ? a p-1 ≡1 (mod p ) for all a in Z * p . ?如何计算a b (mod n)？见下页 清华大学宋斌恒23 MODULAR- EXPONENTIATION(a,b,n) 1 c←0 2 d←1 3 let <b k ,…b 0 > be the binary rep. of b 4 for i←k downto 0 1 c ←2c 2 d←(d ? d) mod n 3 if b i = 1 then 1 c←c + 1 2 d←(d ? a) mod n 5 return d 【复杂度？】 清华大学宋斌恒24 密码学 ?对称加密： ?明文m ?密文e ?密钥k ?加密函数E k ： ?解密函数D k ： ? e=E k (m), 要求 ? m=D k (e) ? D k E k =I. 5 清华大学宋斌恒25 经典与现代对称加密算法 ?字符移位 ?字符置换 ? DES ?双重DES 清华大学宋斌恒26 非对称加密算法 ?解决对称加密算法在分布系统中的密钥管理缺陷：n个 人通讯，需要每个人记载n个密码，秘码存储量总数为 n 2 。 ?工作原理：每个人有一个（公钥，私钥）对，其中公 钥可以发布到任何地方。每个人只需要保存自己的私 钥即可，其中要求： ?利用公钥加密可以用私钥解密，反之亦然， ?可以验证信息的发送人 ?保证只有信息的接收人才能得到消息等 清华大学宋斌恒27 公钥理论 ?理论上要达到以上要求，公钥和私钥是可以互 相确定的，即给定公钥可以求出私钥，反之亦 然，如果给定公钥能求出私钥，那公钥体系岂 不没有任何意义！ ?问题是：理论上要存在，而实际上不可算，就 能达到目标。 清华大学宋斌恒28 RSA算法 ?取2个不等的大素数p,q, 如其长度为512【或更 长】位 ?计算n=pq ?选择较小的奇数e，它和φ(n)＝(p-1)(q-1)互素 ?计算e在模φ(n)下的逆d ?发布(e,n)作为公钥 ?保存(d,n)作为私钥 清华大学宋斌恒29 RSA加密算法 ? A message m is a number in Z n , ?用公钥转换：P(M)=M e (mod n) ?用私钥转换：S (M)=M d (mod n) ?定理：PS(M)=SP(M)=M ?两次转换的复杂性：如果n的长度是k，则需要lge＋lgd 次的长度是k的数的乘法，若乘法复杂度为长度的平 方，则整个复杂度为k 3 。如果k=1024,则需要1 giga的 运算量。 清华大学宋斌恒30 RSA被攻击的可能性 ?由于(e,n) 公开，从(e,n)计算(d,n) ?目前没有发现比分解n＝pq更为容易的算法，而 因式分解是NPC问题，故目前攻击困难 6 清华大学宋斌恒31 RSA算法的应用 ?不可抵赖性：Alice 发信给Bob，如何保证 Bob有充分的理由证明此信是Alice发出而不是 他人？任何人包括Alice不能否认这是Alice发出 的信息。 清华大学宋斌恒32 实现RSA算法体系要做的工作 ?大整数的表示 ?如何任意选取两个大素数（512、1024甚至2048位的 素数）？ ?没有直接方法可用，利用测试法可以保证以足够大的概 率保证选定的数是一个素数，参见p887.- ?大整数的加法运算和模加运算 ?大整数的乘法运算和模乘运算 ? Divide and Conquer 可以得到O(n lg 3 )复杂度的乘法 ?幂乘算法的实现。 清华大学宋斌恒33 RSA及其它加密算法的克星 ?干草堆里找针（大海捞针）Find a needle in a stack of hay, 量子计算机可以在sqrt(n)的时间 内找到n个散乱数字中的某一个。 ?大海捞针：大海里有一根针，需要判断它存在 的位置，如果你有一个具有魔法的吸铁石，可 以在一秒内判断任何区域内有没有针，则你可 以在非常短的时间内把针找到！ ?非确定图灵机可以做到这一点 清华大学宋斌恒34 密码系统需要防范的攻击 1.监听与分析 2.伪造其中一方（服务器或客户端） 3.代理（在线路中伪造双方） 4.窜改 5.重放 6.综合 清华大学宋斌恒35 密码系统要考虑的问题 ?随机数 ?哈希函数 ?对称加密算法 ?非对称加密算法 ?密码协议 清华大学宋斌恒36 安全协议介绍 ?如何利用对称加密系统实现安全通话： ?设k是双方共享的秘密，可以利用此实现抗击前 面提到的各种攻击： ? Alice：生成随机数r1，r2，发送 (r1，des（k，r2））给Bob ? Bob：生成随机数r3，r4，发送 (r3，des（k，r4））给Alice 7 清华大学宋斌恒37 续 ? Alice：发送h(r3,k)给Bob ? Bob：发送h(r1,k)给Alice ? Alice：验证收到的值是否与h（r1，k）相等 ? Bob：验证收到的值是否与h（r3，k）相等 ?如果相等则双方互相验明共享秘密，然后利用其秘密k 解密互相发送过来的随机数r2和r4作为大家会话密钥 ?分析！ 清华大学宋斌恒38 分布授权、验证 ? Alice授权给Bob，Bob以Alice的授权身份给 Carl发送消息，Carl从Alice处得到验证。 ?公钥实现：要求授权只能由Bob使用。 ? Alice发送用自己私钥和Bob公钥加密的授权书 给Bob，Bob解密可以得到授权书 ? Bob用自己私钥和Carl公钥发送授权书到Carl， Carl发送授权书到Alice即可验证