（通信与信息系统专业论文）wpki中有限域切比雪夫多项式算法的设计和实现.pdf

北京交通大学硕十论文 y 8 7 9 8 3 0 中文摘要 摘要 随着信息化的不断深入，人们对信息安全的要求也越来越急迫。各 种与安全有关的体系和算法成为业界研究的热点。本文首先介绍了p k i 和w p k i 的概念，主要技术和发展现状，并指出公钥加密算法的重要性 及其对整个w p k i 体系的影响。 接着介绍了现有的一些公钥加密算法，芳有针对性的研究了切比雪 夫多项式算法。在对其现有破解方法进行深入研究后，独创地将其定义 进行扩展，设计出有限域上的切比雪夫多项式。又通过理论证明、编程 实验和数据分析总结出它的单向性、带陷门特性和伪随机特性等，并指 出这些性质对其应用于加、解密的影响。然后，通过分析这些性质得出， 针对实数域切比雪夫多项式的破解方法在有限域上不再成立或可以避 免，因此有限域切比雪夫多项式可以作为公钥加密体系的基础。 随后利用有限域切比雪夫多项式的上述特性，设计出密钥协商、公 钥加密和数字签名算法。再根据r s a 等算法的具体应用情况，设计出上 述算法的性能测试方案，编程实验，并对实验数据进行分析研究。 最后，将有限域切比雪夫多项式算法应用于x 5 0 9 数字证书。通过 比较分析，指出相对于r s a 和e l g a n l a l 算法，其密钥的产生更容易，算 法的破解更复杂：相对于e c c ，数学概念更易理解，计算效率更高。并 指出其对w p k i 中x 5 0 9 数字证书具体应用的影响。 【关键词】公钥基础设施，切比雪夫多项式，有限域，自相关特性 性能分折 北京交通人学硕士论文英文摘要 a b s t r a c t c o i n c i d e mw i t ht h ed e e p l yp o p u l a r i t yo fm ei n 硒r n l a t i o nt e c h n o l o g ya r e m em o r ea i l dm o r eu r g e n tr e q u i r e m e n t so ni n f o m a t i o ns e c 嘶t y a nk i n d so f s y s t e m sa n da r i t h m e t i cr e i a t e dt oi n f 0 啪a t i o ns e c u r i t ya r eb e i n gm er e s e a r c h l 贼s p o to ft h ef i e l d i nt h i sa n i c l e ，i ti s 氍r s t l yi n t r o d u c e dt h ec o n c e p t i o n so f p a n d1 w p k i ，a sw e l la st h ep r i m a r ys k i l l sa n dd e v e l o p i n gc o n d i t i o no f m e m a f t e r w a r d s ，t l ei m p o r t a l l c eo ft h ep u b l i ck e ye n c r y p t i o n 撕m m e t i c a n d “se 位c t so nw p k ia r ep o i n t e do u t ，t h a t st h e 疗r s tc h a p t e r i n 也ef o l l o w i n g 恤优c h a p t e r s ，“i sd e s 翻b e ds o m ee x i s t e dp u b l i ck e y e n c r y p t i o na r i t h m e t i c t h e n ，t h ec h e b y s h e vp o l y n o m i a l si sb e i n gf o c u s e do n i t i sp r o p o s e dt h en n i t e 丘e l d sc h e b y s h e vp o l y n o m i a l sb ye x t e n d i n gt h e d e f i n i t i o nn e i do fi ta r e rd e e p l yr e s e a r c h i n go nt h ea t t a c km e t h o d so f “ w “he x p e r i n l e n t i n g ，p r o 、7 i n ga n da n a l y z i n g ，s o m ec h a r a c 慨i s t i c so f “，s u c h a s o n e - w a y 打印p e da n dp s e u d o m n d o mc h a r a c t e r i s t i c s ，a r e c o n c l u d e d f o l l o w e db yt 1 1 eg i v i n go mo f t l l e i re 缗j c t so np u b l i ck e ys y s t e m h e r e a r e r ，i t i si l l u s 订a t e dt h a tm et r a d i t i o n a la t t a c km e t h o d sa r en ol o n g e rp r a c t i c a b l eo r c o u l db ea v o i d e da n d 也e 铀i t ef i e l d sc h e b y s h e vp o l y n o m i a l sc o u l db eu s e d 船t h eb a s eo f t l l ep u b l i ck e ys y s t e m i n 也e 矗铷a n ds i x t lc h a p t e r s ，i ti sd e s i 鲫e d 也ep u b l i ck e yc i p h e r ，d i 百t s i g 麒t ea n dk e yn e g o t i a t i o na r i t e t i cb yt h ec h a r a c t e r i s t i c so ft h ef i 血e 6 e l d sc h e b y s h e vp o l y n o m i a l s a 懿刑舡d s ，a c c o r d i n gt ot h ee x i s t e dp u b l i c k e va r i t k n e t i c s u c ha sr s a ，s c h e m e so ft l ep e r f o m l a n c et e s to nm ea b o v e 撕t h m e t i ca r ed e v i s e da r i de x p e r j m e n t e d ，c o m p a n i e dw i t ht h ea n a l y s i so f t h e c x p e r i m e n td a t a 1 1 1t h e1 a s tc h a p t e r ，t l e 矗n i t e 矗e l d sc h e b y s h e vp o l y n o m i a l si sa p p l i e di n x 5 0 9d i g i tc e r t i f i c a t e 1 ti ss u m m a r i z e dm a tt h ep r o p o s e da r i t l l i i l e t i ci se a s i e r t og e n e r a t ek e ya n dh a r d e rt oa 札a c kc o m p a r e dw i t hr s a a n de l g 锄a l ，a n di s m o r ee f f e c t i v ea n dc o m p t e h e n s i v ec o m p a r e dw i t he c c f i n a i l y ，t h ee f 艳c t s 北京交通大学硕十论文英文摘要 o nm o d i f i c a t i o n o fx 5 0 9d i g i tc e n i f i c a t ei nw p k ib yt h ef i l l i t ef i e l d s c h e b y s h e vp 0 1 y n o m i a l sa r ei n d i c a t e d 【k e yw o r d s 】 p u b l i ck e yi n f r a s t r u c t u r e ，c h e b y s h e vp 0 1 y n o m i a l s ， f i n i t ef i e l d s ，a u t o c o r r e l a t i o nc h a r a c t e r i s t i c ，p e r f o r m a n c ea n a l y s i s i i 北京交通大学硕十论文前言 第一章前言 随着移动通信和互联网技术的发展，以及各行各业对i t 技术日渐多 样化的需求增多，用户希望能够无时无刻、在任何地点均能上网，因而 无线通信技术在银行、证券、商务、贸易、办公、教育等各方面的需求 越来越多，随之产生的无线通信领域的安全问题也因此引起了广泛的重 视。 由于无线网络安全技术在移动商务中也起着非常重要的作用，它守 护了商家和客户的重要机密，保证了商务系统的信誉和健康，还确保了 商家和客户的财产安全，同时为服务方和被服务方提供极大的方便，因 此，只有采取了必要和恰当的技术手段才能满足移动商务的安全需要， 从而使之能更加充分地被推广运用，满足各行各业的需求。 1 1 w p k i 概述 1 1 1w p k i 的概念 目前，国内外的一些组织和公司正在按照上述安全性的需求努力地 研究和开发无线网络安全的技术，随着无线网络安全技术的日益发展和 逐步成熟，w p k i 技术在无线网络安全领域得到了高度重视，其应用也 日趋广泛。 这里首先简单介绍一下p k i 的概念，p ( p u b l i ck _ c yi 曲髂订u c t l 鹏) 即公开密钥体系。简单地晚，p k i 技术就是利用公钥理论和技术建立的 提供信息安全服务的基础设施，它是国际公认的互联网电子商务的安全 认证机制，它利用现代密码学中的公钥密码技术在开放的i n t e m e t 网络 北京交通大学硕士论文 环境中提供数据加密以及数字签名服务的统一的技术框架。公钥是目前 应用最广泛的一种加密体制，在这一体系中，加密密钥与解密密钥各不 相同，发送信息的人利用接收者的公钥发送加密信息，接收者再利用自 己专有的私钥进行解密。这种方式既保证了信息的机密性，又能保证信 息具有不可抵赖性。目前，公钥体系广泛地用于c a 认证、数字签名和 密钥交换等领域。 w p ( w i r e l e s sp u b l i ck e yi n f r 勰t n l c t u r e ) 即“无线公开密钥体系”， 它是将互联网电子商务中的p k i 安全机制引入到无线网络环境中的一套 遵循既定标准的密钥及证书管理平台体系，用它来管理在移动网络环境 中使用的公开密钥和数字证书，有效建立安全和值得信赖的无线网络环 境。w p 并不是一个全新的p k i 标准，而是传统的p k i 技术应用于无 线环境的优化扩展。它采用了优化的e c c 椭圆曲线加密算法和压缩的 x 5 0 9 数字证书，并同p k i 一样采用证书管理公钥，通过第三方的可信 任机构认证中心( c a l 验证用户的身份，从而实现信息的安全传输。 1 1 2w p k i 技术及其发展现状 w p k i 系统的主要功能是为基于移动网络的各类移动终端用户、以 及移动数据服务提供商的业务系统提供基于w p 斑体系的各种安全服 务，其系统架构如图1 1 所示。 无线终端通过注册机构向证书中心申请数字证书，证书中心经过审 核用户身份后签发数字证书给用户，用户将证书、私钥存放在u i m 卡中， 无线终端在无线网络上进行电子商务操作时利用数字证书保证端对端 的安全。服务提供商则通过验证用户证书确定用户身份，并提供给用户 相应的服务，从而确保电子商务在无线网络上的安全进行。 北京交通大学硕士论文 图1 1w p k i 安全体系总体架构图 类似于p k i 体系，一个完整的w p k i 系统必须具有权威证书签发机 关( c a ) 、数字证书库、密钥备份及恢复系统、证书作废系统和应用接口 等基本构成部分，其构建也将围绕着这五大系统进行。 1 2 公开密码体系中的加密算法 密码系统的两个基本要素是密钥管理和加密算法。w p k i 就包括了 密钥管理，如证书和c a 。加密算法则是一些公式和法则，它规定了明 文和密文之间的变换方法，是保证整个体系和某个会话安全的基础。 密码的发展大体经历了古典密码、传统密码算法和现代密码算法。 古典密码算法是基于字符替换或对位进行变换的密码算法，现在已很少 使用；传统密码算法又称对称密码算法( s y n e t r i cc r y p t o 孕a p h i c a l g o r i t l l i n s ) ，其特点是加密和解密必须是同一密钥，如d e s 和i d e a 等； 现代密码算法又称非对称密码算法或公钥密码算法( p u b l i c k e y c r y p t o g r a p h i ca 1 9 0 r i t h m s ) ，是1 9 7 6 年由d i f f i e 和h e l l m a n 在文献【1 中 提出的。其特点是用户或系统产生一对密钥，将其中的一个公开，称为 北京交通大学硕士论文前言 公钥，用于其他人加密传送给目的用户的数据；另一个自己保留，称为 私钥，用于该用户解密其他人传来的数据。任何获悉用户公钥的人都可 用该用户的公钥对信息进行加密与用户实现安全信息交互。由于公钥与 私钥之间存在的依存关系，只有用户本身才能解密该信息，任何未受授 权用户甚至信息的发送者都无法将此信息解密。另外，用私钥也可以加 密数据，其密文只有用相应的公钥才能正确的解密为明文。由于公开密 码算法的这两个特点，使得它既可以进行数据加密又可以用来做数字签 名和身份验证。 一般的情况下，网络中的用户约定一个共同的公开密钥密码系统， 每个用户都有自己的公钥和私钥，并且所有的公钥都保存在某个公开的 数据库中，任何用户都可以访问此数据库。便有如图1 - 2 所示的加、解 密过程： 1 1a l i c e 从公丌数据库中取出b o b 的公开密钥。 2 1a l i c e 用b o b 的公开密钥加密她的消息，然后传送给b o b 。 3 ) b o b 用他的私钥解密a l i c e 的消息。 。，9 拿明文艾n 忑意 密文 7 1 。一 一一一一一一一- 一一- 一，一一一j l 一一一一一一一一一一一一一一一一一一一一一- 一i 发送方 接收方 幽1 2 加密，解密基本步骤 现有的公开密码体系中常用的非对称加密算法主要分为三类，它们 北京交通大学硕士论文 分别基于不同的数学难题构造： 大整数分解难题( i m e g e rf k t o r i z a t i o np r o b l e m ，i f p ) ：如r s a ； 离散对数难题( d i s c r e t el o g a r i m mp r o b l e m ，d l p ) ：如e 1 g 锄a l ， d s a ： 椭圆曲线离散对数难题( e l l i p t i cc u “ed i s c r e t e1 0 9 a r i t l l r n 口r o b l e m ，e c d l p ) ：如e ce l g 枷a l ，e c d s a 。 1 3 公钥密码的应用 1 3 1 数据加密 一般说来，公钥密码中的计算是很慢的( 相对于对称密码) ，以至 于在很多情况下是不可行的。所以可以用一个两步过程来代替，从而加 快加密速度： 1 ) 用随机生成的对称密钥来加密数据。 2 ) 用授权接收者的公钥来加密这个对称密钥。 当授权接收者收到加过密的数据后，也采取一个类似的两步过程： 1 ) 授权接收者用自己的私钥柬解出对称密钥。 2 1 接着用对称密钥进行解密获得原始数据。 1 3 2 数字签名 由于公丌密钥算法中不仅公钥加密的消息可以用私钥解密，而且反 过来用私钥加密的消息也可以用公钥解密。因此，数字签名在公钥密码 体制下是很容易获得的一种服务。从根本上说，数字签名就是依靠密钥 对的概念，对数据进行私钥操作。发送方必须拥有一个只有自己知道的 私钥，这样当他签名一些数据时，这些数据唯一而又明确地和他联系在 北京交通人学硕士论文 一起，同时，应该有一个或更多实体都知道的公钥，以便大家验证，并 确认签名是发送方的。其基本协议很简单： 1 ) a 1 i c e 用她的私钥对文件加密，从而对文件签名。 2 ) a l i c e 将签名后的文件传给b o b 。 3 ) b o b 用a l i c e 的公钥解密文件，从而验证签名。 在实际过程中，这种做法的准备效率太低了。从节省时间，数字签 名协议常常与单向哈希函数一起使用。a l i c e 并不对整个文件签名，而是 只对文件的哈希值签名，如图1 3 所示。 籼、h 稍息 消息l。l 散列 l7 | 函数 与黛灏l i 摘啦 爿。 西 h 带l + 鬣黼 l 臂“1慝| | 骥 鳓 潮 a l i c e b o b 图1 3 数字签名协议原理 数字签名不仅提供了数据源认证服务，还保证了数据的完整性及不 可否认性。 6 北京交通火学硕士论文 1 3 3 密钥的建立 公钥密码体制也可以用来实现两个实体间的密钥建立( 即密钥交 换) 。也就是说，一个协议用到公钥和私钥，协议的结果是两个实体共 享一个对称密钥，而这个密钥不为其他的实体所知。密钥的建立有以下 两种方法： ( 1 ) 密钥传递：一个实体产生一个对称密钥送给其他的实体，公 钥密码体制可以用来保证传送的机密性。如发送方用接收方的公钥来加 密对称密钥，使得只有接收方才能得到。 ( 2 ) 密钥协商：两个实体共同来完成对称密钥的产生，公钥密码 体制把这个过程变得相对简单。如d i m e h e l l m a l l ( 1 】体制就是第一个利用 公钥密码的特点来选取双方共同约定的对称密码体制中密钥的方案。 北京交通大学硕士论文 切比雪夫多项式及其应用 第二章切比雪夫多项式及其应用 2 1 切比雪夫多项式定义 在本研究报告中所讨论和应用的都是第一类切比雪夫多项式 ( c h e b y s h e vp 0 1 y n o m i a l s ) ，它是一组正交多项式集合，用( 工) 表示。 下面给出我们主要研究的也是密码学上主要采用的两种定义。 2 1 1 迭代形式的定义 切比雪夫多项式迭代形式的定义如下： 令行z ，变量z 一1 ，1 ，切比雪夫多项式瓦( x ) ：【1 ，1 】- + 一1 ，1 】的 迭代关系为 ( x ) = 2 x 瓦一1 ( x ) 一l 一2 ( x ) 玎2 ( 2 1 ) 并且有瓦( x ) = l ，五( x ) = x 。 由上面的定义可以得出如下的切比雪夫多项式： 瓦( x ) = 1 五( x ) = x 瓦( 工) = 2 x 2 一l e ( x ) = 4 _ ) c 3 3 x l ( x ) = 8 2 4 8 x 2 + 1 e ( z ) = 1 6 x 5 2 0 工3 + 5 x 北京交通大学硕士论文切比雪夫多项式及其应用 2 1 2 三角函数形式的定义 则有 切比雪夫多项式还可以用三角函数的形式表示，定义如下： 令”z ，变量x 卜1 ，1 ，切比雪夫多项式瓦( x ) ：【一1 ，1 斗【一l ，1 z ( x ) = c o s ( n a r c c o s ( z ) ) 由( 2 2 ) 式可以得到： 瓦一1 ( x ) = c o s ( ( n 一1 ) a r c c o s ( x ) ) ( 2 2 ) ( 2 | 3 ) 一2 ( x ) = c o s ( ( n 一2 ) a r c c o s ( x ) ) ( 2 4 ) 再将( 2 ，2 ) 式代入( 21 ) 式的左边，( 2 3 ) 式和( 2 4 ) 式代入( 2 1 ) 式的右边， 利用三角函数的和差化积公式，通过简单的三角变换可以得到等式的左 右两边是相等的。从而可以推知( 2 1 ) 式和( 2 2 ) 式是等价的。 2 2 切比雪夫多项式特性 稳五黼搿 粼 溅i l 潮 图2 1 切比彗夫多项式曲线图 北京交通人学硕士论文切比雪夫多项式及其应用 在这一部分，我们将根据第2 章第1 节中切比雪夫多项式的定义， 介绍分析切比雪夫多项式应用在密码学上的一些特性。图2 1 是n = 1 ， 2 ，3 ，4 ，5 时乙( x ) 的曲线图。从图中我们可以很容易的观察到切比雪 夫多项式的很多特性，下面分别列出并加以说明。 2 2 1 混沌特性 混沌系统的特点是：对初始条件很敏感，同随机行为相似，具有连 续的宽带功率谱f 7 】f 们。这是大部分密码学原型所需要具备的特性。由切 比雪夫多项式的迭代定义我们可以得知它也满足这样一些特点【8 。 切比雪夫多项式e ( x ) 随着n 的增大，它在 1 ，1 上的周期个数不断 增加，与x 轴的交点数也不断增多，当胛斗o 。时，其周期个数及与x 轴 的交点的个数也趋于。，可以认为l ( x ) 与x 轴的交点遍历【一1 ，1 整个区 间。正因为切比雪夫多项式的这种混沌特性，所以它才会在密码学中受 到广泛关注、应用和研究。 从图2 1 可以很明显的看出这个趋势。兀( x ) 与x 轴没有交点，墨0 ) 与x 轴有一个交点，正( x ) 与x 轴有两个交点，五( x ) 与x 轴有三个交点， e ( x ) 与x 轴有四个交点，不( x ) 与x 轴有五个交点。可以推知，瓦( x ) 与x 轴有”个交点。 2 2 2 奇偶对称性 由切比雪夫多项式的三角函数定义式( 2 2 ) 可以推知其具有奇偶对称 特性，当n 为偶数时，瓦( x ) 是偶函数；当n 为奇数时，毛( 石) 是奇函数， o 北京交通人学硕士论文切比雪夫多项式及其应用 即 从图2 1 我们可以直观地看出这一点。正( x ) 、正( x ) 、i ( x ) 是对原点 对称的奇函数：磊( x ) 、己( x ) 、五( x ) 是对y 轴对称的偶函数。 2 2 3 半群特性7 】 切比雪夫多项式具有如下关系式： 。( x ) = z ( 乙( x ) ) = 乇( ( x ) ) 厅，聊z( 2 6 ) 若已知初始值x 。，切比雪夫多项式映射关系为矗。= 耳( _ ) ，则由 ( 2 ，6 ) 式可得二 矗= 耳( 耳( 耳( ) ) ) = l 。( ) ( 2 7 ) 半群特性是切比雪夫多项式在密码学中最重要的特性，是其用于加 密、数字签名和密钥协商的基础。 2 2 4 正交性( 互相关性) 在乘上一个加权函数了圭尹后，n 值不同的切比雪夫多项式( z ) 间构成了一个完备正交集，表示如下： f ；南c 枷仨 l ；七撑 掰薄_ o 孵一箨= t 2 ，3 ，。 由图2 1 也可以看出其正交关系。如瓦( z ) 与五o ) 、正( z ) 、弓 ) 、 北京交通人学硕士论文切比雪夫多项式及其应用 l ( x ) 、正( z ) 正交。我们从三角函数的观点来看可以更加清晰明了，很 明显三角函数集构成了完备正交集。 2 2 5 转换特性 由文献 9 有如下关系式： l ( 圭( x + x _ 1 ) ) = 圭( x ”+ x 一”) ( 2 8 ) 利用这个特性，可以把切比雪夫多项式( x ) 中求n 的难题转换为求 离散对数的问题。 2 2 6x = o 、工= 1 时，瓦值的特殊性 在切比雪夫多项式中，根据( 2 2 ) 式可知： 当x = o 时有： 删s ( 争 ( 2 9 ) 很明显，它的取值是l 、0 、一1 、o 的循环。 当工= l 时有： ( 1 ) = 1( 2 1 0 ) 由于在z = 0 、x = 1 时取值的特殊性使得它们容易被破解，因此在 加密过程中不选择这两个值作为密钥。 2 2 7 系数矩阵迭代特性 根据切比雪夫多项式的迭代定义式( 2 1 ) ，可以将瓦( x ) 的迭代计算转 化为系数矩阵的迭代计算，从而将其计算量减少为o ( 1 0 9 ：n ) 。 北京交通大学硕士论文切比雪夫多项式及其应用 舀冗，将迭1 弋足义阴1 弋毅彤瓦转化为矩阵彤式如p ： ( 划侄瓣嘴) 然后，代入初始值兀( x ) = 1 ，正( z ) = x ，并进行矩阵迭代计算可得： ( ! 。玎】_ c 3 = ( 搿 这种矩阵计算大大简化了切比雪夫多项式的计算过程，在后面数据 2 3 切比雪夫多项式在密码学上的应用 文献 8 】中详细讲述了利用了切比雪夫多项式的混沌特性和半群特 性来构造公钥加密算法和签名算法，具体如下： 2 3 1 密钥生成 假设a l i c e 要同b o b 进行通信，那么最开始b o b 要生成密钥并颁布他的 公钥，过程如下： 1 ) b o b 先选择一个大整数s 。 2 ) 再随机选择一个x 【一1 ，1 ，并计算t ( x ) 。 3 ) 得到公钥对为( x ，正( x ) ) ，私钥为j 。 2 3 2 消息加密 接着，a l i c e 将消息m 加密发送给b o b ，过程如下： 1 ) 获得b o b 的公钥( x ，r ( x ) ) 。 北京交通大学硕十论文切比雪夫多项式及其应用 2 ) 将消息表示成一个数字m 一1 ，1 】。 3 1 选择一个大整数r 。 4 ) 计算i ( x ) ，巧( x ) = i ( i ( x ) ) 和x = m 瓦( z ) 。 5 ) 发送密文c = ( t ( 工) ，工) 给b o b 。 2 3 3 消息解密 b o b 接收到发送的密文c 后，要将之转换成明文消息，需要做如下 工作： 1 ) 用自己的私钥s 来计算巧( x ) = t ( i ( x ) ) ，由半群特性可知它等于 咒( z ) 。 2 ) 计算明文消息m = 苦。 显然，b o b 解密得到的明文消息就是a l i c e 发送的消息。 2 4 切比雪夫多项式的破解 由于切比雪夫多项式自身所具有的一些特性，人们找到了它的一些 求逆算法，即在知道x 和瓦( x ) 的条件下相对快速简单地求出胛。其中， x 和l ( x ) 就是公钥加密体制中的公钥对，而疗则是私钥。 2 4 1 利用反函数破解 文献【8 分析了利用切比雪夫多项式的三角函数定义和半群特性来 进行破解。具体如下。 北京交通大学硕十论文切比雪夫多项式及其应用 假设a l i c e 同b o b 通信，( x ，l ( x ) ) 是b o b 的公钥。a l i c e 为了加密一条 消息m ，选择一个大整数r ，并计算i ( z ) ，( x ) = i ( i ( x ) ) 和 x = m - 瓦( x ) ，然后发送密文c = ( z ( x ) ，x ) 给b o b 。这时破解者可以通 过以下步骤破解出明文消息m ： 1 ) 破解者首先获得b o b 的公开密钥( x ，i ( x ) ) 。 2 ) 然后获得密文中的i ( x ) ，并计算出一个，使得t ( x ) = t ( x ) 。 3 ) 再求出i 。 ) = i ( i ( x ) ) 。 4 ) 最后计算出加密消息m = 瓦。 2 4 2 利用转换特性破解 文献 9 】中利用文中所提出的转换特性式( 2 8 ) ，将求解切比雪夫多项 式中h 的难题转化为求离散对数的难题，从而大大减少了计算量，缩短 了破解时间，方便了进一步破解。 已知公钥( x ，y ) ，y = 瓦( x ) 后，破解月的具体过程如下： 1 ) 令去( n 仃1 ) = x ，口l ( 扫j ) ，则口= x + 拓j 2 ) 又有瓦( x ) = l ( ( 口+ d 1 ) = 吾( 矿+ d 1 = y ； 3 ) 得到= y 万； 4 ) 已知口，矿，可通过求对数得到九。 这种方法的适用性极广，在下文中还将进一步讲述。 北京交通大学硕士论文切比雪夫多项式及其应用 2 4 3 利用共振特性破解 文献 1 1 】中提出了切比雪夫多项式的一种共振特性( r e s o n a n c e p m p e n i e s ) ，即可以通过切比雪夫多项式中某条曲线上的一点推出这条 曲线上所有的点，从而通过似然拟合出该曲线e ( z ) 。具体思路如下： 已知一个公开密钥( z ，y ) ( 切比雪夫多项式中某条曲线上的一点) ， y = i ( x ) ( s 是私钥) ，通过计算： t = l ) ，只= i ( t ) = e ( 1 ( x ) ) = l ( 互( x ) ) = z ( y ) i = 1 ，2 ，。 可以得到足够多的点( t ，m ) 。然后利用这些点来求出曲线瓦( x ) 。 不过由于该文只提出了利用曲线拟和来求得( 工) 中甩的算法，而没 有具体的实现和数据测试，因此这种方法的正确性和实用性还有待进一 步研究。 1 6 北京交通大学硕士论文有限域切比雪夫多项式 第三章有限域切比雪夫多项式 为了将切比雪夫多项式应用为公钥加密体系，将其扩展定义到有限 域。这样，第二章中破解方法所依据的切比雪夫多项式的一些特性消失 或改变，破解方法不再起作用，从而达到安全加密通信的目的。 3 1 有限域切比雪夫多项式的定义 由切比雪夫多项式的迭代定义式( 2 1 ) 可知，任意一个切比雪夫多项 式瓦( x ) 的定义域与值域的取值范围都在 一1 ，1 】的区间上。又由于切比雪 夫多项式可以表示为： t ( x ) = 4 。x ”+ q l x ”_ 1 + - + q x + ( 3 1 ) 所以，可知它是代数多项式。因此可以很容易的将切比雪夫多项式 定义域与值域扩展到实数域，即令x r ，有瓦( x ) ：r r 。在实数域上， 切比雪夫多项式的半群特性仍然成立。 既然切比雪夫多项式在实数域r 上符合半群特性，那么它在整数域 z 上也一定满足半群特性。下面，我们进一步把切比雪夫多项式的定义 域和值域扩展到有限域乙( 模p 生成) 上，其中p 为素数。则在有限域 乙上的切比雪夫多项式可定义如下： 令胛e z ，变量z 乙，多项式l ( x ) ：乙一乙的迭代关系定义为： l ( x ) ；( 2 x 瓦一1 ( x ) 一l 一2 ( x ) ) ( m o d p ) ，z 2 ( 3 2 ) 并有瓦( z ) = 1 ( m o d p ) ，正( x ) ；x ( m o d 尸) 。其中，z 尸为有限域，乙为 北京交通人学硕士论文有限域切比雪夫多项式 整数环，以下有关有限域上切比雪夫多项式的讨论计算都在z p 和乙上 进行。 根据式( 3 2 ) 可知，有限域z p 上的切比雪夫多项式表示如下： 瓦( x ) = 1 ( m o d p ) 正( x ) zx ( m o d p ) 正( x ) ；( 2 x 2 1 ) ( m o d p ) 正( x ) = ( 4 x 3 3 z ) ( m o d p ) l ( x ) 三( 8 x 4 8 x 。+ 1 ) ( m o d p ) 正( x ) ；( 1 6 z 一2 0 x 3 + 5 z ) ( m o d p ) 由于切比雪夫多项式的定义域和值域由原来的卜l ，l 】斗 一l ，l 】扩展到 乙_ + z 尸，因此【一1 ，1 】区间上定义的切比雪夫多项式三角函数形式的表达 式不再存在，从而文献 8 】中如第三章的2 1 所述的利用反三角函数进行 求逆运算，进而破解切比雪夫多项式的方法就不再可行。 又由式( 3 1 ) 可知，有限域切比雪夫多项式还可表示为： 瓦( x ) = ( q x ”+ q 卜l x 一+ 叶q x + ) ( m o dp ) ( 3 3 ) 由于现阶段还没有找到有限域切比雪夫多项式的反函数表达式，因 此，在( 3 3 ) 式中，已知z 和n 求( x ) 是比较容易的，而己知x 和瓦( x ) 要 求，z 却很困难。其求解的困难性可与求离散对数的困难问题类比。在( 3 3 ) 式的最高次幂n 与所求离散对数的最高次幂相同的情况下，由于( 3 3 ) 式 中各低次幂项的存在，如：z ”1 ，x ”2 等，求解( 3 3 ) 式中的最高次幂n 比 求解离散对数的n 更为困难和复杂。所以，( 3 3 ) 式在计算上有着良好的 单向性。因此，有限域切比雪夫多项式在计算上也有良好的单向性。 北京交通人学硕士论文有限域切比雪大多项式 3 2 有限域上切比雪夫多项式的特性 3 2 1 周期性 由于进行了模p 运算，因此在有限域乙中的切比雪夫多项式瓦( 工) 都具有周期p 。 3 2 2 模运算的内移特性 由于切比雪夫多项式是代数多项式，因此有如下关系式： t ( x ) ( m o d p ) = ( x ( m o d p ) ) ( m o d p )( 3 4 ) 3 2 3 半群特性 根据式( 3 4 ) ，可以推导出有限域上切比雪夫多项式的半群特性如下： l ( l ( x ) ( m o dp ) ) ( m o d 尸) = 乙( x ) ( m o dp ) = 乙( 瓦( x ) ( m o dp ) ) ( m o dp ) j 瓦( 瓦( x ) ) ( m o d 尸) = 乙( x ) ( m o d 尸) = 已暇 ) ) ( m o dp ) n ，搠z ( 3 5 ) 同样，有限域上切比雪夫多项式的半群特性也是其应用于密码学的 最重要的特性，是在基于其所构造的公钥加密体系中进行加、解密、数 字签名和密钥协商的基础。 3 2 4 奇偶对称性 在有限域上，切比雪夫多项式仍然具有奇偶对称性，只是此时的对 称轴不是x = 。，而是x = 丢( 尽管詈仨z 尸，但是我们可以虚构这样一条 对称轴) 。当”为偶数时，l ( x ) ( i n o d p ) 关于x ：昙偶对称，是偶函数； 北京交通大学硕士论文有限域切比雪夫多项式 当h 为奇数时，瓦( x ) ( m 。d p ) 关于x = 昙奇对称，是奇函数，即 瓦( 一x ) ( m o d 尸) = ( 一1 ) ”瓦( x ) ( m o d p ) ( 3 6 ) 3 2 5 转换特性 根据式( 2 8 ) ，可以得知有限域上切比雪夫多项式也存在转换特性， 表示如下： l ( 圭( 肘x _ 1 ) ) ( m 。d l p ) = 圭( x ”订顶m o d p ) ( 3 t 7 ) 则已知公钥( x ，y ) ，x ，y 乙，y = ( x ) 后，将切比雪夫多项式难题 转化为离散对数难题的过程如下： 1 ) 令昙( 口打) ：x ，a ( 五) iz ，则口= x + 扫j ； 2 ) 又有( x ) ；l 哇+ 口。) ) ( m o d p ) = 丢( 矿+ 日1 ) ( m o d p ) = y ； 3 ) 得至0 口“= y y 2 一l ； 4 、已知口，a “，可通过求对数得到n 。 从以上破解过程可知，在利用转换特性将求有限域切比雪夫多项式 i ( x ) 中n 的问题转化为求离散对数的问题时，必须满足( x 2 1 ) 是模p 的 平方剩余，即当g c d ( ( x 2 一1 ) ，p ) = 1 时，m 2 = ( x 2 1 ) ( m o d p ) 有解 ( m ，研2 z ，) 【1 ”。否则，就不能求出口，破解也就无从谈起。因此， 我们在选取密钥( x ，y ) 时，只要选择x 使得( x 2 1 ) 不是模p 的平方剩余， 就可以避免破解者利用转换特性将求解n 的复杂度简化。 北京交通大学硕士论文有限域切比雪夫多项式 3 2 6 捌、l 、p l 时取值的特殊性 由有限域上切比雪夫多项式的定义可知： 1 ) 当x = o 时，( o ) 的值是1 、0 、一1 、0 ( m o d p ) 的循环； 2 )当x = 1 时，( 1 ) = l ( m o d p ) ； 3 ) 当x = j p 一1 时，( p 1 ) 的值是1 ，p 一1 ( m o d p ) 的循环。 由于在x = 0 、x = 1 时取值的特殊性使得它们容易被破解，因此在 加密过程中不选择这三个点作为密钥。 3 2 7p 的取值特性 首先，用来进行模运算生成有限域z 。的尸必须是一个素数，这是因 为： ( 1 ) p 取素数可以保证有限域上切比雪夫多项式的周期为p 。由欧 拉定理可知，假如尸为合数的话，切比雪夫多项式的周期就可能小于p ， 为p 的一个约数。这样便使得周期性杂乱无章，不利于密钥的生成。 ( 2 ) p 取素数使得乙是一个域，每一个非零元素都有逆元，这就相 当于存在除法运算，且运算都是封闭的，这才使得解密算法的设计有了 可能；假如p 是合数，那么z 。是一个环，没有除法，即环内的非零元素 不一定有逆元，这就为解密算法的设计造成了很大的障碍。 其次，根据有限域上切比雪夫多项式的定义，很显然有： 驰细恤 ：；篓搿 尸取值的这些特性决定了在构建基于有限域上切比雪夫多项式的 北京交通大学硕士论文有限域切比雪夫多项式 公开密钥加密体系时，其取值为大于2 的素数。 3 2 8 咒的取值特性 根据有限域上切比雪夫多项式的定义和模计算所产生的周期性可 知，在选取密钥时，h 的值应为1 到尸一1 间的整数。这是因为当押取值 大于尸一1 时，瓦( z ) 会出现重复。如：当n = p 时，耳( x ) = 墨( x ) 。 3 2 9 矩阵计算特性 由于切比雪夫多项式是代数多项式，因此( 2 1 3 ) 式中的矩阵计算特性 在有限域上仍然成立，只需加上模运算即可，如下所示： r ( 弘雌 嬲 s ， 在具体的编程实现中我们将在每一次迭代运算后都取模，从而来进 一步减轻计算复杂度。 北京交通人学硕士论文 伪随机特性 第四章伪随机特性 将切比雪夫多项式的定义扩展到有限域后，它的 些特性有了改 变，从而避免了许多实数域切比雪夫多项式难以解决的缺陷口l ；除此之 外，它通过选取一定的密钥点，可以避免破解过程中数学难题的转化例。 但是，由于文献 1 1 中所提出的切比雪夫多项式上点的共振特性在 有限域中仍然存在，为了防i i 利用足够多的点拟合山切比雪夫多项式曲 线( z ) ，需要有限域上切比雪夫多项式还具有伪随机特性( 园为它是周 期的，所以不町能具有随机性) 。 4 1 伪随机序列的定义 4 1 1 伪随机序列定义和特性 伪随机序列是一种自相关的二进制序列，具有赵好的随机性和接近 于白噪声的相关函数，并且有预先的可确定性和可重复性，在一段周期 内其自相关中牛类似_ r 随机的二进制序列【l ”。尽管伪随机序列是确定的， 但是具有很多类似随机二进制序列的性质，具体如下： f 1 1 平衡特性，序列中0 和1 的数日最多相差1 个，概率几乎相等； f 2 ) 游程特性，长度为t 的游程约占整个序列长度的1 ，2 。，而且在 长度为t 的游程中，全为1 和个为。的游程数相同： ( 3 ) 相关特性，序列的自相关性很小，任意两个序列的互相天函数 也很小。当周期t 很长，码元宽度很小时，序列的自相关函数r ( r ) 近似 也很小。当周期t 很长，码元宽度很小时，序列的自相关函数r ( r ) 近似 北京交通大学硕十论文伪随机特性 为冲激函数d ( f ) 的形状，功率谱密度g ) 近似为白噪声的功率谱特性。 这三个特性也是伪随机序列成立的条件，序列只要满足这三个条件 就是伪随机的。 4 1 2 伪随机序列二值特性 伪随机序列还有一个特性就是它的自相关函数具有二值特性【1 5 】，定 义如下： 如果一个序列的自相关函数伪随机序列的自相关函数满足 脚) = = ) i f ，f u 其中，占是一个大于o 小于1 的定值。那么它就是伪随机的。 显然，利用这个特性来判定有限域上切比雪夫多项式的伪随机性要 比利用4 1 1 中的三个特性更加简单。 4 2 有限域切比雪夫多项式的自相关函数及其方差 由自相关函数的定义可知有限域乙上切比雪夫多项式的自相关函 数为： l ，一1 o ) = 亡( 瓦( x ) m o d p ) ( 瓦 + f ) m o d p ) ( 4 - 2 ) j r = o 由于这里切比雪夫多项式的值域不是 0 ，1 ，而是有限域乙，显然 其自相关函数值( f ) 是大于等于1 的。因此，为了便于对不同域( p 不 同) 所生成的有限域上的切比雪夫多项式白相关函数值的实验数据进行 比较分析，对( f ) 除以一个加权因子： 北京交通大学硕十论文伪随机特性 1 ，l 1 告( 瓦( z ) m o d p ) 2 g ) 占( f ) ( 4 3 ) j j = 0 对其进行归一化，得到其归一化自相关函数： p l 。 ( l ( x ) m o d p ) ( + f ) i n o d p ) b ( f ) = 5 = l 面一 ( 4 4 ) ( 五( x ) m o d p ) 2 j = o 显然，通过