MoeCTF 2023

本文最后更新于：2024年9月25日 晚上

（仅有部分题目

Crypto 入门指北

main_py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from secret import flag # 这个secret不是一个库，flag是你要自己求出来的，所以不要问为什么找不到这个库了（

p,q = getPrime(512), getPrime(512) # 随机生成了两个质数
e = 65537 # 这是什么？
n = p*q
m = int.from_bytes(flag.encode(),"big") # 把flag编码成bytes，再转换成一个长整数
c = pow(m,e,n) # RSA加密！

print(p)
print(q)
print(c)

# p = 0xe82a76eeb5ac63e054128e040171630b993feb33e0d3d38fbb7c0b54df3a2fb9b5589d1205e0e4240b8fcb4363acaa4c3c44dd6e186225ebf3ce881c7070afa7
# q = 0xae5c2e450dbce36c8d6d1a5c989598fc01438f009f9b4c29352d43fd998d10984d402637d7657d772fb9f5e4f4feee63b267b401b67704979d519ad7f0a044eb
# c = 0x4016bf1fe655c863dd6c08cbe70e3bb4e6d4feefacaaebf1cfa2a8d94051d21e51919ea754c1aa7bd1674c5330020a99e2401cb1f232331a2da61cb4329446a17e3b9d6b59e831211b231454e81cc8352986e05d44ae9fcd30d68d0ce288c65e0d22ce0e6e83122621d2b96543cec4828f590af9486aa57727c5fcd8e74bd296

m = int.from_bytes(flag.encode(),"big")

这行代码的作用是将字符串 flag 转换成一个大整数 m。具体解释如下：

  • flag: 这是一个字符串，通常包含需要进行加密或其他操作的敏感信息，例如密码或标志。
  • flag.encode(): 这是将字符串 flag 转换为字节序列的操作。在计算机中，所有的数据最终都会以字节的形式表示。encode() 方法将字符串编码为字节，使用默认的编码方式（通常是UTF-8）。
  • "big": 这是一个参数，它告诉Python将字节序列视为一个大端（big-endian）的整数。在大端表示法中，高位字节在前，低位字节在后。这是一种常见的表示整数的方式。
  • int.from_bytes(...): 这是一个方法，用于将字节序列转换为整数。它接受两个参数，第一个参数是要转换的字节序列，第二个参数是表示字节序列顺序的字符串，这里是 "big"。它会将字节序列按照指定的顺序解释为一个整数。

因此，m 将包含了从字符串 flag 转换而来的整数表示。在加密算法中，通常会将明文消息转换成整数形式，以便进行数学运算，例如RSA加密中的指数运算。

c = pow(m,e,n)

这行代码实现了RSA（Rivest–Shamir–Adleman）加密的核心操作。具体解释如下：

  • m: 这是明文消息的整数表示。在RSA加密中，明文消息通常首先被编码成一个整数，这个整数在加密过程中被处理。
  • e: 这是RSA加密算法中的公钥指数。它是一个正整数，通常是65537。公钥指数是用于加密消息的指数。
  • n: 这是RSA加密算法中的模数（或称为模ulus）。它是两个大素数 p 和 q 的乘积。模数在RSA加密和解密过程中都会用到。
  • pow(m, e, n): 这是Python中的一个函数，用于计算 m 的 e 次方除以 n 的余数。也就是说，它执行的是模指数运算。在RSA加密中，这等效于对明文消息 m 进行加密操作。

最终，c 将包含加密后的密文，它是整数形式的，可以通过RSA私钥进行解密，从而还原为原始的明文消息 m。RSA是一种非对称加密算法，公钥用于加密，私钥用于解密，这使得只有拥有私钥的人才能够解密密文。

哦~~，这里就是说flag是不知道的，就是让我们求一下flag

exp

1
2
3
4
5
6
7
8
9
10
11
from Crypto.Util.number import * # 一个非常好用的crypto库

