（基础数学专业论文）z2e上的运算与椭圆曲线上的递归序列.pdf

摘要 由于源序列发生器的重要作用和地位，对它的研究一直是序列密码研 究的基础工作之一。发现新的具有良好密码学性质的源序列发生器仍是序 列密码设计的重要需求之一。 本文的主要工作是寻找一种新的源序列发生器，即寻找一类基于有限 域的椭圆曲线上的线性递归序列。为此分两步进行研窄：一、对有限域吒。 上的运算和剩余类环z ( 2 。) 上的运算的复杂度进行了比较，得到了关于代 数次数、代数项数等密码学参数的计算公式i给出了一类椭圆曲线上 的线性递归序列，给出了阶为p 。的椭圆曲线子群h 上的本原多项式的定 义、计数；给出了h 上的极大长序列的周期，初态的计数及极大长圈的计 数。 第一章是本论文的创新思想。这一章提出了密码学符号不变量的概念， 并就有限域f 1 。上运算的复杂度与剩余类环z ( 2 。) 上的运算进行了比较，得 到了关于代数次数、代数项数等密码学参数的计算公式。 第二章是本论文的主要结果。这一章给出了一类椭圆曲线上的线性递 归序列，给出了阶为p 。的椭圆曲线子群h 上的本原多项式的定义、计数； 给出了h 上的极大长序列的周期，初态的计数及极大长圈的计数。 关键词：密码学符号不变量；代数项数；代数次数：椭圆曲线；线性递归 序列；周期；本原多项式 a b s t r a e t i ti sab a s i cw o r ka n do n eo ft h em o s ti m p o r t a n tn e e d s ，t ot h es e q u e n c e s c r y p t o g r a p h yd e s i g n ，t of i n da n e ws e q u e n c e sg e n e r a t o r , s i n c et h ei m p o r t a n c e a n dt h eu s e f u l n e s so f t h es e q u e n c e sg e n e r a t o r s ， i nt h i sp a p e r , w ef i n dan e ws e q u e n c e sg e n e r a t o r s ，w h i c hi sak i n do f l i n e a rr e c u r r i n gs e q u e n c e so ne l l i p t i cc u r v e so v e rt h ef i n i t ef i e l de i nc h a p t e r o n e ，w ep r o p o s et h ec o n c e p to ft h ec r y p t o g r a p h ys y m b o lc o n s t a n t s a n d c o m p a r e t h eo p e r a t i o n so v e rf i e l dew i t ht h o s eo v e rt h er i n gz ( 2 。) w eg e ta c o m p u t i n gf o r m u l ao fa l g e b r a i cd e g r e e s a n da l g e b r a i ct e r mn u m b e r so f p o l y n o m i a l s i nc h a p t e rt w o ，w eg i v eak i n do fl i n e a rr e c u r r i n gs e q u e n c e so n e l l i p t i cc u r v e so v e rt h ef i n i t ef i e l d 玑w ea l s op r e s e n tt h ed e f i n i t i o na n dt h e n u m b e ro fp r i m i t i v ep o l y n o m i a lo v e rac y c l i cs u b g r o u pho fa ne l l i p t i ec u r v e m o r e o v e r , w ep r e s e n tt h ep e r i o do f am a x i m a ll e n g t hs e q u e n c e ，t h en u m b e ro f ao r i g i n a ls t a t u sa n dt h en u m b e ro f am a x i m a l l e n 甜d ac i r c l e k e yw o r d s ：e r y p t o g r a p h ys y m b o lc o n s t a n t ；a l g e b r a i cd e g r e e ；a l g e b r a i ct e r mn u m b e r ； e l l i p t i cc u r v e ；l i n e a rr e c u r r i n gs e q u e n c e ；p e r i o d ；p r i m i t i v ep o l y n o m i a l i l 声明 学位论文独创性声明 本人声明，所呈交的学位论文系本人在导师指导下独立完成的研究成果。文中 依法引用他人成果，均己作出明确标注或得到许可。论文内容未包含法律意义上已 属于他人的任何形式的研究成果，也不包含本人己用于其他学位申请的论文或成果。 本人如违反上述声明，愿承担由此引发的一切责任和后果。 论文作者签名 日期：年月同 学位论文知识产权权属声明 本人在导师指导下所完成的学位论文及相关的职务作品，知识产权归属学校。 学校享有以任何方式发表、复制、公开阅览、借阅、以及申请专利等权利。本人离 校后发表或使用学位论文或与该论文直接相关的学术论文或成果时，署名单位仍然 为青岛大学。 本学位论文属于： 保密口，在年解密后适用于本声明。 不保密口。 ( 请在以上方框内打“4 ”) 论文作者签名 导师签名 第3 7 页 日期：年月同 日期：加，殍占月j ，同 引言 引言 随着计算机和网络技术的高速发展和广泛应用，社会的信息化程度越来越高，但 社会对计算机和网络系统的依赖性也越来越大。若计算机和网络系统的安全受到危害， 则会危及国家的安全，引起社会混乱，从而造成重大损失。因此确保计算机和网络系 统的安全已成为世人关注的社会问题，并成为计算机科学技术的热点领域。 众所周知，确保信息系统的安全是一个系统工程，必须从整体考虑，从底层着手， 综合采取措旖，才能比较有效的确保信息系统的安全。硬件结构的安全和操作系统的 安全是信息系统安全的基础，而密码等则是关键技术。 密码技术是- - f l 古老的技术，大概自人类社会出现战争便产生了密码。1 9 4 9 年香 农发表了题为保密系统的通信理论这一著名论文，该论文把密码置于峰实的数学 基础之上，标志着密码学作为一门科学的形成。1 9 7 6 年w d i f f i e 和m e h e l l m a n 提出 了公钥密码的概念，从此开创了一个密码新时代。 目前，在国际上研究比较充分而且公认比较安全的公钥密码有，基于大整数因子 分解困难性的r s a 密码，基于离散对数困难性韵e l g a m a l 密码，以及基于椭圆曲线离 散对数困难性的椭圆曲线密码等。 人们对椭圆曲线的研究已有1 0 0 多年的历史，而椭圆曲线密码是n e a lk o b l i t z 和 v i c t o rm i l l e r 于1 9 8 5 年提出来的。目前，椭圆曲线密码已成为除r s a 之外呼声最高 的公钥密码之一。它可以提供同r s a 密码体制同样的功能。然而它的安全性建立在椭 圆曲线离散对数问题( e c d l p ) 的困难性之上现在求解e c d l p 的最好算法具有全指数 时间复杂度，与此不同，整数因子分解问题却具有亚指数时问算法。这意味着要达到 期望的安全程度，椭圆曲线密码可以使用较r s a 密码更短的密钥。普遍认为1 6 0 位椭 圆曲线密码可提供1 0 2 4 位r s a 密码的安全程度。由于密钥短，7 工程实现的加解密速 度较快，并且可节省能源、带宽和存储空闻。正因为如此，一些国际标准化组织已把 椭圆曲线密码作为新的安全标准。由于椭圆曲线密码具有上述优点，因此椭圆曲线密 码特别适于在航空、航天、卫星及智能卡等系统中应用。 另一方面，伪随机码又称为伪随机序列，也是一类有着广泛应用的码，例如，在 连续波雷达中可用作测距信号，在遥控系统中可作遥控信号，在多址通信中可用作地 址信号，在数字通信中可用作群同步信号，还可用作噪声源及保密通信中起加密作用 等等。由于源序列发生器的重要作用和地位，对它的研究一直是序列密码研究的基础 工作之一文献 1 中将序列密码的设计分为源序列发生器、非线性加工、输出合成、 结合函数四部分。源序列发生器是序列密码设计的第一部分，是序列密码的驱动部分， 是古典序列密码中轮子或圆盘的继承和发展。近现代数学理论在序列密码源序列发生 器设计中的引入于发展，使得序列密码的设计由艺术发展为科学技术。它的主要功能 第1 页 ：童鱼奎竺堡主兰垡丝塞 是产生长周期的伪随机序列。另外文献 1 中给出了字序列密码的概念，所谓字序列密 码是指含有以字为运算单元的序列密码。 源序列发生器目前比较成熟的结果主要包括二元线性递归序列、环导出序列、m 序 列等。在序列密码的设计中环导出二元序列作为源序列发生器，体现了环上运算域上用 的特点。发现新的具有良好密码学性质的源序列发生器仍是序列密码设计的重要需求之 一 下面先来介绍椭圆曲线密码的设计思想。 大素数p 域、巧( p 为大于2 的素数) 域上的椭圆曲线公钥密码体制( e c c ) 是基于椭圆曲线离散对数问题的计算困难性基础之上的。用椭圆i 曲线实现加密，首先把 明文肌表示成一个点m ，然后再加上七q 进行加密，其中k 是随机选择的j 下整数，q 是 接受者的公开密钥，发方把密文c i = k p 和c 2 = m + k q 发给接收方。接收方用自己的私 钥d 计算蚂= d ( k p ) = k ( d e ) = 坦进而可恢复出明文m = c 2 一坦。攻击者想要恢复出明 文m ，则需要计算向2 。而从公开的参数组q 和c i = k p 计算】| q 就是椭圆曲线离散对数 问题。 ， 。定义0 1 所谓椭圆曲线离散对数问题是：给定定义于有限域e 上的椭圆曲线e ， 基点，e ( ) ，阶为疗，点q ( p ) ，寻找一个整数，【o ，n - i 】，使得a = p 。整数，称 为q 的基于p 的离散对数，表示为，= l o g ，q 。 为了抗穷举攻击，珂必须足够大；为了抗p o h l i g - h e l l m a n 算法和p o l l a r d sr h o 算法相结合的攻击要求厅含有大素数因子i 另外椭圆曲线还要防止其他的攻击方法。e c c 的本质上是在椭圆曲线的一个大的循环子群上操作的。 在密码编码算法的过程中，赖学嘉在欧洲密码标准算法的设计过程中主张在不同的 代数结构上进行混合运算，例如有进位加、模二加、乘法等。因此对不同的代数结构上 的运算之间的关系进行研究就有了密码学的理论意义和实践意义。 有时我们可以不考虑函数的定义域以及值域的代数结构，而只考虑函数的真值表表 示。所以在一定的集合上，为了方便表出，我们可以合理转化函数的定义域以及值域的 代数结构，只要在一定条件下，真值表形式一致即可。显然，保持真值表不变的函数的 定义域以及值域代数结构的变换，是密码学的加解密意义上的不变量，我们称为密码学 符号不变量。 定义0 2 设a 、b 是两个代数结构，若a 上的函数g “，x 2 ，) - - y ，其中 第2 页 x , 0 s i ”) 和y 均取值于a 中元素的二进制表示，b 上的函数 ( ，屯，) = y ，其中 置( 1 ，蔓哟和y 取值于b 中元素的二进制表示，则映射g _ h 称为密码学符号不变量。 在文献 2 中，说明了环上的映射不能全部由多项式表出，由于域上的映射都可以 由多项式表出，因此在密码学符号不变量的意义下可以将环上的映射变换成域上的多项 式以此来研究它的密码学性质。 在密码学的计算中，比如m d 5 ，正形置换，都用到了坏上和域上的运算。下面我们 用密码学符号不变量来刻画普通代数结构上的运算。判断剩余类环上运算的密码学性质 的好坏与否，主要有代数项数和代数次数两个指标。 、 引理0 1 有限域只上的多项式的代数项数和代数次数对哥域e 的不同的基是不 变量。 + 证明假设域凡的两组基表示之间的坐标变换为盯，则易知盯是同构。因此对b 上多项式厂( 五，) = e 气吨尊尊，仃，( 而，) = e 盯心，) 奇毋，由于盯是 “乜与+ t 同构，因此若仃( c ) = 0 ，则只有c = 0 。因此代数次数和代数项数都不改变。 引理0 1 表明环上算子对应的域上多项式的代数项数和代数次数都是多项式自身蕴 含的性质，与域的基的选取无关。因此本文就以有限域职：的一组基 l ，口) 为代表，其中t ；t 是石2 + 工+ l 的根。则玛= 0 ，1 ，口，口2 = 口+ 1 。在密码学符号不变量的意义下，可以建立 剩余类环z ，( 2 2 ) 与b 的卜l 对应关系：0 斗0 , 1 _ 1 ，2 斗l o - - 4 口，3 1 l 专口2 。 本文借鉴了椭圆曲线公钥密码体制( e c c ) 和环导出序列的设计思想，基于有限域 上的椭圆曲线，给出了其特定子群上的本原多项式的定义、计数、极大长序列的周期、 初态的计数及极大长圈的计数。该类递归序列在几何上线性，但从基域上看是非线性 的，这正是我们探讨基于有限域的椭圆曲线上的线性递归序列的出发点 第3 页 青岛大学硕十学位论文 第一章剩余类环z ( 2 2 ) 上算子的密码学性质分析 本章提出了密码学符号不变量的概念，研究了剩余类环z ( 2 2 ) 到有限域e ：的密 码学符号不变量，即z ( 2 2 ) 上加法、乘法算子所对应的域e ：上的多项式，给出了这 些多项式的代数次数和代数项数等密码学参数。对于剩余类环z ( 2 f ) ，给出了计算 加法密码学不变量的算法。 1 1 剩余类环z ( 2 2 ) 上的加法算子， l 引理1 1 1 剩余类环z ( 2 2 ) 上x + y 对应的有限域蜀上的多项式是： x + yg ( x ，y ) = x + y + ( a + 1 ) x y + a ( x y 2 + 工2 ) ，) + x 2 y 2 证明：( 待定系数法) 由于在域只：上，= x ，故不妨设 g ( x + y ) = a o o + a o i y + a 0 2 y 2 + ，+ q o x + q j 砂+ q 2 x y 2 + q 3 x y 3 + 呸l x 2 y + x 2 y 2 + a 2 ，+ a 3 1 x 3 y + a 3 2 x “y + c 1 3 3 ， 根据环上运算的真值表在密码学符号不变量的意义下到域上的对应，代入线性 方程组得 。 g ( x ，y ) = z + y + ( 口+ 1 ) x y + 以x y 2 + z 2 y ) + x 2 y 2 。 可见x + y 对应的有限域凡上的多项式的代数项数和代数次数分别为6 和4 ， 分别比环上增长了4 和3 ， 定理1 1 1 当口= 2 时，取r = o ，1 ，口，口2 = 口+ 1 ) 的一组基为 l ，盯) ，则； g ( 五，而，毛) = 而+ ( a + 1 ) 五一+ 口妒矽+ 2 _ 2 。 is f | ， i 自j g l a g , + a j t g - 3 l - j 自 证明：当行= 2 时，由引理1 2 1 得 g ( 一，x 2 ) = + 屯+ 瞳+ 1 ) 五t + 口 + 口x ；毪+ 假设 时命题成立，则当n + l 时2 g “，“) = g ( g ( 五，) ，+ 。) = g ( x t ，毛) + + i + ( 口+ 1 ) 矗“+ 口g 瓴，x 。) 矗i + 瑾g ( 五，矗) 2 】o l + 口g ( 葺，) 2 x 。2 + i 第4 面 第一章剩余类环z ( 2 2 ) 上算子的密码学性质分析 = + 以+ 1 ) + 口舻矽+ # 巧+ 靠+ ”“ 。q “幂z 乌 ”。“ + ( a + 1 ) 【而+ ( 口+ 1 ) 葺+ 口矽矽+ x 7 _ 2 】矗+ 1 口如 y , j s sl 鲥，朝l 鲥( j 翻 。 q + 以一3 + 口【x j + + 1 ) x j x i + a # 矽+ 一2 _ 2 j 矗2 “ 1 9 9 l 。s i ， a i j * 叫a j g - 3 1 9 自 + 梯【# + 位+ 1 ) # 彳+ 口弩矽+ 薯2 2 k + ， “9 瑚“嚣z 薯 “ + 【# + 口葺2 2 + ( 口+ 1 ) # 4 2 唧+ _ 】t ， 1 9 9 l g ，g q i + t j 。n ， 墙g = 而+ ( 口+ 1 ) 薯+ 口矽弩+ 薯2 2 l 叠，“ 、盈j 如“l g j 如i s i j j ， a j + a = 3 + 口一毛。+ p 衫“+ ( 口+ 1 ) 薯2 _ 2 毛。 l l l j f a 鬻璺 细。“ 十口t 矗。+ 毛巧巧2 + l + ( a + 1 ) 矽# 矗。+ 口2 2 2 + ， 旧如 脚叫朝象z 器 恼q 如 + 2 k 2l + 口薯2 _ 2 2 。+ ( 口+ 1 ) # 4 # 吩2 “+ 一。 l o ，令q = o 嘲毡5 鼍，“ 。 1 ( 1 f 刀) ，那么q = 西，( q ，) 2 ，其中o ，( q ，以) 按( m o d 2 ) 取值。或l 。 e - i# 一l 引理1 3 2 m ( 权位序列) 设口，z ( 2 。) ，r a = 群，4 = q 2 ，令 = o仁o a j - a = 。- i 只2 t ，口，+ 口；芝g l 重，b ；c ：+ q j ( m o d 2 ) f ，oj ，o 则 p o = q o = e o ，n2 t + 一i c k i + 亏一1 只一i ( m o d 2 ) ， 吼暑+ 弓一i q l + 一l 吼- l + 五l ( r o o d 2 ) ， 其中只，覃，蜀，莓均取值0 或1 ，且互z 蜀+ l ( m o d 2 ) 。、 e - - l ，- i 卜l 定理1 3 1 设口，z ( 2 。) ，且= z ，n = d 。z ，令+ 口e q ，2 ，则 z oi = 0l - 0 ， f 一2 吼= a t 十+ q 一1 吐l + q 群( q + i + 以j ) ( q + 2 + 2 ) ( q i + 吐1 ) ，f 2 0 正i o 其中吼取值0 或1 t 证明假设定理对f 时成立，根据引理1 3 2 ，( 以下加运算都是m o d 2 加) 吼+ l = 岛“+ 亏q + + t 吼 = a t “+ 砍l + ( q + + 1 ) q + ( q + ) + ( q + ) 【q + + q 1 吐l + q a f ( q + 。+ 吐。) ( q + 2 + 口：t 2 ) ( 口f 。+ 吐。) 】 第1 2 页 第一章剩余类环z ( 2 2 ) 上算子的密码学性质分析 = 口，1 + 西l + q 麓+ ( 口f + ) + ( q + 群) + ( q 十研) q l 吐l f 一2 + q 群( q + 。+ 口：+ 。( c i + ：+ 2 ) ( 口，一i + 吐) ( q + ) j = o t - ! = q “+ 吐。+ 呶+ q ( 纵l + 1 ) + 2 + 畋2 ) ( 口f i + 吐。) + ) “o 因此定理对t + l 时成立。从而定理对任意整数纬口成立。 引理1 - 3 3 刚令q ，则溉， 是的一组哆基当且仅当 吃 醒 j 伍f 睇 ； 4 o 定理1 3 2 令缸，9 2 ，口2 z ，g 是咚的一组正规基，其中位是f 2 上擀次本原 多项式的一个根，v x e ，x = x o c t + x l a 2 + 心口一+ + x m l 口，则而，墨。x 2 ，一i 可由x s x 2 , x 2 = , x 矿，x 唯一表出。 证明由于 岔 口 口巨 而由引理1 3 3 取q - - - - c z ，嘞= 口2 ，吒= t z 2 - 可知， l 口口2 l i9 2口2 。 j l ， k 。口 0 ， 从而，玉，鼍，可由x ，x 2 , x ”，茗7 ，x 唯一表出。 ， 根据定理1 3 1 和定理1 3 2 ，我们得到了计算密码学符号不变量的算法： 算法1 3 。l ( 计算密码学符号不变量的算法) 第1 3 页 矿 岱盯矿一扩 r!f叫i 护： 青岛大学硕十学位论文 p i - i 第一步：对剩余类环z l ( 2 。) 上的两个变量x = x , 2 。和y = 巧2 。，令 、 i - ot f f i o e l z + y = h , 2 。，根据定理3 计算囊= 吩( 丘，丘十k ，艺一。) ，o o , i = 1 ，2 ，j ，b u g = g ( a ) o g ( 见) o o g ( n ) ，g ( p ) 表示g 中阶 为素数p 的方幂的元素所形成的子群。 。 定义2 1 1 川如果群g 中一个元素g 的阶为素数p 的一个方幂，则称g 为一个 p 一元素。如果群g 的阶为素数j p 的一个方幂，则称g 为一个p 一群。， 定义2 1 2 6 1 设群g 的阶为 ；p ，m ，r l ，( m ，p ) = l ，p 是一个素数，那么g 的 p 阶子群称为g 的一个& y l o w p 一子群。 引理2 1 。2 说明了当g 是蚪阶有限交换群时，对于拧的每个素因子p ，g 的 s y l o w p - 子群都是存在且唯一的，而且g 可以表示成它的墨瓜 w p 一子群的直积。 引理2 1 3 删有限交换群都可以唯一地表示成循环p 一子群的直积。 由引理2 1 2 和引理2 1 3 可知，有限交换群都可以唯一地分解成阶为素数的 方幂的循环子群的直积。 定理2 1 1 设映射伊：g ( p 1 ) 寸觑a ) o g ( p 2 ) o o g ( 见) ，g ( ，) 表示g 中阶为 素数，的方幂的元素所形成的循环子群定义为a ( 口，岛，e ) ，满足 c p ( a b ) = ( a b ，e ，e ) = 烈口) 伊( 6 ) ，则9 是群同构。 第2 0 页 椭圆曲线上的递归序列 证明若a 西g ( p i ) ，则烈口) = ( 口，p ，e ) ( 6 ，p ，p ) = 矿( 6 ) ，因此是单的。又 对，6 ，p ) g ( p 1 ) o g ( n ) o 固g ( 见) ，存在口e g ( p o ，使得缈( 口) = ( 口，p ，p ) ， 因此满。又对口，b e g ( p i ) ，矿( 口) 认6 ) = ( 口，岛，咖( 6 ，岛，e ) = ( a b ，p ，。p ) = q o ( a b ) 。 因此妒是群同构。 定义2 1 3 7 l 设置是交换环，足嘲上首l 多项式f ( x ) ，如果厂( o ) 是r 中的可 逆元，称f ( x ) 是非奇异的。 本文中讨论的移位寄存器都是非奇异的。 定义2 1 4 设q ( f 是非负整数) 是有限a b e l 群g = 岛，g l ，9 2 ，一i ) 中的 元素，称序列，口i ，a 2 ，a s ，a 4 ，a 5 ，a 6 ，是由递归关系式 j n a k = 一q 嚷叫，后刀，c c z ，其中= 1 ( 1 ) j - 1 产生的g 上的胛级线性递归序列，如果它适合递归关系式( 1 ) 。 定义2 1 5 线性递归关系式( 1 ) 的生成多项式是 f ( x ) = l + q 工+ + c 卜】矿1 + ， 。 其中c ，z 由于q = l 在z 中可逆，因此八d 是非奇异的。 根据线性递归关系式( 1 ) ，易知 引理2 1 4 有限a b e l 群g 上的适合线性递归关系式( 1 ) 的序列 a o ，o l ，a 2 ，a 3 ，口4 ，呜，口6 ，中的每一项都可以表示为如下形式： q = t o 。a 0 + i t i q + 1 2 j 岛+ + - l 口n l ， ，k ，z ，0 k 玎一1 ， 假设q ( eg ) 的阶为，；，则第后分位系数序列，k ，z ( o r d ( a 1 ) ) ，o k 疗一1 。 h 证明( 数学归纳法) 当f 刀时命题成立，即巳= 0 则当i = j + l 时， 1 , inn - - t 一l1 , 1 q 。= 一q 巳+ 。= q ( 0 ( 川。) ) = ( 一q 乙( 川卅) ，从而引理得证 l = l_ im t o_ of _ l 定理2 1 2 当g 上的r l 级线性递归序列适合线性递归关系式( 1 ) 时，它的第 k 分位系数序列( 0 k 开一1 ) 也适合线性递归关系式( 1 ) 。即 乇= 一川) ，厶= l ，qe z ，o k n - 1 ，1 = o 1 2 证明 j 哟时命题成立，即0 = q 川，q q $ 考虑j + l 时的情形。因为 n月h lh 一1 “ q + ，= 艺g 乃+ 。= - q ( 川- 1