有限域上多项式及其在公钥密码体制中应用

1、摘要内容摘要：公钥密码体制的思想是在年由和提出的，它自诞生之日起就引起了广泛的关注，并在实际中得到了广泛应用。人们对这一体制在不同范畴进行了各种模拟。本文基于有限域上多项式的性质，给出了有限域上多项式形式的一种新型体制和体制，这种的新模拟，其安全性能更高。本文首先讨论了有限域上多项式的因式分解问题，给出了有限域上不可约多项式和本原多项式的个数、本原多项式的判定等定理，并且给出了利用低次不可约多项式构造高次不可约多项式的方法，对有限域上多项式的性质进行了深入的研究与探讨。其次，基于有限域上多项式的性质，本文给出了有限域上多项式形式的一种新型体制，这种新体制是在孙琦、曹珍富和张斌等人的新模拟基础上

2、提出的，它具有更高的安全性，并且同样解决了曹珍富模拟中存在的密文扩展问题，其安全性主要基于大整数的分解。最后给出了有限域上多项式形式的一种新体制。关键词：公钥密码体制，有限域上的多项式，体制，体制。： ， ， ， ， ， ， ， ， ， 一有限域上的多项式及其在公钥密码体制中的应用： ， ， 学位论文独创性声明本人承诺：所呈交的学位论文是本人在导师指导下所取得的研究成果。论文中除特别加以标注和致谢的地方外，不包含其他人和其他机构已经撰写或发表过的研究成果，其他同志的研究成果对本人的启示和所提供的帮助，均已在论文中做出了明确的声明并表示谢意。学位论文作者签名：日期：硼占歹学位论文版权使用授权书本

3、学位论文作者完全了解辽宁师范大学有关保留、使用学位论文的规定，及学校有权保留并向国家有关部门或机构送交复印件和磁盘，允许论文被查阅和借阅。本人授权辽宁师范大学，可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段保存、汇编学位论文。学位论文作者签名：舀赢保密的论文在解密后使用本授权书。指导教师签名：日期：珈弓有限域上的多项式及其在公钥密码体制中的应用有限域上的多项式及其在公钥密码体制中的应用引言近二十年来，信息安全已越来越被看作一种基本的需求，安全电子邮件、电子商务、电子政务等各项安全服务日趋增多，随着因特网的普及和通信技术的飞速发展，人们对安全的需求越来越高

4、，信息安全和保密通信逐渐成为与人们的生活息息相关的问题。公钥密码体制作为信息安全保障框架的基石与技术支撑成为当前信息技术领域中最活跃的因素，人们对这一体制在不同范畴进行了各种模拟，得到了不少有意义的结果。文献【，给出了有限域上多项式的定义以及一些基本性质定理。文献【】提供了与不可约多项式个数以及与利用低次不可约多项式构造高次不可约多项式密切相关的一些定义和性质定理。文献【】，【】给出了有限域上三项多项式不可约问题的一些相关定理。文献【】提供了有限域上本原多项式个数的相关定理。在文献中，孙琦提出了有限域上多项式形式的体制。曹珍富在文献【】中指出了孙琦方案中所存在的安全问题，并提出了一种的新模拟，

5、这种新模拟的安全性较高，一次可以加密多个明文，但密文存在扩展。张斌等人在文献中解决了存在的密文扩展问题，得到了较好的的模拟。张青坡等人在文献】中提出了有限域上多项式形式的公钥体制，他们的这些工作，无疑是对现代密码学的新贡献。受到这些方案的启发，本文首先讨论了有限域上多项式的一些性质，基于有限域上多项式的性质，本文给出了有限域上多项式形式的一种新型髓体制和体制，这种新体制是在孙琦、曹珍富和张斌等人的新模拟基础上提出的，它具有更高的安全性，并且同样解决了曹珍富模拟中存在的密文扩展问题，其安全性主要基于大整数的分解。本论文结构如下：第二部分提供了有限域上多项式的一些基本性质定理，讨论了有限域上不可约

6、多项式和本原多项式的个数、本原多项式的判定等定理，并且给出了利用低次不可约多项式构造高次不可约多项式的方法，对有限域上多项式的性质进行了深入的研究与探讨；第三部分利用有限域上多项式的性质，给出了有限域上多项式形式的一种新型体制：第四部分给出了有限域上多项式形式的一种新型体制。有限域上的多项式及其在公钥密码体制中的应用有限域上的多项式有限域上多项式的因式分解一般多项式的分解分解上的多项式，（）第一步：计算夕以（，（），），且设（）（），（）。（）如果（）；，则，知）是一个没有重因子的多项式；（）如果（），），则一定有，（），这时存在（）日，使得（）（），其中是的特征，如果这时夕（）还不是一个没有