p = 0xe82a76eeb5ac63e054128e040171630b993feb33e0d3d38fbb7c0b54df3a2fb9b5589d1205e0e4240b8fcb4363acaa4c3c44dd6e186225ebf3ce881c7070afa7
q = 0xae5c2e450dbce36c8d6d1a5c989598fc01438f009f9b4c29352d43fd998d10984d402637d7657d772fb9f5e4f4feee63b267b401b67704979d519ad7f0a044eb
c = 0x4016bf1fe655c863dd6c08cbe70e3bb4e6d4feefacaaebf1cfa2a8d94051d21e51919ea754c1aa7bd1674c5330020a99e2401cb1f232331a2da61cb4329446a17e3b9d6b59e831211b231454e81cc8352986e05d44ae9fcd30d68d0ce288c65e0d22ce0e6e83122621d2b96543cec4828f590af9486aa57727c5fcd8e74bd296
e = 65537
n = p*q
phi = (p-1) * (q-1) # 你知道什么是 欧拉函数吗 [1]
d = pow(e, -1, phi) # 什么是乘法逆元？ [2]
m = pow(c,d,n)
print(long_to_bytes(m))

相当于我们知道了p，q，c，e，然后求m，那就求出 n 和 d 即可

所以关键的就是求d

d = pow(e, -1, phi)

这行代码计算了私钥 d，它是公钥指数 e 在模 phi 下的乘法逆元。

因为 e 和 d 之间一定满足：(e * d) % phi(n) = 1，即e*d ≡ 1(mod φ(N))

这行代码其实跟之前 [SWPUCTF 2021 新生赛]ez_rsa 解密代码中d = gmpy2.invert(e, phi)是一个意思

答案是可以的，经过简单的运算即可得到

知识：乘法逆元、欧拉函数 等

baby_e

main_py

1
2
3
4
5
6
7
8
9
10
11
12
from Crypto.Util.number import getPrime,bytes_to_long

p,q = getPrime(2048),getPrime(2048)
e = 7
n = p*q
m = bytes_to_long(open('flag.txt','rb').read().strip())
c = pow(m,e,n)
print("c = ",c)
print("n = ",n)

# c =  147693154873835354725007152781732424355869776162377337823960431913672366269917723916891506269449726723757821517328874729037838600793748824028829185409932536014732765063216715033843955453706710187792772702199448156372644163429786386035008302836467605094954587157232829525150652611067567669525072625329634860065850520051628272535479197120008981979404760445193750864902244921407742155742716289495581989134730376783828846663464819337418977287363028738701414486788851136608957124505485242331701209645216580641917007780811842757125048746184068597664780265422321550909392419865169775282217442331295071069272774722564587602419768461231775480847018941840911357926330143045826277813722919121117172763493242590521245640828462665947672485094793188432098216701511715232654611338293295459889814699850788048985878279440740712956248569068077253790198036918598519191892836075254345518967666166925163908185663991353344555402397055977817370082929420443034626201745027965444069777059760865359310439815816749939498993014457995041394803598825093836045546578310632172636478575946653375857640993393714607308326474003446154152048840071034349831168612740218034679021240949747357214453636633636662650940968576792518622437627529244515229173
# n =  553409369582823237678532685244026647155180191225879439432235077135813123637186465008813830373646133388592395760175777499266561095087891764348044063111935877931069321764391883899483374576303169645488542398590564148654412004383012178107972880058460460806768779452529433458826925606225797078653905380530651390617109384086518728626571028089036812787671647095695947167204428442727185744172445701874820612799168887428075695751162763647868386879374037826876671079326544820609721731078985096813307183878793033824330869698508952853770794414757655681370862323768018291030331209143189638496644361618184164228294031490537429556439588954274708598530042700988138862000054458742762198052079867259365645914383561162796796952346445529346145323567650621600171442575319262718389389870407629339714751583360252884338116164466349449862781112019462555743429653595045695696967783338371470032332852204294900011651434678829104876529439166176589508898757122660322523937330848536715937381297551894198974459004139082562228022412335520195652419375915216074658463954339332593244483927157329404652516225481116614815221154229491846087288087715884363786672244655901308480290011237244562251084095684531716327141154558809471185132979704992609461470501119328696999713829

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *
import gmpy2

