0. 课程概述

Mathematical Foundations of Information Security

0.0. 三个数学难题

大整数因数分解问题：
由两个质数p，q之乘积n来分解出p，q很难，RSA公开密钥算法的理论基础；
离散对数问题：
已知有限循环群G=< g > {g^n|k = 0, 1, 2,...},及其生成元g和阶n = |G|，很难由h=g^x,计算出整数x；
椭圆曲线离散对数问题：
已知有限域下F_p上的椭圆曲线群E(F_p) = {(x,y)|<-F_p * F_p, y^2=x3+ax+b,a,b<-F_p}|_|{O},及点P=(x,y)的阶为一个大素数。给定整数a，计算点aP=(x_a,y_a)=Q很容易，给定Q，计算整数x，使得xP=Q很难。

0.1. 课程主要内容

近世代数
群，子群，交换群，循环群，群上的离散对数；环，子环，交换环，整数环，多项式环；域，子域，有限域，有限域上的多项式。
数论
整除性，同余性，二次剩余，素数，因子分解，同余式，欧拉定理，扩展的欧几里得算法和中国剩余定理。
数理逻辑
命题逻辑，谓词逻辑，模态逻辑，逻辑与安全。

1. 近世代数基础之群

1.1. 群的基本概念

集合上的运算

近世代数中的群、环、域的定义都是基于集合的，通过对集合上运算的约束，将集合构造称具有不同特性的新对象。

集合： 具有共同属性的事物的总体。

集合上的二元运算： 设S为集合，映射
n:{ S * S -> S
{ (x,y) -> z
称为集合上的运算。

群：
设三元组(G,·,1)中G为集合，·为集G上的二元运算，1为G中的一个元。若(G,·,1)满足：

G1(乘法结合律)：a·(b·c)=(a·b)·c，a,b,c <- G;
G2(单位元)：1·a=a·1=a，a<-G;
G3(逆元)：对a<-G,有a^{'<-G使得a·a}'=a^'·a=1。

则称(G,.,1)为群，简称群G，1称为群G的单位元，a'称为a的逆元。

若(G,.,1)满足G4(交换律)：a·b=b·a，a,b<-G，则称G为交换群。
若(G,.,1)仅满足G1,G2，则称G为有单位元的半群。
若(G,.,1)满足G1,G2,G4，则称G为有单位元的交换半群。

1.2. 群的例子

例1：
设(Z,+,0)中Z为整数集，+为整数的加法，0为整数零，验证

(Z,+,0)中有(a+b)+c=a+(b+c)，G1满足；
a+0=0+a=a，G2满足；
a+(-a)=(-a)+a=0，(-a)表示a对应的负整数，G3满足；
a+b=b+a，G4满足。
从而(Z,+,0)为交换群。

例2：
设(Q,·,1)中的Q为零以外的所有有理数的集合，·为有理数乘法，1为整数1，则(Q*,·,1)满足G1,2,3,4为交换群。

例3：
设GL_n(R)为n阶实数可逆方阵的集合，.为两矩阵的乘法，1为单位矩阵，则(GL_n(R),·,1)为群。GL_n(R)称为实数域R上n阶一般线性群。

例4：
在希尔密码(Hill Cipher)中加密变换为
(y_1y_2...y_m) = (x_1x_2...x_m)Mmod26
这里密钥M <- GL_m(Z_26),x_i,y_i <- Z_26,Z_26 = {0,1,...,25},x_i为明文，y_i为密文。(式中右边的行向量(x_1x_2...x_m)与矩阵M乘是先进行通常的实数行向量与实数矩阵乘再对所得行向量的每一分量取模26)

加密过程，字母AB...Z分别对应0,1,...,25，加密前先将明文字母串变换成Z_26上的数字串，然后再按上述表达式对每次m个数字的将明文数字串变换成密文数字串，最后将密文数字串变换成密文字母串。

eg：

加密实例

定理(线性代数)，
设A = (A_ij)为一个定义在Z_26上的n · n矩阵，若A在mod26上可逆，则有：
A^-1 = (detA)_-1 A^(mod26)
这里，A^是A的伴随矩阵。

1.3. 子群

定义，设定(G,·,1)为群，A为G的子集合。若1 <- A且(A,·,1)构成群，则称A为G的子群，并记为 A <_ G。

例：
证明nZ={0,+-n,+-2n...}为整数群(Z,+,0)的子群。
证：

nZ 包含于Z
0 <- A
（nZ,+,0）为群

1.4. 循环群

定义，若群G的每一个元素都能表成一个元素a的方幂，则G称为由a生成的循环群,记作G=< a >,a称为循环群G的生成元。

根据元素的阶的性质，循环群G=< a >共有两种类型：

当生成a是无限阶元素，则G称为无限阶循环群。
如果a的阶位n，即a^n=1,那么这时G=< a >=< 1,a,a^2,...,a(n-1) >,则G称为有a所生成的n阶循环群，注意此时1,a,a^2,...,a(n-1)两两不同。

1.5. 对称群

定义，S={1,2,3,...,n}，映射b：S--S是可逆的，则称b为S上的置换；
定义，群体S上的置换所成的集合记为S_n,命1表示恒等置换，在S_n中以b(i)表示i在置换b下的像，定义S_n中的两元素q与p的乘积为
[b·q](i)=b(q(i))
则(S_n,·,1)成群，群S_n称为n次对称群。

b为：

b

q为：

q
&为：
&

<-为：

<-

例1：
在置换密码(Permutation Cipher)中加密变换为
(y_1 y_2 ... y_m) = (b(x_1) b(x_2) ... b(x_m))
这里x_i,y_i <- S={1,2,...,m}，x_i为明文，y_i为密文，b <- S_m，S_m为{1,2,...,m}上m次对称群。加密时按上述表达式每次m个字符的将明文串变换为密文串。
e.g.：