现代密码学(中山大学)Lecture05

Modular Polynomial Arithmetic
• can write any polynomial in the form:
– f(x) = q(x) g(x) + r(x) – can interpret r(x) as being a remainder – r(x) = f(x) mod g(x)
环同态基本定理
定理 设 R与 R 是两个环,且 R ~ R .则 1)这个同态核 N ,即零元的全体逆象,是 R 的一个理想; 2) R N R . 证 设 是环 R 到环 R 的一个同态满射.
N 首先是环 R 的一个子 加群;其次,设 a N , r R ,则
1)核
a 0, r r .
全体整数构成的集合对于普通加法和乘法来说作成一个环。 全体有理数构成的集合对于普通加法和乘法来说作成一个环。 n阶实方阵全体在矩阵的加和和乘法下构成一个环
交换环
• 一个环叫做一个交换环，假如ab=ba，对于属于R的任意 两个元素a,b都成立。 • 剩余类环Zn。Zn为整数模n剩余类的集合 Zn={[0],[1],…,[n-1]},它对剩余类的加法和乘法构成一个 含有单位元“[1]”的交换环。 • 各式各样的数域都对通常的数的加法和乘法形成一个含有 “1”的交换环 • 设F表示上面几个例子给出的任意一个数环。定义 F[x]={anx n+an-1x n-1+…+a1x+a0| ai∈F,n为正整数}， 它是F上的一元多项式环。 • 取大于1的正整数n，则n的一切整数倍形成的集合nZ对数 的加法和乘法形成了一个不含单位元“1”的交换环。
Evariste Galois
A drawing done in 1848 from memory by Evariste's brother.
This is taken from a French stamp
• Imprint: ELSEVIER • ISSN: 1071-5797
• finite fields play a key role in cryptography • of increasing importance in cryptography
有限域的结构
任何一个有限域都可以表示成 GF(P) 或者 GF(Pｎ)，Ｐ是一个素数。 GF(Pｎ)叫做 GF(P)的ｎ次扩域，它可以表示成定义在 GF(P)上一个ｎ维的向量空间。
子域： GF(Pｎ)的子域只有GF(Pｍ)，ｍ｜ｎ。
Ordinary Polynomial Arithmetic
• add or subtract corresponding coefficients • multiply all terms by each other • eg
– AES, Elliptic Curve, IDEA, Public Key
有限域的结构
素域：没有真子域的域
例如：Q 是一个素域。（如何证明？）
提示：若A 是Q的真子域，那么 Z包含于 A，而任意的有理数 都可以表示成一个既约分数 a/b。
有限域的结构
域FP ：用ZP 表示， P是一个素数。所有的素数P阶的
: m n m
是环 Z / n 与 Z n的同构映射,因此, Z / n Z n .
域
• 除环：一个环被称为除环（或斜域），是 指该环的非零元全体对“· ”形成一个群。 • 域：一个可交换的除环称为域。 • Fp为整数模p的剩余类环，p为素数，可以 验证它为域。因为Fp中的元素有限，称它 为有限域；又因为p为素数，又称之为素域. • 有理数域，实数域 • 域首先必是整环；反之则不然
于是在 之下有
ra r 0 0, ar 0 r 0,
故 ra, ar N ,即N 是 R的理想. 2) 令
: a N (a),
则由群同态基本定理知,作为加群, 是 R N 到 R 的一个同构映射.又由于 (a N )(b N ) ab N ,而 (ab) (a) (b) ,因此 是环 R N 到环 R 的一个同 构映射,从而 R N R .
环的定义也可以描述为：一个集合R叫做一个环，假 如R对于加法构成一个交换群，对于乘法运算构成幺 半群，乘法对加法满足左右分配律。
在抽象代数产生的19世纪，数学家们开始研究满足所有合成律（即加法交换律、结 合律，乘法交换律、结合律，以及乘法对加法的分配律等等）或者满足其中的一部 分的集合。倘若一个集合具有加法、乘法和相应的运算性质，就称为环。环论是抽 象代数中较晚成熟的，20世纪以来环论得到了快速和广泛的发展。韦德伯恩研究了 线性结合代数，这种代数实际上就是环，而环和理想的系统理论由诺特给出。
定义 设 R与 R是两个环.如果有一个 R到 R 的 映射 满足 a b a b , ab (a) (b) (a, b R) , 则称 是环 R到 R 的一个同态映射. 如果 是满射(单射、双射),则称 为环同态 满射(环同态单射,环同构).特别 是环同态满射 时,则称 R 与 R 同态,记为 R ～ R .
– let f(x) = x3 + x2 + 2 and 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
Polynomial Arithmetic with Modulo Coefficients
有限域
• 一个元素个数有限的域称为有限域，或者伽罗华域 （Galois field） 。 • 有限域中元素的个数为一个素数，或者一个素数的 幂，记为GF（p）或GF（pn ),其中p为素数。 • 有限域中运算满足交换律、结合律、和分配律。 • 加法的单位元是0,乘法的单位元是1，每个非零元素 都有一个唯一的乘法逆元。 • 密码学中用到很多有限域中的运算，因为可以保持 数在有限的范围内，且不会有取整的误差。 • – GF(p) • – GF(2n )
• 交换群（Abel 群）
A statue of Abel in Oslo
பைடு நூலகம்
环
• 一个集合R叫做一个环，假如 • ① R对于一个叫做加法的代数运算作成一个交换 群 • ② R对于一个叫做乘法的代数运算来说是封闭的 • ③ 这个乘法适合结合律a(bc)=(ab)c，对于属于 R的任意的元素a,b,c都成立 • ④ 分配律成立，a(b+c)=ab+ac，(b+c)a=ba+ca • 环R被称为含有单位元的环，是指R内含有乘法单 位元“1”，使得∀a∈R,有a· 1=1· a=a。 • 我们同城考虑的环一般是有单位元的。无乘法单 位元的的环一般记为Rng
理想的概念
定义1 设 N是环 R的一个子加群,即对 N 中
任意元素 a, b ,差 a b 仍属于 N .如果又有 r R, a N ra N ,
则称 N 是 R 的一个左理想; 如果 r R, a N
ar N
,则称 N是 R的一个
右理想; 如果N 既是环 R的左理想又是右理想,则称 N 是 R的一个双边理想,或简称为理想,并用符号
Polynomial GCD
• can find greatest common divisor for polys
– c(x) = GCD(a(x), b(x)) if c(x) is the poly of greatest degree which divides both a(x), b(x) – can adapt Euclid’s Algorithm to find it: – EUCLID[a(x), b(x)] 1. A(x) = a(x); B(x) = b(x) 2. 2. if B(x) = 0 return A(x) = gcd[a(x), b(x)] 3. R(x) = A(x) mod B(x) 4. A(x) ¨ B(x) 5. B(x) ¨ R(x) 6. goto 2
域都同构于ZP。
特征：任意的a ∈ A，满足 na=0的最小的自然 数n 叫做A的特征。
定理：任何一个有限域都有一个素特征。
Finite Fields
• Zp (p prime) with + and * mod p, is a finite field. 1. (Zp, +) is an abelian group (0 is identity) 2. (Zp \ 0, *) is an abelian group (1 is identity) 3. Distribution: a*(b+c) = a*b + a*c 4. Cancellation: a*0 = 0 • Are there other finite fields? • What about ones that fit nicely into bits, bytes and words (i.e., with 2k elements)?
• if have no remainder say g(x) divides f(x) • if g(x) has no divisors other than itself & 1 say it is irreducible (or prime) polynomial • polynomial arithmetic modulo an irreducible polynomial with coefficients in the field Zp forms a field
例 设 Z 是整数环, n是任意正整数.证明:
Z / n Z n .
证 商环 Z / n {0 n,1 n,, n 1 n}, 而
Z n {0, 1 ,, n 1}, 由于商环中元素(即陪集)的加法
与乘法同 Z n 中元素(即同余类)的加法与乘法一致, 故显然
• when computing value of each coefficient do calculation modulo some value • could be modulo any prime • but we are most interested in mod 2
– ie all coefficients are 0 or 1 – eg. let f(x) = x3 + x2 and g(x) = x2 + x + 1 f(x) + g(x) = x3 + x + 1 f(x) x g(x) = x5 + x2
现代密码学
Modern Cryptography
张方国 中山大学信息科学与技术学院
isszhfg@mail.sysu.edu.cn
第五讲 密码的代数学(二)
• 环论 • 域论 • 有限域: 构造及性质
群
群G，有时记做{G, ◦}，是定义了一个二元运算的非空 集合，这个二元运算可表示为◦ ，G中的每一个序 对(a,b)通过运算生成G中的元素(a ◦ b)，并满足以 下公理： • ①封闭性：如果a 和 b都属于G，则 (a ◦ b)也属于 G 。 • ②结合律成立：a ◦(b ◦ c)=(a ◦ b) ◦ c，对于G的 任意三个元素都a,b,c成立 • ③单位元：G里至少存在一个元素e，对于G的任 何元a，都有e ◦ a=a ◦ e=a成立。 • ④逆元：对于G的每一个元素a，在G里至少存在 一个元素a’，使得a’ ◦ a=a ◦ a’=e成立。
N R表示.否则记为 N R .
定理 设 I 是环 R 的理想,则
R
I
对陪集的加法
与乘法作成一个环,称为 R 关于 I 的商环,且
R~R I
.
证令
: a a I.
则易知这是 R 到 R I 的一个关于加法与乘法的同态 满射,故 R ~ R I ,由于R 是环,因此, R I 也是环.
整环
• 整环：含有乘法单位元“1”而无零因子的 交换环称为整环。 • 若在一个环里，a≠0，b ≠0但ab=0,我们 就说a是这个环的一个左零因子， b是这个 环的一个右零因子。 • 任何一个整环都至少含有2个元素。恰含有 2个元素的整环是存在的，例如F2={0,1}它 对模2的加法乘法运算形成一个整环，事实 上，它为二元域