RSA算法学习

前言

学点Crypto😋

https://www.ruanyifeng.com/blog/2013/06/rsa_algorithm_part_one.html

https://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html

基础知识

对称加密算法

　　（1）甲方选择某一种加密规则，对信息进行加密；
　　（2）乙方使用同一种规则，对信息进行解密。

由于加密和解密使用同样规则（简称”密钥”），这被称为“对称加密算法”（Symmetric-key algorithm）。

非对称加密算法

加密和解密可以使用不同的规则，只要这两种规则之间存在某种对应关系即可，这样就避免了直接传递密钥。

　　（1）乙方生成两把密钥（公钥和私钥）。公钥是公开的，任何人都可以获得，私钥则是保密的。
　　（2）甲方获取乙方的公钥，然后用它对信息加密。
　　（3）乙方得到加密后的信息，用私钥解密。

数学知识

互质关系

两个正整数，除1以外没有其他的公因子，称这两个数为互质关系(coprime)。如35，37就是互质关系。不是质数也能构成互质关系。

互质关系的结论

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

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

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

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

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

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

欧拉函数

　　任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？（比如，在1到8之中，有多少个数与8构成互质关系？）

计算这个值的方法就叫做欧拉函数，以φ(n)表示。在1到8之中，与8形成互质关系的是1、3、5、7，所以 φ(n) = 4。

欧拉定理

欧拉函数的用处，在于欧拉定理。”欧拉定理”指的是：

如果两个正整数a和n互质，则n的欧拉函数 φ(n) 可以让下面的等式成立：

a的φ(n)次方被n除的余数为1。或者说，a的φ(n)次方减去1，可以被n整除。比如，3和7互质，而7的欧拉函数φ(7)等于6，所以3的6次方（729）减去1，可以被7整除（728/7=104）。

模反元素

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

b就是a的模反元素

　　ab ≡ 1 (mod n)

RSA算法

密钥生成原理

第一步

选择两个不相等的质数p和q（实际中，这两个质数越大越不容易破解）

第二步

令密钥长度n=p*q

第三步

计算欧拉函数φ(n) = (p-1)(q-1)

第四步

随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质

第五步

求模反元素d

ed ≡ 1 (mod φ(n))

也就相当于ed - 1 = kφ(n)

等价于对一个二元一次方程求解，ex + φ(n)y = 1

利用扩展欧几里得算法求解

第六步

封装公钥私钥

公钥 KU = (e, n)
私钥 KR = (d, n)

加解密原理

明文M M^e ≡ C (mod n)
秘文C C^d ≡ M (mod n)

题目练习

攻防世界[简单] 初识RSA

from Crypto.Util.number import bytes_to_long,inverse,getPrime
from flag import flag

m = bytes_to_long(flag)

p = getPrime(1024)
q = getPrime(1024)
n = p*q
print(n)
e = 65537

c = pow(m,e,n)

pq = p*(q-1)
qp = q*(p-1)

print("c=",c)
print("n=",n)
print("pq=",pq)
print("qp=",qp)

'''
c= 8722269075970644434253339592758512788160408912707387632591552130175707843950684315083250494010055435391879036285103810263591951437829414438640307561645721347859659807138051841516634704123100270651976676182059252251162982609391666023674158274992400910869692389001622774140191223807887675081808561012755545464977015973615407965906513878979919700065923364884766974187303774330319143647840846354404070430118235352622445115153298578370521811697710289716188726587743282814946239856766713516166990341116198180068191759095913957606379780234116317390622824096667107736103270907349927467971817639795094030622157581511033950777
n= 10466186506773626671397261081802640650185744558208505628349249045496105597268556020207175016523119333667851114848452038431498926527983706092607207796937431312520131882751891731564121558651246025754915145600686076505962750195353958781726515647847167067621799990588328894365930423844435964506372428647802381074584935050067254029262890188260006596141011807724688556673520261743199388391094490191001701011230322653422314758778116196105077883955436582364267530633358016652912054880813710531145973799193443828969535902856467548523653920307742364119002349899553478815101092655897400295925170383678499125295006364960124859003
pq= 10466186506773626671397261081802640650185744558208505628349249045496105597268556020207175016523119333667851114848452038431498926527983706092607207796937431312520131882751891731564121558651246025754915145600686076505962750195353958781726515647847167067621799990588328894365930423844435964506372428647802381074488896197029704465200125337817646702009123916866455067019234171839614862660036737875747177391796376553159880972782837853473250804807544086701088829096838316550146794766718580877976153967582795248676367265069623900208276878140709691073369415161936376086988069213820933152601453587292943483693378833664901178324
qp= 10466186506773626671397261081802640650185744558208505628349249045496105597268556020207175016523119333667851114848452038431498926527983706092607207796937431312520131882751891731564121558651246025754915145600686076505962750195353958781726515647847167067621799990588328894365930423844435964506372428647802381074475956379708898904933143429835002718457573266164923043251954374464149976302585916538814746811455883837138715445492053610047383292461097590195481556557381952895539341802954749542143253491617052100969586396996063822508764438280468492894012685918249843558593322831683872737943676955669923498182824352081785243246
'''

