摘要
网络安全依赖于两种技术。一是传统意义上的存取控制和授权,如存取控制表技术、口令验证技术等;二是利用密码技术实现对信息的加密、身份鉴别等。前者从理论和技术上是完全可以攻破的,而后者是有条件的。所以,网络安全的核心仍将建立在密码学理论与技术上。数据加密技术是最基本的网络安全技术,被誉为信息安全的核心。
只有有限个元素的域称为有限域,或Galois域,它在方程式实验设计和编码理论等方面有很广泛的应用。有很多构造元素个数为素数方幂的有限域的方法,常见的是多项式基表示等方法。设F为有限域,g∈F~*,F~*是F的乘法群F~*=F-{0}。并且对于任意正整数x,计算g~*是容易的;但是已知g和y求x使得y=g~x,是计算上基本不可能的。这一问题称为有限域F上的离散对数问题,因为其在密码学中的应用特性,对于有限域的研究在计算机科学中显得非常重要。
1. GF(2~k)上的遍历矩阵及其特性
在同构的意义下,我们把GF(2~k)看成是所有K位二进制数在特定加、乘运算下所构成的有限域。令M_n是GF(2~k)上的所有n阶满秩方阵所构成的集合,C_n为GF(2~k)中所有非0的n维列矩阵所构成的集合。定义映射f_m:C_n→C_n,使对有f(x)=mx,则f为C的一个置换。因此可将F唯一地表为如下不相杂的轮换之乘积(包括长度为1的轮换):
f_m=(a_(11)a_(12)……a_(1n_1))(a_(21)a_(22)……a_(2n_2))……(a_(t1)a_(t2)a_(t3)) (1)
对分解式中任一轮换之长度必整除m在GF(2~k)矩阵乘法下的周期。当f_m分解式中只有一个长度为(2~(kn)-1)的轮换时,可知对恰好取遍C_n。故称M_n中具有这样性质的n阶方阵m为“遍历矩阵”。
对为遍历矩阵当且仅当m在GF(2~K)矩阵乘法下的周期为(2~(kn)-1)。如果m∈M_n为遍历矩阵,则(m)={m.m~2……,m~(2~(kn)-1} 中恰有φ(2~(kn)-1)个遍历矩阵。
GF(2~k)上的遍历矩阵m的性质充分显示,作成一
个有限域GF(2~(kn)),GF(2~(kn))中的加法和乘法即是通常的矩阵加法和乘法,并且m是它的一个生成元。
通过对GF(2~(kn))上n阶遍历矩阵的讨论,可知其对C_n中的向量有良好的发散性。由GF(2~(kn))上n阶遍历矩阵的特性可知,用其左乘GF(2~(n))上一个n阶方阵M相当于对M的每一列作了相应的变换;而用其右乘M,则对M的每一行作了相应的变换。所以用不同的遍历矩阵在两边同时乘上一个矩阵可充分地“弄乱”该矩阵的各元素。这一过程可重复多次以达到所需的复杂变换,这在密码学中的有很重要的应用价值。
2. 构造GF(2~(n))上的遍历矩阵
为了构造遍历矩阵,对,定义递推关系如下:
上面定义中所用的加法和乘法均为GF(2~(k))中的加法和乘法。
易知,由递推关系(1)所得诸的序列必以循环的形式出现,且循环节的长度由唯一地确定。那么由所确定的循环节长度正是使的最小整正数L,我们称其为关于递推关系(1)的循环节长度。将关于递推关系(1)的循环节首尾相连便能够得到由位二进制数构成的圆环。且在该圆环上任取连续的n位,紧接其后的下一个n位(b_n……b_2b_1)满足:
上面GF(2~(k))中的n阶方阵Q由g_n……g_2g_1唯一地确定,称上述的n阶方阵Q为(g_n……g_2g_1)关于递推关系(1) 的“生成矩阵”。
当n和(2~(kn)-1)互素时,对于g=(g_n……g_2g_1)∈GF(2~k)~n,(g_n……g_2g_1)的生成
矩阵Q_g为遍历矩阵,当且仅当Q_g在GF(2~k)矩阵乘法下的周期是(2~(kn)-1)。
F=GF(2~k)中n阶遍历矩阵的寻找(生成)算法:
特别的,当F=GF(2)并且(2~(kn)-1)为素数(梅森素数)时,算法的第⑥步可以省略,并且最多只需做F上的n次n阶矩阵乘法运算便可完成一次判断。易知这样的Q_g恰为个。故在GF(2~k)较大时,可利用上述算法找到GF(2~k)中足够多的n阶遍历矩阵,每一个这样的 n×n 矩阵可用一个n维向量来表示。此外,该算法也可用来快速地寻找GF(~2k)中的一个n次不可约多项式。
信息交换主要涉及到信息收发双方如何在非安全的通道上安全地传递信息。其常用的手段主要有:
1 基于SKC(secret key cryptography)的信息交换
2 基于PKC(public key cryptography)的信息交换
3 基于其他技术的信息交换
利用遍历矩阵的特性,我们可以实现多种密码学应用模式。例如可以用如下方法实现对称加密:
设F=GF(2~k),将要交换的信息 M 看成是F 中元素的序列,并按kn~2位来分块,
每一块对应于F上的一个n阶方阵M_1,M_2,……。则A,B双方可按如下方式来进行通讯:
A,B事先约定密钥Q_1,Q_2和s_0,t_0∈C_N.这里Q_1和Q_2为F上的m阶遍历矩阵;
A 计算并将每个都看成一个位无符号整数。然后计算密文序列:最后将C_1,C_2……发送给B;
B 计算然后计算并得到明文序列:M_1,M_2……
A,B都用最后一次的s_j和t_j来更新s_0和t_0。
利用GF(2~k)上的遍历矩阵,我们还可以实现基于离散对数的数据交换,Shamir三次传递协议以及生成伪随机数,不对称加密等很多密码学应用模式。还可以根据本文推导和证明出的GF(2~k)上遍历矩阵的特性,得到更普遍的有限域GF(p~k)上的遍历矩阵,并可以进一步利用它的密码学特性。
The network security depends on two kinds of technology. First, the access in the traditional meaning is controlled and authorizes, for instance access control the technology of forms, password and verifies technology, etc.; Second, make use of technology of secret code to realize the encryption, identity of the information to distinguish etc.. The former can be broken through from the theory and technology, and the latter is conditioned. However, the core of network security set up based the theory and technology of cryptography. Digital Encryption is the basal technology for the network security, and it is the core of the information security.
In abstract algebra, a finite field or Galois field (so named in honor of Evariste Galois) is a field that contains only finitely many elements. Finite fields are important in cryptography and coding theory.
The multiplicative subgroup of any finite fieldis cyclic. Given a primitive element g∈F and any u∈F~*=F-{0} , the discrete logarithm of u with respect to g is that integer k, for which u=g~k. We will write k=log_(g)u. The discrete logarithm of u is sometimes referred to as the index ofu. The well-known problem of computing discrete logarithms in finite fields has acquired additional importance to its applicability in cryptography. In cryptographic applications, attention has been focused on the fields, since arithmetic in them is much easier to implement, with respect to both software and hardware. Therefore we concentrate on the fields GF(2~K).
1 Ergodic Matrix in GF(2~K) and Its Properties
We regard GF(2~K) as the set of all k-bit binary numbers. Suppose M_n is the set of all n×n matrices in GF(2~K) and C_n is the set of all nonzero n-bit column matrix in GF(2~K).(M_n,+,×) constructs a matrix ring. The “+” and “×” here are the matrix addition and multiplication.
Definition. Let m∈ M be a regular matrix. If and mx,m~2x……m~(2~(nk)-1)=x are just ergodic over C_n, we call the matrix m the “Ergodic Matrix”.
By the definition, we can deduce the following result:
If m∈ M_n is ergodic, if and only if m’s period= (2~(kn)-1)
If m∈ M_n is ergodic, then it happens that there are φ(2~(kn)-1)ergodic matrix in the
matrix ring (m)={m,m~2,……m~(2~(kn)-2),m~(2~(kn)-1)=E}.
Because of the properties of the ergodic matrices, we can conclude that the matrix ring,{0,m,m~2,……m~(2~(kn)-2),m~(2~(kn)-1)=E} , is isomorphic to the finite field with 2~(kn) elements. The addition and multiplication here are the matrix addition and multiplication, and the element m is one of its primitive elements.
Let Q_1 and Q_2be the ergodic matrices in GF(2~k), let’s take the n2-bit plaintext Mas a n×n matrix in GF(2~k), Then multiply M by Q_1 on the left which encodes each row of M, Whereas multiply M by Q_2on the right which encodes each column of M. Q_1MQ_2 (The cipher text) can well disarrange the plaintext M by the ergodicity of the ergodic matrix. These encoding operations can also be done as many times as needed to have the plaintext M shuffled sufficiently.
When the size of Q_1 and Q_2 is large enough, for those who do not know them, decoding the cipher text is difficult. But for the authorize receiver who knows the matrices Q_1 and Q_2, the decoding is simple. So we can use the ergodic matrices to encrypt and exchange information securely over the insecure medium.
2 Constructing the Ergodic Matrix in GF(2~k)
In order to construct (find) the ergodic matrix m∈M , for defines the following recursion formula:
The addition and multiplication above are those in GF(2~k)
. It is clear that the sequence of a_m(m》0)is cyclic, and the length of the cycle-segment is only determined by (g_n,……g_2,g_1). The length of the cycle-segment determined by (g_n,……g_2,g_1) is the minimal positive integer Lthat meets: .
If the cycle-segment determined by (g_n,……g_2,g_1) were connected end to end, we can get a cycle-segment ring. Let (a_n,……a_2,a_1) be an n-bit sub string on it and the successive one is (b_n,?
引文
冯克勤。有限域。湖南教育出版社,1991年12月第1版,14-45
《现代应用数学手册》编委会。现代应用数学手册:离散数学卷。清华大学出版社,2002年3月第1版,279-310
孙吉贵,杨凤杰,欧阳丹彤,李占山。离散数学。高等教育出版社,2002年8月第1版,250-277
卢开澄。组合数学。清华大学出版社,1991年10月第2版,21-39
N.Jacobson著,李忠傧,俞曙霞,李世同译。抽象代数学:卷三 域论及伽罗瓦理论。科学出版社,1987年8月第1版,54-82
戴执中。域论。高等教育出版社,1990年7月第1版,34-63
卿斯汉,冯登国。信息和通信安全——CCICS’99 第一届中国信息和通信安全学术会议论文集。北京科学出版社,2000年1月第1版,71-89
周玉洁,冯登国。公开密钥密码算法及其快速实现。国防工业出版社,2002年9月第1版,4-11
(美)William Ford,(美)William Topp著,刘卫东,沈官林译,严蔚敏审。数据结构:C++语言描述。清华大学出版社,1998年11月第1版
张凯院,徐仲。矩阵论 导教、导学、导考。西北工业大学出版社。2001年3月第1版,59-69
(加)Guy, R.K.著,张明尧译。数论中未解决的问题。科学出版社,2003年1月第1版,15-19
(美)Andress, M.著,杨涛等译。计算机安全原理。机械工业出版社,2002年1月第1版,51-69
徐景实,谭利。矩阵加密与解密的一些方法。长沙电力学院学报(自然科学版),03年2月,第18卷第1期,1-3
芮义鹤,陈宜治。关于有限域Fq上矩阵阶的研究。工科数学,2002年8月,第18卷第4期,35-36
韦卫,王行刚。密钥交换理论与算法研究。通信学报,1999年7月,第20卷第7期,64-66
张清华。基于密钥交换中离散对数生成元的研究。重庆邮电学院学报,2002年9月,第14卷第3期,90-91
刘端森,杨存典,李超。关于有限域中生成元的一些性质。西北大学学报(自然科学版),2003年8月,第33卷第4期,381-383
常新功,杨君辉,戴宗铎。幂函数的一些密码学性质。系统科学与数学,1998
年10月,第18卷第4期,466-477
郭宝安,蔡长年。有限域上的不可约多项式。北京邮电大学学报,1994年3月,第17卷第1期,23-26
王金华。在有限域上可逆矩阵的个数和有限域的矩阵表示。连云港师范高等专科学校学报。2001年3月,第1期,54-55
谭晓青。两类有限域加法的计算机实现。衡阳师范学院学报(自然科学)。2001年12月,第2卷第6期,54-56
龙莹山,刘长明。数据加密的密码体制与DES算法。山东科学,1994年3月,第7卷第1期,5-7
白国强,伊丽江,肖国镇。一种基于GF(p)上移位寄存器序列密钥交换体制的弱密钥。通信学报,2000年9月,第21卷第9期,13-18
W. Diffie and M. E. Hellman, New directions in cryptography, IEEE Trans. Inform. Theory, IT-22, 1976, 644-654.
Bruce Schneier, Aplied Cryptography Second Edition: protocols, algorithms, and source code in C, John Wiley & Sons, Inc., 1996
RSA Laboratories, RSA Laboratories' Frequently Asked Questions About Today's Cryptography, RSA Security Inc. Electronic Privacy Information Center, 2000, Version 4.1
A. M. Odlyzko, Discrete logarithms in finite fields and their cryptographic significance, AT&T Bell Laboratories, 1-29
B. Arazi, Sequences constructed by operations modulo 2n - 1 or modulo 2n and their application in evaluating the complexity of a log operation over GF( 2n ), preprint.
Captain Gregory C. Ahlquist, Brent Nelson, and Michael Rice, Optimal Finite Field Multipliers for FPGAs, 1-4
http://www.fact-index.com/f/fi/finite_field.html