当前位置：文档之家 › 私钥低比特特定泄露下的RSA密码分析

私钥低比特特定泄露下的RSA密码分析

  • 格式：pdf
  • 大小：846.40 KB
  • 文档页数：14

presented the best result known so far. As for the attacks on RSA with exposed least significant bits of the private key, they are important partial key exposure attacks and closely related to low private exponent attacks. Based on Coppersmith’s method for finding small roots of modular polynomial equations and the technique of unraveled linearization, this paper presents a new attack with exposed least significant bits of the private key. The technique of unraveled linearization arises from Herrmann and May’s elementary proof of Boneh and Durfee’s result of low private exponent attacks. Notice that known attacks with exposed least significant bits of the private key only care about how many bits are exposed, while this paper also cares about what the value of each exposed bit is. Under certain condition for the values of the exposed bits, our result improves the result of Ernst et al. Additionally, Ernst et al. only considers the special case where public exponent is roughly equal to RSA modulus, while this paper further studies the general case where public exponent is less than RSA modulus. Key words: RSA; exposed least significant bits; Coppersmith’s method; lattice; LLL algorithm
f ( x) [ x], 以 及 常 数 X N 1 , 那 么 在 关 于 (log 2 N , 2 ) 的 多 项 式 时 间 内 就 可 找 到 满 足 xห้องสมุดไป่ตู้ X ,
f ( x0 ) 0 mod N 的 所 有 整 数 解 x0 ( 文 献 [4] 的 推 论 1). 双 变 元 整 系 数 方 程 方 面 , 设 不 可 约 多 项 式
密码学报 ISSN 2095-7025 CN 10-1195/TN Journal of Cryptologic Research,2015,2(5):390–403 ©《密码学报》编辑部版权所有.
E-mail: jcr@ Tel/Fax: +86-10-81033101
Abstract: There are many new results of cryptanalysis of RSA based on Coppersmith’s method, which include partial key exposure attacks and low private exponent attacks. With side channel attacks, partial bits of the private key can be exposed, and partial key exposure attacks’ aim is to break RSA from these exposed partial bits. Low private exponent attacks on RSA are those targeting at RSA with small private exponent, and Boneh and Durfee
Cryptanalysis of RSA with Special Exposed Least Significant Bits of the Private Key
WANG Shi-Xiong1, QU Long-Jiang1, LI Chao1,2, FU Shao-Jing2
1. College of Science, National University of Defense Technology, Changsha 410073, China 2. College of Computer Science, National University of Defense Technology, Changsha 410073, China Corresponding author: WANG Shi-Xiong, Email: wsx09@
RSA 密码的应用非常广泛 , 因此密码分析工作也显得十分重要 . 在基于格的 RSA 密码分析中 , Coppersmith 方法起着关键的作用. Coppersmith 方法通过格基约化算法来解决 v 元模多项式方程(或者 v 1
元整系数多项式方程)求小值解的问题. 最初在 1996 年的欧密会上, Coppersmith 得到了 v 1 时关于模多项 式方程、整系数方程的两个结论[2,3], 并在 1997 年总结完善[4]. 单变元模方程方面, 设 次的首一多项式
1
引言
1977 年, 麻省理工学院的 Rivest, Shamir 和 Aldeman 提出了著名的公钥密码算法 RSA[1]. 设 M 为明文,
C 为密文, 则加密过程为 C M e mod N , 解密过程为 M C d mod N . 其中 RSA 模 N 为两个大素数 p, q 的
乘积, 加密指数 e 与解密指数 d 满足 e d 1mod N , 为欧拉函数, 也称 d 为私钥.
p( x, y ) x, y , 为 p x, y 中 x 或者 y 的次数的最大值, W 表示 p xX , yY 中系数的绝对值的最大值,
其中 XYW 2 3 , 那么在关于 (log 2 W , 2 ) 的多项式时间内就可找到满足 x0 X , y0 Y , p x0 , y0 0 的所有 整数解 ( x0 , y0 ) (文献[4]的推论 2). 后来, Howgrave-Graham[5]与 Coron[6]分别在 1997 年与 2004 年改进了
指数攻击. 现实中侧信道攻击能够泄露私钥的部分比特位, 而部分私钥泄露攻击正是通过泄露的这些比特 位来实现对 RSA 密码的破解. 低解密指数攻击则是在解密指数取值较小的条件下来破解 RSA, Boneh 和 Durfee 给出了至今最好的结果. 针对私钥最低几位比特泄露的攻击, 是一类重要的部分私钥泄露攻击, 并 且和低解密指数攻击紧密相关. 基于 Coppersmith 方法在模多项式方程求小值解的应用, 以及线性化模方 程的技巧 , 本文给出了新的针对私钥最低几位比特泄露的攻击结果 . 其中线性化模方程的技巧 , 来源于 Herrmann 和 May 对于 Boneh 和 Durfee 的低解密指数攻击结果的简化证明. 注意到目前针对私钥最低几位 比特泄露的攻击只关注所泄露比特的位数, 而本文还关注所泄露比特的取值. 当所泄露比特的取值满足一 定的条件时, 本文的结果改进了 Ernst 等人的攻击结果. 另外 Ernst 等人只考虑了加密指数与 RSA 模基本相 等的特殊情况, 本文进一步研究了加密指数小于 RSA 模的一般情况. 关键词: RSA; 最低几位比特泄露; Coppersmith 方法; 格; LLL 算法 文献标识码: A DOI: 10.13868/ki.jcr.000088 中图法分类号: TP918
* 基金项目 : 国家自然科学基金 (61272484,11531002); 国防科技大学科研计划项目 (CJ13-02-01); 湖南省自然科学基金 (13JJ4005) 收稿日期: 2015-04-27 定稿日期: 2015-09-09
王世雄 等: 私钥低比特特定泄露下的 RSA 密码分析
391
中文引用格式: 王世雄, 屈龙江, 李超, 付绍静. 私钥低比特特定泄露下的 RSA 密码分析[J]. 密码学报, 2015, 2(5): 390–403. 英文引用格式: Wang S X, Qu L J, Li C, Fu S J. Cryptanalysis of RSA with special exposed least significant bits of the private key[J]. Journal of Cryptologic Research, 2015, 2(5): 390–403.
私钥低比特特定泄露下的 RSA 密码分析*

