第９卷第２期浙江工商职业技术学院学报Ｖｏｌ。９Ｎｏ．２２０１０年６月ＪｏｕｒｎａｌｏｆＺｈｅｊｉａｎｇＢｕｓｉｎｅｓｓＴｅｃｈｎｏｌｏｇｙＩｎｓｔｉｔｕｔｅＪｕｎ．２０１０公开密钥算法ＲＳＡ策略及程序实现毛建儿（余姚四职校，浙江宁波３１５４７０）摘要：随着通信的飞速发展，信息安全显得越来越重要，计算机密码的基本思想就是将要保护的信息变成伪装信息，在公开密钥算法提出之前，所有密码系统的解密密钥和加密密钥彼此有着直接的联系。这也是秘密密钥的缺陷所在。为此公开密钥算法ＲＳＡ算法就顺应而生。这种叫加密算法可用ＶＢ程序编程实现。关键词：密钥弱点；公开密钥；策略；程序中图分类号：ＴＰ３０９．７文献标志码：Ａ文章编号：１６７１－９５６５（２０１０）０２－０３６－０３ＲＳＡＰｕｂｌｉｃＫｅｙＡｇｏｒｉｔｈｍａｎｄＰｒｏｃｅｓｓＲｅａｌｉｚａｔｉｏｎＭＡ０Ｊｉａｎ—ｅｒ（ＴｈｅＦｏｕｒｔｈＹｕｙａｏＰｒｏｆｅｓｓｉｏｎａｌｓｃｈｏｏｌ，Ｍ，１９６０３１５４７０，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ｓａｆｅｔｙｏｆｉｎｆｏｒｍａｔｉｏｎｉｓｇｅｔｔｉｎｇｍｏｒｅａｎｄｍｏｒｅｉｍｐｏｒｔａｎｔｗｉｔｌｌｔｈｅｒａｐｉｄｄｅｖｅｌｏｐｍｅｎｔｏｆｔｅｌｅ—ｃｏｍｍｕｎｉｃａｔｉｏｎｓ．Ｔｈｅｅｓｓｅｎｔｉａｌｉｄｅａｏｆｔｈｅｃｏｄｅｓｙｓｔｅｍｏｆｃｏｍｐｕｔｅｒｓｉｓｔｏｃｈａｎｇｅｔｈｅｉｎｆｏｒｍａｔｉｏｎｔｏｂｅｐｒｏｔｅｃｔｅｄｉｎｔｏｃａｍｏｕｆｌａｇｅｄｉｎｆｏｒｍａｔｉｏｎ．ＢｅｆｏｒｅｐｕｂｌｉｃｋｅｙａｌｇｏｒｉｔｈｍｃａｎｌｅｉｎｔｏｂｅｉＩｌｇ，ｔｈｅｄｅｃｒｙｐｔｉｏｎａｎｄｅｎｃｒｙｐｆｉｏｎｏｆａｌｌｔｈｅｃｏｄｉｎｇｓｙｓｔｅｍｓａｒｅｉｎｔｅｒｒｅｌａｔｅｄ，ｗｈｉｃｈｉｓｉｔｓｄｅｆｉｃｉｅｎｃｙ．Ｔｏｓｏｌｖｅｔｈｅｐｒｏｂｌｅｍ，ＲＳＡＲｉｖｅｓｔ－Ｓｈａｍｉｒ－Ａｄｌｅｍａｎｐｕｂｌｉｃｋｅｙａｌｇｏｒｉｔｈｍｃａｌｎｅａ１０ｎｇ，ｗｈｉｃｈｃａｌｌｂｅｒｅａｌｉｚｅｄｗｉｔｈＶＢｐｒｏｃｅｓｓ．Ｋｅｙｗｏｒｄｓ：ｄｅｆｉｃｉｅｎｃｙｏｆｐｕｂｌｉｃｋｅｙａｌｇｏｒｉｔｈｍ；ｐｕｂｌｉｃｋｅｙａｌｇｏｒｉｔｈｍ；ｓｔｒａｔｅｇｙ；ｐｒｏｃｅｓｓ随着通信的飞速发展，信息安全显得越来越重要，计首先满足Ｍ＜ｎ，计算其对应密文为：Ｃ＝Ｍｅ（ｍｏｄｎ）；若对Ｃ解密，计算Ｍ＝Ｃｄ（ｍｏｄｎ）。加密参数为ｅ和ｎ，此为公开密钥（ｅ，ｎ）；解密参数为ｄ和ｎ，此为私人密钥（ｄ，ｎ）。举例来说，假设取ｐ＝３，ｑ＝１１，则计算ｎ＝３３，ｚ＝２０。由于３和２０没有公因子，因此取ｄ＝３，解方程３・ｅ＝１（ｒｏｏｄ２０），得到ｅ＝７。的加密思想——公开密钥算法ＲＳＡ算法。因此公开密钥为（７，３３），私人密钥为（３，３３）。假设加密明公开密钥算法的思路与加密密钥和解密密钥不同，加文Ｍ：４，则计算密文Ｃ＝Ｍｅ（ｍｏｄｎ）－－４７（ｍｏｄ３３）＝１６；若要对收到密文进行解密，计算明文方法：Ｍ＝Ｃｄ（ｍｏｄｎ）＝１６３（ｍｏｄ３３）－－４，恢复出原文。根据ＲＳＡ算法，可以对以下几个环节进行具体分析。首先是选择素数ｐ，ｑ。理论上应选择两个大素数（典型值大于１０１００），考虑到程序的容易实现。这里采用了１—５０，由于没有直接可用的素数判断的函数，因此素数的ｚ）。而对于明文Ｍ，产生由自定义函数ＰｒｉｍｅＮｕｍｂｅｍ（）。－３６・万方数据算机密码的基本思想就是将要保护的信息变成伪装信息，在公开密钥算法提出之前，所有密码系统的解密密钥和加密密钥都彼此有着直接的联系，这是秘密密钥的缺陷所在。为此，１９７６年，Ｄ瓶ｅ和Ｈｅｌｌｍａｎ提出了一种全新密Ｅ和解密算法Ｄ必须满足以下三个条件：Ｄ（Ｅ（Ｐ））＝Ｐ；从导出Ｄ非常困难；使用“选择明文”攻击不能攻破。研究者们努力寻找符合以上条件的算法，较好的策略是ＲＳＡ算法，在此文中并不做理论上的推导，只说明如何使用这种算法：选择两个大素数（素数又称为质数）Ｐ和ｑ；计算ｎ＝ｐ＊ｑ和ｚ＝（ｐ一１）丰（ｑ一１）；选择一个与ｚ互质的数，令其为ｄ；找到一个ｅ，使满足ｅ＇ｄ＝１（ｍｏｄ收稿日期：２０１０—０４—２６作者简介：毛建儿（１９７３一），女，浙江宁波人，余姚四职校中学一级教师。主要从事程序设计方面研究。第９卷第２期２０１０年６月Ｖｏｌ－９Ｎｏ．２毛建儿：公开密钥算法ＲＳＡ策略及程序实现ＦｕｎｃｔｉｏｎＰｒｉｍｅＮｕｍｂｅｒｓ（）ＡｓＩｎｔｅｇｅｒ产生５０以内的素数集合及素数个数Ｄｉｍｉ，ｊ，ｋ，ｎＡｓＩｎｔｅｇｅｒＤｉｍｆｌａｇＡｓＢｏｏｌｅａｎｎ＝０Ｆｏｒｉ＝２Ｔｏ５０ⅡｉＭｏｄ２◇０Ｔｈｅｎｆｌａｇ＝Ｔｒｕｅ：ｋ＝Ｉｎｔ（Ｓｑｒ（ｉ））ｊ＝２Ｗｈｉｌｅｊ＜＝ｋＡｎｄｆｌａｇＩｆｉＭｏｄｊ：ｏＴｈｅｎｆｌａｇ＝Ｆａｌｓｅｊ．ｊ＋ｌＷｅｎｄＩｆｆｌａｇＴｈｅｎｎ＝ｎ＋１：ＳｕＳｈｕ（ｎ）＝ｉＥｎｄＩｆＮｅｘｔＰｒｉｍｅＮｕｍｂｅｌ隐＝ｎＥｎｄＦｕｎｃｔｉｏｎ产生ｌ一５０以内的素数集合后，从中选择两个素数，这里设计两种产生方式：手工输入和自动产生。若手工输入，需检验素数是否正确，代码略；若自动产生，选择两个互不相同的素数。ｔ＝ＰｒｉｍｅＮｕｍｂｅｒｓ由自定义生成函数时，统计素数个数，以便确定素数选择的范围Ｒａｎｄｏｍｉｚｅ由素数集合．随机产生两个素数ｐ＝ＳｕＳｈｕ（１＋Ｒｎｄ宰（ｔ－１））ｑ＝ＳｕＳｈｕ（１＋Ｒｎｄ木（ｔ－１））从要求两个素数互不相同Ｗｈｉｌｅｑ＝ｐｑ＝ＳｕＳｈｕ（１＋Ｒｎｄ木（ｔ－１））Ｗｅｎｄ其次是选择一个与ｚ互质的数ｄ。对于小于５０的两数ｐ，ｑ，可以直接计算ｎ＝ｐ木ｑ和ｚ＝（ｐ－－１）＋（ｑ－１）。现要求与Ｚ互质，可以从素数集合中随机选择一个素数，检验其不整除ｚ，则该数必与Ｚ互质，即为所找ｄ。ｔ＝ＰｆｉｍｅＮｕｍｂｅｌｓｄ＝ＳｕＳｈｕ（１＋Ｒｎｄ（ｔ—１））随机产生一个素数检验素数与ｚ互质ＷｌｌｉｈｚＭｏｄｄ＝０ｄ＝ＳｕＳｈｕ（１＋Ｒｎｄ（ｔ－１））Ｗｅｎｄ再次是找到ｅ，满足ｅ＇ｄ＝１（ｍｏｄｚ）。ｄ已经产生，要找万方数据Ｊｕｎ．２０ｌＯ满足条件的ｅ，可以将数由小到大尝试的方法，以找到满足条件的最小ｅ，用自定义函数ＳｅａｒｃｈＥ实现。ＦｕｎｃｔｉｏｎＳｅａｒｃｈＥ（ＢｙＶａｌｄＡｓＩｎｔｅｇｅｒ，ＢｙＶａｌｚＡｓＩｎｔｅｇｅｒ）ＡｓＩｎｔｅｇｅｒＤｉｍｅＡｓＩｎｔｅｇｅｒｅ＝ｌ从ｌ开始寻找满足条件的最小数ｅＷ１１ｉｌｅ（ｄ木ｅ）ＭｏｄＺ＜＞１ｅ＝ｅ＋ｌＷｅｎｄＳｅａｒｃｈＥ＝ｅＥｎｄＦｕｎｃｔｉｏｎ然后是计算Ｃ＝Ｍ‘ｅ（ｍｏｄｎ）中Ｍ＾ｅ部分。以上计算的参数有已经具备。对于输入的明文Ｍ需满足Ｍ＜ｎ（ｎ＝ｐ＊ｑ），其对应密文的计算方法为：Ｃ＝Ｍｅ（ｍｏｄｎ），尽管在先前参数选择过程中ｐ，ｑ的数据范围都没有超出５０，但由于ｄ参数随机产生，加之ｚ＝（ｐ－１）＋（ｑ－１）的数据也有些大，使得在找到符合ｅ＇ｄ＝１（ｍｏｄｚ）条件下的ｅ数据也较大，因此计算过程中Ｍｅ的结果很可能会出现数据溢出的情况，因此对于计算Ｍｅ需采用高精度的幂运算实现，用自定义函数ＧＪＤＣｈｅｎｇＦａｎｇ实现，计算结果用字符串表示。ＦｕｎｃｔｉｏｎＧＪＤＣｈｅｎｇＦａｎｇ（ＢｙＶａｌＭＡｓＩｎｔｅｇｅｒ，ＢｙＶａｌｅＡｓＩｎｔｅｇｅｒ）ＡｓＳｔｒｉｎｇ高精度幂运算产生结果为字符型Ｄｉｍａ（１Ｔｏ１０００），ｂ（１ＴｏｌＯＯＯ），Ｃ（１Ｔｏ４００００）ＡｓＩｎｔｅｇｅｒＤｉｍｓ，ｓｔｒｌＡｓＳｔｒｉｎｇＤｉｍ１１，１２，ｉ，Ｊ，ｋ，Ｘ，Ｗ，ｅｅＡｓＩｎｔｅｇｅｒｓｔｒｌ＝Ｔｒｉｍ（Ｓｔｒ（Ｍ））获取形如ＮＡＭ运算的Ｎ部分（用字符表示）ｌｌ＝Ｌｅｎ（ｓ仃１）获取底数长度１２＝ｅ获取指数值分离底数的各数码，分别赋给ａ（），ｂ（）数组Ｆｏｒｉ＝ｌＴｏ１１ａ（ｉ）＝Ｖａｌ（Ｍｉｄ（ｓｔｒｌ，ｌｌ＋ｌ－ｉ，１））ｂ（ｉ）：ａ（ｉ）Ｎｅｘｔｅｅ＝ｌｌ相乘Ｆｏｒｋ＝ｌＴｏ１２—１执行相乘运算次数Ｆｏｒｉ＝ｌＴｏｅｅ执行本次乘法运算时，将先前运算结果作为本次运算中的一个乘数，长度为ｅＦｏｒｊ＝１Ｔｏ１１按位执行相乘运算Ｘ＝ａ（ｉ）％（ｊ）本位相乘・３７・第９卷第２期２０１０年６月Ｖ０１．９Ｎｏ．２浙江工商职业技术学院学报ｗ＝ｉ＋ｊ一１当前运算结果低位应属于的第几位Ｃ（ｗ＋１）＝Ｃ（ｗ＋１）＋（Ｃ（ｗ）＋Ｘ）＼１０高位操作Ｃ（ｗ）＝（Ｃ（ｗ）＋Ｘ）Ｍｏｄ１０低位操作ＮｅｘｔＮｅｘｔ本次运算结果整理找到当前运算后非零高位的起始位ｅｅ＝ｅｅ＋ｌｌＷ１ｌｉｌｅＣ（ｅｅ）＝Ｏｅｅ＝ｅｅ—ｌＷｅｎｄ找到非零高位的起始位ｅＦｏｒｉ－ＩＴｏｅｅ若不是末次运算，按位依次将结果复制给数组ａ（）Ｉｆｋ＜＞１２—１Ｔｈｅｎａ（ｉ）＝Ｃ（ｉ）：Ｃ（ｉ）－－－０清空数组ｃ（）的数据ＮｅｘｔＮｅｘｔ按位由高到低依次输出运算结果８－－－－“”Ｆｏｒｉ＝ｅｅＴｏｌＳｔｅｐ－１ｓ＝ｓ＋Ｔｒｉｍ（Ｓｔｒ（Ｃ（ｉ）））ＮｅｘｔＧＪＤＣｈｅｎｇＦａｎｇ。８ＥｎｄＦｕｎｃｔｉｏｎ最后是计算Ｃ＝Ｍ＾ｅ（ｍｏｄｎ）中（ｍｏｄｎ）部分。Ｍｅ的结果已经出来，接下来要计算取余的操作，由于ｎ是两个小于５０的数的乘积。因此ｎ无需将ｎ各个数字分离。而被除数的数据可能会溢出，采用高精度方法表示，在计算取余的过程中，仍旧部分的采用了高精度的方法，一位一位剥离，直到得到最后的余数，这里也用一个自定义函数ＭｏｄＲｅｓｕｌｔ来实现。ＦｕｎｃｄｏｎＭｏｄＲｅｓｕｈ（ＢｙＶａｌ８ＡｓＳｔｒｉｎｇ，ＢｙＶａｌｎｌｌＡｓＩｎｔｅｇｅｒ）ＡｓＩｎｔｅｇｅｒ产生ｍｏｄ操作的结果Ｄｉｍｓｎ，ｔＡｓＳｔｒｉｎｇＤｉｍｌｅｎｇ，ｔｎ，ｉ，ｊＡｓＩｎｔｅｇｅｒｓｎ＝Ｔｒｉｍ（Ｓｔｒ（ｎｎ））：ｌｅｎｇ＝Ｌｅｎ（ｓｎ）ｔ＝ｌｅｄｔ（ｓ，ｌｅｎｇ—１）：ｔｎ＝Ｖａｌ（ｔ）ｉ＝ｌｅｎｇＷｈｉｌｅｉ＜＝Ｌｅｎ（ｓ）按位操作的次数ｔｎ－－ｔｎ＊１０＋Ｖａｌ（Ｍｉｄ（ｓ，ｉ，１））先前余数＊１０，加上本位上的数作为当前被除数ｔｎ－－ｔｎＭ０ｄｎｎ得到本次操作的余数ｉ：“ｌＷｅｎｄ・３８・万方数据Ｊｕｎ．２０１０ＭｏｄＲｅｓｕｌｔ＝ｔｎ取余的结果ＥｎｄＦｕｎｃｔｉｏｎ另外，这些算法在编程实现上，界面如下图所示，应添加相关控件，合理布局。根据先前已经写好的若干自定义函数。ＲＳＡ的加密和解密操作就变得比较简单了。需要说明的是解密过程由于只知道公开密钥的（ｄ，ｎ），因此要先找到对应的ｅ，组合成私人密钥（ｅ，ｎ），这里都可以套用自定义函数，显然加密和解密过程是互逆过程。计算上是反函数的关系。以加密代码为例。ＰｒｉｖａｔｅＳｕｂＣｍｄＲＳＭｉａＭｉ＿Ｃｌｉｃｋ（）Ｄｉｍｐ，ｑ，１１，ｚ，ｄ，ｅ，ｔ，Ｍ，ＣＡｓＩｎｔｅｇｅｒ获取参数ｐ，ｑｐ＝Ｖａｌ（ＴｘｔＰ．Ｔｅｘｔ）：ｑ＝Ｖａｌ（ＴｘｔＱ．Ｔｅｘｔ）计算ｎ和ｚｎ＝ｐ幸ｑ：筘（ｐ－１）宰（ｑ－１）获取明文。检验明文Ｍ＝Ｖａｌ（’ｒｘｔＭ．Ｔｅｘｔ）ＩｆＭ＞＝ｎＴｈｅｎＭｓｇＢｏｘ“明文数据不符合要求！（要求＜ｐ奉ｑ）”，ｖｂＥｘｃｌａｍａｔｉｏｎ，“．’’ＥｘｉｔＳｕｂＥｎｄＩｆ找一个与ｚ互质的ｄｔ＝ＰｒｉｍｅＮｕｍｂｅｍｄ＿Ｓｌｌｓｈｕ（１＋Ｒｎｄ（ｔ－１））Ｗ１ＩｉｌｅｚＭｏｄｄ＝０ｄ＝ＳｕＳｈｕ（１＋Ｒｎｄ（ｔ－１））Ｗｅｎｄ找符合条件的ｅ，ｅ＇ｄ＝１（ｍｏｄｎ）ｅ＝ＳｅａｒｃｈＥ（ｄ。ｚ）计算出密文ＣｆＭ＾ｅ（ｍｏｄｎ）Ｃ＝ＭｏｄＲｅｓｕ］ｔ（Ｇ叩ＣｈｅｎｇＦａｎｇ（Ｍ，ｅ），ｎ）．ＩｈＣ．Ｔｅｘｔ＝Ｔｒｉｍ（Ｓｉｒ（Ｃ））ＥｎｄＳｕｂ应该指出的是，ＲＳＡ算法虽然安全方便，但运行速度很慢，因此其通常只用来进行用户认证、数字签名或发送一次性的秘密密钥，而数据加密仍使用秘密密钥算法。［责任编辑：熊荣生］
