rsa加密算法的研究论文

在探究RSA算法的原理之前，我们先来学习一点有趣的数论知识（数学分支之一，主要研究整数的性质）。你会发现一些简单的数学知识竟然背后有如此神奇的魔力。

说起质数，想必大家不陌生了，一个大于1的整数除了其本身和1之外，不存在因数则被称为质数或者是素数。比如2、3、5、7等。在小学课堂里，我们可能只是记住了这个概念，但是这里我谈下自己的一些思考帮助大家理解，质数就好比是构成数字的基本元素，想想看，氢分子仅由两个氢原子（组成一个氢分子）构成，那么一个非质数的6=3*2 即表示为6是由两个“3”元素或3个“2”元素构成。其中“3”或者“2”是不可以继续拆分的元素（3，2都是质数）。所以对一个非质数进行因式分解过程就好比对一个物体进行深入解剖，拆分至不可拆分的元素为止。这样看来，数学家们提出这些数学概念，其实也是一种对数字世界的认识和思考的概括，和我们日常生活理解周边事物方式也是相似的。

知道了质数，我们再看看互质关系，那么什么是互质呢？就是说两个数没有相同的因数称为互质关系。我们对6进行因数分解，拆分到质数的乘积即6＝3* 2而 35=5*7,这两者没有相同的因数则称6与35互质，就好像氢气分子只是由氢原子构成，而氧气分子只是由氧原子构成，这二者这间没有相同的原子就是一种互质的体现。 所以互质只是一个数和数之间有没有相同的因数关系的体现(公约数也称公因数)，和两者是不是质数是没有关系的。当然质数之间必然是互质关系，因为它们都是构成数字的不同元素。数学上来表示a,b互质一般用gcd(a,b)=1来表示。即a和b的最大公约数是1.

质数和互质的关系是不是很容易理解？但是大数学家欧拉先生可绝不仅仅停步于此，数学家嘛总爱问一下抽象概括性的问题，希望找寻规律比如

如果能找到规律，无论数字如何千变万化10位数还是100000位数，我们都能根据准则轻易计算数互质关系的数量。你发现了没有，数字也是一片世界，真是一花一世界一叶一如来啊！好了回归正传，对于这个问题欧拉先生给出了他的答案。他是这样作答的： 首先呢上述问题可以简化为一个函数来描述即： \Phi(n) 这也是数学家老毛病在他们看来任何问题就是对函数的求解。既然这个函数由欧拉提出来的，那么我们就称他为 欧拉函数 .还好这个函数简单只有一个变量，即给定的正整数n。接下来就要分析这个n

n＝1的时候这个问题极其简单： \Phi(n)＝1 因为1与任何数包含他自身都构成互质关系。1本身也是质数且不作为其他数的因数，因为任何数乘以1都是其本身

大家想想看n是质数，其自身就不存在因数了，而那些与他非互质关系(存在公约数)的数进行因式分解后一定都会有一个因数与n相等。比如n＝3为一个质数，那么6＝3*2与3是非互质关系，因为存在公约数3。所以我们发现与n非互质关系的数都是n的倍数即(kn)，因为kn>=n所以与n互质的数都小于n即 \Phi(n)＝n-1

还记得我们前面提到的质数吗，他可是构成数字的元素呀，所以如果n不是质数，那么他一定可以被因式分解拆分成多个质数的乘积。比如24=6*4=3*8=2*2*2*3 比如6=2*3，这些质数因数相互乘积也可以形成如下情况：

我们把相同质数因数进行相乘，很容易将一个非质数分解为两个互质关系的数的乘积，比如24=6*4=2*2*2*3＝3*8 从简单的情况来考虑，即n被拆分为两个互质关系的数的乘积： 即

n=p*q p与q互质，那么根据剩余定理:

\Phi \left( pq\right) =\Phi(p)*\Phi(q)