7、重因子的多项式，我们可对夕（）继续进行简化；（）如果）（），（），那么）一定是，（）的一个非平凡因子，且（）（）不包含重因子，这样分解，（）的问题就转化成了分解（）和没有重因子的（）（）的问题。在（）仍具有重因子的情况下，我们可以重复上面的化简过程。这样就把一般多项式的分解问题转化成了没有重因子的多项式的分解问题。以后我们假定，（）是无重因子的佗次多项式。第二步：计算），一。第三步：构造礼矩阵（），一，其中口巧由同余方程三“舢口一叼， 佗一 确定。第四步：计算（一厶）的秩，多项式，（）可分解成个不同的不可约多项式的乘积。第五步：（）若七，则，（）是一个不可约多项式，分解程序终止；（）若，找出（

8、，一）（一厶）的解空间的一组基（），（），（）取（），它总是方程舻）三（）（），（）的解，令（），用欧几里得算法计算（，（），（）一），日，则，一御吼，九有限域上的多项式及其在公钥密码体制中的应用如果还得不到，（）的所有个不可约因子，对新得到的因子进一步使用上述过程，不过这次要使用，一约化多项式九（），依次类推，上述过程最终一定会得到，（）的完全分解。护一型、型及割圆多项式。（）的分解定义【】令是特征为的域，扎是一个不能被整除的正整数，为上的一个次本原单位根，则多项式（）割圆多项式。一）称为上的次定理【】系数取自（口）上的多项式矿”一兀（）（），这里（）是（口）上所有次首一既约多项式之积，主反

9、演公式又有（）（一一）咖佃（俨）艄（）这里（）是函数。定理】设是一特征为的域，为正整数， ，则矿一吼（）（）扫反演公式，对所有佗有（）（一）小阍（矿一）艄（）定理】如果，则。可分解成【中（）个不同的次首一不可约多项式的乘积【（）：吲，这里是满足三的最小正整数。定义令集合巩【，），如果存在使得三（），我们就说中两元素和是等价的，此等价关系可把分成两两不相交的等价类，把每个等价类称为模他的一个口一轮换。这样：（）对矿一型，可利用公式（）将矿一化为锄（）之积，或者按如下方法分解：第一步：将以，佗一分解成模的轮换：第二步：若（，）是模的任意一个轮换，则令（）口一有限域上的多项式及其在公钥密码体制中的应

10、用则每个模的轮换对应一个多项式九（），于是我们得（，口）的一组基（），（），（）显然（）三（）（）；第三步：应用中第五步，可得一的完全分解。（）对一型，可利用公式（）先化为（）之积，再利用公式（）和公式（）化为七（）之积。（）对于（），可利用定理确定其既约因式的个数及次数，然后利用待定系数法求分解式，或利用一般多项式的分解方法进行分解。有限域上的不可约多项式有限域上不可约多项式个数引理【】设最是日上次数为的不可约多项式且，（），贝（，）等（）在乘法群昂。中任意根的阶。定理【】设是的所有因子中不等于凡本身的最大因子，如果（，口），一，是使得矿一成立的最小正整数。证明：设是满足矿一的最小正整数，由

11、于一。若，因为是的所有因子中不等于本身的最大因子，所以，从而扫。一知口一一，这与口一矛盾。，即佗是满足口矿一的最小正整数。定理【】如果且是模的乘法阶，那么日中次数为阶为的首一不可约多项式的个数为（）；如果，则个数为；在其他情形下，个数为。特别地，阶数为的不可约多项式的次数一定等于模的乘法阶。证明：设，）是中的不可约多项式且，（），则根据引理我们有（）甘，（）的所有根为上的阶本原单位根，且（）营，（）。（），又由定理 。的任一首一不可约因子都是次的，其中是满足口三的最小正整数，而且所有这样的因子共有（）个。对的情况，须把，）算进去，共有（）个。推论】设，为正整数，若，则不存在疋上以一为周期的次不

12、可约多项式。推论【】设，是正整数，（，），是佗的所有因子中不等于的最大因子，若且一，则上以为周期的扎次不可约多项式存在且这样的不可约多项式的个数等于（）。有限域上的多项式及其在公钥密码体制中的应用证明：由于（，口），是的所有因子中不等于的最大因子，若：且一，则根据引理知礼是使得矿一成立的最小正整数，再根据定理便得到结论。定理【】上佗次首一不可约多项式的个数（礼）为：（）熹（三）击（）口 证明：在反演公式的加法情形中，取，并令危（）扎（），（）。则、 因此死。（）（三）口（） 从而定理得证。利用低次不可约多项式构造高次不可约多项式定义【】设，（）为（口）上的次多项式，令：称）为，）的线性相联多项

