利用中国剩余定理加速 RSA

admin 2022年8月24日02:45:03CTF专场评论13 views1435字阅读4分47秒阅读模式
RSA 作为世界上使用最为流行的公钥密码算法,被广泛应用在数据加密和数字签名上。为了提高加密和签名验证的效率,一般会将RSA的加密指数设置的较小,一般为 65537 ,而解密或签名效率却不能够简单的通过减小私钥的长度来实现,因为过短的私钥将直接导致安全问题。于是乎,基于中国剩余定理(Chinese Remainder Theorem,简称 CRT)的 RSA 加速方案被提出。以RSA加解密为例,本文将首先讲解 RSA 基本原理,再介绍中国剩余理论和费马小定理,最后介绍 RSA-CRT算法。

1. RSA 算法流程

RSA 包括密钥生成算法和加解密算法。

1.1 RSA 密钥生成

  1. 随机选取两个大的素数
  2. 计算模数
  3. 计算 的欧拉函数,
  4. 选取加密模式 , 满足 并且 与   互质。
  5. 计算私钥 关于 的模逆,
  6. 确认公钥 , 私钥 .

1.2 RSA 加密与解密

假设待加密消息为 , 对 使用 RSA 加密流程如下:

  1. 计算
  2. 得到密文 , 由于公钥公开,私钥不公开,所以任何主体都能够使用公钥进行加密。但只有拥有私钥的情况下能够对 解密。

假设待解密消息为 , 对 使用 RSA 解密流程如下:

  1. 计算
  2. 得到明文 .

1.3 RSA 数字签名与验证

数字签名与加密恰恰相反,由于任何主体都能够验证签名串的正确性,而只有私钥拥有者才能够生成签名串。假设待签名消息为 , 由于签名仅为了证明签名主体的行为,所以为了加快签名效率,首先对 提取数字摘要,比如使用 SHA256 等哈希算法得到数字摘要 ,对 进行签名,流程如下:
  1. 计算数字摘要
  2. 计算
  3. 得到签名串
假设待验证签名息为 , 消息为 , 对 使用 RSA 签名验证流程如下:
  1. 计算
  2. 计算数字摘要
  3. 对比 则验证通过,否则不通过。

2. 中国剩余定理

中国剩余定理(Chinese Remainder Theorem,简称 CRT) 主要讲的是数论中的一个关于一元线性同余方程组的定理。说明了一元线性同余方程组有解的准则以及求解方法。由于一元线性同余方程组问题最早出现于我国的《孙子兵法》中,原文为:“有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?”。所以被称为中国剩余定理。
CRT描述的一元线性同余方程组一般形式如下:

假设 两两互质,则对任意的整数: 方程组组有解,并且通解可以用如下方式构造得到:
  1. 是整数 的乘积,并设 .
  2. 的逆,也就是说:
  3. 方程组的通解形式为:,并且在模  的情况下,方程组只有一个解

3. 欧拉定理及费马小定理

在数论中,欧拉定理也叫做费马-欧拉定理,是一个关于同余的性质。欧拉定理表明,若 为正整数,且 互素(即 gcd() = 1), 则

为欧拉函数,而费马小定理实际上说的是在欧拉定理的基础上,如果 是一个质数,那么

4. RSA-CRT

前文提到,由于RSA密钥中的 很大,导致在解密时的计算开销很大。令 表示明文, 表示密文, 表示 RSA 算法的模, 表示私钥。由于 太大以至于计算开销很大,为了简化计算,就要考虑是否存在别的方案来构造 ,而不是直接对 进行幂运算。
现假设 ,  假定其中 已知, 未知,根据 CRT ,可以得到 的通解,并且在模 的意义下, 只有一个解,这个解就是我们要得到的 . 通过上述分析可以知道的是,只要知道 , 使用 CRT 通解方程,就能够轻松得到
在未知 的情况下,如何计算 呢。这里以 为例,推导过程如下:

因为 ,  所以

改写成 。所以

再根据费马小定理,可知  ,  所以

最后得到

同理得到。
不难发现, 的计算难度要比 的计算容易很多, 在长度上是一般是 的关系。
计算得到 以后,再根据 CRT 算法,就可以很快的计算出 ,根据下列公式

       

原文始发于微信公众号(山石网科安全技术研究院):利用中国剩余定理加速 RSA

特别标注: 本站(CN-SEC.COM)所有文章仅供技术研究,若将其信息做其他用途,由用户承担全部法律及连带责任,本站不承担任何法律及连带责任,请遵守中华人民共和国安全法.
  • 我的微信
  • 微信扫一扫
  • weinxin
  • 我的微信公众号
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2022年8月24日02:45:03
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出):
                  利用中国剩余定理加速 RSA http://cn-sec.com/archives/1249672.html

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: