数论的基本知识

• 素数(略)
• 同模
  
  • a mod p = b mod p => a=b mod p(这里的等号表示同模符号,三根横线)
• 模运算的性质(略)
• 最大公约数(gcd)(略)
• 模乘的逆
  
  • a×b mod p = 1 mod p(这里指同模)
• 欧拉函数phi(n)
  
  • φ(n)表示小于n的,与n互质的正整数个数.
  • φ(n)=n-1,当n为素数
  • φ(n)=n(1-1/p1)(1-1/p2)…(1-1/pn),其中n=p1x1p2x2p3x3…pnxn
• 费马小定理及推论(略)
• 欧拉定理
  
  • 对于任意互质的两个数a,n,有

aφ(n)=1 mod n;(同模)
or
aφ(n)+1=a mod n

• 欧拉定理推论
  
  • 对于两个素数p,q以及整数n=pq.数m满足0
    mφ(n)+1 mod n = m(p-1)(q-1)+1 mod n = m mod n;(最后一个指同模)
    (mφ(n))k=mkφ(n)=1 mod n;(同模,其中k为任意整数)
    mkφ(n)+1 mod n = mk(p-1)(q-1)+1 mod n = m mod n;(同模)
    

RSA密钥产生算法

• 取两个大素数p和q;
• 计算n=p×q;
• 计算φ(n)=(p-1)(q-1)
• 计算de=1 mod φ(n);(同模)
  

{以上p,q,d为保密的,私有的,不可公开的,原则上n也是私有的,不过n公开不会有很大的影响,RSA的安全性基于大素数乘积分解的复杂度}
#RSA加密解密过程 * 假定M为明文,C为密文,e为公钥,d为私钥,n为大数,并且M #RSA解密过程证明 关键证明Med mod n = M mod n;
根据密钥产生的过程,ed = 1 mod φ(n)
则 ed = k*φ(n)+1;
根据欧拉定理推论,Med mod n = M mod n;
由于M #RSA使用场景 假设A与B要通信,A为发送方,B为接收方.整个通信过程如下
* B产生生成两个素数p,q,并求n=pq,之后将n公开给A * B选择满足条件的e,并且将e公开给A * B计算满足条件的d * A利用e加密信息,发送给B * B利用d解密信息

RSA的安全性

  对RSA的算法攻击可能有如下四种方式:

• 穷举攻击:这种方法试图穷举所有可能的私钥
  
• 数学攻击:有多种数学攻击方法,它们的实质都是试图分解两个素数的乘积
  
• 计时攻击:这类方法依赖于解密算法的运行时间
  
• 选择密文攻击:这种攻击利用了RSA算法的性质
  

Copyright© by 寒江雪
Date:2016.12.09