有限域gfpn乘子法的有限域gfpn

有限域gfpn乘子法的有限域gfpn

0密码学界的土地设计有限域的操作具有无进座、等比特、无遗入误差等特点，广泛应用于纠正码、加密和数字数据处理领域。有限域gf（pn）是一个包含pn元素的区域。在这个区域，乘法逆元计算密码学中非常常见。例如，sda算法是对称密码系统中的字节变换（s盒计算）和列的混合变换，以及基于有限域离散对数问题的sda算法，以及基于椭圆曲线离散对数问题的eccdsa算法以及基于椭圆曲线的超级椭圆曲线加密算法的方法。密码学院对有限域乘法、乘法逆元计算的研究非常活跃。我们主要关注欧洲大陆算法和小李算法的开发。在分析二进制有限域的基础上，我们提供了一种有效的算法，并在吸收前人经验的基础上提出了系统的理论分析。1pn元有限域一般来说,认识Galois域,大体上是从模7剩余集、模8剩余集确立模p剩余集上的有限域概念,继而从GF(24)开始认识q=pm阶的有限域.也就是说,有限域中示例域的元素个数要么是素数,要么是素数幂.这不是偶然,对于1个抽象的有限元数学结构,要构造有限域,3条结构定理是必要的:1)对于q元域Fq,一定存在特征素数p,使得q=pn;2)对于任意素数幂pn,一定存在1个pn元有限域,这意味着2,3,4,5,7,8,9元域是存在的,而6,10元域不存在;3)对于q元域Fq,从同构意义上讲,若q=pn,p是素数,n≥2,则Fq=Fp[x]/<m(x)>,记作GF(pn),其中m(x)是Fp上n次不可约多项式.若q=p是素数,则Fq=Fp,这样就完全刻画了有限域.对于GF(pn)的构造,m(x)不可约多项式的取法很重要.非常有趣的是:如果m1(x)≠m2(x),且同为n次不可约多项式,则Fp[x]/<m1(x)>和Fp[x]/<m2(x)>虽然同构,有可逆影射h存在,但其中的同型多项式f1(x),f2(x)却未必是相同元素.即自Fp[x]/<m1(x)>取f1(x),f2(x),令g1(x)=f1(x)×f2(x)①再自Fp[x]/<m2(x)>取f1(x),f2(x),令g2(x)=f1(x)×f2(x)②则从形式上g1(x)=g2(x)未必成立,这将导致各自对应的GF(pn)中p进制表示式迥异.在密码学中应用最广泛的域是Fp(p为素数)和GF(2n)这2大类,Fp的结构相对简单,GF(2n)因为对应不可约多项式的问题使其计算相对复杂,较一般的计算公式更难掌握.笔者主要分析GF(2n)域.2约函数的可约性通过研究不难发现,对于有限域的构造,Fp上的不可约多项式的判定及其多寡的推演极其重要.以F2[X]为例,容易证明,F2上n次不可约多项式f(x)一定整除x2n-x,但不能整除x2m-x,0<m<n,而F2上d次不可约多项式f(x)|(x2n-x)⇔d|n中x2n-x无重因式,从而有F2上次数整除n的首一不可约多项式之积等于x2n-x.由此可利用莫比乌斯反演公式求出F2上n次不可约多项式的数目.判断1个F2上n次多项式是否可约就不那么简单,有理数域上判断可约性的方法是行不通的,但是可以证明F2上任意次不可约多项式都是存在的.GF(2n)域含有2n个元素,每个元素对应1个n位二进制表示式,如果其上的1个基表示为n个GF(2n)中元素组成的基向量β={θ0,…,θn-1},则域中任一元素可以表示为n个基元素的和式,即x=n-1∑i=0αiθiαi∈F2x∈GF(2n)x=∑i=0n−1αiθiαi∈F2x∈GF(2n)基向量β有多项式基和正规基2个典型表示.2.1明确广义法定因果关系2n中的解设GF(2n)对应的不可约多项式是m(x),而t是m(x)=0在GF(2n)中的解,则多项式基向量β1={θ0,…,θn-1}={t0,t1,…,tn-1}③∀x∈GF(2n)x=n-1∑i=0αitiαi∈F2∀x∈GF(2n)x=∑i=0n−1αitiαi∈F2④2.2en-12ib设w是GF(2n)上的非零元,则正规基向量β2={θ0,…,θn-1}={w20,…,w2n-1},w∈GF(2n)⑤∀x∈GF(2n)x=n-1∑i=0λiw2iλi∈F2∀x∈GF(2n)x=∑i=0n−1λiw2iλi∈F22.3明确n-11111111212121211111211设多项式基向量为③,正规基向量为⑤,则βT2=H×βT1,其中Η={σ0,0σ0,1⋯σ0,n-1σ1,0σ1,1⋯σ1,n-1⋮⋮⋮⋮σn-1,0σn-1,1⋯σn-1,n-1}H=⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪σ0,0σ0,1⋯σ0,n−1σ1,0σ1,1⋯σ1,n−1⋮⋮⋮⋮σn−1,0σn−1,1⋯σn−1,n−1⎫⎭⎬⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪是多项式基到正规基之间的转换矩阵,进而有∀x∈GF(2n)x=n-1∑i=0λiw2i=(λ0λ1⋯λn-1)×(w20w21⋯w2n-1)Τ=(λ0λ1⋯λn-1)×βΤ2=(λ0λ1⋯λn-1)×Η×βΤ1=n-1∑i=0αiti=(α0α1⋯αn-1)×βΤ1所以(α0α1⋯αn-1)=(λ0λ1⋯λn-1)×Η其中,αi,λi∈F2.3在有限的二进制域中寻求逆法GF(2n)域中任意非零元素x都有乘法逆元.3.1使用maia算法求解传统的euclidean算法在多项式基表示下,有∀x∈GF(2n)∧x≠0x=n-1∑i=0αitiαi∈F2把x看成关于t的函数x(t),则gcd[x(t),m(t)]=1,由扩展的Euclidean算法可求出多项式u(t),v(t)∈GF(2n)满足x(t)×u(t)+m(t)×v(t)=1但是,t是m(t)的根,所以m(t)=0,由此可推出x(t)×u(t)=1于是x-1=x-1(t)=u(t),这样求逆问题就归结为多项式环中扩展的Euclidean算法.多项式基下,在扩展的Euclidean算法基础上衍生出很多改良算法,如AlmostInverse,Montgomery模逆算法、MAIA算法等.其通常的求逆思路是对于a∈GF(2n),将求解满足a×b≡1[modm(t)]的b问题转化为求解满足a×b≡tk[modm(t)]的(b,k)对,进一步计算出a-1≡b×t-k[modm(t)].MAIA算法:输入:∀a∈GF(2n)∧a≠0,首一不可约多项式m(x)输出:a-1[modm(x)]步骤:3.2正常基下的函数转换在正规基表示下,有∀x∈GF(2n)∧x≠0x=n-1∑i=0λiw2iλi∈F2由于GF(2n)域的阶是2n-1,则有x2n-1=1恒成立,于是x-1=x2n-2=x21+22+…+2n-1=x2·x22…x2n-1上式右侧是n-1个因式相乘,且每个因式都是前一个因式的平方,而正规基下的平方运算是简单移位运算,则乘法求逆运算转换为先做n-1次移位再做n-2次乘法运算的代数问题,便于算法实现.另外,考虑各方面的需要,还有利用多项式基求逆后通过基转换矩阵再变换为正规基下的逆,效率有很大提高.4maia算法的实现本文在研究二进制有限域一般结构特征的基础上分析了二进制有限域的构造方法,并对二进制模式下的乘逆算法进行了归纳,在很大范围内解决了有限域运算模块无法通用的问题.但此项研究仍不够完善,下一步研究工作将主要集中在基转换矩阵的建立和实现上.MAIA算法的实现过程中,首先判断u是否为0,若为0则进行右移操作;接下来判断b是否为0,若为0则进行右移操作;若为1则先与m相异或后再进行右移操作.这样的操作直至u为1结束.接着判断v是否为0,若为0则进行右移操作;接下