文档介绍：RSA算法的数论基础
公钥密码体制基础
一个好的密码体系的必要条件是合法用户能够很容易对秘密消息进行加密和解密,而这些过程对于其他人则是非常难的。
公钥密码体制的实现基于单向陷门函数。
单向陷门函数:
设f是一个函数,t是与f有关的一个参数。对于任意给定的x,计算y,使得y=f(x)是容易的。
如果当不知道参数t时,计算f的逆函数是难解的。
但当知道参数t时,计算f的逆函数是容易的。
则称f是一个单向陷门函数,参数t称为陷门。
二、RSA算法的安全基础
计算机科学家Rivest、Shamir和Adleman提出了基于素性检测和整数分解的第一个使
用公钥密码体制。算法的安全性建立这一数论难题基础上:将两个大素数相乘是容易计算的,而将该乘积分解成两个大素数因子是困难的。
素性检测问题:检测n的素性的最好额判定算法运行时间为,关于输入长度呈超越多项式速度增长。
整数因子分解问题:分解一个一般的整数n的最好的算法运行时间为,关于输入长度呈亚指数速度增长。
三、RSA算法实现的基础定理
算术基本定理:
任何大于1的整数n能被因式分解为如下唯一形式:
n=p1p2…pl(p1,p2,…,pl为素数)
费马小定理:
若p是素数,a与p互素,则
欧拉定理:
欧拉函数表示不大于n且与n互素的正整数的个数。
当n是素数,。,p,q均为素数时,则
对于互素的a和n,有
RSA算法的实现
1. 密钥的产生
①选两个互异的大素数p和q。
②计算n=p×q,φ(n)=(p-1)(q-1),其中φ(n)是n的欧拉函数值。
③选一随机整数e,满足1<e<φ(n),且gcd(φ(n),e)=1。
④计算d,满足d·e≡1 mod φ(n),即d是e在模φ(n)下的乘法逆元,因e与φ(n)互素,由模运算可知,它的乘法逆元一定存在。
⑤以{e,n}为公开钥,{d,p,q}为秘密钥。
2. 加密
加密时首先将明文比特串分组,使得每个分组对应的十进制数小于n,即分组长度小于。然后对每个明文m,作加密运算:
3. 解密
对密文分组的解密运算为:
五、证明RSA算法中解密过程的正确性
设p,q是不同的素数,n=pq记φ(n)=(p-1)(q-1),如果e,d是与φ(n)互素的两个正整数(e,d<φ(n)),并满足ed≡1(mod φ(n)),则对于每个整数x,都有。
分析:为了证明,只要证明φ(n)是的因数即可。又因为n=pq,而p,q都是素数,故只要证明p和q都是的因数即可,即
(1)
(2)
证明:证明式1,若p是x的因数则式1必然成立
若p不是x的因数,则由ed≡1(mod φ(n))得ed-1=k(p-1)(q-1),k为任意整数
则
根据费马小定理
因为x与p互素所以
所以
同理可证
即证
六、RSA算法中的计算问题
RSA的加密、解密过程的运算都为求一个整数的整数次幂,再取模。如果按其含义直接计算,则中间结果非常大,有可能超出计算机所允许的整数取值范围。而用模运算的性质:(a×b) mod n=[(a mod n)×(b mod n)] mod n就可减小中间结果。
例如求,直接计算的话需做15次乘法。然而如果重复对每个部分结果做平方运算即