|
2 RSA相关理论知识 2.1 RSA的数学基础知识 http://www.paper51.com 2.1.1 关于数的基本理论 内容来自www.paper51.com
整除：设a，b是任意两个整数，其中b≠0.如果存在一个整数q使得等式 a=bq成立，就称为b整除a或者a被b整除，记作b|a，并把b叫做a的因数，把a叫做b的倍数。这时，q也是a的因数，我们常常将q写成a/b。否则，就称b不能整除a或者a不能被b整除。 http://www.paper51.com 模运算：如果A模N运算，它给出了A的余数，余数是从0到N-1的某个整数，这种运算称为模运算。 内容来自www.paper51.com 素数与合数：一个大于1的正整数p，只能被1和它本身整除，不能被其它正整数整除，则这样的正整数p叫做素数或者质数；一个大于1的正整数a，除了能被1和它本身整除外，还能被其它的正整数整除，这样的正整数a叫做复合数或者合数。这样，全体正整数可分为三类：1，全体素数，全体合数。 http://www.paper51.com 公因数和最大公因数：设a1…an是n（n>=2）个整数。若整数d是它们中每一个数的因数，那么d就叫做a1…,an 的一个公因数.由于任何非零整数只存在有限个因数。因此，如果b和c不全为0，b和c只存在有限个公因数。在所有公因数中最大的一个，就称为最大公因数，并用符号gcd（b,c）表示。 copyright paper51.com 同余：若n|a-b，若a -b = kn，k是整数，则称整数a和b 模n同余，记为a≡ b (mod n )，n称为同余式的模。 copyright paper51.com 模n同余具有以下性质： paper51.com 1、若 n|a-b，则a ≡ b (mod n )； paper51.com
2、(a mod n) =(bmod n )等价于a ≡b(mod n )； 内容来自www.paper51.com
3、自反性：a≡a(mod n )； copyright paper51.com
4、对称性：a≡b (modn ) 等价于b ≡a (modn )； 内容来自论文无忧网 www.paper51.com 5、传递性：若a≡b (modn ) 且b≡c (mod n) ，则a≡c (modn )。 内容来自论文无忧网 www.paper51.com 欧拉函数：用符号φ(m )表示不大于m 并和m 互素的正整数的个数，它是正整 内容来自论文无忧网 www.paper51.com 数m 的函数，称φ( m)为m 的欧拉函数。 copyright paper51.com
φ (m )具有以下的性质： http://www.paper51.com 1、 φ (1) = 1； paper51.com 2、如果 p 是素数，则φ( p) =p-1； paper51.com
3、欧拉φ 函数是积极函数。即如果gcd(m ,n ) = 1,则φ(mn ) = φ(m)φ(n ) http://www.paper51.com 2.1.2 欧拉定理 费马小定理 paper51.com 欧拉定理和费马定理在公钥密码学中有重要的理论基础作用。 内容来自论文无忧网 www.paper51.com
欧拉定理：如果(a ,m)= 1，则恒有 copyright paper51.com aφ( m ) ≡1(modm) copyright paper51.com 其中,φ( m)为m的欧拉函数。 内容来自论文无忧网 www.paper51.com 欧拉定理的另一种等价形式为： 内容来自www.paper51.com aφ(m ) +1≡a(mod m) http://www.paper51.com 费马小定理：令p为素数，如果( p, a )= 1则有： 内容来自www.paper51.com a p-1≡1(mod p) paper51.com 费马小定理的另一种等价形式为：如果 p 为素数，a为任意正整数，则： 内容来自www.paper51.com
a p≡a(mod p ) 内容来自论文无忧网 www.paper51.com 因此费马小定理实际上是欧拉定理的一个推论。 paper51.com 2.1.3 中国剩余定理 paper51.com 设m1，m2，…mk，是k个两两互素的正整数，则对任意的整数b1，…bk,同余式组 内容来自论文无忧网 www.paper51.com
x≡b1 ( mod m1) copyright paper51.com
x≡b2 ( mod m2) 内容来自论文无忧网 www.paper51.com …….. copyright paper51.com x≡bK ( mod mk) paper51.com 一定有解，且解是唯一的，事实上 paper51.com 若令 内容来自www.paper51.com M=m1…mk,m=miMi, i=1,…,k 内容来自论文无忧网 www.paper51.com 则同于式组的解可表示为 内容来自论文无忧网 www.paper51.com x≡ b1M1′M 1 +b2M2′M2 +. ..+bkMk′Mk(modM) 内容来自论文无忧网 www.paper51.com
其中 paper51.com M′Mi≡1(modmi),i=1.2,…,k-1 内容来自www.paper51.com
2.1.4单向陷门函数 copyright paper51.com 公钥密码体制中公开密钥密码是基于单向陷门函数。 http://www.paper51.com 所谓单向函数，认为有许多函数正向计算上是很容易的，但是求其逆计算在计算上是不可行的，也就是很难从输出推算出它的输入。即已知x，我们很容易求出f（x）。但是已知f（x），却难于计算出x。单向函数不能用作加密。因为用单向函数加密的信息是无人能解开它的。 内容来自论文无忧网 www.paper51.com
单向陷门函数是有一个陷门的一类特殊单向函数。它首先是一个单向函数，在一个方向上易于计算而反方向却难以计算。但是，如果知道那个秘密陷门，则也能很容易在另一个方向计算这个函数。即已知x，易于计算f（x），而已知f（x），却难以计算x。然而，一旦给出f（x）和一些秘密信息y，就很容易计算出x。在公开密钥密码中，计算f（x）相当于加密，陷门y相当于私有密钥，而利用陷门y求f（x）中的x则相当于解密。 内容来自www.paper51.com 2.2 RSA加密解密算法 http://www.paper51.com RSA加密解密算法如下： 内容来自论文无忧网 www.paper51.com ⑴取两个随机大素数p和q（保密）； 内容来自www.paper51.com
⑵计算公开的模数n=pq（公开）； 内容来自论文无忧网 www.paper51.com ⑶计算秘密的欧拉函数φ(n)=（p-1）（q-1）（保密），两个素数p和q不再需要，应该丢弃，不要让任何人知道； 内容来自论文无忧网 www.paper51.com ⑷随机选取整数e，满足gcd（e,φ(n)）=1（公开e，加密密钥）； 内容来自论文无忧网 www.paper51.com
⑸计算d，满足de≡1（modφ(n)）（保密d，解密密钥，陷门信息）； copyright paper51.com ⑹将明文m首先分成小于n的数据块，加密，从而产生密文，公式为ci=mie（modn） http://www.paper51.com
要解密信息，取每个加密块ci并计算 mi=cid（modn） paper51.com
因为ed=1-rφ(n)，因此cid≡(mie)d≡m i(miφ(n))-r≡ mi(mod n) = mi http://www.paper51.com 其中，r 为整数。这里利用了欧拉定理： miφ( n)≡1(modn)。以上公式从密文恢复出了明文。 paper51.com 公钥 n：两个素数p和q的乘积（p和q必须保密）。e：与( p- 1)(q-1)互素 copyright paper51.com 私钥 d :e-1(mod( p - 1)(q -1)) 内容来自www.paper51.com 加密 c = me(mod n) 内容来自论文无忧网 www.paper51.com 解密 m = cd(mod n) paper51.com
2.3 RSA参数的选择 内容来自论文无忧网 www.paper51.com
技术上，RSA 算法的安全性等价于求解 RSA 单向函数的逆的困难性。但是，在实际应用中，很多时候是因为算法实现的细节的漏洞导致攻击，所以在使用RSA 算法构造密码系统时，为了保证系统的安全性，必须仔细选择各个参数。RSA的主要参数有三个：模数n，加密密钥e，解密密钥d。 内容来自论文无忧网 www.paper51.com 下面我们讨论参数的选择以及相关的问题。 paper51.com |