rsa算法中的代数结构

《rsa算法中的代数结构》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第１期电子学报Ｖｏｌ．３９Ｎｏ．１２０１１年１月ＡＣＴＡＥＬＥＣＴＲＯＮＩＣＡＳＩＮＩＣＡＪａｎ．２０１１ＲＳＡ算法中的代数结构司光东，杨加喜，谭示崇，肖国镇（西安电子科技大学ＩＳＮ综合业务网国家重点实验室，陕西西安７１００７１）摘要：本文首次应用二次剩余理论对ＲＳＡ中的代数结构进行了研究．计算出了Ｚｎ中模ｎ的二次剩余和二次非剩余的个数，对它们之间的关系进行了分析，并用所有二次剩余构成的群对Ｚｎ进行了分割，证明了所有陪集构成的商群是一个Ｋｌｅｉｎ四元群．对强ＲＳＡ的结构进行了研究，证明了强Ｒ

2、ＳＡ中存在阶为（ｎ）／２的元素，并且强ＲＳＡ中Ｚｎ可由三个二次非剩余的元素生成．确定了Ｚｎ中任意元素的阶，证明了Ｚｎ中所有元素阶的最大值是ｌｃｍ（ｐ－１，ｑ－１），并且给出了如何寻找Ｚｎ中最大阶元素方法．从而解决了ＲＳＡ中的代数结构．关键词：ＲＳＡ算法；代数结构；二次剩余；欧拉函数中图分类号：ＴＮ９１８．１文献标识码：Ａ文章编号：０３７２２１１２（２０１１）０１０２４２０５ＡｌｇｅｂｒａＳｔｒｕｃｔｕｒｅｏｆＲＳＡＡｒｉｔｈｍｅｔｉｃＳＩＧｕａｎｇｄｏｎｇ，ＹＡＮＧＪｉａｘｉ

3、，ＴＡＮＳｈｉｃｈｏｎｇ，ＸＩＡＯＧｕｏｚｈｅｎ（ＳｔａｔｅＫｅｙＬａｂｏｒａｔｏｒｙｏｆＩｎｔｅｇｒａｔｅｄＳｅｒｖｉｃｅＮｅｔｗｏｒｋ，ＸｉｄｉａｎＵｎｉｖｅｒｓｉｔｙ，Ｘｉ’ａｎ，Ｓｈａａｎｘｉ７１００７１，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ｂａｓｅｄｏｎｔｈｅｔｈｅｏｒｙｏｆｑｕａｄｒａｔｉｃｒｅｓｉｄｕｅｓ，ｔｈｅａｌｇｅｂｒａｓｔｒｕｃｔｕｒｅｏｆＲＳＡａｒｉｔｈｍｅｔｉｃｉｓｒｅｓｅａｒｃｈｅｄｉｎｔｈｉｓｐａｐｅｒ．Ｔｈｉｓｗｏｒｋｃａｌｃｕｌａｔｅｓｎｕｍｂｅｒｓｏｆｑｕａｄｒ

4、ａｔｉｃｒｅｓｉｄｕｅｓａｎｄｎｏｎｒｅｓｉｄｕｅｓｉｎｔｈｅｇｒｏｕｐＺｎａｎｄｉｎｖｅｓｔｉｇａｔｅｓｔｈｅｉｒｒｅｌａｔｉｏｎｓｈｉｐ．ＺｎｉｓｄｉｖｉｄｅｄｕｐｂｙｔｈｅｇｒｏｕｐｍａｄｅｕｐｗｉｔｈａｌｌｑｕａｄｒａｔｉｃｒｅｓｉｄｕｅｓｉｎＺｎａｎｄａｌｌｃｏｓｅｔｓｆｏｒｍａｑｕｏｔｉｅｎｔｇｒｏｕｐｏｆｏｒｄｅｒ４ｗｈｉｃｈｉｓａＫｌｅｉｎｇｒｏｕｐ．ＳｔｕｄｙｅｄｔｈｅｓｔｒｕｃｔｕｒｅｏｆｓｔｒｏｎｇＲＳＡｆｕｒｔｈｅｒ，ｉｔｓｈｏｗｓｔｈａｔｔｈｅｅｌｅｍｅｎｔｏｆ

