记一次演讲–RSA密码体制简介

两个月前的演讲,现在才想起来放上来,某些细节已经忘了= =。

用prezi做的演示文稿放上了度盘 密码iad7,有需要可以自行下载。

下面是演示文稿的文字部分,疏漏在所难免,还请大佬在评论区or发邮件sendtoyirabbit@gmail.com斧正!

RSA简介

  • RSA公钥密码算法,它是Rivest,Shamir和Adle man与1978年提出的一个非对称密码体制。
  • 它的安全性依赖于大整数分解的困难性。
  • 到目前为止还不存在威胁RSA本身安全性的多项式时间分解算法,是目前人们最常用的公钥密码算法之一。
RSA的应用背景
  • RSA目前广泛应用于web服务器和浏览器信息安全、Email的安全认证,网上银行的身份认证,信用卡数字证书等多个方面。
  • 同时,他也被作为“工业标准”使用,不少Internet安全协议例如S/MINE,SSL,S/WAN等都引入了RSA加密算法。
  • 除此之外,VISA,IBM,Microsoft等公司协力制定的安全电子交易标准(SET)就采用了标准RSA算法。

标准RSA算法

密钥生成
  1. 随意选择两个大的质数p和q,p不等于q,计算N=pq。
  2. 根据欧拉函数,不大于N且与N互质的整数个数為(p-1)(q-1)。
  3. 选择一个整数e与(p-1)(q-1)互质,并且e小于(p-1)(q-1)。
  4. 用以下这个公式计算d:d× e ≡ 1 (mod (p-1)(q-1))。
  5. 将p和q的记录销毁。

以上得到内容中,(N,e)是公钥,(N,d)是私钥。

加密解密过程

A生成了所需的RSA参数之后,公开(e,N)作为公钥,保留(d,N)作为私钥。如果B需要向发送一条信息给A,他需要将这条消息:

  1. 使用特定的转换规则将这条消息表示成十进制数m(1<m<N).
  2. 利用公钥e和N,计算其加密值C=(N^e)%n.将密文C发送给A.
  3. A收到密文后开始解密,计算解密后的值为s=(m^d)%n.
  4. 使用转化规则将s转化为消息.

RSA算法效率分析

  1. 模指数运算需要使用“平方乘”算法
  2. 计算m^e mod N,先以二进制的形式表示e
  3. 设置初始值x=1,y=m,使用迭代的方法计算:
    1) 如果ei(e的第i位)=1,return x=x*y mod N
    2) 如果i<n-1,那么return y=y^2 mod N
  • 平方的次数取决于e的比特长度
  • 乘积的次数取决于e的二进制表示中“1”的个数

每一次乘积或平方都可以在c*n^2时间内完成,
∴整个算法的运算时间至多是2*bitsize(e)*cn^2<=2cn^3

特殊的RSA密码算法

使用小加密指数的RSA
  • 加密指数e很小的RSA普遍运用于日常生活中。
  • e=3或者e=2^16+1是最常见的选择。

例如:
e=3的时候,加密过程只需要做两次乘法和一次平方。
e=2^16+1的时候,只需要做两次乘法和16次平方就可以完成加密运算。

  • 一个随机选择的e(假设n是1024-bit)则大约需要1000次
使用小解密指数的RSA
  • 应用上的即时性:智能芯片的使用
  • 选取较短长度的解密密钥d
    根据扩展欧几里得算法计算出相应的加密密钥e。
    –>平方乘算法耗时减少
基于中国剩余定理的RSA(CRT-RSA)
  • 存在两个互素的整数r和s
  • 已知两个整数a1和a2使得x≡a1 mod r,x≡a2 mod s
    ->则存在唯一的x<r*s同时满足以上两个等式。
  • 使用这里的CRT指数dp=d mod(p-1)和dq=d mod(q-1),
  • 根据中国剩余定理合并mp≡c^dp mod p和 mq=c^dq mod q
    –>m
  • 运行时间:
    总共需要的平方和乘法的次数和标准RSA一样
    平方运算和乘法运算至多只需要1/4 *cn^2
    耗时 1/4

标准RSA算法的安全性

  • 迄今不存在多项式时间的破解算法
  • 一般数域筛选法(指数级的算法)

攻击RSA分析

攻击RSA体系的分析
  • 直接分解RSA模数的方法在实际中可行性非常低
  • 直接分解–>指数时间
  • 已知额外的信息–>可能多项式时间
  • 特殊的RSA密码算法–>暴露某些信息+使用者泄露/攻击者其他手段得到部分密钥–>多项式时间分解RSA模数

针对RSA具体实现的攻击方法