至于如何证明呢？说实话我也不清楚。在我理解看来，与24互质的数都有这样一个特点：他进行因式分解后其因数不包含有3与2（因为8=2*2*2）。所以与3互质的数定义为集合A，且个数为 \Phi \left( 3\right) 与8互质的数定义为集合B，且个数为 \Phi \left( 8\right) 这AB两组的数字可以在组与组间两两进行组合乘积，构成与24互质的数。所以两组数字个数相乘就可以知道乘积的组合个数，也就知道与24互质的个数了。这样的证明并不严谨但姑且可以先记住。 另外还需要记住欧拉函数是一个 积性函数 ,也就是n如果为多个互质的数构成即(n=a*b*c*d.... )，那么 \Phi \left( n\right)=\Phi \left( a\right) *\Phi \left( b\right)....

也就是n为某一个质数的倍数，比如27=3*3*3=3^3 27就是3的倍数。那么小于27且存在非互质关系的数一定都是3的倍数也就是：1*3、2*3,3*3...9*3 共计9个， 所以3^3 - 9 ＝3^3 - 3^2 .所以归纳一下也就是说如果p是质数，求与p^n 互质的数的个数，只要将如下的数 (1*p)、(2*p)、(3*p)、....(p^n-1 *p) 进行剔除，剩余的都将与p^n （切记p是质数）互质所以我们得出：

\Phi \left( p^{k}\right)=p^{k}-p^{k-1}＝p^{k}(1-\dfrac {1}{p} )

当k＝1的时候即 \Phi \left( p\right)=p-1 又回到了之前n为质数的情况下的表达式。这里我们也看到数学追求简洁和普适性的思想，再繁杂的规律都可以变成一个简洁抽象的表达式。

比如24=6*4=3*8=2*2*2*3，因为质数之间就是互质关系而且质数的多次方也是互质关系所以 我们把24演变一下：24=2^3 * 3即把相同的质数进行合并为质数的多次方。这样2^3 与3是互质关系( 质数的多次方之间也都是互质关系 )，于是当我们求与24互质的数的个数时候，就可以套用之前公式即：

\Phi \left(24\right)=\Phi \left( 2^{3}*3\right)=\Phi \left(2^3\right)*\Phi \left(3\right)=(2^{3}-2^{3-1})(3-1) =8

再进一步归纳因为p1、 p2...pm等都是质数且 n = p_{1}^{k_{1}}p_{2}^{k_{2}}p_{3}^{k_{3}}...p_{m}^{k_{m}}

则由于欧拉函数是积性函数，那么： \Phi \left(n\right)=\Phi \left( p_{1}^{k_{1}}p_{2}^{k_{2}}p_{3}^{k_{3}}...p_{m}^{k_{m}}\right) =\Phi \left( p_{1}^{k_{1}}\right)* \Phi \left( p_{2}^{k_{2}}\right)*...\Phi \left( p_{m}^{k_{m}}\right) 由上一小节n为质数的多次方的结论 \Phi \left( p^{k}\right)=p^{k}-p^{k-1}＝p^{k}(1-\dfrac {1}{p} ) 可以得出： \Phi \left( p_{1}^{k_{1}}\right)* \Phi \left( p_{2}^{k_{2}}\right)*...\Phi \left( p_{m}^{k_{m}}\right)=p_{1}^{k_{1}}p_{2}^{k_{2}}...p_{m}^{k_{m}}*(1-\dfrac {1}{p_{1}} )*(1-\dfrac {1}{p_{2}})...(1-\dfrac {1}{p_{m}} )

则 \Phi \left(n\right)=n*(1-\dfrac {1}{p_{1}} )*(1-\dfrac {1}{p_{2}})...(1-\dfrac {1}{p_{m}}) 此时我们仍然计算24互质个数则 \Phi \left(24\right)=\Phi \left( 2^{3}*3\right)=\Phi \left(2^3\right)*\Phi \left(3\right)=24*(1-\dfrac {1}{2})(1-\dfrac {1}{3})＝8

上面说的那么多其实归结起来就是这样一个道理：当我们去求小于某个数范围内与其互质的数的个数时候，无非就是把n分为质数还是非质数。