c = 147693154873835354725007152781732424355869776162377337823960431913672366269917723916891506269449726723757821517328874729037838600793748824028829185409932536014732765063216715033843955453706710187792772702199448156372644163429786386035008302836467605094954587157232829525150652611067567669525072625329634860065850520051628272535479197120008981979404760445193750864902244921407742155742716289495581989134730376783828846663464819337418977287363028738701414486788851136608957124505485242331701209645216580641917007780811842757125048746184068597664780265422321550909392419865169775282217442331295071069272774722564587602419768461231775480847018941840911357926330143045826277813722919121117172763493242590521245640828462665947672485094793188432098216701511715232654611338293295459889814699850788048985878279440740712956248569068077253790198036918598519191892836075254345518967666166925163908185663991353344555402397055977817370082929420443034626201745027965444069777059760865359310439815816749939498993014457995041394803598825093836045546578310632172636478575946653375857640993393714607308326474003446154152048840071034349831168612740218034679021240949747357214453636633636662650940968576792518622437627529244515229173
n = 553409369582823237678532685244026647155180191225879439432235077135813123637186465008813830373646133388592395760175777499266561095087891764348044063111935877931069321764391883899483374576303169645488542398590564148654412004383012178107972880058460460806768779452529433458826925606225797078653905380530651390617109384086518728626571028089036812787671647095695947167204428442727185744172445701874820612799168887428075695751162763647868386879374037826876671079326544820609721731078985096813307183878793033824330869698508952853770794414757655681370862323768018291030331209143189638496644361618184164228294031490537429556439588954274708598530042700988138862000054458742762198052079867259365645914383561162796796952346445529346145323567650621600171442575319262718389389870407629339714751583360252884338116164466349449862781112019462555743429653595045695696967783338371470032332852204294900011651434678829104876529439166176589508898757122660322523937330848536715937381297551894198974459004139082562228022412335520195652419375915216074658463954339332593244483927157329404652516225481116614815221154229491846087288087715884363786672244655901308480290011237244562251084095684531716327141154558809471185132979704992609461470501119328696999713829
e = 7       # 但是我们不知道p和q啊，这怎么求啊


a, b = gmpy2.iroot(c, 7)

print(long_to_bytes(a))
# print(a)

思路（very very very 感谢峰哥（其实是学弟，惭愧））：

小公钥指数攻击：

  • 因为 e 很小，n 很大
  • 所以明文 m 乘了 e 次方也没到 n ，n 根本没用到
  • 所以 c 直接开7次根就是明文了，这里要用gmpy2.iroot(c, 7)，而不能pow(c,1/7)，后者算不动
  • 找时间去看：公钥指数相关攻击 - CTF Wiki (ctf-wiki.org)

bad_E

main

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import *
p = getPrime(512)
q = getPrime(512)
e = 65537

print(p) # 6853495238262155391975011057929314523706159020478084061020122347902601182448091015650787022962180599741651597328364289413042032923330906135304995252477571
print(q) # 11727544912613560398705401423145382428897876620077115390278679983274961030035884083100580422155496261311510530671232666801444557695190734596546855494472819

with open("flag.txt","r") as fs:
    flag = fs.read().strip()

m = bytes_to_long(flag.encode())
c = pow(m,e,p*q)
print(c) # 63388263723813143290256836284084914544524440253054612802424934400854921660916379284754467427040180660945667733359330988361620691457570947823206385692232584893511398038141442606303536260023122774682805630913037113541880875125504376791939861734613177272270414287306054553288162010873808058776206524782351475805

exp

参考下面的博客：

e与phi不互素的情况_余切66的博客-CSDN博客

1694699685619

e和phi不互素，本题是gcd(e,q-1)=1，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import * # 一个非常好用的crypto库
from gmpy2 import *

p = 6853495238262155391975011057929314523706159020478084061020122347902601182448091015650787022962180599741651597328364289413042032923330906135304995252477571
q = 11727544912613560398705401423145382428897876620077115390278679983274961030035884083100580422155496261311510530671232666801444557695190734596546855494472819

c = 63388263723813143290256836284084914544524440253054612802424934400854921660916379284754467427040180660945667733359330988361620691457570947823206385692232584893511398038141442606303536260023122774682805630913037113541880875125504376791939861734613177272270414287306054553288162010873808058776206524782351475805
e = 65537

print(gcd(e,q-1))


phi = q-1
d = gmpy2.invert(e,phi)
m = pow(c,d,q)
print(long_to_bytes(m))

factor_signin

main

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
from Crypto.Util.number import getPrime
from math import prod

