RSA-CRT 使用中国剩余定理CRT对RSA算法进行解密

这篇具有很好参考价值的文章主要介绍了RSA-CRT 使用中国剩余定理CRT对RSA算法进行解密。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


前言

使用中国剩余定理对RSA进行解密,可以提高RSA算法解密的速度。
有关数论的一些基础知识可以参考以下文章: 密码学基础知识-数论(从入门到放弃)


一、中国剩余定理(CRT)

设p和q是不同的质数,且n = p*q。对于任意(X1, x2),其中 0 ≤ x1 < p 和 0 ≤ x2 < q,存在数x,其中 0 ≤ x < n。
中国剩余定理给出了以下的一元线性同余方程组:

x1 = x mod p
x2 = x mod q

因此,任何整数x (0 < x< n)都可以在其CRT表示(X1, X2)中唯一表示。

二、欧拉定理

欧拉定理是费马小定理的推广。或称为欧拉-费马定理。
n是一个正整数,a是gcd(a, n) = 1的任意整数,则a^Φ(n) = 1 (mod n)。
Φ(n)是欧拉函数,即不超过n,与n互素的正整数的个数。对于质数p, Φ § = p-1。

三、RSA正常解密流程

RSA算法流程可以参考以下文章: 公钥加密算法-RSA
m = c^d mod n(d是私钥)
为了保证安全性,要求算法中的p和q为512 bit以上长度的素数。在使用RSA算法对密文进行解密时,私钥指数d和模数n的位数一般比较大,计算起来比较困难。
可以使用中国剩余定理和欧拉函数对其进行解密。

根据中国剩余定理可以将 m = c^d mod n写成

m1=c^d mod p
m2=c^d mod q

这个时候n的位数降低了。但是d的位数依旧很大。
为了计算c^d mod p,我们可以使用欧拉定理来降低d的位数

c ^ d mod p = c ^ ( d mod Φ ( p ) ) mod p = c ^ ( d mod (p-1) ) mod p

上面式子证明如下:

d = kφ( p ) + d mod φ( p )(或者d = k(p-1) + d mod ( p-1 ))其中k是一个整数。
c ^ d = c ^( k φ ( p ) + d mod φ( p ) ) = (c ^ φ( p )) ^k * c ^ d mod φ( p )
根据欧拉定理可以得到c ^ φ ( p ) = 1 (mod p)
则c ^ d = 1^k * c ^ d mod φ( p ) = c ^ d mod φ( p ) ( mod p)

同理可得:

c ^ d mod q = c ^ ( d mod Φ ( q ) ) mod q = c ^ ( d mod (q-1) ) mod q

令dP = d mod (p-1) = e^(-1)mod(p-1)
dQ = d mod (q-1) = e^(-1)mod(p-1)
m1 = c^dP mod p
m2 = c^dQ mod q

则RSA的求解过程如下所示:

qInv = q ^ (-1) mod p
h = qInv * ( m1-m2 ) mod p
m = m2 + h*q (m为明文)

最后的求解过程可以写成:

S=CRT(m1,m2)=m2+((m1–m2)(q^(–1)modp) modp)⋅q

上面写的有些乱,可以看下面的图片:
RSA-CRT 使用中国剩余定理CRT对RSA算法进行解密


四、举例如下:

使用中国剩余定理对以下例子进行解密
RSA-CRT 使用中国剩余定理CRT对RSA算法进行解密
计算过程如下:
RSA-CRT 使用中国剩余定理CRT对RSA算法进行解密
参考文章如下: Using the CRT with RSA文章来源地址https://www.toymoban.com/news/detail-443766.html