首先题目没有明确给出p和q，但给出了一些关系

n = p*q
pq = p*(q-1)
qp = q*(p-1)

由前置知识我们知道

φ(n) = (p-1)(q-1)

所以我们同样能求出φ(n)，利用(pq * qp) / n

"""
@Author: C4ry7nk
@Date: 2023/5/9
@Time: 20:35
"""
from Crypto.Util.number import *

c = 8722269075970644434253339592758512788160408912707387632591552130175707843950684315083250494010055435391879036285103810263591951437829414438640307561645721347859659807138051841516634704123100270651976676182059252251162982609391666023674158274992400910869692389001622774140191223807887675081808561012755545464977015973615407965906513878979919700065923364884766974187303774330319143647840846354404070430118235352622445115153298578370521811697710289716188726587743282814946239856766713516166990341116198180068191759095913957606379780234116317390622824096667107736103270907349927467971817639795094030622157581511033950777
n = 10466186506773626671397261081802640650185744558208505628349249045496105597268556020207175016523119333667851114848452038431498926527983706092607207796937431312520131882751891731564121558651246025754915145600686076505962750195353958781726515647847167067621799990588328894365930423844435964506372428647802381074584935050067254029262890188260006596141011807724688556673520261743199388391094490191001701011230322653422314758778116196105077883955436582364267530633358016652912054880813710531145973799193443828969535902856467548523653920307742364119002349899553478815101092655897400295925170383678499125295006364960124859003
pq = 10466186506773626671397261081802640650185744558208505628349249045496105597268556020207175016523119333667851114848452038431498926527983706092607207796937431312520131882751891731564121558651246025754915145600686076505962750195353958781726515647847167067621799990588328894365930423844435964506372428647802381074488896197029704465200125337817646702009123916866455067019234171839614862660036737875747177391796376553159880972782837853473250804807544086701088829096838316550146794766718580877976153967582795248676367265069623900208276878140709691073369415161936376086988069213820933152601453587292943483693378833664901178324
qp = 10466186506773626671397261081802640650185744558208505628349249045496105597268556020207175016523119333667851114848452038431498926527983706092607207796937431312520131882751891731564121558651246025754915145600686076505962750195353958781726515647847167067621799990588328894365930423844435964506372428647802381074475956379708898904933143429835002718457573266164923043251954374464149976302585916538814746811455883837138715445492053610047383292461097590195481556557381952895539341802954749542143253491617052100969586396996063822508764438280468492894012685918249843558593322831683872737943676955669923498182824352081785243246
e = 65537

phi = (pq * qp) // n
print(phi)
//inverse 函数，用于计算模数下的乘法逆元
d = inverse(e, phi)
print(d)
m = pow(c, d, n)
print(long_to_bytes(m))

bageiRSA

import libnum
from Crypto.Util import number
from secret import flag

size = 128
e = 65537
p = number.getPrime(size)
q = number.getPrime(size)
n = p*q

m = libnum.s2n(flag)
c = pow(m, e, n)

print('n = %d' % n)
print('c = %d' % c)

n = 88503001447845031603457048661635807319447136634748350130947825183012205093541
c = 40876621398366534035989065383910105526025410999058860023908252093679681817257

主要是分解出p,q

利用网站

"""
@Author: C4ry7nk
@Date: 2023/5/9
@Time: 20:34
"""
from Crypto.Util.number import *
n = 88503001447845031603457048661635807319447136634748350130947825183012205093541
c = 40876621398366534035989065383910105526025410999058860023908252093679681817257
e = 65537
p = 274539690398523616505159415195049044439
q = 322368694010594584041053487661458382819
phi = (p - 1) * (q - 1)
print(phi)
d = inverse(e, phi)
print(d)
m = pow(c, d, n)
print(long_to_bytes(m))

GUET-CTF2019-BabyRSA

p+q : 0x1232fecb92adead91613e7d9ae5e36fe6bb765317d6ed38ad890b4073539a6231a6620584cea5730b5af83a3e80cf30141282c97be4400e33307573af6b25e2ea
(p+1)(q+1) : 0x5248becef1d925d45705a7302700d6a0ffe5877fddf9451a9c1181c4d82365806085fd86fbaab08b6fc66a967b2566d743c626547203b34ea3fdb1bc06dd3bb765fd8b919e3bd2cb15bc175c9498f9d9a0e216c2dde64d81255fa4c05a1ee619fc1fc505285a239e7bc655ec6605d9693078b800ee80931a7a0c84f33c851740
e : 0xe6b1bee47bd63f615c7d0a43c529d219
d : 0x2dde7fbaed477f6d62838d55b0d0964868cf6efb2c282a5f13e6008ce7317a24cb57aec49ef0d738919f47cdcd9677cd52ac2293ec5938aa198f962678b5cd0da344453f521a69b2ac03647cdd8339f4e38cec452d54e60698833d67f9315c02ddaa4c79ebaa902c605d7bda32ce970541b2d9a17d62b52df813b2fb0c5ab1a5
enc_flag : 0x50ae00623211ba6089ddfae21e204ab616f6c9d294e913550af3d66e85d0c0693ed53ed55c46d8cca1d7c2ad44839030df26b70f22a8567171a759b76fe5f07b3c5a6ec89117ed0a36c0950956b9cde880c575737f779143f921d745ac3bb0e379c05d9a3cc6bf0bea8aa91e4d5e752c7eb46b2e023edbc07d24a7c460a34a9a