with open("flag.txt","rb") as f:
    flag = f.read().strip()
assert len(flag) == 72

m1 = int.from_bytes(flag[:36],"big")
m2 = int.from_bytes(flag[36:],"big")

e = 65537

p,q = getPrime(2048),getPrime(2048)
n1 = p*q
c1 = pow(m1,e,n1)
print("c1 = ",c1)
print("n1 = ",n1)

primes = [getPrime(64) for _ in range(32)]
n2 = prod(primes)
c2 = pow(m2,e,n2)
print("c2 = ",c2)
print("n2 = ",n2)

# c1 =  10004937130983861141937782436252502991050957330184611684406783226971057978666503675149401388381995491152372622456604317681236160071166819028679754762162125904637599991943368450200313304999566592294442696755822585022667008378021280392976010576970877334159755332946926433635584313137140987588847077645814987268595739733550220882135750267567373532603503399428451548677091911410732474324157868011686641243202218731844256789044721309478991918322850448456919991540932206923861653518190974620161055008847475600980152660468279765607319838003177639654115075183493029803981527882155542925959658123816315099271123470754815045214896642428657264709805029840253303446203030294879166242867850331945166255924821406218090304893024711068773287842075208409312312188560675094244318565148284432361706108491327014254387317744284876018328591380705408407853404828189643214087638328376675071962141118973835178054884474523241911240926274907256651801384433652425740230755811160476356172444327762497910600719286629420662696949923799255603628210458906831175806791599965316549386396788014703044837917283461862338269599464440202019922379625071512100821922879623930069349084917919100015782270736808388388006084027673781004085620817521378823838335749279055639005125
# n1 =  343504538870081878757729748260620800783581983635281373321527119223374418103340873199654926888439040391545101913132680017655039577253974802351999985470115474655124168592386965001556620077117966153475518658881140827499124290142523464795351995478153288872749817655925271395693435582010998996210909883510311066017237567799370371513462802547313382594409676803895262837061350017911885033133654781876923251129406855067993830824618637981136966134029212516871210627954762147349788788999116702635535406398258621926040887099782494271000823401788337120154104692934583729065189687995570122890809807661370008740283447636580308161498808092269041815719148127168137018600113465985504975054319601741498799761500526467431533990903047624407330243357514588557352746347337683868781554819821575385685459666842162355673947984514687068626166144076257334426612302554448774082488600083569900006274897032242821388126274957846236552373226099112200392102883351088570736254707966329366625911183721875374731791052229266503696334310835323523568132399330263642353927504971311717117370721838701629885670598853025212521537158141447625623337563164790788106598854822686494249848796441153496412236527242235888308435573209980270776407776277489669763803746640746378181948641
# c2 =  4948422459907576438725352912593232312182623872749480015295307088166392790756090961680588458629287353136729331282506869598853654959933189916541367579979613191505226006688017103736659670745715837820780269669982614187726024837483992949073998289744910800139692315475427811724840888983757813069849711652177078415791290894737059610056340691753379065563574279210755232749774749757141836708161854072798697882671844015773796030086898649043727563289757423417931359190238689436180953442515869613672008678717039516723747808793079592658069533269662834322438864456440701995249381880745586708718334052938634931936240736457181295
# n2 =  8582505375542551134698364096640878629785534004976071646505285128223700755811329156276289439920192196962008222418309136528180402357612976316670896973298407081310073283979903409463559102445223030866575563539261326076167685019121804961393115251287057504682389257841337573435085535013992761172452417731887700665115563173984357419855481847035192853387338980937451843809282267888616833734087813693242841580644645315837196205981207827105545437201799441352173638172133698491126291396194764373021523547130703629001683366722885529834956411976212381935354905525700646776572036418453784898084635925476199878640087165680193737

exp

前半部分：直接分解n1

后半部分：n2是多个素数的乘积，求欧拉函数，我教过你吧😋（但是这个脚本我还真第一次见

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
from Crypto.Util.number import *
from gmpy2 import *
from functools import reduce

e = 65537

