以一道CTF题真正初识RSA

给我的 crypto 入个门，入个门被数学✌薄纱

本文借 (chao) 鉴 (xi) 了鄙校北神上课用的用例，希望明年上课的师弟搜到这个文章不会影响佬师上课啊哈哈哈 ww

开始前可以看一眼 RSA 的基本原理，本文不会提到很深

~~数学不好，密码还是太难了，一个字都看不懂哈哈哈哈哈哈哈~~

先用一个入门的 pip 包吧

pip install pycryptodome

开始，根据一道 CTF 题慢慢来

# 先改一下 flag 以调通 newcomer.py 代码

题目：初识 RSA
来源：XSCTF 新人选拔赛
描述：p 和 q 藏起来了，你能帮我找到它们吗？

我找个 damn

	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
	'''

原题是引入的 flag 文件，把那行注释掉，下面加一行自己写的 flag 就行，记得用 b 包裹

# 用自己的语言写出 RSA 公钥和私钥的计算公式（使用 p，q，phi，n，e，d 为符号）

设 p，q 为大质数，n=pq

phi=(p-1)(q-1)

根据欧拉函数，phi=(p-1)(q-1)，此部分的证明可以搜一下或者问问强大的大语言模型

e=65537 (公钥指数，任意小于 phi 并与其互质的即可)

d=inverse (e,phi)(私钥指数)

inverse 在库里带了，求逆元的意思

公钥对即为 e，n；私钥对即为 d，n

# 利用题目下方注释中的已知变量计算 phi，并利用 inverse 函数编程计算 e 在模 phi 意义下的乘法逆元，记为 d，根据程序运行结果写出 d 的具体数值；

别想太多，n=p*q，那么极其显然

phi 就是 pqqp/n（别把这里面的 pq 理解成 p * q，看上面的 python 代码哦同学）

（请忽略我的背景柚子厨怎么你了 wwwwwww）

sagemath 命令行还有一些常用的东西，可以看我其他的文章（挖坑）

你算对了吗？

phi=(pq*qp) //n，这句话如果用单 / 会报 OverflowError: integer division result too large for a float。是除法运算导致的类型溢出，用双 // 即可。

单 / 就是执行浮点数除法，即普通的除法操作，双 // 就是执行整数除法，即地板除法

# 根据下列给出的 p、q、e，根据 RSA 算法编程计算公钥 n 与私钥 d；

p=173747400775037237499119138628710917207976935718394035613063219109153197713240288497094852951328821120301146137416392125632164384666157952079993477037237778043103278877799120982366215399159107746276881271883220494577745511406216675640773966244559596835970378099355485746784486359013819361014997811485589135463

q=131816585373639721213952582957741137275970828607414189698553233434142961482639192734668517311468596205692079539001403643395543816907261944034422413069781755026864643651448329100659792941632674865761952547883089120086825249692433942528976412805682521697534499714513072333159601382118300897685368738513700813533

e=65537

没什么好说的，建议同学们先自己做一下在对答案，错了回去看看上面的

n=22902789087710692282201627723972920087676945775651369909558749681603601877066490004280829887082860024866325792922333359888979450409785852136285331867214311784932513053946349686873084098919921626735642656688483918867105990444133292660146552582773030563402978424369091489168537829677450378086515187008083500599611600232061376101775199885242634728744796816625633726726074004731386467983188726961022911791843528459801349329514692878947844318287016330210241002676592845651108656701768277324789376390295075009358573926461653230171198186299924562887630088294834319717425915382663997302617669638278141644149065887129240620779

d=19271863372140646463624718313226644858249851666842334809381515307252297674818586817615620577428910108660806391844117335212132837202625393102518076757881313639679468046843452495262065227324059965356828746942945552493466195508226172853946655099900580076597708945613657755972616318922476707819049590581423940789934387916037469210407055279325381173039093072419831193470910945428027164177392052950722125466565541460489747701257832749756103367996775905993293368370146016279539314698750416709668194421867922941773222876602958853233196249715041186342934713607756322667953880385223035641130659335671630397231173571336884350777

# 利用上述公钥 n、e 对你名字全拼（如：liuyangfan）进行加密

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

	flag=b'flag coming~'

	m = bytes_to_long(flag)


	p=173747400775037237499119138628710917207976935718394035613063219109153197713240288497094852951328821120301146137416392125632164384666157952079993477037237778043103278877799120982366215399159107746276881271883220494577745511406216675640773966244559596835970378099355485746784486359013819361014997811485589135463
	q=131816585373639721213952582957741137275970828607414189698553233434142961482639192734668517311468596205692079539001403643395543816907261944034422413069781755026864643651448329100659792941632674865761952547883089120086825249692433942528976412805682521697534499714513072333159601382118300897685368738513700813533
	e=65537
	n=22902789087710692282201627723972920087676945775651369909558749681603601877066490004280829887082860024866325792922333359888979450409785852136285331867214311784932513053946349686873084098919921626735642656688483918867105990444133292660146552582773030563402978424369091489168537829677450378086515187008083500599611600232061376101775199885242634728744796816625633726726074004731386467983188726961022911791843528459801349329514692878947844318287016330210241002676592845651108656701768277324789376390295075009358573926461653230171198186299924562887630088294834319717425915382663997302617669638278141644149065887129240620779
	d=19271863372140646463624718313226644858249851666842334809381515307252297674818586817615620577428910108660806391844117335212132837202625393102518076757881313639679468046843452495262065227324059965356828746942945552493466195508226172853946655099900580076597708945613657755972616318922476707819049590581423940789934387916037469210407055279325381173039093072419831193470910945428027164177392052950722125466565541460489747701257832749756103367996775905993293368370146016279539314698750416709668194421867922941773222876602958853233196249715041186342934713607756322667953880385223035641130659335671630397231173571336884350777

	c = pow(m,e,n)
	print("c=",c)

豪丸，哈哈

# 利用上述私钥 d，将下列密文 c 解密为明文（用 long_to_bytes 转为字节码打印）

c=22383445933736798279478032679517743837766449187698865398822423786317612396771654040156586654564003392384975014045643201026069165276350584034120841617657486555798948939049343900381125798000000172357016404870066390095970211708364996514629691512019106870733929516372325207940525326467947232996619729431748024769431567208774806188872803942768881324395058229038610826245541466028073553184615680354118655959979504640632739098044460639023736294401801478667944983999124796530293982085703611284581213900570723479615642643430713949661089128106079384524944632103663244376051089098793845750645708721359256022997797080498949228931

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

	p=173747400775037237499119138628710917207976935718394035613063219109153197713240288497094852951328821120301146137416392125632164384666157952079993477037237778043103278877799120982366215399159107746276881271883220494577745511406216675640773966244559596835970378099355485746784486359013819361014997811485589135463
	q=131816585373639721213952582957741137275970828607414189698553233434142961482639192734668517311468596205692079539001403643395543816907261944034422413069781755026864643651448329100659792941632674865761952547883089120086825249692433942528976412805682521697534499714513072333159601382118300897685368738513700813533
	e=65537
	n=22902789087710692282201627723972920087676945775651369909558749681603601877066490004280829887082860024866325792922333359888979450409785852136285331867214311784932513053946349686873084098919921626735642656688483918867105990444133292660146552582773030563402978424369091489168537829677450378086515187008083500599611600232061376101775199885242634728744796816625633726726074004731386467983188726961022911791843528459801349329514692878947844318287016330210241002676592845651108656701768277324789376390295075009358573926461653230171198186299924562887630088294834319717425915382663997302617669638278141644149065887129240620779
	d=19271863372140646463624718313226644858249851666842334809381515307252297674818586817615620577428910108660806391844117335212132837202625393102518076757881313639679468046843452495262065227324059965356828746942945552493466195508226172853946655099900580076597708945613657755972616318922476707819049590581423940789934387916037469210407055279325381173039093072419831193470910945428027164177392052950722125466565541460489747701257832749756103367996775905993293368370146016279539314698750416709668194421867922941773222876602958853233196249715041186342934713607756322667953880385223035641130659335671630397231173571336884350777
	c = 22383445933736798279478032679517743837766449187698865398822423786317612396771654040156586654564003392384975014045643201026069165276350584034120841617657486555798948939049343900381125798000000172357016404870066390095970211708364996514629691512019106870733929516372325207940525326467947232996619729431748024769431567208774806188872803942768881324395058229038610826245541466028073553184615680354118655959979504640632739098044460639023736294401801478667944983999124796530293982085703611284581213900570723479615642643430713949661089128106079384524944632103663244376051089098793845750645708721359256022997797080498949228931
	pq = p*(q-1)
	qp = q*(p-1)
	phi=(pq*qp) //n
	d=inverse(e,phi)
	c=pow(c,d,n)

	print(long_to_bytes(c))

当然，flag 没变哦，答案还是 “flag coming~”

豪丸，当然，碰到几个难题就老实了

CTF 密码