王世雄 1, 屈龙江 1, 李 超 1,2, 付绍静 2
1. 国防科学技术大学 理学院, 长沙 410073 2. 国防科学技术大学 计算机学院, 长沙 410073
通讯作者: 王世雄, E-mail: wsx09@
摘
要:
基于 Coppersmith 方法, RSA 密码分析取得了许多新结果, 其中包括部分私钥泄露攻击与低解密
Coppersmith 这两个结论的证明方法, 并为学者们广泛应用于 RSA 密码分析中. 一般来说, Coppersmith 方

合集下载

rsa算法基本原理

rsa算法基本原理

rsa算法基本原理RSA算法基本原理RSA是一种非对称加密算法，它的基本原理是利用大素数的因数分解困难性来实现加密和解密的过程。

RSA算法由三个步骤组成：密钥生成、加密和解密。

1. 密钥生成RSA算法中，首先需要生成一对密钥：公钥和私钥。

公钥用于加密数据，私钥用于解密数据。

密钥的生成过程如下：1.1 选择两个大素数p和q，并计算它们的乘积n=p*q。

n的长度决定了RSA算法的安全性。

1.2 计算n的欧拉函数φ(n)=(p-1)*(q-1)。

1.3 选择一个与φ(n)互质的整数e，1 < e < φ(n)。

1.4 计算e关于φ(n)的模反元素d，即满足e*d ≡ 1 (mod φ(n))的整数d，1 < d < φ(n)。

1.5 公钥为(n, e)，私钥为(n, d)。

2. 加密加密过程是指使用公钥对原始数据进行加密的过程。

加密过程如下：2.1 将原始数据转换为整数m，满足0 ≤ m < n。

2.2 计算密文c ≡ m^e (mod n)，即对m进行模n的指数操作。

2.3 密文c即为加密后的数据。