13、式。引理【】设，）为（）上的不可约多项式，（）为其线性相联多项式，令（）（）肛，则夕（）的任一不可约因式的次数均为厂（）的周期（）。定理设，（）为（）上的扎次本原多项式，）为（）消去因式后所得的多项式，即夕（）（），那么夕（）为（口）上的旷一次不可约多项式。证明：由本原多项式的定义知，（）的周期（）一，再由引理知（）的所有不可约因式的次数均为（）一，而夕（）本身的次数就是一，所以（）除了常数和（）外，没有其他因式，这里（），故夕（）不可约。此方法所产生的不可约多项式或本原多项式的次数是随着原本原多项式的次数成指数增长的，因此随着原本原多项式次数的增加，所构造的不可约多项日）矿一、矿有限域上的多

14、项式及其在公钥密码体制中的应用式的个数分布也越来越稀疏，所以从应用的方面来讲，这些不可约多项式的次数受到了严格限制，这是此构造方法的一个弱点，下面介绍更为一般的方法：引理】设，且，是互素的整数，是模的乘法阶，设是的整数且它的素因子整除但不整除（一）。若三，假设仇三，则模的乘法阶为。定理【】设，（）为中次数为阶为的首一不可约多项式，且设是大于等于的整数，它的素因子整除但不整除（俨一）。若亡三，设兰，则，（）是日中次数为亡阶为的首一不可约多项式。证明：所满足的条件意味着，由引理知，（）的根是只上的次本原单位根。（）。（）（。）。（），又。（）。（）（）矗（）。由定理知。（）在日】中每个不可约因子的

15、次数都等于模的乘法阶，由引理知模的乘法阶等于，又（。）的次数为亡，（）在【】中不可约，此外，（），（）的阶为耐。定理【】如果，（）是日上的一个次不可约多项式，设最，（），日，那么（）也是上的一个佗次不可约多项式。证明：若（）上的一个佗次可约多项式，则存在（）日，（）日使得（）夕（）危（），其中（）几，（），因为扇，（），日，所以存在日，一分别使得，（）。令（一），则（）（一可（一）（一可（一）九（一可（一）这与，）是日上的不可约多项式矛盾，所（）是上的一个几次不可约多项式。注：先通过定理得到一些高次不可约多项式，然后再利用定理的结论可得到另外一些高次不可约多项式，甚至是本原多项式。三项多项式不

16、可约问题理】劭为素数，（），可约多项式，则，（），一营。（）昂阁为一个（）次不定理设是素数，昂）， ，礼是任意正整数，令（）一士，则（）当时，（）不可约当且仅当扎；（）当时，）不可约当且仅当佗且。证明：设是，（）的一个根，则矿“千，于是矿“（矿“）矿（卢千口）矿：千：千口，有限域上的多项式及其在公钥密码体制中的应用矿“（矿”）一（千）矿矿”：千易见，上述过程施行下去，必有矿卢，即是上的多项式一的一个根，于是，（），一。由引理得矿， 。因此，当时，必有礼或，且显然；当时，只能是。反之，当时，不难验证，够均不可约，而当，时，由前面证明可见扩一士一，但由引理易见，一的不可约因式或是一次式或是次多项式

17、，但当时护士口无一次因式，因此矿一士不可约，定理得证。定理设且晶的特征为，则三项多项式护一在吲中不可约甘它在中无根。证明：若是妒一士。在某扩域中的根，而护一的根的集合是，其中是线性多项式矿一的根的集合，但，矿一 兀一一），假设矿一 有因子（）】，（）（）首一，则夕（）（一卢一良）对某昂成立，比较矿的系数可知是日的元素，在日中有乘法逆，这样我们可证若矿一在日中有非平凡因子，则它在日中有根，反之亦然。推论对。，三项多项式在吲中不可约甘妒一士在日中无根。证明：对蜀，（）在上不可约铮（）在上不可约。以厶记集合厶，（，），当为奇数时，在如中的阶即是指使得兰成立的最小正整数。引理定理【】却为奇素数，砚为在