c1 =  10004937130983861141937782436252502991050957330184611684406783226971057978666503675149401388381995491152372622456604317681236160071166819028679754762162125904637599991943368450200313304999566592294442696755822585022667008378021280392976010576970877334159755332946926433635584313137140987588847077645814987268595739733550220882135750267567373532603503399428451548677091911410732474324157868011686641243202218731844256789044721309478991918322850448456919991540932206923861653518190974620161055008847475600980152660468279765607319838003177639654115075183493029803981527882155542925959658123816315099271123470754815045214896642428657264709805029840253303446203030294879166242867850331945166255924821406218090304893024711068773287842075208409312312188560675094244318565148284432361706108491327014254387317744284876018328591380705408407853404828189643214087638328376675071962141118973835178054884474523241911240926274907256651801384433652425740230755811160476356172444327762497910600719286629420662696949923799255603628210458906831175806791599965316549386396788014703044837917283461862338269599464440202019922379625071512100821922879623930069349084917919100015782270736808388388006084027673781004085620817521378823838335749279055639005125
n1 =  343504538870081878757729748260620800783581983635281373321527119223374418103340873199654926888439040391545101913132680017655039577253974802351999985470115474655124168592386965001556620077117966153475518658881140827499124290142523464795351995478153288872749817655925271395693435582010998996210909883510311066017237567799370371513462802547313382594409676803895262837061350017911885033133654781876923251129406855067993830824618637981136966134029212516871210627954762147349788788999116702635535406398258621926040887099782494271000823401788337120154104692934583729065189687995570122890809807661370008740283447636580308161498808092269041815719148127168137018600113465985504975054319601741498799761500526467431533990903047624407330243357514588557352746347337683868781554819821575385685459666842162355673947984514687068626166144076257334426612302554448774082488600083569900006274897032242821388126274957846236552373226099112200392102883351088570736254707966329366625911183721875374731791052229266503696334310835323523568132399330263642353927504971311717117370721838701629885670598853025212521537158141447625623337563164790788106598854822686494249848796441153496412236527242235888308435573209980270776407776277489669763803746640746378181948641
c2 =  4948422459907576438725352912593232312182623872749480015295307088166392790756090961680588458629287353136729331282506869598853654959933189916541367579979613191505226006688017103736659670745715837820780269669982614187726024837483992949073998289744910800139692315475427811724840888983757813069849711652177078415791290894737059610056340691753379065563574279210755232749774749757141836708161854072798697882671844015773796030086898649043727563289757423417931359190238689436180953442515869613672008678717039516723747808793079592658069533269662834322438864456440701995249381880745586708718334052938634931936240736457181295
n2 =  8582505375542551134698364096640878629785534004976071646505285128223700755811329156276289439920192196962008222418309136528180402357612976316670896973298407081310073283979903409463559102445223030866575563539261326076167685019121804961393115251287057504682389257841337573435085535013992761172452417731887700665115563173984357419855481847035192853387338980937451843809282267888616833734087813693242841580644645315837196205981207827105545437201799441352173638172133698491126291396194764373021523547130703629001683366722885529834956411976212381935354905525700646776572036418453784898084635925476199878640087165680193737

p1 = 18055722101348711626577381571859114850735298658417345663254295930584841136416234624852520581982069555948490061840244710773146585295336094872892685938420880462305333393436098181186277450475949236132458958671804132443554885896037342335902958516394876382378829317303693655605215373555988755516058130500801822723195474873517960624159417903134580987202400855946137101429970119186394052011747475879598126195607938106163892658285305921071673588966184054026228745012993740035399652049777986535759039077634555909031397541116025395236871778797949216479130412500655359057128438928721459688727543057760739527720641179290282309741
q1 = 19024691283015651666032297670418553586155390575928421823630922553034857624430114628839720683172187406577114034710093054198921843669645736474448836706112221787749688565566635453151716934583685087745112614898780150391513798368931496744574075511968933800467288441832780919514199410584786925010518564670786685241724643282580795568609339268652910564215887176803735675069372979560024792322029911970574914829712553975379661212645059271137916107885326625543090473004683836665262304916304580076748336858662108554591235698235221618061328251985929904075811056422186525179189846420226944944513865790999242309352900287977666792901

phi = (p1-1)*(q1-1)
d = invert(e,phi)
m = pow(c1,d,n1)

print(long_to_bytes(m))


