技术流丨RSA算法原理

admin 2022年6月11日01:33:09CTF专场评论5 views5017字阅读16分43秒阅读模式
技术流丨RSA算法原理


1

互质关系


如果两个正整数,除了1以外,没有其他公因子,我们就称这两个数是互质关系(coprime)。关于互质关系,不难得到以下结论:

任意两个质数构成互质关系,比如13和61。

数是质数,另一个数只要不是前者的倍数,两者就构成互质关系,比如3和10。

果两个数之中,较大的那个数是质数,则两者构成互质关系,比如97和57。

1和任意一个自然数是都是互质关系,比如1和99。

p是大于1的整数,则p和p-1构成互质关系,比如57和56。

p是大于1的奇数,则p和p-2构成互质关系,比如17和15

技术流丨RSA算法原理



2

欧拉函数


在数论中,对正整数n,欧拉函数是小于n的正整数中与n互质的数的数目。

φ(n) 的计算方法:

第一种情况如果n=1,则 φ(1) = 1 。因为1与任何数(包括自身)都构成互质关系。

第二种情况如果n是质数,则 φ(n)=n-1 。因为质数与小于它的每一个数,都构成互质关系。比如5与1、2、3、4都构成互质关系。

第三种情况如果n是质数的某一个次方,即 n = p^k (p为质数,k为大于等于1的整数),则

技术流丨RSA算法原理

第四种情况如果n可以分解成两个互质的整数之积,

n = p1 × p2

φ(n) = φ(p1p2) = φ(p1)φ(p2)

即积的欧拉函数等于各个因子的欧拉函数之积。

五种情况因为任意一个大于1的正整数,都可以写成一系列质数的积。

技术流丨RSA算法原理

根据第4条的结论,得到

技术流丨RSA算法原理

再根据第3条的结论,得到

技术流丨RSA算法原理

也就等于

技术流丨RSA算法原理

技术流丨RSA算法原理



3

欧拉定理


欧拉定理指的是:如果两个正整数a和n互质,则n的欧拉函数 φ(n) 可以让下面的等式成立:
技术流丨RSA算法原理
也就是说,a的φ(n)次方被n除的余数为1。或者说,a的φ(n)次方减去1,可以被n整除。欧拉定理有一个特殊情况。假设正整数a与质数p互质,因为质数p的φ(p)等于p-1,则欧拉定理可以写成
技术流丨RSA算法原理
这就是著名的费马小定理。它是欧拉定理的特例。欧拉定理是RSA算法的核心。理解了这个定理,就可以理解RSA。
技术流丨RSA算法原理



4

模反元素


如果两个正整数a和n互质,那么一定可以找到整数b,使得 ab-1 被n整除,或者说ab被n除的余数是1。

技术流丨RSA算法原理
这时,b就叫做a的"模反元素"。欧拉定理可以用来证明模反元素必然存在。
技术流丨RSA算法原理
可以看到,a的 φ(n)-1 次方,就是a的模反元素。
技术流丨RSA算法原理


5

密钥生成步骤


