应用密码学-2016-(第4讲) new

域 Field
• 域F
– F是整环 – 存在乘法逆元(0除外) • 除法定义: a/b = a(b-1)
• 有理数域、实数域、复数域 • 有限域
Group >> Ring >> Field
可逆在加/解密中的重要性
• 加密的操作对象是比特分组，通常被看作整数 加密是对整数的变换。这种变换必须能恢复( 解密时)，即可逆。如果加密是乘法，则解密 就是除法，而域上正好有除法---乘法逆元。 • 对于8bits字节，希望Z256是域，但它不是； 于是转而寻求GF(2^8)，它是域。 • AES的S盒是基于模2系数的模某8次不可约多 项式的剩余类。
多项式环
• • • • 系数是域F的多项式，构成环 系数是Zn的多项式环 系数是Zp的多项式环 在Z2上的多项式环， 在计算机上操作时有优势
– 加法，即XOR – 乘法，即AND
• 构造GF(p^n)
– 从环到域
构造GF(p^n)
• 系数在Zp上的n-1次多项式f(x)集合S
– 共有p^n个
• (S,＋,×)构成有限域GF(p^n) – 需要某n次不可约多项式m(x) – 使用模m(x)的多项式加法和乘法 • 从GF(p^n)到GF(2^n)
4.2剩余类与剩余系
第 四 讲 同 余
第 四 讲 同 余
Z/m或者Zm 整数模m等价类的集合 给定整数x和模数m，x模m等价类： {y∈Z: y≡x mod m} 通常记为x或x，又称为x模m的同余类或者剩余类。
例：对于模数12，有
0 12 12 2400 1 13 11 2401
第 六 讲 群 与 置 换
举例： (1)<Z,+>是群，其中Z为整数集合，+是普通 的加法，单位元是0，整数x的逆元是-x。 (2)<Z6,>是群，Z6={0,1,2,3,4,5}，为模6 加法。显然满足结合律，单位元是0；由于15=0， 24=0，33=0，所以1和5互为逆元，2和4互为逆 元，3和0的逆元仍然是3和0。
第 六 讲 群 与 置 换
阶的定义： (1)设<G,>是群，aG，使得等式ak=e成立的 最小正整数k称为a的阶，记做|a|=k，a称为k阶元， 若不存在这样的整数k，则a称为无限阶元。 例如： 在<Z6,>中，2和4是3阶元，3是2阶元， 1和5是6阶元，0是1阶元。 在<Z,+>中，0是1阶元，其他都是无限阶元。 (2)设<G,>为群，aG，且|a|=r。设k是整数， 则ak=e当且仅当r|k。
• m(x) = x^8 + x^4 + x^3 + x + 1 • 运算表：8x8
• { AES }
模m等价类的集合表示形式：
Z / 3 {0, 1, 2} {9, 31, 1}
{0,1, 2, {0,1, 2, , m 2, m 1} 模m等价类的集合 , m 2, m 1} 模m的代表元组成的集合
模m的完全剩余系
• 例子：
第 四 讲 同 余
第 四 讲 同 余
Z/m中的结论： m≡0 mod m x+(-x)≡0 mod m x±km≡x mod m (x+y)%m=((x%m)+(y%m))%m (xy)%m=((x%m)· (y%m))%m 4.Z/mX或ZmX
ZmX= {y∈Zm|gcd(y,m)=1} 即：Zm中与m互素的元素的集合。 例如：Z15X={1,2,4,7,8,11,13,14} Z11X={1,2,3,4,5,6,7,8,9,10}
模m的简化剩余系==缩系
5.定理
第 四 讲 同 余
定理1：设m,n是两个互素的正整数，如果x,y 分别遍历模m,n的完全(简化)剩余系， 则nx+my遍历模mn的完全(简化)剩余系。 举例：分别用模4和模5的完全剩余系和简化剩系 来表示模20的完全剩余系和简化剩余系。 Z4={0,1,2,3} Z4X={1,3} Z5={0,1,2,3,4} Z5X={1,2,3,4} 所以：Z20={0,4,8,12,16,5,9,13,17,21,10, 14,18,22,26,15,19,23,27,31} Z20X={9,13,17,21,19,23,27,31}
(3)设<G,>为群，则群中任何元素a与其逆元a-1 具有相同的阶。
第 六 讲 群 与 置 换
阶的定义： (1)设<G,>是群，aG，使得等式ak=e成立的 最小正整数k称为a的阶，记做|a|=k，a称为k阶元， 若不存在这样的整数k，则a称为无限阶元。 例如： 在<Z6,>中，2和4是3阶元，3是2阶元， 1和5是6阶元，0是1阶元。 在<Z,+>中，0是1阶元，其他都是无限阶元。 (2)设<G,>为群，aG，且|a|=r。设k是整数， 则ak=e当且仅当r|k。
多项式运算
• 多项式 {一元n次整数域}
• 多项式运算
– 加，减 –乘 例子：f(x) = x3 + x2 + 2，g(x) = x2 - x + 1 f(x) + g(x) = x3 + 2x2 - x + 3 f(x) – g(x) = x3 + x + 1 f(x) x g(x) = x5 + 3x2 - 2x + 2
应用密码学
计算机科学与技术学院 田秀霞 83876668@
第四讲 群环域
本章主要内容
• 1 同余及其基本性质 • 2 剩余类与剩余系 • 3 群、环、域 • 4 一次同余式
4.1 同余及其基本性质 第 四 讲 同 余
1.x≡y mod m x模m同余y 这种关系叫模m的同余。 等价的说法有x≡y mod m 当且仅当m|x-y。 2.同余的性质 对于固定的整数m，模m同余是一个等价关系。 自反性：对于任意的x，总有x≡x mod m； 对称性：x≡y mod m y≡x mod m； 传递性：x≡y mod m,y≡z mod mx≡z mod m。 其他性质： (1) x≡y mod m ax≡ay mod m,x±a≡y±a mod m； (2) x≡y mod m ax≡ay mod am, a>0； (3) (a· b) mod m≡(a mod m· b mod m) mod m。
– – – – 集合，元素 二元运算 · 封闭性、结合律 单位元、逆元
• 有限群、无限群 • 交换群（Abel） • 循环群
– 生成元
第 六 讲 群 与 置 换
6.1 群 1.二元运算 定义：设s为集合，函数f:sss称为s上的二 元运算或代数运算。满足： 可计算性：s中任何元素都可以进行这种运算； 单值性：运算结果唯一； 封闭性：s中任何两个元素运算结果都属于s。 2.群的定义 定义：设<G,>是代数系统，为G上的二元运 算，如果运算是可结合的，则称<G,>半群。
+: associativity, commutativity交换律, identity, inverse 0 *: associativity, distributivity分配律