知道了欧拉函数，接下来我们再理解一个同余概念，简单来说也就是25除以3的余数为1，而1除以2的余数为1，则我们称25与1对于模3同余数，用人话来说就是25和1 除以2得到的余数都一样。求余数的过程在数学里的黑话叫取模。所以才有上面那么拗口的说法。但是不要紧，数学喜欢简单不啰嗦，于是搞出了如下的表达式来表达上述说法： 25\equiv 1\left( mod\ 3\right) 也就是说 25 \% 3 = 1\%3=1 注意到了吗？上述表达式也可以这样表述，即25除以3得到的余数为1.围绕着同余这个概念，欧拉大师结合他的欧拉函数活脱脱就搞出了个欧拉定理，我们来看看他有什么发现？

另外根据取模运算的规则： a^{b}\%p = ((a \% p)^{b}) \% p 我们还可以得出 （a^{\Phi \left(n\right)})^{k}\equiv 1\left( mod\ n\right) 因为 (a^{\Phi \left(n\right)})^{k} \% n=（a^{\Phi \left(n\right)}\%n)^{k}\%n=1^k\%n =1 我们举个例子：比如 {\Phi \left(10\right)}＝{\Phi \left(2*5\right)}={\Phi \left(2\right)}*{\Phi \left(5\right)}=(2-1)*(5-1)=4

所以根据欧拉定理：因为9与10互质所以 9^{\Phi \left(10\right)}=9^4\equiv 1\left( mod\ 10\right) 于是(9^4 )^k 除以10都余1。

如果a与n互质，则必然能够找到一个数使得 ab\equiv 1\left( mod\ n\right) 则b称为a的模反元素，我们可以通过欧拉定理来给予证明 a^{\Phi \left(n\right)}=1\left( mod\ n\right) a^{\Phi \left(n\right)}= a*a^{\Phi \left(n\right)-1}\equiv 1\left( mod\ n\right)

模反元素的概念对后续在已知道公钥情况下，计算合适的私钥是有很重要的意义的。 掌握了这些数学知识，你可能觉得这些东西似乎很孤立，看不到任何作用和价值，不过接下来我们来看看RSA是怎么运作的，你就会发现这些看似毫无作用的东西是如何产生价值的。

从加解密的表达式可以看出在，数学原理上公钥和私钥其实并没有什么差异。你可以用公钥加密、私钥解密，也可以用私钥加密，公钥进行解密。但是对于密码学来说，对公钥和私钥会有不同的要求。 另外需要注意的是这里 明文数值不能大于等于N ，否则解密的结果并不会等于明文。

因为加密的公式为： x^e mod n = y 而解密公式为 y^d mod n = x 从上面表达式可以看出在数学原理上公钥和私钥其实并没有什么差异。你可以用公钥加密、私钥解密，也可以用私钥加密，公钥进行解密。 所以根据： y=x^e - kn 且因为Y^D mod N = x 所以 y^D \equiv x (mod\ n) 所以确定能否加解密的过程本质就是证明： （x^e - kn)^d \equiv x (mod\ n) （） 而根据二项式定理 [图片上传失败...(image-ca75c7-10)]

（x^e - kn)^d 展开后演变为 x^ed-m_{1}x^{e(d-1)}kn+m_{2}x^{e(d-2)}(kn)^2...m_{n}(kn)^{d} 你会发现二项式展开后，唯有x^ed 没有包含n，因此结合模运算加法运算规则(a + b) % p = (a % p + b % p) % p ，要想证明的表达式，则必然证明： x^{ed} \equiv x (mod\ n) 由于 ed \equiv 1 (mod\ {\Phi \left(n\right)}) 所以 ed=h{\Phi \left(n\right)})+1 则从证明 x^{ed} \equiv x (mod\ n) 演变为证明 x^{h{\Phi \left(n\right)}}*x\equiv x (mod\ n) 如果x与n 互质则根据欧拉定理 x^{{\Phi \left(n\right)}}\equiv 1 (mod\ n) 基于在欧拉定理中提及的，根据取模运算规则可以得出 x^{h{\Phi \left(n\right)}}\equiv 1 (mod\ n) 仍然是基于取模运算乘法规则，我们又可以得出 x^{h{\Phi \left(n\right)}}x\equiv x (mod\ n) 这样原式得到证明。 那么如果x与n不互质的情况下，因为n=p*q且p和q都是质数，所以n的因数只有p和q了，因为x与n不互质，那么我们可以认为： x=k_{1}p 0 < u< q 或者 x=k_{2}q 0 < k