3. 解密解密过程是指使用私钥对密文进行解密的过程。

解密过程如下：3.1 计算明文m ≡ c^d (mod n)，即对密文c进行模n的指数操作。

3.2 明文m即为解密后的数据。

RSA算法的安全性基于大整数的因子分解问题的困难性，因为在当前计算能力下，对于非常大的整数进行因子分解是非常耗时的。

这使得RSA算法在现实应用中具有较高的安全性。

除了加密和解密外，RSA算法还可以用于数字签名和密钥协商等领域。

数字签名是指用私钥对数据进行签名，然后用公钥进行验证，以确保数据的完整性和来源可靠性。

密钥协商是指两个通信方通过交换公钥来协商出一个共享的对称密钥，以便进行后续的加密通信。

总结一下，RSA算法是一种基于大整数的非对称加密算法，利用大素数的因子分解困难性来实现数据的加密和解密。

它的安全性建立在大整数因子分解问题的困难性上，适用于保护数据的机密性、完整性和来源可靠性。

rsa加密算法详解及例题

rsa加密算法详解及例题

RSA加密算法详解及例题
RSA加密算法是一种非对称加密算法，其安全性基于对极大整数做因数分解的困难性。

以下是RSA加密算法的详解及例题：
1. 密钥生成：
* 随机选择两个质数P和Q，越大越安全。

* 计算它们的乘积N=P*Q。

* 计算欧拉函数φ(N)=(P-1)*(Q-1)。

* 随机选择一个整数E，条件是1<E<φ(N)，且E与φ(N)互质。

* 计算E对于φ(N)的模反元素D，使得EDmodφ(N)=1，即D=E-1modφ(N)。

* 公钥为(E, N)，私钥为(D, N)。

2. 加解密过程：
* 加密：明文M进行加密后得到密文C，计算公式为C=MemodN。

* 解密：将密文C进行解密后得到明文M，计算公式为M=CdmodN。

例题：在RSA加密体制中，已知素数P=7，Q=11，公钥E=13，试计算私钥D并给出对明文M=5的加密，求其密文。

解：首先，根据上述算法进行密钥生成。

根据素数P和Q得到N=77。

计算φ(N)=60。

因为E小于φ(N)且与φ(N)互质，选择E=13作为公钥。

根据公式计算D模反元素得到D=7。

现在有公钥(E, N)=(13, 77)和私钥(D, N)=(7, 77)。

接下来，用公钥加密明文M=5得到密文C=5^13mod77=15。

所以，密文为15。

此例题仅展示了RSA加密算法的基本原理和步骤，实际应用中需要考虑更多安全因素和操作细节。

深入浅出RSA在CTF中的攻击套路

深入浅出RSA在CTF中的攻击套路

深⼊浅出RSA在CTF中的攻击套路0x01 前⾔本⽂对RSA中常⽤的模逆运算、欧⼏⾥得、拓展欧⼏⾥得、中国剩余定理等算法不展开作详细介绍，仅对遇到的CTF题的攻击⽅式，以及使⽤到的这些算法的python实现进⾏介绍。

⽬的是让⼤家能轻松解决RSA在CT 0x02 RSA介绍介绍⾸先，我这边就不放冗长的百度百科的东西了，我概括⼀下我⾃⼰对RSA的看法。

RSA是⼀种算法，并且⼴泛应⽤于现代，⽤于保密通信。

RSA算法涉及三个参数,n,e,d，其中分为私钥和公钥，私钥是n,d，公钥是n,en是两个素数的乘积，⼀般这两个素数在RSA中⽤字母p,q表⽰e是⼀个素数d是e模 varphi(n) 的逆元，CTF的⾓度看就是，d是由e,p,q可以求解出的⼀般CTF就是把我们想要获得的flag作为明⽂，RSA中表⽰为m。

然后通过RSA加密，得到密⽂，RSA中表⽰为C。

加密过程c=m^e mod nc=pow(m,e,n)解密过程m=c^d mod nm=pow(c,d,n)求解私钥dd = gmpy2.invert(e, (p-1)*(q-1))⼀般来说，n，e是公开的，但是由于n⼀般是两个⼤素数的乘积，所以我们很难求解出d，所以RSA加密就是利⽤现代⽆法快速实现⼤素数的分解，所存在的⼀种安全的⾮对称加密。