18、易中的阶，若，则，）设为奇素数，妒）为妒的不可约因式，妒）。若在山中的阶不等于在如中的阶，则妒（矿）为的不可约因式（）。证明：已知的不可约因式的个数等于数集，一）所分成的的轮换的个数，且的每个次不可约因式与一个长度为的的轮换相对应，今设护的完全的因式分解为妒（）妒（）忱）协（），则妒），妒（），阱（）的次数均等于在易中的阶数，而（一）。今考察，（，）（，）妒（，）（，）怫（，），有限域上的多项式及其在公钥密码体制中的应用为计算矿的不可约因式的个数，考察，矿）勘个数所分成的的轮换，其中，）这矿个数自成一组，它们与矿的因式护“相对应，他们所分成的“的轮换的个数就是，的不可约因式的个数，而剩下的集合

19、，矿，一）乃与护叶的因式妒（矿”）妒（俨）妒，（矿）相对应，由于中各数均与互质，故所分成的各个的轮换的长度均相同，设此长度为，则就是在加。中的阶数，由于满足引理所述条件，故矿，于是数集所能分出的的轮换的个数为鱼二！鲨：鱼二竺：型：这就是说：妒（）妒（）怫（，）的不可约因式个数为，因而妒（）不可约。在此定理中要求：在五。中的阶不等于在咖中的阶，这就产生了一个问题，究竟什么样的奇素鳓具有此性质呢？现已知道，若且，则具有此性质；对于大于的素数，此问题不清楚。推论对某个非负整数，一，则三项多项式仇号在足上不可约。证明：为奇素数，为的不可约因式，且在如中的阶不等于在以中的阶，由定理得铲扩不可约，令一，一

20、即可。同理可得如下不可约三项式在足上不可约：护妒（）一：护妒：护妒（）“护”护：尹”：”严；“有限域上的本原多项式本原多项式个数定理【】设局（）表示（口）上次数为的首一本原多项式的个数，一一一少 。有限域上的多项式及其在公钥密码体制中的应用则马（）去（矿一），其中（）是欧拉函数。定理对（）， ）表示（）上次数为迹为的首一本原多项式的个数，则除只（）（）；， ）是正的。定理【】若口（），则局 ）是的倍数，其中是扩域（）（）在（）上的次数。证明：（矿）为本原元素，则口百丁是（）的本原元素，对，（俨），存在唯一的，一满足，若的极小多项式（，（）次数为，则（，（）（一，）一口）一，旷），且它所有根的集

21、合是，俨，。），幻，）称（酽，（）的次数为在（）上的次数，记为夕（，（）。对每个孙一，（，（）是的因子，记（一）为孙一中与一素的所有元素的集合。若（）。是本原的，则对任意正整数，矿是（口）的本原元素，且打（）（打（）。所以若（）。是本原元素，则对每个，一，矿（俨）同样是本原的。而且若打（），则打（矿。）打（）对每个移，一成立。（矿，（）一矿矿）脚一矿）对每个，一成立，（）恰有个与对应的本原多项式，此外，若是）上不与共轭的本原元素，则对，矿，这样（。，（）（，）， （）。定理【若，（）在（）上共轭，则，（）。：（）。证明：设口，口（）在（）共轭，则存在（）的同构盯满足盯（）口。设为盯在（）中的任

22、一扩张，（），（，）为（仇）中迹为的本原元素的集合，对每个元素玩（，），易知（）（打（）（）口这意味着丁把（，）映到（，），事实上，因为（，），（）（，），它是到上的， （。，）（，），这样岛（）岛口：（）。有限域上的多项式及其在公钥密码体制中的应用本原多项式判定定理定义设夕（）昂【】为佗次不可约多项式，如果夕（）（一），（）（一）。，则称夕）为佗次本原多项式。定理设（）昂陋】为佗次（）首一多项式，为素数，其中，则）为佗次本原多项式的充要条件为：（）（一），矿一，夕（）（一），对任意的素数因子成立。证明：充分性：由条件知夕（）为不可约多项式，又夕）（一），如果存在，使（）（），则夕（）甜（一，

23、矿一），故夕）（一），（，），故一三（），设的素数因子为，也为的素数因子，所以（一）三（）与（）（一一）矛盾，故夕（）（矿一），矿一，即夕（）为佗次本原多项式。必要性：夕（）为次本原多项式故必不可约，故（）（一），本原性定义中令得证，证毕。定理设夕）为次（）首一多项式，口，为素数，允许，则夕（）为次本原多项式的充要条件是（）（）（）均成立，其中（）（），昂；（）夕（）（一），夕（）（），夕（）（），矿一，矿，；（）对任意的素数因子，夕（）（一）。证明：必要性显然：充分性：先设，不妨设，由（）知夕（）无次不可约多项式作因式，当夕（）（一）时，如果夕（）可约则其不可约因式次数只能为，口，设七幻夕（