请注意k值的取值范围，这里要牢记一点明文值必须大于0且小于n值。 这里我们先姑且定义 x=kq 0 < k< p

那么因为p与q都是质数，根据k

得出

(kq)^{h*(q-1)(p-1)} = 1+u*p 这里的u为任意整数，这时候两边都乘以kq (kq)^{h*(q-1)(p-1)}*kq = 1+u*k*q*p 因为n=pq x=kq那么 (x)^{\Phi \left(n\right)+1} = x+u*k*n 还是根据之前取模运算定义得出 (x)^{h\Phi \left(n\right)+1}\equiv x\left( mod\ n\right) 即原式得到了证明。

之所以RSA是安全的，很大程度取决于n值是否足够大以至于在已知公钥e和模数n的情况下仍然难以找出d。根据之前的谈及的密钥对计算方式： E*D \equiv 1(mod\ M) 要想算出D就必须计算出M 而M = (p-1)(q-1) ，n=p*q则要算出M就需要知道p和q，即从一个庞大的数中分离出两个也很大的质数。大数的素因数分解被认为是一个困难的问题，即使是现代的计算机也非常难于处理，所以许多加密系统的原理都是建基于此。 目前最安全的做法是选择使用rsa-2048，随着2009年12月12日，编号为RSA-768（768 bits, 232 digits）数也被成功分解。这一事件威胁了现通行的1024-bit密钥的安全性。这里的2048表示的是模数N 的二进制位为2048位。而一般公钥世面上普遍选择65535，这是安全性和计算速度之间的综合考虑下选择出来的一个比较妥当的数值。因为加解密函数都是在做大数的指数运算，所以在工程方面会尽量考虑公钥加解密的执行速度，毕竟公钥是被外部使用的。 此外还记得前面提到rsa加密的明文数值大小不能大于N，或者其位数不能超过N的位数的限制。一旦超过密文解密后和原文数据不相匹配，这时候就需要采用分段加密技术。而另一方面明文的值也不能为0或1，-1因为这样导致密文也是0，1或者-1。另外也有一个问题即如果用私钥解密一段非法数据，那么得到是解密失败还是一个毫无意义的解密内容呢？这时候需要采用 rsa padding技术。对这个概念理解可以参考 浅谈RSA Padding 这篇文章。

通过学习一些简单的数论知识即质数、欧拉函数、模反元素等概念后，我们也了解RSA算法大致过程，总的来说公私密钥对需要计算如下几个数据：

RSA的安全性不仅仅建立于大数质因数分解困难这一理论基础上，在工程上如何对上述这些数值的选取也是很大的学问。通过对rsa学习让我对工程和理论之间的关系理解上更进一步。理论确定了方向的可行性，而工程实践则要确保在有限资源下，理论结果是可以应用起来解决特定规模的问题。而在加密算法领域，一旦工程实践出现偏差，往往就容易产生安全漏洞，尽管算法理论证明是安全的。比如rsa中p q值的选择等。这里我罗列几个工程问题有兴趣的童鞋可以再进一步做探索：

密码学论文写作范例论文

随着网络空间竞争与对抗的日益尖锐复杂，安全问题以前所未有的深度与广度向传统领域延伸。随着移动互联网、下一代互联网、物联网、云计算、命名数据网、大数据等为代表的新型网络形态及网络服务的兴起，安全需求方式已经由通信双方都是单用户向至少有一方是多用户的方式转变。如果你想深入了解这方面的知识，可以看看以下密码学论文。

题目：数学在密码学中的应用浅析

摘要：密码学作为一门交叉学科，涉及学科广泛，其中应用数学占很大比例，其地位在密码学中也越来越重要，本文简单介绍密码学中涉及数学理论和方法计算的各种算法基本理论及应用，并将密码学的发展史分为现代密码学和传统密码学，列举二者具有代表性的明文加密方法，并分别对其中一种方法进行加密思想的概括和阐述。

关键词：密码学 应用数学 应用

