欧拉函数 给定一个正整数n,用n表示比n小但与n互 为素数的正整数的个数，也称m为欧拉函数。 0(n)=r4-(5-1)5-(3-1)….-(n-1) 其中n=r52…rn。 例如：24=23*3,0(24)=23-1(2-1)*31-1(3-1)=8 1,5,7,11,13,17,19,23} 35=5*7,0(35)=(5-1)(7-1)=24 {1,2,3,4,6,8,9,11,12,13,16,17,18,19,22,23, 24,26,27,29,31,32,33,34} 23 CNR@HEU http://machunguang.hrbeu.edu.cn
欧拉函数 给定一个正整数 给定一个正整数 n ，用 ϕ( )n 表示比 n 小但与 n 互 为素数的正整数的个数，也称 为素数的正整数的个数，也称 为欧拉函数。 ϕ( ) ϕ( )n 其中 。 1 2 1 1 1 11 2 2 ( ) ( 1) ( 1) ( 1) n a a an n ϕ nr r r r r r − − − =− − − " 1 2 n a a a 其中 n rr r = " 。 例如：24 = 23*3，φ(24)= 23-1(2-1)*31-1(3-1)=8 1 2 1 2 n n n rr r = " {1,5,7,11,13,17,19,23} 35=5*7， φ(35)=(5 (35)=(5-1)(7-1)=24 {1,2,3,4,6,8,9,11,12,13,16,17,18,19,22,23, 24,26,27,29,31,32,33,34} 23
欧拉定理 用于证明RSA解密算法的正确性 若整数a和n互素，则am三1(modn) 证明：设中(n)=k。又设r1,r2,,rk是小于n并与n互素的数， 且由于a是与n互素的数，则ar1,ar2,,ark也和n互素且两两 不同。 若：ar三arj(modn) 则根据数论定理，因a与n互素，所以存在a满足： aa=1 (mod n) aar;=aari (mod n) 即：rr;(modn)(与假定矛盾) 所以，{r1,r2,…,rk}={ar1,ar2,…,ark} 所以， 等式arr2rk(modn）三rr2rk(modn)成立。 但r1,r2,…,rk和n互素，故ak1(modn) 24 CNR@HEU http://machunguang.hrbeu.edu.cn
欧拉定理 若整数 a 和 n 互素，则aφ(n) ≡ 1 (mod n)1 (mod n) 证明：设φ(n)=k。又设r1,r2,…,rk是小于n并与n互素的数， 且由于a是与n互素的数，则ar1,ar2,…,ark也和n互素且两两 不同。 若：ari≡arj (mod n) 则根据数论定理，因 则根据数论定理，因a与n互素，所以存在 互素，所以存在ã满足： ãa≡1 (mod n)1 (mod n) ãari≡ãarj (mod n) 即：ri≡rj (mod n) (mod n) （与假定矛盾） （与假定矛盾） 所以，{r1,r2,…,rk}={ar1,ar2,…,ark} 所以，等式akr1r2…rk (mod n)≡r1r2…rk (mod n) (mod n)成立。 24 但r1,r2,…,rk和n互素，故 ak≡1 (mod n) 用于证明RSA解密算法的正确性
举例说明 5p(24)=1m0d24 p(24)=8。又1,5,7,11,13,17,19,23是小于24并与24互素的数 1*5=5m0d24=5 5*5=25m0d24=17*5=35m0d24=11 11*5=55m0d24=713*5=65m0d24=1717*5=85m0d24=13 19*5=95m0d24=23 23*5=115m0d24=19 {1,5,7,11,13,17,19,23}={5*1,5*5,5*7,5*11,5*13,5*17,5*19,5*23} 5*1*5*5*5*7*5*11*5*13*5*17*5*19*5*23m0d24 =1*5*7*11*13*17*19*23m0d24 58=1m0d24即：5(24)=1m0d24 25 CNR@HEU http://machunguang.hrbeu.edu.cn
举例说明 5φ(24)≡1 mod 24 φ(24) 8 (24)=8。又1 11 13 1 19 23 1,5,7,11,13,17,19,23是小于24并与24互素的数. 1*5=5 mod 24≡5 5*5=25 mod 24≡1 7*5=35 mod 24≡11 11*5=55 mod 24≡7 13*5=65 mod 24≡17 17*5=85 mod 24≡13 19*5=95 mod 24≡23 23*5=115 mod 24≡19 {1 5 7 11 13 17 19 23} {5*1 5*5 5*7 5*11 5*13 5*17 5*19 5*23} {1,5,7,11,13,17,19,23} ={5*1,5*5,5*7,5*11,5*13,5*17,5*19,5*23} 5*1*5*5*5*7*5*11*5*13*5*17*5*19*5*23 mod 24 = 1 5 7 11 13 17 19 23 1 5 7 11 13 17 19 23 *5*7*11*13*17*19*23 mod 24 23 mod 24 58≡1 mod 24 即：5φ(24) ≡1 mod 24 25
应用举例 AS算法中一个引理： 计算21000000m0d77=? 设n≥2是一个自然数，ae1,gcd(a,n)=l, 则：是素数的充要条件是 (X+a)”≡Xn+a(modn) 10244mod77=(23+1001)mod77(1001与4互 显然，gcd(2,77)=1,中(77)=φ(7*11 =23+1001(mod77) =(234mod77+1001m0d77)mod77 根据欧拉定理，26m0d77=1。 =23mod77 =(462+67)2m0d77 =672mod77=(4389+100)mod77=100mod7 由于，1000000=16666*60+40 所以，21000000m0d77=216666*60+40m0d77 =240m0d77=10244mod77=234m0d77 672mod77=102mod77=23. 26 CNR@HEU http://machunguang.hrbeu.edu.cn
应用举例 计算21000000 1000000 mod 77 ≡？ 显然，gcd(2,77)=1 gcd(2,77)=1，φ(77)=φ(7*11)=6*10=60 φ(77)=φ(7*11)=6*10=60。 根据欧拉定理， 根据欧拉定理，260mod 77=1 mod 77=1。 由于，1000000=16666*60+40 1000000=16666*60+40 所以，21000000 mod 77 = 216666*60+40 所以，2 mod 77 1000000 mod 77 = 216666*60+40 mod 77 ≡ 240 mod 77 ≡10244 mod 77 ≡234 2 mod 77 1024 mod 77 23 mod 77 mod 77mod ≡ 672 mod 77 ≡ 102 mod 77≡23。 26
RSA的密钥对生成算法 1.选取两个大素数p和q,两个数长度接近且相差较 大。 2.计算n=p*q,Φ(n)=(p-1)(g-1) 3.随机选取整数e,满足gcd(e,Φ(n)=1 4.计算d,满足d*e≡1(modΦ(n))。 注：p和q保密。 e和n为公钥，d为私钥。 27 CNR@HEU http://machunguang.hrbeu.edu.cn
RSA的密钥对生成算法 1.选取两个大素数p和q，两个数长度接近且相差较 两个数长度接近且相差较 大。 2.计算n=p*q,φ(n)=(p-1)(q-1) 3. 随机选取整数e，满足gcd(e,φ(n))=1 4. 计算d，满足d*e ≡1（modφ(n)）。 注：p和q保密。 e和n为公钥 d为私钥 27 e和n为公钥，d为私钥