24、）鼠。（）鼠。（），（吼。）（：），故（）乜 兮口尼，；七令兮，；号乜口号 ，乜如果夕（）：向鼠，），吼。扛）互不相同而次数均为口，鼠。（）为咿式，故（）也为一之因式，即夕（）（一），与（）矛盾，其余情况类似。有限域上的多项式及其在公钥密码体制中的应用夕）不可约，（）（一），由定理可知夕（）为次本原多项式。当时是上述情况特例，类似可证。推论设夕）为马上次首一多项式，为梅森素数，即一为素数，则夕（）为礼次本原多项式的充要条件为夕（），（），（）（一）。有限域上的多项式及其在公钥密码体制中的应用有限域上多项式形式的体制预备知识设为素数，耳为元有限域，昂为耳的乘法群，昂【】为易上的多项式环。定义【】

25、设，（），定义（厂）为模，（）的一组完全剩余系中与，（）互素的多项式的个数。定义【】设亿是一个正整数，是一个素数，将一，昂，（，一）简记为佗【，咖】，称之为的形式，称为其长度。定理设昂为日上的多项式环，夕（）昂】是一个次多项式，且在昂中夕）可分解为夕（）夕（）（）乳），其中毛，吼（）一尼）是上的次不可约多项式，记七（夕（）【（杪），（）昂，只要（）次数大于。且夕），夕），就有（）唧（王）兰（）。定理【】设昂【】为昂上的多项式环，夕）昂陋】是一个次多项式且在昂【】中夕（）可分解为夕（）夕（）夕（）矶（），吼（）一七）是【】上的；次不可约多项式，记七（夕（）矿（伊），唧（），（，饰（夕（），满足三

26、（唧（夕（），则（）昂，只要其次数大于，就有乱（）甜三（）（）。定理的详细证明可参阅文献【】。一个的新模拟（）选取个互不相同的素数，（保密），轨（公开）；（）选取整系数环上的一个首项系数是的次多项式夕（）（公开），使得在昂。上有分解式（）（）夕（）巩。（），这里夕（）（）是昂。上互不相同的（）次不可约多项式（一）；在如上有分解式（）（）（）吼：（），一有限域上的多项式及其在公钥密码体制中的应用这里吼（）是如上互不相同的（）次不可约多项式（一乜）在翰上有分解式（）（）现（。（）（。（），这里吼（。）是如上的（）次不可约多项式，（一）。记妒，（夕（）。（夕（）妒耽（夕（）妒玩（夕（）：（，）（一肛

27、（保密）；（）随机选取（加密密钥，公开），使圆（），（，怫（），一：（）用眈算法求出，田，满足兰（，（夕（），怫（夕（），其中是私人密钥（保密）；于是明文空间与密文空间都是历仇。，。（夕），（夕）保密，夕（）】作公钥，【，怫（夕（）作私钥。加密算法：设明文（口仇一，一，）历仇。计算（一 一一 一口）。） 一一 一，这里，（）（）表示多项式，（）模夕（）的余式，其系数模，于是（一，仇一，）作为密文。解密算法：已知（一，一，） ，计算（一 一，一 一）扣）口一 一口一 一口，恢复明文（一，一，）磊。定理改进后的加密算法是单射。证明：设在磊【叫中有（一一仇一价一）（）（仇一一口一一）。（），有限域上

28、的多项式及其在公钥密码体制中的应用则有（一一知）三（二一二一：）。（）于是在磊【】中有（仇一口仇一一知）三（：，一一二一：）（）。三（ （夕（），怫（夕（），并且怫（）是妒，。（夕（），妒玩（夕（）的乘积，所以兰（。（夕（）；三（唧。（夕（）由定理在昂。陋】中有（一一一）三（一一一一）兰一 一一 一（），（二一一：一士一口：）兰（口二一一厶一一蠢）兰二一。一口二一，。晶。（），这里是模的余数，是模的余数。在昂。中有一一一三：一。仇一二一。口：（），但是夕）是一个首项系数是的次多项式，所以咖，一有三西（如）。同理，对，；，一，有三）（鼽）。这说明与都满足同余方程组三 吩三 （ ）一 一一，、兰 吩兰 町。（ ）由孙子定理可知三（轨），即三 吩（），所以（仇一，一，）（口一，一，口）磊所以加密算法是单射的。有限域上的多项式及其在公钥密码体