5、ｏｒｄｅｒ（ｎ）／２ｅｘｉｓｔｓａｎｄｔｈｅｇｒｏｕｐＺｎｃａｎｂｅｇｅｎｅｒａｔｅｄｂｙｔｈｒｅｅｅｌｅｍｅｎｔｓｏｆｑｕａｄｒａｔｉｃｎｏｎｒｅｓｉｄｕｅｓ．Ｌｅｔｔｈｅｆａｃｔｅｒｉｚａｔｉｏｎｎ＝ｐ·ｑ，ｔｈｅｏｒｄｅｒｏｆｅａｃｈｅｌｅｍｅｎｔｃａｎｂｅｃａｌｃｕｌａｔｅｄ，ａｎｄｔｈｅｂｉｇｇｅｓｔｏｒｄｅｒｏｆａｌｌｅｌｅｍｅｎｔｉｓｌｃｍ（ｐ－１，ｑ－１）ｉｎＺｎ．Ｉｔａｌｓｏｓｈｏｗｓｈｏｗｔｏｆｉｎｄｔｈｅｅｌｅｍｅｎｔｏｆｔｈｅｂｉｇｇｅｓｔｏｒｄｅｒ．Ｓｏｔｈｅａ

6、ｌｇｅｂｒａｓｔｒｕｃｔｕｒｅｏｆＲＳＡａｒｉｔｈｍｅｔｉｃｉｓｓｏｌｖｅｄ．Ｋｅｙｗｏｒｄｓ：ＲＳＡａｒｉｔｈｍｅｔｉｃ；ａｌｇｅｂｒａｓｔｒｕｃｔｕｒｅ；ｑｕａｄｒａｔｉｃｒｅｓｉｄｕｅｓ；ｅｕｌｅｒ’ｓｐｈｉｆｕｎｃｔｉｏｎ［２］法，称为ＲＳＡ算法．这种算法既可以用于加密，又可１引言［３，４］以用作数字签名，并可构造其它的签名方案，是目自从１９７６年ＷＤｉｆｆｉｅ和ＭＨｅｌｌｍａｎ提出公钥密码体前最能被人们接受也是最被广泛使用的算法．国际上一［１］制以来，以数学为基础的非对称加密算法取得了

7、突破些标准化组织ＩＳＯ，ＩＴＵ，ＳＷＩＦＴ等都已接受ＲＳＡ体制作性进展．这一体制的最大特点就是采用两个密钥将加密为标准．在Ｉｎｔｅｒｎｅｔ中，电子邮件是最常用的一种网络服与解密能力分开，公开的密钥作为加密密钥，保密的密务，广泛采用的ＰＧＰ（ＰｒｅｔｔｙＧｏｏｄＰｒｉｖａｃｙ）技术就是用ＲＳＡ钥作为解密密钥，实现了通信双方无需事先交换密钥就算法作为传送会话密钥和数字签名的标准算法来保证可以进行保密通信．这些算法都是基于某个数学上的困电子邮件中的机密性和身份认证．难问题，在有限的计算资源和有限的储存

8、空间下要从公在ＲＳＡ算法中，ｎ＝ｐ·ｑ，其中ｐ，ｑ是长度约为５１２开的密钥或密文中分析出私有密钥是不可行的．如果把比特的大素数．其困难性基于：知道两个大素数ｐ，ｑ，容私有密钥作为加密密钥而把公开密钥作为解密密钥，就易计算ｎ＝ｐ，ｑ．反之仅知道ｎ，分解ｎ＝ｐ，ｑ在计算上可实现由一个用户加密的消息使多个用户解读，从而实是不可行的．ＤＢｏｎｅｈ证明了ＲＳＡ算法中私有密钥长度现了代替手写签名的数字签名．公钥密码体制的提出为小于ｎ０．２９２时方案容易被攻破［５］，并对２０年中ＲＳＡ算法解决计算机信息网络中