第五讲 密码学数学基础
2013/10/23
1
★本章授课提纲★
（1）整除、素数、最大公约数，欧几里德算法 （2）模运算、同余、乘法逆元素、扩展的欧几里 德算法 （3）中国剩余定理、费马小定理、欧拉定理
（4）模的幂、模n逆矩阵、模n平方根
（5）有限域理论
（6）素数判定和因数分解
2013/10/23 2
有限域GF(pm)上的加法和减法
举例：在GF(33)中，若a=2x2+x+2，b=2x2+2x+2
c a b cm1xm1 cm2 xm2 c1x c0
ci ai bi (mod p) i m 1
那么，c=a+b=x2+1
2013/10/2的乘法和除法 举例：在GF(33)中，若a=2x2+x+2，b=2x2+2x+2 求d=ab (2)再除以f(x)=x3+2x+1 x4+x2+1——10101 x3+2x+1——1021 二者相除，得到的余数是221 即最终结果为2x2+2x+1
26
★有限域GF(pm)上的代数运算★
有限域GF(pm)上的乘法和除法 若a,b∈GF(pm)，a与b的乘积与一般的多项式乘积 相同。其差别为，若其积的阶数等于或比m大时， 必须以不可分解多项式f(x)除之。 举例：在GF(33)中，若a=2x2+x+2，b=2x2+2x+2 求d=ab
2013/10/23
（1）素数分布极不规则
（4）模的幂、模n逆矩阵、模n平方根
（5）有限域理论
（6）素数判定和因数分解
2013/10/23 33
★本讲授课提纲★
（1）素数判定概述 （2）米勒－拉宾素数判定 （3）因数分解概述
2013/10/23
34
★本讲授课提纲★
（1）素数判定概述 （2）米勒－拉宾素数判定 （3）因数分解概述
2013/10/23
pm(p为素数)的完全剩余集的每一个元素，可以 使用m位的p进制数来表示，并进而可以使用多项 式来表示。
2013/10/23 18
★有限域的概念★
有限域GF(pm)上元素的多项式表示
令a∈GF(pm)，则a可表示成如下阶数为m-1的多项式
a am1x
m1
am2 x
m2
a1x a0
2013/10/23 29
★有限域GF(pm)上的代数运算★
有限域GF(2m)上的代数运算 有限域GF(2m)上的代数运算，是密码学里最为 关心的，因为现代密码学系统中绝大部分数据都是 01这样的比特。
加、减运算是异或，加无进位，减无借位，乘 法运算是“与”，除法运算只要位数够长即可进行。
2013/10/23
2013/10/23
13
本原根不惟一。可验证除3外，19的本原根还有2， 10，13，14，15。 注意并非所有的整数都有本原根，只有以下形式的 整数才有本原根： 2,4,pα,2pα 其中p为奇素数。
2013/10/23
14
离散对数

设p是素数，a是p的本原根，即a1,a2,…,ap-1在 mod p下 产生1到p-1的所有值，所以对b∈{1,…,p-1}，有惟一的 i∈{1,…,p-1}使得b≡ai mod p。称i为模p下以a为底b的离 散对数，记为i≡logab(mod p)。 当a、p、i已知时，用平方和乘法可比较容易地求出b，但 如果已知a、b和p，求i则非常困难。目前已知的最快的求离 散对数算法其时间复杂度为：
2013/10/23
37
★素数判定概述★
素数定理
素数定理给出一种估计素数个数的方法： 设π(x)是小于x的素数的个数，则 π(x)≈x/lnx 应用举例： 64位二进制表示的素数的个数为 264/ln264-263/ln263≈2.05×1017个
2013/10/23
38
★素数判定概述★
素数的分布特点
一般地,如果a的阶m等于φ(n)，则称a为n的本原根。 如果a是n的本原根，则 a,a2,…,aφ(n) 在mod n下互不相同且都与n互素。 特别地，如果a是素数p的本原根，则 a,a2,…,ap-1 在 mod p下都不相同。
2013/10/23
9
例如：n=9，则φ(n)=6，考虑2在mod 9下的幂 21 mod 9≡2,22 mod 9≡4
21
★本讲授课提纲★
（1）有限域及其元素的多项式表示法 （2）有限域GF(pm)上的代数运算
2013/10/23
22
★有限域GF(pm)上的代数运算★
多项式的加减乘除运算
2013/10/23
23
★有限域GF(pm)上的代数运算★
有限域GF(pm)上的加法和减法 令a,b∈GF(pm)，
a am1xm1 am2 xm2 a1x a0
1 O exp ln p 3 ln ln p
2013/10/23