选择密文攻击
  • 攻击者可以任意创造一条明文,并得到其加密后的密文:比如用一定的手段渗透发信息者A的系统,但是不能直接攻破秘钥,于是只能以她的身份发信息,然后用抓包或者别的方法得到她发送出来的加密的消息
  • 攻击者还可以选择密文,并得到特定密文解密后的明文:用一定的手段在通信过程中伪造消息替换真实消息,然后窃取获得解密的结果,透过未知的密钥获得解密后的明文。由此能够计算出加密者的私钥或者分解模数。
实例

密文接受者为T,公钥对为(e, n),私钥为d,T收到的密文为c,c对应的明文为m。
现在A想知道m = c^d mod n,但是他不想分解n。于是A找了一个随机数r,r < n。他进行如下计算:
1.x = r^e mod n (对r用T的公钥加密,得到临时密文x)
2.y = (x * c) mod n (将临时密文x与密文c相乘)
3.t = r^(-1) mod n
如果x = r^e mod n,那么 r = x^d mod n
现在A要做的是使T用d对t签名:u = t^d mod n。A需要获得u,然后计算:m = (t * u) mod n

t *u mod n = [r^(-1) * y^d] mod n
= [r^(-1) * x^d * c^d] mod n
= c^d mod n
= m

RSA循环攻击
  1. 攻击者已知某个密文 c (c =m^e mod N),
  2. 循环计算, 即计算 c^e mod N , c^e2 mod N , c^e3 mod N , …
  3. 由于 c^e i mo d N ∈{0 , 1 , …, N -1},因此经有限步 后, c必然再次出现.
  4. 不妨设c^e k mod N =c ,则 c^e k -1 mod N 即为明文m
缺陷:
  1. 若 p -1 和 q -1 都有大素因子,则上述循环攻击方法极不容易成功 .
  2. 若 p 和q 是随机选择的具有相同比特长度的素数 ,则循环攻击方法成功时平均需要穷举的次数至少为
    N^1/6 .
RSA共模攻击

大前提:RSA体系在生成密钥的过程中使用了相同的模数n

Leader首先生成了两个大质数P,Q,取得PQ乘积N。并且以N为模数,生成多对不同的公钥及其相应的私钥。Leader将所有公钥公开。而不同的成员获得自己的私钥,比如,成员A获得了私钥d1.成员B获得了私钥d2.
现在,Leader将一条相同的消息,同时经过所有公钥加密,发送给所有成员。
作为攻击者,同时监听了A和B接收到的密文C1,C2,因为模数不变,以及所有公钥都是公开的,那么利用共模攻击,他就可以在不知道d1,d2的情况下解密得到消息m。

首先假设,e1,e2互质,即gcd(e1,e2)=1
此时则有e1*s1+e2*s2 = 1
式中,s1、s2皆为整数,但是一正一负。
通过扩展欧几里德算法,我们可以得到该式子的一组解(s1,s2)
假设s1为正数,s2为负数.
因为c1 = m^e1%n c2 = m^e2%n
所以
(c1^s1*c2^s2)%n = ((m^e1%n)^s1*(m^e2%n)^s2)%n
根据模运算性质,可以化简为
(c1^s1*c2^s2)%n = ((m^e1)^s1*(m^e2)^s2)%n

(c1^s1*c2^s2)%n = (m^(e1^s1+e2^s2))%n
又前面提到
e1*s1+e2*s2 = 1
所以
(c1^s1*c2^s2)%n = (m^(1))%n
(c1^s1*c2^s2)%n = m%n

c1^s1*c2^s2 = m
所以当n不变的情况下,知道n,c1,c2 可以在不知道d1,d2情况下,解出m。

侧信道攻击

针对加密电子设备在运行过程中的时间消耗、功率消耗或电磁辐射之类的侧信道信息泄露而对加密设备进行攻击

攻击方法:

  1. 功耗分析
  2. 电磁场分析
  3. 时间分析

硬件在进行加密时进行的模指数运算是一个比特一个比特进行的,而为比特位1进行的运算要比比特位0进行的运算要多得多,因此若能得到多组消息与其加密时间,就有可能反推出私钥的内容。

左侧峰值是在运行RSA迭代中没有乘法的部分时处理器的功率,右侧则是在乘法步骤中处理器的功率。

总结

使用RSA的建议
  1. 768位的模数N可以被分解,1024位的RSA模数开始被认为可能是不安全的,故在相当重要的信息传递时,可以选择2048位的模数。
  2. 设计不同的素数生成方案,使得团体内的每一位用户获得不同的大素数消除用户共模,避免共模攻击。
  3. e不要选得过小,特别是e=3的情况,容易被小指数攻击所攻破。
参考文献

1.RL Rivest, A Shamir, L Adleman.A method for obtaining digital signatures and public-key cryptosystems– Communications of the ACM, 1978
2.Don Coppersmith.Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities,1997
3.李世晓 RSA算法的攻击与防范
4.石梦 LLL算法在RSA安全性分析中的应用

发表评论

电子邮件地址不会被公开。 必填项已用*标注