• Lattice, Boolean
a ring multiplicative inverse 乘法逆元
群
• 群 Group
模n逆元
讨论在模n余数集上进行 加法逆元 如果a＋b≡0 mod n，则a和b互为加法 逆元 Zn中有：0,0 1,n-1 2,n-2 … n/2,n/2
• 乘法逆元 如果a×b≡1 mod n，则a、b互为乘法 逆元
4.4 有限域GF(p)
• 域，无限域 • 有限域，又叫Galoris域 有限域的阶都有pn的形式 阶为p的有限域记为GF(p) • 唯一性 (Isomorphism) • GF(p)：(Zp, +, x) GF(p^m)：
– 除法: f(x)/g(x)=q(x) … r(x) • 整除，若r(x)=0
• 模g(x)同余
– f(x) = q(x) g(x) + r(x) f(x) ≡ r(x) mod g(x)
• 不可约多项式(素多项式,既约多项式)
– g(x)不能表示为另两个多项式的乘积
• 关于系数∈Zn的多项式
第 四 讲 同 余
第 四 讲 同 余
3.命题 两个整数x和x’，x=qm+r, x’=q’m+r’,0≤r,r’ ≤|m|， 则x≡x’ mod m当且仅当r≡r’ mod m。 对于固定的模数m，如果x≡x’，那么对于y有 x+y ≡ x’+y mod m xy ≡ x’y mod m
推论：同余直接继承了普通算术运算的一些性质。 分配律：x(y+z)≡xy+xz mod m 加法结合律：(x+y)+z≡x+(y+z) mod m 乘法结合律：(xy)z≡x(yz) mod m 1的性质：1· x≡x· 1≡x mod m 0的性质：0+x≡x+0≡x mod m
(3)设<G,>为群，则群中任何元素a与其逆元a-1 具有相同的阶。
环 Ring
• 环R
– – – – 二元运算: 加法+、乘法× (R, +)是交换群 乘法封闭性、乘法结合律 分配律 a(b+c) = ab+ac
• 交换环
– 乘法交换律
• 整环（交换环且）
– 乘法单位元1 – 无零因子: ab=0 a=0或b=0
3.群的阶
第 六 讲 群 与 置 换
4.群中元素的阶 定义：设<G,>是群，aG，nZ，则a的n次 幂为 e n=0 an= an-1a n>0 (a-1)m n<0,m=-n 举例：在群<Z,+>中，30=0，35=15，3-5=-15 在群<Z3,>中，20=0，23=0，2-3=0