基础RSA加密脚本from Crypto.Util.number import *import gmpy2msg = 'flag is :testflag'hex_msg=int(msg.encode("hex"),16)print(hex_msg)p=getPrime(100)q=getPrime(100)n=p*qe=0x10001phi=(p-1)*(q-1)d=gmpy2.invert(e,phi)print("d=",hex(d))c=pow(hex_msg,e,n)print("e=",hex(e))print("n=",hex(n))print("c=",hex(c))基础RSA解密脚本#!/usr/bin/env python# -*- coding:utf-8 -*-import binasciiimport gmpy2n=0x80b32f2ce68da974f25310a23144977d76732fa78fa29fdcbf#这边我⽤yafu分解了np=780900790334269659443297956843q=1034526559407993507734818408829e=0x10001c=0x534280240c65bb1104ce3000bc8181363806e7173418d15762phi=(p-1)*(q-1)d=gmpy2.invert(e,phi)m=pow(c,d,n)print(hex(m))print(binascii.unhexlify(hex(m)[2:].strip("L")))0x03 p和q相差过⼤或过⼩利⽤条件因为n=p*q其中若p和q的值相差较⼩，或者较⼤，都会造成n更容易分解的结果例如出题如下p=getPrime(512)q=gmpy2.next_prime(p)n=p*q因为p和q⼗分接近，所以可以使⽤yafu直接分解yafu分解使⽤factor(*)括号中为要分解的数在线⽹站分解0x04 公约数分解n利⽤条件当题⽬给的多对公钥n是公⽤了⼀个素数因⼦的时候，可以尝试公约数分解出题⼀般如下p1=getPrime(512)p2=getPrime(512)q=getPrime(512)n1=p1*qn2=p2*q所以当题⽬给了多个n，并且发现n⽆法分解，可以尝试是否有公约数。

rsa算法的原理

rsa算法的原理

rsa算法的原理RSA算法是一种公钥密码算法，它经常被用于信息安全领域中的加密和数字签名等方面，是目前最广泛使用的公钥加密算法之一。

本文将介绍RSA算法的原理，从密钥生成、加密和解密三个方面详细讲解。

一、密钥生成RSA算法是一种基于大素数因子分解的加密方法，其密钥包括公钥和私钥两部分。

公钥由两个参数n和e组成，其中n为两个大质数p和q 的乘积，e为整数且满足1<e<φ(n)且e与φ(n)互质。

私钥由两个参数n和d组成，其中n相同，d为整数，满足ed≡1(modφ(n))，φ(n)=(p-1)(q-1)是欧拉函数。

密钥生成的具体流程如下：1.选取两个不同的大质数p和q，并计算它们的积n=p*q。

2.计算φ(n)=(p-1)*(q-1)。

3.选取一个大于1且小于φ(n)的整数e，使得e与φ(n)互质。

4.使用扩展欧几里得算法计算出d。

具体地，我们需要求出方程ed=k*φ(n)+1的正整数解d。

5.将n和e组成公钥，n和d组成私钥。

二、加密RSA算法的加密过程如下：1.将明文M转化为整数m，确保0 <= m < n。

2.计算密文C = m^e mod n。

其中，C为密文。

三、解密RSA算法的解密过程如下：1.将密文C转化为整数c，确保0 <= c < n。

2.计算明文M = c^d mod n。

当然，在实际应用中还需要考虑信息安全领域常常面临的各种攻击手段，比如重放攻击、中间人攻击等等。

此外，RSA算法的安全性也与密钥长度有关。

通常情况下，我们需要保证密钥长度足够长，这样攻击者才会愈发显得无能为力。

综上所述，RSA算法是一种基于大素数不易分解原理的公钥密码算法。

密钥包括公钥和私钥两部分，其加密和解密过程都依赖于密钥的组成。

在使用时需要注意信息安全问题，并根据具体应用需求确定密钥长度。