第一步:机选择两个不相等的质数p和q。选择61和53。(实际应用中,这两个质数越大,就越难破解。
第二步:计算p和q的乘积n。把61和53相乘。n = 61×53 = 3233,n的长度就是密钥长度。3233写成二进制是110010100001,一共有12位,所以这个密钥就是12位。实际应用中,RSA密钥一般是1024位,重要场合则为2048位。
第三步:计算n的欧拉函数φ(n)。根据公式:
φ(n) = (p-1)(q-1)
算出φ(3233)等于60×52,即3120。
第四步:随机选择一个整数e,条件是1< e < φ(n),且e与φ(n) 互质。在1到3120之间,随机选择17。(实际应用中,常常选择65537。
第五步:计算e对于φ(n)的模反元素d。所谓"模反元素"就是指有一个整数d,可以使得ed被φ(n)除的余数为1。
ed ≡ 1 (mod φ(n))
这个式子等价于
ed - 1 = kφ(n)
于是,找到模反元素d,实质上就是对下面这个二元一次方程求解。
ex + φ(n)y = 1
已知 e=17, φ(n)=3120,
17x + 3120y = 1
这个方程可以用"扩展欧几里得算法"求解,此处省略具体过程。总之,算出一组整数解为 (x,y)=(2753,-15),即 d=2753。
至此所有计算完成。
第六步:将n和e封装成公钥,n和d封装成私钥。
在例子中,n=3233,e=17,d=2753,所以公钥就是 (3233,17),私钥就是(3233, 2753)。实际应用中,公钥和私钥的数据都采用ASN.1格式表达。
技术流丨RSA算法原理


6

加密和解密


有了公钥和密钥,就能进行加密和解密了。

(1)加密要用公钥 (n,e)
假设发送加密信息m,就要用公钥 (n,e) 对m进行加密。这里需要注意,m必须是整数(字符串可以取ascii值或unicode值),且m必须小于n。
所谓"加密",就是算出下式的c:
技术流丨RSA算法原理
公钥是 (3233, 17),m假设是65,那么可以算出下面的等式:
技术流丨RSA算法原理
于是,c等于2790,就把2790发出。
(2)解密要用私钥(n,d)
拿到发来的2790以后,就用私钥(3233, 2753) 进行解密。可以证明,下面的等式一定成立:
技术流丨RSA算法原理
也就是说,c的d次方除以n的余数为m。现在,c等于2790,私钥是(3233, 2753),那么算出
技术流丨RSA算法原理
因此,加密前的原文就是65。至此,"加密--解密"的整个过程全部完成。
我们可以看到,如果不知道d,就没有办法从c求出m。而前面已经说过,要知道d就必须分解n,这是极难做到的,所以RSA算法保证了通信安全。
公钥(n,e) 只能加密小于n的整数m,那么如果要加密大于n的整数,该怎么办?有两种解决方法:一种是把长信息分割成若干段短消息,每段分别加密;另一种是先选择一种"对称性加密算法"(比如DES),用这种算法的密钥加密信息,再用RSA公钥加密DES密钥。


私钥解密的证明
最后我们来证明,为什么用私钥解密,一定可以正确地得到m。也就是证明下面这个式子
技术流丨RSA算法原理
因为,根据加密规则
技术流丨RSA算法原理
于是,c可以写成下面的形式
技术流丨RSA算法原理
将c代入我们要证明的那个解密规则
技术流丨RSA算法原理
它等同于求证
技术流丨RSA算法原理
由于
技术流丨RSA算法原理
所以
技术流丨RSA算法原理
将ed代入:
技术流丨RSA算法原理


接下来,分成两种情况证明上面这个式子。
(1)m与n互质。
根据欧拉定理,此时
技术流丨RSA算法原理
得到
技术流丨RSA算法原理
原式得到证明。
(2)m与n不是互质关系。
此时,由于n等于质数p和q的乘积,所以m必然等于kp或kq。
以 m = kp为例,考虑到这时k与q必然互质,则根据欧拉定理,下面的式子成立:
技术流丨RSA算法原理
进一步得到
技术流丨RSA算法原理
技术流丨RSA算法原理
将它改写成下面的等式
技术流丨RSA算法原理
这时t必然能被p整除,即 t=t'p
技术流丨RSA算法原理
因为 m=kp,n=pq,所以
技术流丨RSA算法原理
原式得到证明。
技术流丨RSA算法原理


7

互质关系实例题目


/基础算法类

这类题目是RSA的基础题目,往往会给出很多已知的条件,利用公式求出未知的条件,所以会和基础的算法关系比较密切。

比如题目给出了p、q、e的值,求出d,可以把已知的条件带入到基本的公式中,知道了p、q就可以利用φn = (p−1) * (q−1) 和n = p * q求出φn和n,那么知道了φn和e就可以根据e * d ≡ 1 (mod φn)求出d。当然求其它的参数也是一样的道理。

题目

已知:

p=447685307 q=2037 e=17 提交flag{d}

解密RSA的题目往往会通过编写python脚本的方式,这道题目脚本为:

import gmpy2from Crypto.Util.number import long_to_bytes,bytes_to_longp=447685307q=2037e=17fn = (p-1)*(q-1)d = gmpy2.invert(e, fn)print(d)

出d的值为

技术流丨RSA算法原理

/SA共模攻击
共模攻击即用两个及以上的公钥(n,e)来加密同一条信息m(也就是明文)。
共模攻击利用的最大前提就是在生成密钥的过程中生成了相同的指数n,一般会给出多条加密后的密文。比如:
c1 = pow(m, e1, n)
c2 = pow(m, e2, n)
可以总结为同一密文m,同一指数n,不同的e,而且上式中的e1和e2要互质,gcd(e1,e2)=1。根据扩展欧几里德算法对于不完全为0的整数e1,e2,因为e1和e2互质,所以1是e1,e2的最大公约数。那么一定存在整数 a,b 使得gcd(e1,e2)=ae1+be2。也就是ae1+be2=1,因为e1和e2都是大于1的正整数,所以ae1和be2之间必定有一个为负数,也就是a和b之间必定有一个为负整数。

接下来看一下计算过程,这里会用到模的幂运算公式(同底数幂相乘,底数不变,指数相加。同底数幂相除,底数不变,指数相减。幂的乘方,底数不变,指数相乘)
(a * b) % p = (a % p * b % p) % p
a ^ b % p = ((a % p) ^ b) % p
因为c1 = pow(m, e1, n),可以写作c1 = m^e1%n,那么c2也是这样:c2 = m^e2%n,假设s1、s2皆为整数,s1为正数,s2为负数,将条件带入后得到
(c1^s1*c2^s2)%n = ((m^e1%n)^s1(m^e2%n)^s2)%n
通过上面的幂运算公式可以对公式进行化简
(c1^s1*c2^s2)%n = ((m^e1%n)^s1(m^e2%n)^s2)%n
=((m^e1%n)^s1*(m^e2%n)^s2)%n
=((m^e1)^s1%n*(m^e2)^s2%n)%n   //消掉%n
=((m^e1)^s1*(m^e2)^s2)%n
=((m^(e1*s1)*(m^(e2*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

所以,在相同的m、n,不同的e,进行加密后。在不需要知道d的情况下,是可以进行解密的。这就是RSA共模攻击的运算过程。

题目——
已知如下条件:{6266565720726907265997241358331585417095726146341989755538017122981360742813498401533594757088796536341941659691259323065631249,773}{6266565720726907265997241358331585417095726146341989755538017122981360742813498401533594757088796536341941659691259323065631249,839}
c1=3453520592723443935451151545245025864232388871721682326408915024349804062041976702364728660682912396903968193981131553111537349
c2=5672818026816293344070119332536629619457163570036305296869053532293105379690793386019065754465292867769521736414170803238309535

由题目条件可以得出,第一个大括号和第二个大括号中的第一个大数据是一样的,表示大整数n,后面的773和839表示的是e1和e2,c1和c2也给出了,这就满足了共模攻击的条件,输出m即为flag,以下是解题脚本:

import gmpy2import libnumn=6266565720726907265997241358331585417095726146341989755538017122981360742813498401533594757088796536341941659691259323065631249e1 = 773e2 = 839c1=3453520592723443935451151545245025864232388871721682326408915024349804062041976702364728660682912396903968193981131553111537349c2=5672818026816293344070119332536629619457163570036305296869053532293105379690793386019065754465292867769521736414170803238309535
def rsa_gong_N_def(e1,e2,c1,c2,n): e1, e2, c1, c2, n=int(e1),int(e2),int(c1),int(c2),int(n) s = gmpy2.gcdext(e1, e2) s1 = s[1] s2 = s[2] if s1 < 0: s1 = - s1 c1 = gmpy2.invert(c1, n) elif s2 < 0: s2 = - s2 c2 = gmpy2.invert(c2, n) m = (pow(c1,s1,n) * pow(c2 ,s2 ,n)) % n return int(m)m = rsa_gong_N_def(e1,e2,c1,c2,n)print(m)
可得出值为

技术流丨RSA算法原理

技术流丨RSA算法原理

技术流丨RSA算法原理

原文始发于微信公众号(小草培养创研中心):技术流丨RSA算法原理

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

发表评论

匿名网友 填写信息

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