factor = '''P20 = 14745811312384518031
P20 = 18345408081492711641
P20 = 14678737767649343977
P20 = 14619040595108594017
P19 = 9949603102225364603
P20 = 12034779627328165471
P20 = 10596280721192026229
P20 = 15211380502610462057
P20 = 14813953870710226847
P20 = 13062839684118954553
P20 = 15332916111580607077
P20 = 16870346804576162551
P20 = 11092420583960163379
P20 = 14397830993057803133
P20 = 16123604149048919099
P20 = 13645878578452317313
P20 = 17093292308638969889
P20 = 17289161209347211817
P20 = 15175734709842430433
P20 = 15751974537676958401
P20 = 10864078180916418691
P20 = 17673334943789572513
P20 = 18390046459144888243
P20 = 12404642343676224637
P20 = 18106525049998616747
P20 = 11853704782834170959
P20 = 17543713628803023199
P20 = 10049235158029375571
P20 = 12448177342966243757
P20 = 17265001711647542137
P20 = 10547615587767500213
P20 = 16408421615173973083'''

factor = list(map(int,[i.split()[-1] for i in factor.split('\n')]))
phin = reduce(lambda a,b:a*(b-1),[1] + factor)
d = pow(e,-1,phin)
m2 = pow(c2,d,n2)

# print(bytes.fromhex(hex(pow(c2,d,n2))[2:]))


print(long_to_bytes(m2))
# b'moectf{fACtord6_And_YAfu_Are_6oth_good_utils_to_fACtorize_num6ers_ff90S}'

feistel

main

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
from Crypto.Util.number import *

round = 2
flag = open("./secret", "rb").read().strip()


def f(m, key):
    m = m ^ (m >> 4)
    m = m ^ (m << 5)
    m = m ^ (m >> 8)
    m ^= key
    m = (m * 1145 + 14) % 2**64
    m = (m * 1919 + 810) % 2**64
    m = (m * key) % 2**64
    return m


def enc(m, key, round):
    key = bytes_to_long(key)
    left = bytes_to_long(m[:8])
    right = bytes_to_long(m[8:])
    for i in range(round):
        left, right = right, f(right, key) ^ left
    left, right = right, left
    return long_to_bytes(left).rjust(8, b"\x00") + long_to_bytes(right).rjust(8, b"\x00")


def padding(m):
    mlen = len(m)
    pad = 16 - mlen % 16
    return m + pad * bytes([pad])


