北京交通大学密码学第9-10章公钥密码1.ppt

* * * * * * * * * * * * * * 可见寻找大素数是一个比较繁琐的工作。 然而在RSA体制中，只有在产生新密钥时才需执行这一工作。 p和q决定出后，下一个需要解决的问题是如何选取满足1eφ(n)和gcd(φ(n),e)=1的e，并计算满足d·e≡1 mod φ(n)的d。这一问题可由推广的Euclid算法完成。 * * * * * * * * * * * * * * * 对RSA的小解密指数攻击 使用较小的d会产生穷尽解密攻击的可能 当d为n的1/4长度时，而e小于n时，可以恢复d， 当e,d是随机选择时，这种情况很少发生，当e 很小时不会发生。 注意：应选择一个大的d值 计时攻击 是Paul Kocher 在1996年证明，攻击者可以通过记录解密消息所用的时间来确定私钥。 由前边的模幂算法可知，RSA算法中的模幂运算是通过一位一位来实现的，每次迭代之星一次模乘运算，且弱该位为1，则还需要再执行一次模乘运算。 解决方法： 不变的幂运算时间 随机延时 隐蔽：在执行幂运算之前先将密文乘上一个随机数。 * * * * * * * * * * * * * * * 密钥这种； 对称，非对称比较 使用； * * * * * * * * * * * * * * * RSA算法的论证 RSA的安全性是基于加密函数ek(x)=xe(mod n)是一个单向函数，所以对的人来说求逆计算不可行。 而Bob能解密的陷门是分解n=pq，知? (n)=(p-1)(q-1)。从而用扩展的Euclid算法解出解密私钥d。 密码分析者攻击RSA体制的关键点在于如何分解n。若分解成功使n=pq，则可以算出φ(n)＝（p-1)(q-1)，然后由公开的e，解出秘密的d。 猜想：攻破RSA与分解n是多项式等价的。然而，这个猜想至今没有给出可信的证明！！！ 两个问题和两个假设 RSA的安全性是基于RSA假设，而不是基于分解大整数的困难性假定 RSA算法举例 RSA密码体制的实现 实现的步骤如下：Bob为实现者 (1) Bob寻找出两个大素数p和q (2) Bob计算出n=pq和? (n)=(p-1)(q-1). (3) Bob选择一个随机数e(0e ? (n))，满足(e,? (n))=1 (4) Bob使用辗转相除法计算d=e-1(mod ? (n)) (5) Bob在目录中公开n和e作为她的公开钥。 选好这些参数后，将明文划分成块，使得每个明文报文P长度m满足0mn。 加密P时，计算C＝Pe(mod n)，解密C时计算P＝Cd(mod n)。由于模运算的对称性，可以证明，在确定的范围内，加密和解密函数是互逆的。 为实现加密，需要公开(e, n)，为实现解密需要(d, n)。 RSA的加、解密过程示例 RSA的实现——参数选择 为了确保RSA密码的安全，必须认真选择密码参数： ① p和q要足够大： 一般应用：p和q应512b 重要应用：p和q应1024b ② p和q应为强素数 文献指出，只要(p-1)、(p+1)、(q-1)、(q+1)四个数之一 只有小的素因子，n就容易分解。 ③ (p-1)和(q-1)的最大公因子要小 如果(p-1)和(q-1)的最大公因子太大，则易受迭代加密 攻击。 RSA的实现——参数选择 ⑤ e的选择 随机且含1多就安全，但加密速度慢。于是，有的学者 建议取e=216+1=65537 ⑥ d的选择 d不能太小，要足够大 ⑦ 不要许多用户公用一个模n：易受共模攻击 另外两个常用的e的选择是3和17.但是如果e=3。这时加密速度一般比解密速度快10倍以上。但是易受低指数攻击。 注意：密钥产生要求（e, ? (n)）=1，因此如果用户选择了e=65537，接着生成了素数p，q， 很有可能不能满足（e, ? (n)）=1，因此用户应该去掉那些模65537和1不同余的p和q。 RSA实现中的问题 （1）如何计算ab mod n 需要计算模 300 digits (or 1024+ bits) 的乘法 （2）如何判定一个给定的整数是素数？ （3）如何找到足够大的素数p和q ? 其中d是中间结果，d的终值即为所求结果。c在这里的作用是表示指数的部分结果，其终值即为指数m，c对计算结果无任何贡献，算法中完全可将之去掉。 快速加解密 加密很快，指数小 解密比较慢，指数较大 利用中国剩余定理CRT，分别计算mod p和mod q，再组合成所需的 结果。可以加快运算速度，比直接计算M=Cd mod n 相比，速度大约快4倍。 CRT