《RSA 数学基础分析》2100字

RSA数学基础分析目录TOC\o"1-2"\h\u21475RSA数学基础分析 1105191.1数论的基础知识 189031.1.2素数与合数 2325161.1.3互质数 2119871.2模算术运算 3124151.2.1模运算的概念 372011.2.2模运算的性质 3234141.3欧拉定理及相关概念 4迄今为止,大部分的公钥密码体制算法都是一套由一些数学难题作为其理论基础的加解密机制,其中,大整数的分解困难等问题也就是RSA加密算法研究的基础。和其他大部分公钥密码体制一样,其加密算法的逆元问题决定了RSA加密算法安全性的强弱。换句话说,求把任意的两个大的素数相乘所得的结果相对还是可以很容易得的,但是如果把每一个正大数都拆分成这两个大素数的话还是有非常多困难的。所以说,我们要把这样类型的密码函数取名叫为单向密码函数。在当今我们每天所必须接触用到的各种密码学工具中,单向密函数在它们其中也占比量很大,构建这样一个公钥密码体制,单向函数也是非常重要的。在此部分,为了更好地了解RSA加密算法,我将对数论中与之相关的部分做一下基本的介绍。1.1数论的基础知识定义1:假设m和n为两个任意的整数,n不等于0,如果存在一个整数r,让m等于nr,那么就把n叫做m的公因数,m也是n的倍数,m可被n整除,可记作n|m。定义2:假设m和n为两个整数,如果存在一个整数r,使m可被r整除,n也可被r整除,那么r就是m和n的公因数,其中,在公因数里最大的那个公因数叫做最大公因数。定理1:假设m和n是两个整数,如果m等于q乘以n加r,那么q为商,r为其余数,r小于n,则m和n的最大公因数等于n和r的最大公因数。证明:假设d为m和n的最大公因数,d1为n和r的最大公因数由m等于q乘n加r,m减q乘n等于r,已知r可被d整除,由n可被d整除及r可被d整除,故d1可被d整除。反过来,d1是n和r的最大公因数,m等于q乘n加r,所以m可被d1整除,由m可被d1整除及n可被d1整除,故d可被d1整除。由d1可被d整除和d可被d1整除,可知d等于d1,所以m和n的最大公因数等于n和r的最大公因数。1.1.2素数与合数取一个大于一的整数p,如果1和它本身为p仅有的两个因子,那么我们就把p叫做质数,如果p不仅仅有1和它本身两个因子,那么我们就把p叫做合数。既不是只有一个正质数也就不是负整合正数负的负质数中也有很多个负数,0之和才是正负1,素数的个数也是有无限穷高的,而且是对其中任意数的任意一个的负正质整数,把将其分解成乘积的形式,此乘积中的所有乘数都可以是质数。公式1:整数n的标准分解式:n等于p1的e1次方乘p2的e2次方乘p3的e3次方乘p4的e4次方乘一直乘到pm的em次方。其中p1小于p2小于p3小于p4直到小于pm,ei为零或正整数。在这个公式中,如果n的取值到达非常大的时候,那么如果想要求出n的标准分解式是十分困难的,也正因为这样的困难的公式,才使得RSA算法的安全性得到了强有力的保证,这也是RSA算法中较为突出的优点,也是RSA算法中非常重要的特质,所以RSA算法适合于大数方面的运算。1.1.3互质数m,n为两个正整数,如果1是m和n唯一的公因数,那我们把这种特质叫做m和n互质。m1,m2,m3,m4.,mk为k的个正整数,如果对于其中任意一点的i不等于j,且其中i大于或等于1,j都小于和等于k,ni和nj都是互质,那么现在我们便把这点k为个的正整数就叫做两两互质。如果存在了一个同质数p并使得另外两个的正整数都可以与其互质,那么和这另外两个的正整数相乘得的数值就也称为和这个p的互质。1.2模算术运算1.2.1模运算的概念A可以为一对任意一个整数,n可为另一对正整数,存在对应着对唯一的对整数的q和的r,满足设r大于或等于为零且n大于为r,a等于为q和与对n和的乘积再加为r,则可以称作r是一个a的对数n和的模运算。A如果除以所有n次方的算术商记为q,那么[x]就应该表示为一个小于或至少等于这个x数的算术最大的整数,所以,对其中任意的一个大整数的a都应该可以这样表示即为a=[a/n次方]n+amodn1.2.2模运算的性质数学中包含着模运算的一些概念,我们可以通过这些概念发现,几乎是所有的整数的集合可以通过模运算和n次模的运算把他们直接的映射到另一个充满了整数的集合中{0,1.,(n-1)}中,这种运算的方式我们又习惯上称他为模n运算。模数运算形式也是可以说和许多其它的普通数学的数学运算的形式极为相似,他这种形式同时也很特别地适用于分配律,交换律,结合律。交换律(x+y)modn=(y+x)modn(x*y)modn=(y*x)modn结合律((x+y)+z)modn=(x+(y+z))modn((x*y)*z)modn=(x*(y*z))modn(xmodn+ymodn)modn=(x+y)modn(xmodn*ymodn)modn=(x*y)modn分配律(x+y)modn=(xmodn+ymodn)modn(x*y)modn=(xmodn*ymodn)modn(x*(y+z))modn=(x*y+x*z)modn恒等式(0+x)modn=xmodn(1*x)modn=xmodn幂模运算可以把其看成对应次数的模成运算例如15^7mod11=(15mod11)^7mod11=4^7mod11=×((4^2mod11)^3*4mod11)mod11=×(4mod114mod11)mod11=16mod11=51.3欧拉定理及相关概念数论领域中著名的欧拉定理也是建立RSA密码体制必需的一个基础理论。定理1:取一个正整数m,把正整数1到m中与m互为素数的数的个数称为ϕ(m)此函数就叫做欧拉函数。定理2:如果整数a与m互为质数,那么a^ϕ(m)≡1modm。证明:设ϕ(m)=k,r1,r2,r3,r4...rk为1,2,...,m−1中和m互为素数的数。因为a与m互为素数,所以ari和m互为素数。那么我们还需要证明ar1,ar2,...ark的模m互不相同。如果ari≡arjmodm,那么m|a(ri-rj),因为整数a和m互为素数,那么m|(ri-rj),就使得ri=rj,任意的i大于等于1,i小于等于k,ari和m互为素数,所以存在ari≡rjmodm,当ri取遍r1,r2,...rk时,rj也恰好取遍r1,r2,...rk,通过模运算的结合律可知,a^kr1r2.rk≡r1r2.rkmodm,又因为r1,r2,.rk和m互为素数,那么a^k≡1modm。证毕。定义1:如果对于我们而