“只许州官放火，不许百姓点灯”的又一个典型事例。

n123zj3

“探究密码体制里的数学问题”，是我于2012年3月10日，递送给“火花”的第十二篇文章，由于我将二改“证明梅森素数无限”，提到了前面与“证明梅森素数无限”一并讨论，因此只好将“探究密码体制里的数学问题”，排序为第十四篇文章了。近几年来，出版了好几本，专门论述关于密码编制方面的数学书籍，其中冯克勤的《数论与密码》，格外引起了我的注意，让我反复思考了这个问题。
密码的问题，是一个关系到信息安全的大事，千万不可掉以轻心。冯克勤的《数论与密码》，全部都是抄袭的外国的东西，如果我国的密码编制，真的是按照冯克勤所说的方法，那么，我国的信息安全就会存在着极大的隐患，因为你运用外国人的方法所编制的密码，根本毫无保密可言。因此我在“探究密码体制里的数学问题”一文里，提出了一定要按照我们自己的方法，并且必须予以多重设防。然而“火花”的退稿意见却是：
“经专家审阅，认为这篇短文对36年前麻省理工学院的三位专家编制出的第一个RSA密码体制作了分析，针对它的不安全性，提出了自己的设想。这些设想并不难，容易想到。而问题在于本文所探讨内容对于密码学来说太老了。麻省的文章发表已有36年，密码学在这期间有了迅猛的发展，加之本文没有列出任何参考文件，建议作者参阅近年来这个领域的学术文章和著作。您的来稿不符合本栏目的定位和要求，因此予以退稿。”
对于这个退稿意见，我只能说是“只许州官放火，不许百姓点灯”的又一个典型事例。现在对于这个问题，我又有了新的认识，运用大数分解的分解困难编码，是极易被破译的，并且不具唯一性，只有4k+1形素数的平方，它的两平方和分拆，才是既具唯一性，又是极难予以破解。倪则均，2015年1月6日。
探究密码体制里的数学问题
倪则均
一，RSA密码体制的推出
1976年美国斯坦福大学的Hellman和Diffie，发表了一篇题为“密码学新方向”的学术论文，提出了公钥密码的新概念。这个公钥密码体制的设想思路，是根据两个大素数之积的难以分解特性所提出来的。次年麻省理工学院的Rivest，Shamir和Adleman按照他们的设想，运用了一个129位的含有两个奇素因子的合数，编制出了第一个RSA密码体制，这种RSA密码体制一直沿用至今。
其实，这种仅仅根据位数多所编制出来的密码是很不安全的，因为位数多与难分解之间，对于电子计算机来说，绝对不是一种主要的因果关系。许多十分庞大的合数，只要给出一套算法，编制出相应的运算程序，即可通过计算机将它们迅速分解出来。然而，有些合数好象不是太大，但是却无法找到分解它们的算法，这才是真正的难以分解。
含有两个奇素因子的合数，能不能迅速分解，甚至能不能分解，主要与其所含有的两个奇素因子的性质密切相关。如果这两个奇素因子都不是同周期素数，即没有其它素数与它具有相同的2的周期，那么不管它们多大，都是容易分解的。若是这两个奇素因子的2的周期都是素数，则更好分解，特别当一个素数是另一个素数的2的周期，只要通过判断即可知道分解结果会出现什么样的重因子。
如果这两个奇素因子是二种不同的同周期素数，那么它们的分解就会变得极其艰难，因为在它们的分解过程中，必然要涉及到同周期分解的问题。费马合数和梅森合数的分解都属于这类分解，它们是这类分解中最容易分解的二种情况，因为它们只是2的幂的二项式。至于具有许多项的2的幂的多项式，尽管它们都是显性表达式，但是它们的同周期分解难度就会更大。然而，真正难的是那些隐性表达式的同周期分解，所谓隐性表达式是一个分式，其分子分母都是若干个2的幂的多项式的积，而且这些多项式的数量还会无限增加下去。
二，0层2阶数的分解规律
0层2阶数是指n=2^q1q2-1（q1，q2是个不同的素数）形数或n=2^q12-1形数，我们只要掌握了前一种数的分解规律，就不难知道后一种数该如何分解的了，因此下面仅给出前一种数的分解规律。这种数的分解，可以运用以下二种方式展开：
n=2^q1q2-1=（2^q1-1）（2^q1（q2-1）+2^q1（q2-2）+…+2^q1+1）
n=2^q1q2-1=（2^q2-1）（2^q2（q1-1）+2^q2（q1-2）+…+2^q2+1）
其中（2^q1-1）和（2^q2-1）如果是梅森合数，那么还要再作同周期分解，不管它可以分解出多少个素因子，它们的2的周期必定分别都是q1和q2。由于上述二种分解的结果应该相同，因此有
（2^q1（q2-1）+2^q1（q2-2）+…+2^q1+1）/（2^q2-1）
=（2^q2（q1-1）+2^q2（q1-2）+…+2^q2+1）/（2^q1-1）
这是二个最简单的隐性多项式，它们所表示的数如果是合数，同样不管它可以分解出多少个素因子，它们的2的周期必定都是q1q2。如果上述三个数都是素数，那么，任取二个相乘，它们的积的2的周期必定都是q1q2。这就是说，二个数乘积的2的周期，必定是这二个数的2的周期的最小公倍数，由于证明极其简单，应该不需予以赘证。
由此可见，二个非同周期素数的积，运用上述方法予以分解，其结果只会多出一个数来，然而，二个同周期素数的积，运用上述方法予以分解，其结果会多出许多个数来。对于RSA密码体制来说，二个作为乘数的素数是保密的，公开的只是它们的积n，其实这个积的2的周期是极易得到的，只要从2开始不断地连续乘2，不断地取其模n的余数，当余数为1时，其幂就是积n的2的周期。
三，RSA密码体制的钥匙
RSA密码体制的钥匙有公私之分，公钥e是可以公开的加密钥匙，私钥d是必须保密的解码钥匙。所谓的公钥和私钥，实际上是二个素数环的积环里的一对乘法互逆元素，即有de≡1（mod （p1-1）（p2-1）），p1，p2为二个奇素数。其实，只要对方根据n的2的周期，分解得到p1和p2二个素因子，那么其解码钥匙将会显得毫无保密可言，根本起不到第二道防护作用。
这是由于这样的公钥和私钥，完全是根据二个素数环的积环里的欧拉群所设计，破解欧拉群里的乘法互逆元素，早已不是什么难事，若是运用秦九韶的“大衍求一术”，更是举手之劳的事情。其实，在二个素数环的积环里，除了欧拉群之外，还有为数十分众多的因子群，在这些群里同样也有着乘法互逆的概念，只是它们的单位元各不相同，并且全都不是1而已。
因此，如果选择一个因子群来设计公钥和私钥，显然又可以增加二道防线。即使对方攻破了第一道防线，得到了p1和p2二个素因子，也无法知道你到底选用的是那一个因子群。即使对方知道了这个因子群，那么现在尚未有人研究过，如何计算它们的乘法逆元的问题。综上所述，我觉得我国的密码编制，首先要选择具有多个同周期素数的素数积，以加强第一道防线。还要尽量运用因子群来设计公钥和私钥，以充实第二道防线，更要利用因子群的乘法求逆，无人知晓的条件增设第三道防线。2012年3月10日