2
3

所以当p很大时，该算法也是不可行的。 15
离散对数问题的算法
首先回忆一下一般对数的概念，指数函数 y=ax(a>0,a≠1)的逆函数称为以a为底x的对数，记 为y=logax。对数函数有以下性质： loga1=0, logaa=1, logaxy=logax+logay, logaxy=ylogax
这种非常大的素数通常也叫强素数
2013/10/23 36
★素数判定概述★
素数有多少个呢？
在长度为512位或略短一些的数中，有超过10151个 素数。宇宙中仅有1077个原子，如果宇宙中从诞生到 现在为止，每一微秒都需要10亿个新的素数，那么 总共需要10109个素数，现在仍然剩下约10151个512位 的素数。
35
★素数判定概述★
素数在公钥密码体制中的重要性
公开密钥密码体制中需要大的素数，如基于因数 分解困难性的RSA体制的密钥就是两个非常大的素 数的乘积，如果素数选择过小，则分解它们是容易 的，因而整个RSA密码体制系统就不安全。ElGamal 是基于离散对数求解困难的公钥密码体制，同样需 要产生非常大的素数，以保证密码体制的安全。
2013/10/23 5
★有限域的概念★
交换群的概念
交换群就是满足交换律的群 交换律(A5)： a . b= b . a
交换群例子： 加法运算下的整数集合（＋，－，0）； 乘法运算下的非零实数集合；
2013/10/23
6
★有限域的概念★
域的概念 若一集合F在已定义的两个运算“+”和“.”中，具有 下列性质者，则F称为一个域。 （1）F在运算“+”中为一交换群，且具有单位元素0 （2）F非零的元素在“.”中也为交换群（注意：交换 群有逆元存在） （3）F中“.”对“+”运算满足分配律，即对F中的所有 a,b,c满足a.(b+c)=a.b+a.c
2013/10/23 11
★有限域的概念★
有限域的概念
一个域，如果其元素个数为无限个，则称为无限域 反之，如果域的元素个数为有限个，则称为有限域
有限域的例子：模p的同余运算中，它的完全剩余 集构成一个域，通常用GF(p)表示。
2013/10/23 12
例如： n=19，a=3在mod 19下的幂分别为 3，9，8，5，15，7，2，6，18，16，10，11， 14，4，12，17，13，1。 即3的阶为18=φ(19)，所以3为19的本原根。
离散对数有以下性质： ① loga1=0。 ② logaa=1。 分别由以下关系得出： a0 mod p=1 mod p=1,a1 mod p=a。 以上假定模数p是素数，对于非素数也有类似的结 论。
2013/10/23 17
★有限域的概念★
有限域GF(pm)上元素的多项式表示
数学家已经证明，一个有限域GF(k)，其k必为p 或者pm(p为素数)，其它的k将不能构成有限域。
2013/10/23 20
★有限域的概念★
有限域GF(pm)上元素的多项式表示
m1 m2
a am1x
am2 x
a1x a0
a 2x x 2
2
举例：在GF(33)，即GF(27)中，
表示3位3进制数212，它转换成十进制数为
2×32+1×31+2＝23
2013/10/23
b bm1xm1 bm2 xm2 b1x b0
那么 c a b cm1xm1 cm2 xm2 c1x c0 其中 ci ai bi (mod p) i m 1
2013/10/23
24
★有限域GF(pm)上的代数运算★
27
★有限域GF(pm)上的代数运算★
有限域GF(pm)上的乘法和除法 举例：在GF(33)中，若a=2x2+x+2，b=2x2+2x+2 求d=ab (1)先求ab: 2 1 2 × 2 2 2 1 2 1 1 2 1 + 1 2 1 1 0 1 0 1=x4+x2+1
2013/10/23 28
23 mod 9≡8,24 mod 9≡7，25 mod 9≡5,
26 mod 9≡1。即2的阶为φ(9)，所以2为9的本 原根
2013/10/23
10
★有限域的概念★
域的概念
本质上说： 域就是一个集合，可以在其上进行加法、减法、乘法 和除法而不脱离该集合。
例子:有理数集合，实数集合，复数集合 这些都是无限域
★本讲授课提纲★
（1）有限域及其元素的多项式表示法 （2）有限域GF(pm)上的代数运算