根据关系展开得n = (p+1)(q+1) - (p+q+1)

"""
@Author: C4ry7nk
@Date: 2023/5/9
@Time: 21:48
"""
from Crypto.Util.number import *
# n = (p+1)(q+1) - (p+q+1)

p_q = 0x1232fecb92adead91613e7d9ae5e36fe6bb765317d6ed38ad890b4073539a6231a6620584cea5730b5af83a3e80cf30141282c97be4400e33307573af6b25e2ea
p1_q1 = 0x5248becef1d925d45705a7302700d6a0ffe5877fddf9451a9c1181c4d82365806085fd86fbaab08b6fc66a967b2566d743c626547203b34ea3fdb1bc06dd3bb765fd8b919e3bd2cb15bc175c9498f9d9a0e216c2dde64d81255fa4c05a1ee619fc1fc505285a239e7bc655ec6605d9693078b800ee80931a7a0c84f33c851740
e = 0xe6b1bee47bd63f615c7d0a43c529d219
d = 0x2dde7fbaed477f6d62838d55b0d0964868cf6efb2c282a5f13e6008ce7317a24cb57aec49ef0d738919f47cdcd9677cd52ac2293ec5938aa198f962678b5cd0da344453f521a69b2ac03647cdd8339f4e38cec452d54e60698833d67f9315c02ddaa4c79ebaa902c605d7bda32ce970541b2d9a17d62b52df813b2fb0c5ab1a5
enc_flag = 0x50ae00623211ba6089ddfae21e204ab616f6c9d294e913550af3d66e85d0c0693ed53ed55c46d8cca1d7c2ad44839030df26b70f22a8567171a759b76fe5f07b3c5a6ec89117ed0a36c0950956b9cde880c575737f779143f921d745ac3bb0e379c05d9a3cc6bf0bea8aa91e4d5e752c7eb46b2e023edbc07d24a7c460a34a9a

n = p1_q1 - (p_q + 1)
m = pow(enc_flag, d, n)
print(long_to_bytes(m))

babyRSA

from Crypto.Util.number import *
from Crypto.Util.Padding import *
from flag import FLAG

p=getPrime(64)
q=getPrime(64)
N=q**8 * p**8
e=65537

c=pow(bytes_to_long(pad(FLAG,120)),e,N)

print(N)
print(c)
'''
195869853761605418565912426575165155310138169878437113242420866794581458121010172175123773271172966494737601637192319031324980923234574024717004578493417782613794332361852436053080758357356796975886814896748127864437682733874594209237175890215554823802759715050092541290013484514244379930939120479013336321
97005606970821804403994763488668565541380119944415342813038679665968492985759461541273864242512555285439143004622121856190251008775641399317706165715818778134144273158588994292880105800607038946430945921187911592583778698219033437461671853884487810872315564812232169491576154432524236217382798380345144152
'''

注意这里的N是p和q八次方的乘积

根据结论

如果n是质数的某一个次方，即 n = p^k (p为质数，k为大于等于1的整数)，则φ(n)=p^k - p^k-1

所以得φ(N) = (p^8-p^7)*(q^8-q^7)

"""
@Author: C4ry7nk
@Date: 2023/5/9
@Time: 22:16
"""

from Crypto.Util.number import *
N = 195869853761605418565912426575165155310138169878437113242420866794581458121010172175123773271172966494737601637192319031324980923234574024717004578493417782613794332361852436053080758357356796975886814896748127864437682733874594209237175890215554823802759715050092541290013484514244379930939120479013336321
c = 97005606970821804403994763488668565541380119944415342813038679665968492985759461541273864242512555285439143004622121856190251008775641399317706165715818778134144273158588994292880105800607038946430945921187911592583778698219033437461671853884487810872315564812232169491576154432524236217382798380345144152
e = 65537
q = 11795576488031432147
p = 12296365925077812421

assert N == pow(q, 8) * pow(p, 8)

phi = (pow(p, 8) - pow(p, 7)) * (pow(q, 8) - pow(q, 7))
d = inverse(e, phi)
m = pow(c, d, N)
print(long_to_bytes(m))