到了这里,关于RSA-CRT 使用中国剩余定理CRT对RSA算法进行解密的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数论——中国剩余定理、扩展中国剩余定理 学习笔记

    中国剩余定理(Chinese Remainder Theorem,CRT) 求解如下形式的一元线性同余方程组(其中 (m) 两两互质): $left{begin{matrix}x equiv a_1 pmod {m_1} \\\\x equiv a_2 pmod {m_2} \\\\ dots \\\\x equiv a_k pmod {m_k}end{matrix}right.$ 计算所有模数的积 (M = prod m_i) ; 对于第 (i) 个方程: 计算: (M_i

    2024年02月08日
    浏览(37)
  • 「学习笔记」(扩展)中国剩余定理

    有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何? 该问题出自《孙子算经》,具体问题的解答口诀由明朝数学家程大位在《算法统宗》中给出: 三人同行七十希,五树梅花廿一支,七子团圆正半月,除百零五便得知。 (2 times 70 + 3 times 21 + 2 times

    2024年02月06日
    浏览(31)
  • RSA算法习题 (采用RSA算法,其中e=7,p=11,q=13,求出公钥和私钥,并求出明文85进行加密后的密文。)

    1、采用RSA算法,其中e=7,p=11,q=13,求出公钥和私钥,并求出明文85进行加密后的密文。 2. 找出质数 P、Q P=11 Q=13 3. 计算公共模数 N = P * Q = 143 4. 欧拉函数 Φ(N) = (P-1)*(Q-1) = 10 *12 = 120 5. 计算公钥E 1Eφ(N) 所以1E120 E的取值范围{3,7,9,11,13,17,19,...,117,119} E的取值必须和φ(N)互质 取

    2024年02月09日
    浏览(88)
  • postman使用RSA进行加密

    在接口测试或者性能测试中,经常会遇到要对数据进行加密的情况。本文主要介绍的是利用RSA加密的情况。其中引用的加密代码来自互联网,不知是哪位大牛分享的,在此表示感谢! 本文采用的方案是使用第三方模块forge.js来实现加密。 git作用:下载forge.js的源码 node作用:

    2024年02月16日
    浏览(33)
  • 若依ruoyi前端vue使用jsencrypt.js加密后端java进行RSA解密(前后端交互RSA加解密)

    目录 1、前后端RSA加解密实现思路 2、前端 3、后端 按照约定来说公钥一般用来加密,大家都可以获取得到,私钥用来解密,当然你也可以混着用,以下示例是前端通过加密,后端解密.  -----BEGIN PUBLIC KEY----- MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ81AMIIBCgKCAQEA1+05vAf7m5NcLNLkRtsm gp+QdzcW6MVdayGTGBJG0v

    2024年02月06日
    浏览(70)
  • Python(30):非对称加密算法RSA的使用(openssl生成RSA公私钥对)

    1.1、生成RSA公私钥对命令 1.2、公钥 -----BEGIN PUBLIC KEY----- MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCfNHu9aoeNUTAZH3GCP2CQaSOg XNx0tImsIaCWBEQK3/fvUx8f17hIOtttCMrrTPWefUdcUxLIZ+xzqeU/eISsz9Ym kguImd1+bMkGIYiHBKmF5Uww2jGSU738c+AUuRKpixZP+VPekLY+KbOH7NkE2U/L XGbDeMXeiqQ22UmOSQIDAQAB -----END PUBLIC KEY----- 1.3、私钥 -----BEGIN RSA PRIVATE KEY--

    2024年02月03日
    浏览(40)
  • 使用RSA密钥交换和密码验证进行安全的stelnet远程登录配置实验(华为ensp实现)

    配置R1与R3之间的RSA密钥交换,使得R1可以通过stelnet方式安全地访问R3。 配置R2通过使用密码登录,使得R2可以通过stelnet方式安全地访问R3。 了解了RSA密钥交换和密码验证方式在实际中的应用,加深了对这些知识点的理解。 设备:ensp下的路由器R1,R2,R3和交换机。 连接:R1的

    2024年02月04日
    浏览(54)
  • 前端js使用jsrsasign,生成RSA秘钥,获取一系列信息(公钥,私钥,模数,指数等)进行加密解密

    前言: 之前的项目里用的RSA加解密的时候是生成固定的公钥(模数,指数)和私钥放在代码里进行数据的解密。现在要修改成前端自己生成(模数和指数)传给后台。后台加密数据返回给我。我在用私钥解密。 后面查了很多,开始的window.crypto里的方法可以生成公钥和私钥,

    2024年02月16日
    浏览(75)
  • 从加密到签名:如何使用Java实现高效、安全的RSA加解密算法?

    目录 1. 接下来让小编给您们编写实现代码!请躺好 ☺ 1.1 配置application.yml文件 1.2 RSA算法签名工具类 1.3  RSA算法生成签名以及效验签名测试 1.4 RSA算法生成公钥私钥、加密、解密工具类 1.5 RSA算法加解密测试 我们为什么要使用RSA算法来进行加解密?  RSA 加密算法是一种非对

    2024年02月12日
    浏览(52)
  • vue前端对密码进行Rsa加密

    在信息技术发达的信息化世界,我们的敏感信息在各个平台都已进行注册使用。例如我们支付宝的支付密码、微信的支付密码、电子银行的登陆密码、我们的个人身份信息等等都会被不法分子利用。为了保障我们的身份不被暴露以及账户财产安全,研发人员使用了很多加密算

    2024年02月13日
    浏览(62)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包