欧博allbet网址:RSA遇上中国剩余定理

admin 5个月前 (07-06) 科技 54 0

1.Introduction

最近读论文恰好用到了这个,之前只是有耳闻,没有仔细研究过,这里就好好捋一下,会逐步完善

不外貌似CRT(中国剩余定理)的实现更容易被攻击

2. RSA: Overview

rsa算法形貌如下:

  1. 选择两个大素数\(p、q\),盘算\(N = p*q\)(最好保证N在2048bit以上,最新的研究工作已经可以乐成剖析762bit的N)

  2. 盘算\(\phi(N)=(p-1)*(q-1)\)

  3. 选择一个\(e\)使得\(gcd(e, \phi(n)) == 1\),e由于是作加密使用,故推荐使用小值,推荐使用3、65537(\(2^{16}+1\)),65537只有两个1bit,所以在幂运算(加入我的另一篇博客:快速指数算法)时只需要两次分外的乘法运算;此外,不需要忧郁使用固定值会造成的安全问题,RSA的安全性不会受影响

  4. 盘算\(ed = 1 (\mod\phi(n))\),获得\(d\)值用于解密

  5. 公钥:(N, e),私钥:(N, d)

  6. 一次RSA加解密:

    \[c = m^e \mod N\\ m = d^d \mod N\\ \]

  7. 注释:

    \(m = (m^e)^d = m^{1\mod\phi(N)}=m^{h*\phi(N)+1}\mod N\)

    由欧拉定理\(a^{\phi(n)}=1 \mod n\),获得前式等价于

    \(1^h*m^1 = m\)

3. Using CRT

3.1 中国剩余定理

形貌起来对照贫苦,见中国剩余定理,可以把大模数变小模数

3.2 在RSA中使用CRT

RSA中盘算耗时最大的地方是解密的\(c^d\)操作,由于d值往往较大,故盘算难度较高,可以使用中国剩余定理适当降低盘算量。

盘算私钥

下面几部分会被预盘算并存入私钥:

  • \(p、q\)
  • \(dp = d \mod {p-1}\)
  • \(dq = d \mod {q-1}\)
  • \(q_{inv} = q^{-1} \mod p\)

这样最后的私钥就是\((p,q,d,dp,dq,q_{inv})\)

解密

  • \(m_1 = c^{dp} \mod p\)
  • \(m_2 = c^{dq} \mod q\)
  • \(h = q_{inv}(m_1-m_2)\mod p\)
    • \(m_1<m_2\)时,有些实现会这样盘算\(h = q_{inv}[(m_1+\lceil{\frac{q}{p}}\rceil p)-m_2]\mod p\)
  • \(m = m_2+hq \mod {p*q}\)

这样做虽然要盘算两次模幂,但效率依然要比直接盘算高得多。由于不管是指数照样模数都要小得多

4. 列几个常见的算法库

  • Botan
  • Bouncy Castle
  • cryptlib
  • Crypto++
  • Libgcrypt
  • Nettle
  • OpenSSL
  • wolfCrypt
  • GnuTLS
  • mbed TLS
  • LibreSSL

5 Reference

  • RSA (cryptosystem)
,

欧博亚洲电脑版下载

欢迎进入欧博亚洲电脑版下载(Allbet Game):www.aLLbetgame.us,欧博官网是欧博集团的官方网站。欧博官网开放Allbet注册、Allbe代理、Allbet电脑客户端、Allbet手机版下载等业务。

Sunbet声明:该文看法仅代表作者自己,与本平台无关。转载请注明:欧博allbet网址:RSA遇上中国剩余定理

网友评论

  • (*)

最新评论

标签列表

    文章归档

      站点信息

      • 文章总数:663
      • 页面总数:0
      • 分类总数:8
      • 标签总数:1110
      • 评论总数:241
      • 浏览总数:11658