网络安全原理与技术(第二版) 作者 冯登国 徐静 chapter2c.pptVIP

RSA算法 RSA算法是1978年由R.Rivest, A.Shamir和L.Adleman提出的一种用数论构造的、也是迄今为止理论上最为成熟完善的公钥密码体制，该体制已得到广泛的应用。 素数选取 为了防止敌手通过穷举式方法发现p 和q,这些素数必须从足够大的集合中选取。 现在还没有产生任意大素数的有用技术，通常使用的过程是随机选取一个需要的数量级的奇数并检验这个数是否是素数。 e 和 d 的选取 需要选择一个e 使得 gcd(φ(n),e)=1, 然后计算 d= e-1 mod φ(n) Euclid推广算法可以计算两个整数的最大公约数，并且在gcd是1的情况下，计算出一个整数模另一个整数的逆元。 对RSA实现的攻击 对RSA的具体实现存在一些攻击方法，但不是针对基本算法的，而是针对协议的。 对RSA的攻击－共模攻击 在实现RSA时，为方便起见，可能给每一用户相同的模数n，虽然加解密密钥不同，然而这样做是不行的。 设两个用户的公开钥分别为e1和e2，且e1和e2互素（一般情况都成立），明文消息是m，密文分别是 c1≡me1(mod n) c2≡me2(mod n) 敌手截获c1和c2后，可如下恢复m。用推广的Euclid算法求出满足 re1+se2=1 的两个整数r和s，其中一个为负，设为r。再次用推广的Euclid算法求出c-11，由此得 (c-11)-rcs2≡m(mod n)。 Diffie-Hellman 密钥交换算法的数学基础 公钥密码经典算法 RSA算法 Diffie-Hellman 密钥交换算法 ElGamal加密算法 椭圆曲线密码算法 公钥密码经典算法 RSA算法 Diffie-Hellman 密钥交换算法 ElGamal加密算法 椭圆曲线密码算法 * 在线教务辅导网： 教材其余课件及动画素材请查阅在线教务辅导网 QQ:349134187 或者直接输入下面地址： RSA 算法描述—密钥产生 1. 选两个必威体育官网网址的大素数p和q。 2. 计算n=p×q，φ(n)=(p-1)(q-1),其中φ(n)是n的欧拉函数值。 3. 选一整数e，满足1eφ(n)，且gcd(φ(n),e)=1。 4.计算d，满足d·e≡1 mod φ(n),即d是e在模φ(n)下的乘法逆元，因e与φ(n)互素，由模运算可知，它的乘法逆元一定存在。 5. 以{e,n}为公开钥,{d,n}为秘密钥。 RSA 算法描述—加密 加密时首先将明文比特串分组，使得每个分组对应的十进制数小于n，即分组长度小于log2n。然后对每个明文分组m，作加密运算： c≡me mod n RSA 算法描述—解密 对密文分组的解密运算为： m≡cd mod n 下面证明RSA算法中解密过程的正确性。 证明： 由加密过程知c≡me mod n，所以 cd mod n≡med mod n≡m1 mod φ(n) mod n≡mkφ(n)+1 mod n RSA 算法描述—解密 下面分两种情况： ① m与n互素，则由Euler定理得 mφ(n)≡1 mod n,mkφ(n)≡1 mod n,mkφ(n)+1≡m mod n 即cd mod n≡m。 ② gcd(m,n)≠1， mkφ(n)+1≡m mod n，所以cd mod n≡m。(证毕) RSA 安全性依据 RSA的安全性是基于分解大整数的困难性假定，之所以为假定是因为至今还未能证明分解大整数就是NP问题，也许有尚未发现的多项式时间分解算法。如果RSA的模数n被成功地分解为p×q，则立即获得φ(n)=(p-1)(q-1)，从而能够确定e模φ(n)的乘法逆元d，即d≡e-1 mod φ(n)，因此攻击成功。 RSA 安全性 随着人类计算能力的不断提高，原来被认为是不可能分解的大数已被成功分解。例如RSA-129（即n为129位十进制数，大约428个比特）已在网络上通过分布式计算历时8个月于1994年4月被成功分解，RSA-130 已于1996年4月被成功分解。 RSA 安全性 对于大整数的威胁除了人类的计算能力外，还来自分解算法的进一步改进。使用RSA算法时对其密钥的选取要特别注意其大小。估计在未来一段比较长的时期，密钥长度介于1024比特至2048比特之间的RSA是安全的。 RSA 实现中的问题 1。如何计算abmod n 2。密钥产生 如何计算 abmod n RSA的加密、解密过程都为求一个整数的整数次幂，再取模。如果按其含义直接计算，则中间结果非常大，有可能超出计算机所允许的整数取值