DASCTF Sept X 浙江工业大学秋季挑战赛
crypto
签到
题目
from Crypto.Util.number import *
import random
flag=b'flag{******************}'
n = 2 ** 256
flaglong=bytes_to_long(flag)
m = random.randint(2, n-1) | 1
c = pow(m, flaglong, n)
print('m = ' + str(m))
print('c = ' + str(c))
已知n、c、m，求e
而且n不能分解
这道题跟之前2020网鼎杯的一道题很像
应该用sage解
n = 2 ** 256
m = 73964803637492582853353338913523546944627084372081477892312545091623069227301
c = 21572244511100216966799370397791432119463715616349800194229377843045443048821
e=discrete_log(Mod(c,n),Mod(m,n))
print(e)
然后再用python
from Crypto.Util.number import *
print(long_to_bytes(e))
运行就能得到了
RSA1
nc 连接，连接后等待一分钟，才会有回显。
动态靶机，每次启动靶机的 flag 不同，请注意。
from flag import get_flag
from hashlib import sha512
from Crypto.Util.number import getPrime,bytes_to_long
from libnum import invmod, gcd
import random
def m_exit(n):
print "==============Game Over!================="
exit(n)
def cal_bit(num):
num = int(num)
l = len(bin(num))
return l-2
def pi_b(x):
bt = 536380958350616057242691418634880594502192106332317228051967064327642091297687630174183636288378234177476435270519631690543765125295554448698898712393467267006465045949611180821007306678935181142803069337672948471202242891010188677287454504933695082327796243976863378333980923047411230913909715527759877351702062345876337256220760223926254773346698839492268265110546383782370744599490250832085044856878026833181982756791595730336514399767134613980006467147592898197961789187070786602534602178082726728869941829230655559180178594489856595304902790182697751195581218334712892008282605180395912026326384913562290014629187579128041030500771670510157597682826798117937852656884106597180126028398398087318119586692935386069677459788971114075941533740462978961436933215446347246886948166247617422293043364968298176007659058279518552847235689217185712791081965260495815179909242072310545078116020998113413517429654328367707069941427368374644442366092232916196726067387582032505389946398237261580350780769275427857010543262176468343294217258086275244086292475394366278211528621216522312552812343261375050388129743012932727654986046774759567950981007877856194574274373776538888953502272879816420369255752871177234736347325263320696917012616273L
return invmod(x, bt)
def get_ed(p, q):
k = cal_bit(q*p)
phi_n = (p-1)*(q-1)
r = random.randint(10, 99)
while True:
u = getPrime(k/4 - r)
if gcd(u, phi_n) != 1:
continue
t = invmod(u, phi_n)
e = pi_b(t)
if gcd(e, phi_n) == 1:
break
d = invmod(e, phi_n)
return (e, d)
def main():
flag = get_flag()
p=getPrime(2048)
q=getPrime(2048)
n = p * q
e, d = get_ed(p, q)
print "n: ", hex(n)
print "e: ", hex(e)
flag = bytes_to_long(flag)
enc_flag = pow(flag, e, n)
print "Your flag is: ", hex(enc_flag)
if __name__ == '__main__':
main()
打开靶机得到
n: 0x9224ffc48f301b65df2bebceab3770e57484ff5107dda920aa712b2ed2a2c943b7b11f7ab883b584b2b5eec4597dde4af3e268983ec3804c073a4c78107a866a733d49d9c0e7412001b1f4b448a01355ee27a4a5589ca22d774335b694ed53d329f286a71254188c308821e52080d33895c72c2a17bdfd8ba4d57480f2238cf9f628b1ff59561da34938ac0b4715496ec7598d99d0fd2be547f123a47c564760be2e5c930897fc8d25c5b59633f37e4549c975c207983f4fcc72ae2f8a0fdbf62e0262bd019f28422d5a53871a571d6ff91c7e648bb809834295776c36c0e6d1f738ffb2e888dc646f7ea47f3a577ec83efcb3df4f981c6cc00b5652916350be21b2debc6bfe1eab293d6cffeb117d24784a917cc2f737b624499d66641a24b073f710d3706f355aafadfb45e9d2353ee38920ad2e6b213cc9d674b1626b8fa1cb93633fd9bb5da55fe711a21d104714c2415c995cc17695bd87c0e815f4f4336196ff356aa3a82e42f0eb710377af23b5a5bf25bea687640c3821012c1a2c3619886b517080eb501497bbd068e9d4ce4bf3df311eebc37a63028161a580edc3b8d8196ea1f72ed12ea6c0756939cf33305d4cbd186a346e901167613a4ba32aa6ba616a61eb3ac8697ca2a6990442c9482ee846dbe15fa2cac72fb2740c2732bb9479c85e23f4f9d493bb55dac7e5c1f07ca3dc5cc97799743f07794eaf9f09L
e: 0x108da1d7d12dee41613a7c73c574919ee91f6c638c5ec12fa62453d7398caa48c3190cb42fc5815735fb2fb5dd3c5055b534b11cdc092d457f38db1c79900b8259e79934105b3ee47fea4df9ef1d6e084c50ce785e629159c1d713cc00535140470a2ab85ac664fa195a3cb57f3307047c99aa7dcd7869b7f6ad9b21667b5e0263f2028cc0a18e469fc8f219018cda0cfd2406a3ea74296aa0bb00db2d523b5622fa60f5b08e2a5f1ca3932472fb8f5fafe7f2d2e9c4e601f52ad53a6a0bb7cfced6d675f0715f7fcb294ca7869c51a4913a0448fa29d5a256b0e05bc665090623b06dc5ceed6c281dec2e22db5fcd26e47cddcb84e033ea7ba062d4d50ae0b19ea16929ad0fe35817ba46020b832640bce7276b04a50ddca0e7e3028ecf2f5ed9277e70d936b4ded4523b9bf31a7c927adf1ae1c021101d38cbfa1f6a329c283176d5267ce8b10f4f568725a1ef561647e578bc7928f4e65c76b394d38cd65e3d9d3a8cef3066e963a5b7b6de6fe14a1f66cd2a0bf645beaa079b84536b7238300c4605994f73c30f2341f728a0e0e3d17cd8566b677dc6b2fb1eef036649c4012f2b7c16cae18f1aa07ee3223726269255a062d771cf4e5f424663b834dc97ad19a77abca8adc2ba998f4919b5dd16c28e433922129faf1ab17aa62852805e2c2b647408fe7d8c2f999dbc536f60e74a4bc5d803f1d1a68a0b0f0995b1ff67L
Your flag is: 0x61dbd98692a5cca45cf48d22e6f3012828ccfbd3b7a3f41145b0872c51b57f77ecf439348cf7c866c8658f520a6627231d77fa38dd7fd8bd37da734b12f53bc3f656d5a5342f12f208e0497804af05aa66dc6e65104a36a675f8f4eda3a146b140a477fd3026848fd7f8aaa51f56af62d25b9dca36b31d27dc73f369cc68a008a7b1424e2db2a403d4b1015f4bc0763f31c0a0a9e28775e64ae287adcf0cf70899a26e770128f9fe1f37c1ee296ac50e48d0d10a9a90d58647b2731e88d435055d8ed884a39012c351d26747a2aa57d2be0de4632bd11806b1c98dcd4eb7a5257f04a7b0a998d48ca9d7766e710673ec6f0b783b79dc213b5e567276dbc8e13db7f263b97ef2c0659ae2951f3b4d0107e635486f8e7a309b7df61101fca51ba5d0833e49e9945054fcd361f4de6811225efb64b7e3ac36e24914b34f2457a984960c0e5df745a9836b1a094c661ff01d7c77165387ae6ec5f9f35f0c63721ae2215131db63fbb4b1d35da378cc07a7de24d9bd47c3d775b92cabdc17fb089097507e6b39bfe4987da364c32e7151771da9211919dfb121f4ed4a34989f12ba0bd6219f418d0444d6317759ca66181fd187d32d23ce281b66515f0ae4bac1547f8a592064abfa29858c01d9a8bfc4904c0bcdbdd146bee7b9b11228175aa24c9ed387e41938f34eb8f310b77bfd1ff8ee05fe0ad3360daa5d74ad0b9d8d467ffcL
非常大的n，非常大的e，非常大的m
先尝试的用pythonsympy.nthroot_mod(c,e,n)，需要太长时间了，没跑出来
可能因为n太大了，不能在线工具分解，
用yafu可以分解大n
先下载：https://sourceforge.net/projects/yafu/
直接解压就能用，最好的是用cmd打开，（因为直接打开用的话，不太容易看结果）
一般的n，直接factor(n)就能分解出来
但是，我们不是一般的n啊
当n非常大时，要先把n存到文件中，然后再用yafu解
而且，放到文件中，保存前一定一定要在后面加回车，不然依旧会报错：eof; done processing batchfile
保存到文件之后，用cmd打开，输入yafu-x64 "factor(@)" -batchfile p.txt（这里默认保存到了p.txt)
值得一提是，当运行结束后，原来的p.txt会自动消失
，测试结束就能用到这到题上了
然后就是漫长的等待
等待
等待
等待
忽然觉得是我的思路错了
easy_pow
from Crypto.Util.number import *
from gmpy2 import lcm, invert
from secret import flag
e = 65537
p = getPrime(512)
q = getPrime(512)
n = p**4*q
c = pow(bytes_to_long(flag), e, n)
print(c)
hint1 = (invert(e, lcm(p - 1, q - 1))) % (p - 1)
print(hint1)
b = 449703347709287328982446812318870158230369688625894307953604074502413258045265502496365998383562119915565080518077360839705004058211784369656486678307007348691991136610142919372779782779111507129101110674559235388392082113417306002050124215904803026894400155194275424834577942500150410440057660679460918645357376095613079720172148302097893734034788458122333816759162605888879531594217661921547293164281934920669935417080156833072528358511807757748554348615957977663784762124746554638152693469580761002437793837094101338408017407251986116589240523625340964025531357446706263871843489143068620501020284421781243879675292060268876353250854369189182926055204229002568224846436918153245720514450234433170717311083868591477186061896282790880850797471658321324127334704438430354844770131980049668516350774939625369909869906362174015628078258039638111064842324979997867746404806457329528690722757322373158670827203350590809390932986616805533168714686834174965211242863201076482127152571774960580915318022303418111346406295217571564155573765371519749325922145875128395909112254242027512400564855444101325427710643212690768272048881411988830011985059218048684311349415764441760364762942692722834850287985399559042457470942580456516395188637916303814055777357738894264037988945951468416861647204658893837753361851667573185920779272635885127149348845064478121843462789367112698673780005436144393573832498203659056909233757206537514290993810628872250841862059672570704733990716282248839
a = 2021*p**3 + 2022 + 2023*p**4
hint2 = pow(2, a, b)
print(hint2)
依旧的RSA
我的思路是，先根据b和hint2求出a，进而求出p，然后再根据hint求出q，最后就能解flag了
先尝试的用yuafu分解b
=== Starting work on batchfile expression ===
factor(449703347709287328982446812318870158230369688625894307953604074502413258045265502496365998383562119915565080518077360839705004058211784369656486678307007348691991136610142919372779782779111507129101110674559235388392082113417306002050124215904803026894400155194275424834577942500150410440057660679460918645357376095613079720172148302097893734034788458122333816759162605888879531594217661921547293164281934920669935417080156833072528358511807757748554348615957977663784762124746554638152693469580761002437793837094101338408017407251986116589240523625340964025531357446706263871843489143068620501020284421781243879675292060268876353250854369189182926055204229002568224846436918153245720514450234433170717311083868591477186061896282790880850797471658321324127334704438430354844770131980049668516350774939625369909869906362174015628078258039638111064842324979997867746404806457329528690722757322373158670827203350590809390932986616805533168714686834174965211242863201076482127152571774960580915318022303418111346406295217571564155573765371519749325922145875128395909112254242027512400564855444101325427710643212690768272048881411988830011985059218048684311349415764441760364762942692722834850287985399559042457470942580456516395188637916303814055777357738894264037988945951468416861647204658893837753361851667573185920779272635885127149348845064478121843462789367112698673780005436144393573832498203659056909233757206537514290993810628872250841862059672570704733990716282248839)
=============================================
fac: factoring 449703347709287328982446812318870158230369688625894307953604074502413258045265502496365998383562119915565080518077360839705004058211784369656486678307007348691991136610142919372779782779111507129101110674559235388392082113417306002050124215904803026894400155194275424834577942500150410440057660679460918645357376095613079720172148302097893734034788458122333816759162605888879531594217661921547293164281934920669935417080156833072528358511807757748554348615957977663784762124746554638152693469580761002437793837094101338408017407251986116589240523625340964025531357446706263871843489143068620501020284421781243879675292060268876353250854369189182926055204229002568224846436918153245720514450234433170717311083868591477186061896282790880850797471658321324127334704438430354844770131980049668516350774939625369909869906362174015628078258039638111064842324979997867746404806457329528690722757322373158670827203350590809390932986616805533168714686834174965211242863201076482127152571774960580915318022303418111346406295217571564155573765371519749325922145875128395909112254242027512400564855444101325427710643212690768272048881411988830011985059218048684311349415764441760364762942692722834850287985399559042457470942580456516395188637916303814055777357738894264037988945951468416861647204658893837753361851667573185920779272635885127149348845064478121843462789367112698673780005436144393573832498203659056909233757206537514290993810628872250841862059672570704733990716282248839
fac: using pretesting plan: normal
fac: no tune info: using qs/gnfs crossover of 95 digits
div: primes less than 10000
fmt: 1000000 iterations
Total factoring time = 1.5964 seconds
***factors found***
PRP1473 = 449703347709287328982446812318870158230369688625894307953604074502413258045265502496365998383562119915565080518077360839705004058211784369656486678307007348691991136610142919372779782779111507129101110674559235388392082113417306002050124215904803026894400155194275424834577942500150410440057660679460918645357376095613079720172148302097893734034788458122333816759162605888879531594217661921547293164281934920669935417080156833072528358511807757748554348615957977663784762124746554638152693469580761002437793837094101338408017407251986116589240523625340964025531357446706263871843489143068620501020284421781243879675292060268876353250854369189182926055204229002568224846436918153245720514450234433170717311083868591477186061896282790880850797471658321324127334704438430354844770131980049668516350774939625369909869906362174015628078258039638111064842324979997867746404806457329528690722757322373158670827203350590809390932986616805533168714686834174965211242863201076482127152571774960580915318022303418111346406295217571564155573765371519749325922145875128395909112254242027512400564855444101325427710643212690768272048881411988830011985059218048684311349415764441760364762942692722834850287985399559042457470942580456516395188637916303814055777357738894264037988945951468416861647204658893837753361851667573185920779272635885127149348845064478121843462789367112698673780005436144393573832498203659056909233757206537514290993810628872250841862059672570704733990716282248839
ans = 1
eof; done processing batchfile
我确定我再保存的时候加了回车，难道是b是素数
找个程序判断一下
while True:
num = int(input("请输入一个数："))
if num <= 1:
print("质数必须大于1")
continue
i = 2
flag = True
while i < num:
if num % i == 0:
flag = False
i += 1
if flag:
print(f"您输入{num}是质数")
else:
print(f"您输入{num}不是质数")
运行得到
然后就是新一轮的漫长等待
|