随着信息时代的高速发展，信息的安全越来越重要，小到个人信息，大到国家安全。信息安全主要是将计算机系统和信息交流网络中的各种信息进行数学化的计算和处理，保护信息安全，而密码学在其中正是处于完成这些功能的技术核心。在初期的学习当中，高等数学、线性代数、概率论等都是必须要学习的基础学科，但是涉及密码学的实际操作，数论和近世代数的'数学知识仍然会有不同程度的涉及和应用，本文在这一基础上，讨论密码学中一些基本理论的应用。

一、密码学的含义及特点

密码学是由于保密通信所需从而发展起来的一门科学，其保密通讯的接受过程如下： 初始发送者将原始信息 （ 明文） 进行一定方式转换 （ 加密） 然后发送，接受者收到加密信息，进行还原解读 （ 脱密） ,完成保密传输信息的所有过程，但是由于传输过程是经由有线电或无线电进行信息传输，易被窃取者在信息传输过程中窃取加密信息，在算法未知的情况下恢复信息原文，称为破译。

保密信息破译的好坏程度取决于破译者的技术及经验和加密算法的好坏。实际运用的保密通信由两个重要方面构成： 第一是已知明文，对原始信息进行加密处理，达到安全传输性的效果； 第二是对截获的加密信息进行信息破译，获取有用信息。二者分别称为密码编码学和密码分析学，二者互逆，互相反映，特性又有所差别。

密码体制在密码发展史上是指加密算法和实现传输的设备，主要有五种典型密码体制，分别为： 文学替换密码体制、机械密码体制、序列密码体制、分组密码体制、公开密钥密码体制，其中密码学研究目前较为活跃的是上世纪70年代中期出现的公开密钥密码体制。

二、传统密码应用密码体制

在1949年香农的《保密系统的通信理论》发表之前，密码传输主要通过简单置换和代换字符实现，这样简单的加密形式一般属于传统密码的范畴。

置换密码通过改变明文排列顺序达到加密效果，而代换密码则涉及模运算、模逆元、欧拉函数在仿射密码当中的基本理论运用。

传统密码应用以仿射密码和Hill密码为代表，本文由于篇幅所限，就以运用线性代数思想对明文进行加密处理的Hill密码为例，简述其加密思想。

Hill密码，即希尔密码，在1929年由数学家Lester Hill在杂志《American Mathematical Monthly》

上发表文章首次提出，其基本的应用思想是运用线性代换将连续出现的n个明文字母替换为同等数目的密文字母，替换密钥是变换矩阵，只需要对加密信息做一次同样的逆变换即可。

三、现代密码应用

香农在1949年发表的《保密系统的通信理论》上将密码学的发展分为传统密码学与现代密码学，这篇论文也标志着现代密码学的兴起。

香农在这篇论文中首次将信息论引入密码学的研究当中，其中，概率统计和熵的概念对于信息源、密钥源、传输的密文和密码系统的安全性作出数学描述和定量分析，进而提出相关的密码体制的应用模型。

他的论述成果为现代密码学的发展及进行信息破译的密码分析学奠定理论基础，现代的对称密码学以及公钥密码体制思想对于香农的这一理论和数论均有不同程度的涉及。

现代密码应用的代表是以字节处理为主的AES算法、以欧拉函数为应用基础的RSA公钥算法以及运用非确定性方案选择随机数进行数字签名并验证其有效性的El Gamal签名体制，本文以AES算法为例，简述现代密码应用的基本思想。

AES算法的处理单位是计算机单位字节，用128位输入明文，然后输入密钥K将明文分为16字节，整体操作进行十轮之后，第一轮到第九轮的轮函数一样，包括字节代换、行位移、列混合和轮密钥加四个操作，最后一轮迭代不执行列混合。

而且值得一提的是在字节代换中所运用到的S盒置换是运用近世代数的相关知识完成加密计算的。

四、结语

本文通过明确密码学在不同发展阶段的加密及运作情况，然后主要介绍密码学中数学方法及理论，包括数论、概率论的应用理论。

随着现代密码学的活跃发展，数学基础作为信息加密工具与密码学联系越来越密切，密码学实际操作的各个步骤都与数学理论联系甚密，数学密码已经成为现代密码学的主流学科。

当然，本文论述的数学理论与密码学的应用还只是二者关系皮毛，也希望看到有关专家对这一问题作出更深层次的论述，以促进应用数学理论与密码学发展之间更深层次的沟通与发展。