def ecb_enc(m, key):
    m = padding(m)
    mlen = len(m)
    c = b""
    for i in range(mlen // 16):
        c += enc(m[i * 16 : i * 16 + 16], key, round)
    return c


print(ecb_enc(flag, b"wulidego"))

# b'\x0b\xa7\xc6J\xf6\x80T\xc6\xfbq\xaa\xd8\xcc\x95\xad[\x1e\'W5\xce\x92Y\xd3\xa0\x1fL\xe8\xe1"^\xad'

n&n

main

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import *

p = getPrime(1024)
q = getPrime(1024)

with open("flag.txt","r") as f:
    flag = f.read().strip().encode()

m = bytes_to_long(flag)
n = p * q
e1 = 0x114514
e2 = 19198101

c1 = pow(m,e1,n)
c2 = pow(m,e2,n)
print(c1) 
print(c2)
print(n)

# 5776799746376051463605370130675046329799612910435315968508603116759552095183027263116443417343895252766060748671845650457077393391989018107887540639775168897954484319381180406512474784571389477212123123540984850033695748142755414954158933345476509573211496722528388574841686164433315356667366007165419697987147258498693175698918104120849579763098045116744389310549687579302444264316133642674648294049526615350011916160649448726069001139749604430982881450187865197137222762758538645387391379108182515717949428258503254717940765994927802512049427407583200118969062778415073135339774546277230281966880715506688898978925
# 4664955020023583143415931782261983177552050757537222070347847639906354901601382630034645762990079537901659753823666851165175187728532569040809797389706253282757017586285211791297567893874606446000074515260509831946210526182765808878824360460569061258723122198792244018463880052389205906620425625708718545628429086424549277715280217165880900037900983008637302744555649467104208348070638137050458275362152816916837534704113775562356277110844168173111385779258263874552283927767924979691542028126412133709129601685315027689094437957165812994784648540588277901241854031439324974562449032290219652206466731675967045633360
# 13612969130810965900902742090064423006385890357159609755971027204203418808937093492927060428980020085273603754747223030702684866992231913349067578014240319426522039068836171388168087260774376277346092066880984406890296520951318296354893551565670293486797637522297989653182109744864444697818991039473180752980752117041574628063002176339235126861152739066489620021077091941250365101779354009854706729448088217051728432010328667839532327286559570597994183126402340332924370812383312664419874352306052467284992411543921858024469098268800500500651896608097346389396273293747664441553194179933758992070398387066135330851531

exp

共模攻击，用的脚本

这里十六进制的e1竟然不用转换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
from Crypto.Util.number import *
from gmpy2 import gmpy2
 
c1 = 5776799746376051463605370130675046329799612910435315968508603116759552095183027263116443417343895252766060748671845650457077393391989018107887540639775168897954484319381180406512474784571389477212123123540984850033695748142755414954158933345476509573211496722528388574841686164433315356667366007165419697987147258498693175698918104120849579763098045116744389310549687579302444264316133642674648294049526615350011916160649448726069001139749604430982881450187865197137222762758538645387391379108182515717949428258503254717940765994927802512049427407583200118969062778415073135339774546277230281966880715506688898978925
c2 = 4664955020023583143415931782261983177552050757537222070347847639906354901601382630034645762990079537901659753823666851165175187728532569040809797389706253282757017586285211791297567893874606446000074515260509831946210526182765808878824360460569061258723122198792244018463880052389205906620425625708718545628429086424549277715280217165880900037900983008637302744555649467104208348070638137050458275362152816916837534704113775562356277110844168173111385779258263874552283927767924979691542028126412133709129601685315027689094437957165812994784648540588277901241854031439324974562449032290219652206466731675967045633360
e1 = 0x114514
e2 = 19198101

# e1 = int(str(e1), 16) 


n = 13612969130810965900902742090064423006385890357159609755971027204203418808937093492927060428980020085273603754747223030702684866992231913349067578014240319426522039068836171388168087260774376277346092066880984406890296520951318296354893551565670293486797637522297989653182109744864444697818991039473180752980752117041574628063002176339235126861152739066489620021077091941250365101779354009854706729448088217051728432010328667839532327286559570597994183126402340332924370812383312664419874352306052467284992411543921858024469098268800500500651896608097346389396273293747664441553194179933758992070398387066135330851531


 
def RSA_ComModAtk(e1, e2, c1, c2, n):
    e1, e2, c1, c2, n = int(e1), int(e2), int(c1), int(c2), int(n)
    if gmpy2.gcd(e1,e2) ==1:
        s = gmpy2.gcdext(e1, e2)  # 扩展欧几里得算法-辗转相除法使得  x*e1+y*e2=1,求出t和z
        x = s[1]
        y = s[2]
        if x < 0:
            x = - x  # 变指数为正值
            c1 = gmpy2.invert(c1, n)  # 求c1的逆元
        if y < 0:
            y = -y  # 变指数为正值
            c2 = gmpy2.invert(c2, n)  # 求c2的逆元
        m = (pow(c1, x, n) * pow(c2, y, n)) % n  # (c1^x*c2^y)%n=m^e1x*me2y%n=m^(e1x+e2y)%n=m%n=m
        return m
    else :
        return bytes_to_long(b'e1 and e2 are not relatively prime') # e1和e2不互质
    

m = RSA_ComModAtk(e1, e2, c1, c2, n)

print(long_to_bytes(m))

factorize_me!

main

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from Crypto.Util.number import getPrime
from math import prod
from sympy import nextprime
from random import choices

with open('flag.txt', 'rb') as fs:
    flag = fs.read().strip()

primes = [getPrime(512) for _ in range(9)]
print(f"{prod(primes) = }")
print(f"{prod(p - 1 for p in primes) = }")

primes2 = [nextprime(p) for p in choices(primes, k=3)]
n = prod(primes2)
e = 65537
c = pow(int.from_bytes(flag, 'big'), e, n)

print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')

# 363364907814244019888662301376841344262476227242899756862391470731421569394957444030214887114615748277199649349781524749919652160244484352285668794188836866602305788131186220057989320357344904731322223310531945208433910803617954798258382169132907508787682006064930747033681966462568715421005454243255297306718356766130469885581576362173340673516476386201173298433892314145854649884922769732583885904512624543994675379894718657682146178638074984373206937523380103438050549181568015985546172618830480078894445808092527561363650503540062128543705172678754195578429520889784813733491180748361345720247750720179608752244490362713103319685024237941527268458213442611663415417005556439749055222361212059968254748751273361732365487788593341859760309778894350385339764442343374673786357175846291309425081492959910254127778240522152676060766139057453197528944251599979227271074508795482632471242983094008619339488744362509349734218480932255216087706001484182136783834973304870508270118505737767002256270427907341952256516206663258530300791364944105025764611810001781971638030661367630116818647252727909489405550104641122269772492252464714694507693447974171377200402508765841829763548525530878309985480248379655169722567051495205792089930014228403456098065971372039443284193603395249634283366194562380309469628114581468645669390610963076340643757972439104287127375438663839421605531570285615180251
# 363364907814244019888662301376841344262476227242899756862391470731421569394957444030214887114615748277199649349781524749919652160244484352285668794188836492373364350673588273863828369502073826782362255108313852264064760467561392054178047091483873483255491431451728274259516789065331176728192953741805933100379191778599394515981288225535175013258094287912195847642598436035132783919453991516358280321085873745330313812205910011387125778714795906023110368957596998222544234082487264006696812862179916726781327290284827659294751262185328816323311831349296593013038823107653943652771448719760448938995150646738377177532550757319539185878535087009904848382493668686831331474113789651777885239747000076063679062106375348803749466079052774597412239427050432901553466002731972993029311850718200685157193170716432600165476733200831046297530470544781309612128231925681374239849452623513538498417735984094919756374577623486416462101457492789215144166273775249387638107644634704270216130852885082174564648445147377239033930079759024399532146184753110240154062693457622208373371290126810856885343328090305620627668495081760346853701632815149478447405718664667978825807101325764916405446176183238866136433205933785973568759281210319422288153910340542098573782006262190181726245838857185687242960093445000287347616796984610291664809895901301187179157382169999966124177588884152267266994164841066291200
# n = 899081756851564072995842371038848265712822308942406479625157544735473115850983700580364485532298999127834142923262920189902691972009898741820291331257478170998867183390650298055916005944577877856728843264502218692432679062445730259562784479410120575777748292393321588239071577384218317338474855507210816917917699500763270490789679076190405915250953860114858086078092945282693720016414837231157788381144668395364877545151382171251673050910143023561541226464220441
# e = 65537
# c = 841335863342518623856757469220437045493934999201203757845757404101093751603513457430254875658199946020695655428637035628085973393246970440054477600379027466651143466332405520374224855994531411584946074861018245519106776529260649700756908093025092104292223745612991818151040610497258923925952531383407297026038305824754456660932812929344928080812670596607694776017112795053283695891798940700646874515366341575417161087304105309794441077774052357656529143940010140

exp

[RSA1]P7，直接分解n运算即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import *

e = 65537
c = 841335863342518623856757469220437045493934999201203757845757404101093751603513457430254875658199946020695655428637035628085973393246970440054477600379027466651143466332405520374224855994531411584946074861018245519106776529260649700756908093025092104292223745612991818151040610497258923925952531383407297026038305824754456660932812929344928080812670596607694776017112795053283695891798940700646874515366341575417161087304105309794441077774052357656529143940010140

p = 6991223361118904775931217829045348785013077549030883418924453538830605687999480005714979700653172534877541317997174968789510984315425270755055110913347349
q = 9987009117206906203158749743824168660291275882852229158070368815160479543708376165641735042845357978292384303332559592302507789120810447986634662721490849
r = 12876877424944854147075816504195994138450356002779004886384584287813869165469217718717854027672044903401715370348223932937626725119320180795716270261309141


n = p * q * r
phi = (p-1)*(q-1)*(r-1)

d = pow(e,-1,phi)
m = pow(c,d,n)

print(long_to_bytes(m))  

# 不知道上面给那两个大数是干啥的
CTF-Crypto
#CTF #Crypto
MoeCTF 2023
http://viper2383.github.io/2023/09/24/MoeCTF 2023/
作者
w1per3
发布于
2023年9月24日
许可协议