RSA刷题

funnyrsa1

题目

e1 = 14606334023791426
p1 = 121009772735460235364940622989433807619211926015494087453674747614331295040063679722422298286549493698150690694965106103822315378461970129912436074962111424616439032849788953648286506433464358834178903821069564798378666159882090757625817745990230736982709059859613843100974349380542982235135982530318438330859
q1 = 130968576816900149996914427770826228884925960001279609559095138835900329492765336419489982304805369724685145941218640504262821549441728192761733409684831633194346504685627189375724517070780334885673563409259345291959439026700006694655545512308390416859315892447092639503318475587220630455745460309886030186593
c1 = 11402389955595766056824801105373550411371729054679429421548608725777586555536302409478824585455648944737304660137306241012321255955693234304201530700362069004620531537922710568821152217381257446478619320278993539785699090234418603086426252498046106436360959622415398647198014716351359752734123844386459925553497427680448633869522591650121047156082228109421246662020164222925272078687550896012363926358633323439494967417041681357707006545728719651494384317497942177993032739778398001952201667284323691607312819796036779374423837576479275454953999865750584684592993292347483309178232523897058253412878901324740104919248

e2 = 13813369129257838
p2 = 121009772735460235364940622989433807619211926015494087453674747614331295040063679722422298286549493698150690694965106103822315378461970129912436074962111424616439032849788953648286506433464358834178903821069564798378666159882090757625817745990230736982709059859613843100974349380542982235135982530318438330859
q2 = 94582257784130735233174402362819395926641026753071039760251190444144495369829487705195913337502962816079184062352678128843179586054535283861793827497892600954650126991213176547276006780610945133603745974181504975165082485845571788686928859549252522952174376071500707863379238688200493621993937563296490615649
c2 = 7984888899827615209197324489527982755561403577403539988687419233579203660429542197972867526015619223510964699107198708420785278262082902359114040327940253582108364104049849773108799812000586446829979564395322118616382603675257162995702363051699403525169767736410365076696890117813211614468971386159587698853722658492385717150691206731593509168262529568464496911821756352254486299361607604338523750318977620039669792468240086472218586697386948479265417452517073901655900118259488507311321060895347770921790483894095085039802955700146474474606794444308825840221205073230671387989412399673375520605000270180367035526919

题解

gcd(e1, phi) = 14
e1 | p1 - 1 & e1 | q1 - 1

e, phi不互素的第二种情况

这里头脑风暴一下，就可解决（非预期？

直接对c1在有限域开e1次方，开不出来（e1太大了
对c1开14次方，便得到$c_1 ^ \frac{1}{14}$,有：

$$c_1 ^ \frac{1}{14} = m^ \frac{e1}{14} \mod n$$

即：$$c1’ = m^{e’} \mod n$$

此时，e1’ = e1/14, gcd(e1, phi1) = 1

e1‘, phi互素了，解出m

#Sage
import libnum
import gmpy2

e = 14
e1 = 14606334023791426 // 14
p = 121009772735460235364940622989433807619211926015494087453674747614331295040063679722422298286549493698150690694965106103822315378461970129912436074962111424616439032849788953648286506433464358834178903821069564798378666159882090757625817745990230736982709059859613843100974349380542982235135982530318438330859
q = 130968576816900149996914427770826228884925960001279609559095138835900329492765336419489982304805369724685145941218640504262821549441728192761733409684831633194346504685627189375724517070780334885673563409259345291959439026700006694655545512308390416859315892447092639503318475587220630455745460309886030186593
c = 11402389955595766056824801105373550411371729054679429421548608725777586555536302409478824585455648944737304660137306241012321255955693234304201530700362069004620531537922710568821152217381257446478619320278993539785699090234418603086426252498046106436360959622415398647198014716351359752734123844386459925553497427680448633869522591650121047156082228109421246662020164222925272078687550896012363926358633323439494967417041681357707006545728719651494384317497942177993032739778398001952201667284323691607312819796036779374423837576479275454953999865750584684592993292347483309178232523897058253412878901324740104919248
phi = (p-1)*(q-1)
d = gmpy2.invert(e1, phi)

P.<a>=PolynomialRing(Zmod(p),implementation='NTL')
f=a^e-c
mps=f.monic().roots()

P.<a>=PolynomialRing(Zmod(q),implementation='NTL')
g=a^e-c
mqs=g.monic().roots()

for mpp in mps:
    x=mpp[0]
    for mqq in mqs:
        y=mqq[0]
        solution = CRT_list([int(x), int(y)], [p, q])
        m = int(pow(int(solution), d, p*q))
        flag = libnum.n2s(m)
        if b'flag' in flag:
            print(flag)
        
print('Over.')
# b"flag{gcd_e&\xcf\x86_isn't_1}"

对乱码部分hex解码，得：

flag{gcd_e&φ_isn't_1}

ctfshow·EASYRSA

ROARCTF复现

题目

from Crypto.Util.number import *
from gmpy2 import *
from secret import *

assert(flag.startwith('flag{')) and (flag.endwith('}'))
assert(is_prime(beta) and len(bin(beta)[2:]) == 512) 
assert(len(bin(x)[2:]) == len(bin(y)[2:]))
# This is tip!!!
assert(tip == 2*x*y*beta + x + y)

p = 2*x*beta + 1
q = 2*y*beta + 1

assert(is_prime(p) and is_prime(q))

n = p*q
e = 65537
m = bytes_to_long(flag)
enc = powmod(m,e,n)
#n=17986052241518124152579698727005505088573670763293762110375836247355612011054569717338676781772224186355540833136105641118789391002684013237464006860953174190278718294774874590936823847040556879723368745745863499521381501281961534965719063185861101706333863256855553691578381034302217163536137697146370869852180388385732050177505306982196493799420954022912860262710497234529008765582379823928557307038782793649826879316617865012433973899266322533955187594070215597700782682186705964842947435512183808651329554499897644733096933800570431036589775974437965028894251544530715336418443795864241340792616415926241778326529055663
#e=65537
#enc=10760807485718247466823893305767047250503197383143218026814141719093776781403513881079114556890534223832352132446445237573389249010880862460738448945011264928270648357652595432015646424427464523486856294998582949173459779764873664665361437483861277508734208729366952221351049574873831620714889674755106545281174797387906705765430764314845841490492038801926675266705606453163826755694482549401843247482172026764635778484644547733877083368527255145572732954216461334217963127783632702980064435718785556011795841651015143521512315148320334442235923393757396733821710592667519724592789856065414299022191871582955584644441117223
#beta=11864389277042761216996641604675717452843530574016671576684180662096506094587545173005905433938758559675517932481818900399893444422743930613073261450555599

题解

我写的颇为费劲，起初想通过n // pow(beta, 2)得到4xy

再利用%来获得x+y来解方程

以上都是不可行的，因为通过简单判断，知道p、q都是大于beta的

还得向tip看齐
然后根据余数遍历k来爆破x+y，从而得到x*y

最近做的题居然都偏向于这种易被我忽视的
解出x, y
发现p、q是素数
求解rsa

import gmpy2
import libnum
from z3 import *

e = 65537
n = 17986052241518124152579698727005505088573670763293762110375836247355612011054569717338676781772224186355540833136105641118789391002684013237464006860953174190278718294774874590936823847040556879723368745745863499521381501281961534965719063185861101706333863256855553691578381034302217163536137697146370869852180388385732050177505306982196493799420954022912860262710497234529008765582379823928557307038782793649826879316617865012433973899266322533955187594070215597700782682186705964842947435512183808651329554499897644733096933800570431036589775974437965028894251544530715336418443795864241340792616415926241778326529055663
enc = 10760807485718247466823893305767047250503197383143218026814141719093776781403513881079114556890534223832352132446445237573389249010880862460738448945011264928270648357652595432015646424427464523486856294998582949173459779764873664665361437483861277508734208729366952221351049574873831620714889674755106545281174797387906705765430764314845841490492038801926675266705606453163826755694482549401843247482172026764635778484644547733877083368527255145572732954216461334217963127783632702980064435718785556011795841651015143521512315148320334442235923393757396733821710592667519724592789856065414299022191871582955584644441117223
beta = 11864389277042761216996641604675717452843530574016671576684180662096506094587545173005905433938758559675517932481818900399893444422743930613073261450555599
tip = (n - 1) // (2 * beta)  # 2xy*beta+x+y

# a = (x+y) % beta = tip % beta
# x+y = k*beta + a
a = tip % beta
x = 4668043289052029901343771698523052922596858535604154804368853607181324334964567257637285439401177209511493949633696749298641147411501031244979219281057378320
y = 6843057810980339658872333593534427464545104752516312442185148369974064674864085821085976673212477585701065946365239235648157162338024362013460418665527344009
p = 2*x*beta + 1
q = 2*y*beta + 1
assert gmpy2.is_prime(p)
assert gmpy2.is_prime(q)
phi = (p-1)*(q-1)
d = int(gmpy2.invert(e, phi))
m = int(pow(enc, d, n))
print(libnum.n2s(m))

"""
# 求x, y
k = 0
while True:
    x_a_y = k*beta + a
    print(k)
    if (tip-x_a_y) % beta == 0:
        xy = (tip-x_a_y) // (2*beta)
        x = Int('x')
        y = Int('y')
        S = Solver()
        S.add(x+y == x_a_y)
        S.add(x*y == xy)
        S.add(x > 0, y > 0)
        if str(S.check()) == 'sat':
            print(S.model())
    k += 1
"""

ctfshow大🐮杯·小二难度R54

刷知乎刷到的题🤔，la佬出的签到题

做的破为曲折，记录一下

题目

1 2	# x, y = [random_prime(2 ^ 1024 - 1, False, 2 ^ 1023) for _ in range(2)] # x * y, pow(2021 * x + 501 * y, x * y - x - y, x * y), pow(flag, 0o200001, x * y)

[20947495659013288660808536751393787394664606045798093048128257278988208709333248671898749660848208653968668634891579612784633367362177864996602736258460476691940723323282467207875842974409286563660436709535601954405015261428106261369927836045794170912665351432105165546188591486357060490032334793140396757102052999128194027485573053073959574695808224922102635888141991154365047911830780778957642166757152369955362399379720841279167832886144458760347392316082994786119404006382441787685301119197529946566027319295285387108473752590621030421978808950305190250697199878929419723511578437404000924310974770501204226510397, 12911378830212711575909332427930495830030418987483519620282504671823307660633472092466534392403086505995560725428252134905285658936113891795434303336259751169171583600394870893708505805256284455729584616439559184469715186920464999723861722097244025658190194027561300165723184060071016117033960821040587421503448139025974851980482004179865110864844573575034406782936965166402665401330436229441569042660851847498727291447251591027480750458209012729510702196684303778564353025395186191064801000127420683298000173389589468742142444444759536629401472836827952997758216526858512433131954439154124668711408079361172485321041, 13390681135321846035598057088735733735860895610541899486616159864716324918810264721878447895634342127744578566110322466944217562868186608760962032192994397783118528288276520451944892998435079744244578731427626946331165523865930693902700790185275273534104979885060728696532991031786741950704918951536399577118136416956670893081637730646528913282395731901667720418372650030593319596584787752412110672058692368924987360383096340538971725402687347195347344826404005229912821371282465882351660619944919637382790572267512735645269618163597227604601321699186335016345484182059187046972681187078878556533926780789183784240737]

题解

可见把x、y当作p、q,则有：

p、q is prime
给了一下值
- p*q 即n
- $(2021•p+501•q)^{pq-p-q} \mod n$
- $c = flag^e \mod n$
- e = 0o200001 (十六进制下的65537)

一开始觉得怪复杂的，后然看到幂pq-p-q，想到的有威尔逊定理和欧拉定理，显然后者可能有效

于是观察到$(p-1)*(q-1) = pq-p-q+1$

尝试构造之，设$A = (2021•p+501•q)$，$tmp = (2021•p+501•q)^{pq-p-q} \mod n$则：

$tmp*A = A^{\phi (n)} \mod n = 1 \mod n$

我是很不情愿尝试拆开来直接爆破的，但前几次做题都有这操作，这里也情不自禁想：

$tmp•A = k•n +1$, 所以遍历k使得kn+1能被tmp整除，则爆破出A

然后用z3解方程得到p、q

from z3 import *

n, tmp, c = ...
S = Solver()

e = 0o200001
k = 0
while 1:
    print(k)
    if (k*n + 1) % tmp == 0:
        a = (k*n + 1) // tmp
        print(a)
        break
        p = Int('p')
        q = Int('q')
        S.add(q > 0)
        S.add(p > 0)
        S.add(2021*p + 501*q == a)
        if S.check():
            print(S.model())
            break
    k += 1

实际跑起来，几分钟都没结果，作罢

然后再仔细观察👀

$tmp*A = 1 \mod n$

🤔啊这，逆元嘛，这不是

易得：A = inv(tmp, n)

于是，觉得万事大吉！

(其实题目里random_prime(2 ^ 1024 - 1, False, 2 ^ 1023)没看懂，猜测生成素数是小于2\^1024-1，大于2\^1023的)

上z3

import gmpy2
import libnum
from z3 import *

n, tmp, c = 20947495659013288660808536751393787394664606045798093048128257278988208709333248671898749660848208653968668634891579612784633367362177864996602736258460476691940723323282467207875842974409286563660436709535601954405015261428106261369927836045794170912665351432105165546188591486357060490032334793140396757102052999128194027485573053073959574695808224922102635888141991154365047911830780778957642166757152369955362399379720841279167832886144458760347392316082994786119404006382441787685301119197529946566027319295285387108473752590621030421978808950305190250697199878929419723511578437404000924310974770501204226510397, 12911378830212711575909332427930495830030418987483519620282504671823307660633472092466534392403086505995560725428252134905285658936113891795434303336259751169171583600394870893708505805256284455729584616439559184469715186920464999723861722097244025658190194027561300165723184060071016117033960821040587421503448139025974851980482004179865110864844573575034406782936965166402665401330436229441569042660851847498727291447251591027480750458209012729510702196684303778564353025395186191064801000127420683298000173389589468742142444444759536629401472836827952997758216526858512433131954439154124668711408079361172485321041, 13390681135321846035598057088735733735860895610541899486616159864716324918810264721878447895634342127744578566110322466944217562868186608760962032192994397783118528288276520451944892998435079744244578731427626946331165523865930693902700790185275273534104979885060728696532991031786741950704918951536399577118136416956670893081637730646528913282395731901667720418372650030593319596584787752412110672058692368924987360383096340538971725402687347195347344826404005229912821371282465882351660619944919637382790572267512735645269618163597227604601321699186335016345484182059187046972681187078878556533926780789183784240737
S = Solver()

e = 0o200001
A = int(gmpy2.invert(tmp, n))


p = Int('p')
q = Int('q')
S.add(q > 2**1023)
S.add(q < 2*1024-1)
S.add((p > 2**1023))
S.add(p < 2*1024-1)
S.add((2021*p + 501*q) % n == A)
if S.check():
    print(S.model())
    print(S.model()[0])
    print(type(S.model()))

q = ...
p = ...
phi = (p-1)*(q-1)
d = gmpy2.invert(e, phi)
m = int(pow(c, d, n))
print(libnum.n2s(m))

S.add(q < 2*1024-1)、S.add(p < 2*1024-1)这两句一加上就报错，没办法删了，解出来的p、q也不满足大小要求😭

看了下wp

奥！傻了，n=p*q忘记加了

再用z3跑，出了，我觉得万事大吉！

import gmpy2
n, tmp, c = 
e = 0o200001

A = int(gmpy2.invert(tmp, n))
from z3 import *
# S = Solver()
# p = Int('p')
# q = Int('q')
# S.add(q > 2**1023)
# S.add((p > 2**1023))
# S.add(p*q == n)
#
# S.add((2021*p + 501*q) % n == A)
# if S.check():
#     print(S.model())

p = 118025808013874567502972067396154378205921004159004592806833496003217679639841107629090128959992942958292926872941356148283178987927403535617729247751812776636333788905610726461255956234207606642302396722821445909489968841256943549868105578713493559907241758893208485830735235619636112619927867287431575647321
q = 177482332140024816122816575300851746457741976238942019223639223243373845838446387378093437677008231609976122718397287922224412805145965728166071230572137942154170172214953182121671014605624049869925600226560127948579957435119412752482229481128742488177414523194528098131635883615390771259266866469500527361157
phi = (p-1)*(q-1)
d = gmpy2.invert(e, phi)
m = int(pow(c, d, n))
print(libnum.n2s(m))
# emkkocy{lnyu_wp_kxs_kc_ahz_dvjg_by?}

❓这明显是古典加密过了

尝试了凯撒、维吉尼亚、quip无果

实在没办法，看了下wp,春哥写的有些复杂（我看不下去😕），但我看到其解题的思想

于是，自己开始尝试当密码学家了！

明确已知和未知

c = emkkocy{lnyu_wp_kxs_kc_ahz_dvjg_by?}
m = ctfshow….

显然，像是{ _ }这些符号没有参与加密，剔除之

于是有

c = emkkocylnyuwpkxskcahzdvjgby
m = ctfshow

古典的本质是规律，尝试找到这些字符ASCII之间的关系

用密文-已知明文（c-m=key）

flag = 'emkkocy{lnyu_wp_kxs_kc_ahz_dvjg_by?}'
flag_ = 'ctfshow'
key = []
for i in range(len(flag)):
    a = ord(flag[i])
    try:
        b = ord(flag_[i])
        key.append(a - b)
    except:
        pass
print(key)
# [2, -7, 5, -8, 7, -12, 2]

🤔没什么特别明显的规律，因为2出现了两次不妨大胆猜测一个周期有：2, -7, 5, -8, 7, -12

则：明文 = 密文 - 密钥 (m=c-key)

key = [2, -7, 5, -8, 7, -12, 2]

flag = 'emkkocylnyuwpkxskcahzdvjgby'  # 去掉非字母部分
for i in range(len(flag)):
    flag_ = ord(flag[i]) - key[i % 6]
    print(chr(flag_), end='')
# ctfshowsinnrs{do_ouloveit

有不是字母的字符，这就得约定好范围（小写字母）

这种思路源自凯撒密码为代表的古典密码用的 mod26 的思想

于是有：

key = [2, -7, 5, -8, 7, -12, 2]

flag = 'emkkocylnyuwpkxskcahzdvjgby'  # 去掉非字母部分
print(ord('a'))  # 97
print(ord('z'))  # 122
for i in range(len(flag)):
    flag_ = ord(flag[i]) - key[i % 6]
    if flag_ < 97:
        flag_ = 122 - (97 - flag_) + 1  # like 96 对应122（z）
    if flag_ > 122:
        flag_ = (flag_-122) + 97 - 1  # like 123 对应 97(a)
    print(chr(flag_), end='')
# ctfshowsigninrsadoyouloveit

可知，flag为ctfshow{sign_in_rsa_do_you_love_it?}

收获

除了学会灵活性的处理rsa问题外，还对古典密码加深了认知

这后一点尤为关键，队内已出现过只差一步解密出flag的情况了，密码手得给力，一锤定音！

总之，对于古典密码找规律解密，有：

古典明文以字母为内容
古典算法以模的运算为方法
古典解密以约束住范围为关键

👴不只会一一对应的古典密码解密了

哦耶✌️

（实测维吉尼亚还得要全部密文来破解正确密钥！此法无效）

ctfshow 摆烂杯 easy-peasy

据说还是签到题（la佬恐怖如斯Orz）

题目

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

p = getPrime(1024)
q = getPrime(1024)
n = p * q
print(f'n = {n}')

l = len(flag)
assert(l == 86)
m = bytes_to_long(b'\x00' * (l - 1) + flag + b'\x00' * (l - 2))
e = 3
c = pow(m, e, n)
print(f'c = {c}')

# n = 23570098360097260908266914080954003513706885568390448463720576188146956287111601604870247233822682630020002051748117520481402155749832096007629686239669192722978473890311246293580246256300691145653885805730865515297134808702766299205253761028235483781919393575836334910012714628455073300114978717047912395404034141622115001451888302617428376998024080880564792294546406688814397757714979980790018933407614160131827023349206138480523080173634617167828920519758917549492886733519381497665596997617399404664611446202014908853898043742964782757859701755202188366852773164911994663079171498909577012208742001609095258401847
# c = 7802816471025387606454709075933309958303134972861203739854774032383575355964299097074709350633475519273512630813578801152996777689686451397201513854823239337669091889776200179028891111154423623765139235199507280104544068425347533121731521700106757148551520759776111224072064131087547685154285120156917449926992033491342535410929828988598182819897435365878832122138552492908774845437576910276499625679469289655841639181182040186931130789588869657335253479416209378458303531995734157105918063227453396477282662136225029972745246845372963076381252679409317314514131852117346576265346926741908194011319430767975281696400

题解

n分不出来，没有p、q，无法直接有限域开方
e=3，维纳无效，低e攻击跑了很久没结果

觉得能利用的只有m末尾的b'\x00' * (l - 2)，但🤔想不出，没见过，实在不知如何利用

看其他师傅的题解

🐮啊.

但I=86，I-2不是84吗？(确实是师傅着急写错了)

我领悟

不知道p、q就断然不是有限域开方

e=3,只能对应低e攻击

再由以上规律，得：

$m = (flag)•16^{2•84}$

$c = m^e \mod n = flag^3 • 16^{2•3•84}\mod n$

$c’ = c•inv(16^{2•3•84}, n) \mod n = flag^3 \mod n $

将c改小后，简单的低加密指数即可解！

import gmpy2
import libnum
# m越长越不利于爆破出结果

def de(c, e, n):
    k = 0
    while True:
        print(k)
        mm = c + n*k
        result, flag = gmpy2.iroot(mm, e)
        if True == flag:
            return result
        k += 1
e = 3
n = 23570098360097260908266914080954003513706885568390448463720576188146956287111601604870247233822682630020002051748117520481402155749832096007629686239669192722978473890311246293580246256300691145653885805730865515297134808702766299205253761028235483781919393575836334910012714628455073300114978717047912395404034141622115001451888302617428376998024080880564792294546406688814397757714979980790018933407614160131827023349206138480523080173634617167828920519758917549492886733519381497665596997617399404664611446202014908853898043742964782757859701755202188366852773164911994663079171498909577012208742001609095258401847
c = 7802816471025387606454709075933309958303134972861203739854774032383575355964299097074709350633475519273512630813578801152996777689686451397201513854823239337669091889776200179028891111154423623765139235199507280104544068425347533121731521700106757148551520759776111224072064131087547685154285120156917449926992033491342535410929828988598182819897435365878832122138552492908774845437576910276499625679469289655841639181182040186931130789588869657335253479416209378458303531995734157105918063227453396477282662136225029972745246845372963076381252679409317314514131852117346576265346926741908194011319430767975281696400
A = 16**(6*84)
c *= int(gmpy2.invert(A, n))
c = c % n  # 容易忘，c不能比n大
m = de(c,e,n)
print(libnum.n2s(int(m)).decode())

总结

byte后每加一个16进制的‘0’则扩大为原来的16倍
对于低e攻击，flag越长爆破越久以至于失效，所以我们最好能降低flag长度

ctfshow 摆烂杯比烂为主

太长了，i‘m lazy dog

ctfshow 卷王杯真·简单·不卷·现代密码签到

题目

from Crypto.Util.number import bytes_to_long
from secrets import p,q,r,s,t,flag

n = p * q * r * s * t
e = 2
m = bytes_to_long(os.urandom(500) + flag)
c = pow(m,e,n)

print(p,q,r,s,t,sep='\n')
print(c)

'''
p, q, r, s, t = [145332367700944303747548912160113939198078051436029477960348968315913956664143693347226702600438608693933768134575289286283267810723137895903153829001826223446477799895493265422562348917012216790077395795861238257357035152687833639085415763850743538206986781418939737511715957738982536382066693822159860701263,
116660458253067608044065523310547233337730583902133756095473339390057738510707447906971188577217274861047379404014140178165569604404468897712846876108444468370709141219302291601408652742006268186059762087155933131837323952675627966299810891805398890428420575425160696531236660480933905879208166090591482794763,
157931722402853245421436270609912823260313730941283152856444641969403238646482562190531038393124087232554754746464603598717356255570166081501573727336977292059427220330169044611674973569766966838498453232642731737958791706086957762244686953294662693939604300864961637325536379321027705854708492453330690705531,
100973451687449518854742673778783266158999451072058606348222018797891147675959983616210003484476577612134482311993701677242007759556951494382833070563369964294544839433671087037596159753825249018950693369209927951667775267086896180395776150188902057785214767230658487267587289809918132337927575673868568976679,
93960345071948255233882121683650797512129333868351496468898834736770441398743300745703393838320587998953678254272245400344928586394089488734271897540051673996675973642347859306921527430850673334243441180183460927865980713929789963587608547554858491264614271309608925634272282292964002897650355047792764365447,
9144597920381774885442906257311149465702295057238600973973598305004391534618770363098565074541384771979931799878381439264848137810353858418200992191234142740194489573540381681161219332611454834544291634628456257670178843484698324641739324687497388018406214041657278323855749902661752448796122517061920880552011343608609622885787617238758769398972009949575526258430282648817039091284796330585349957724522615105102735930258969562103112238020133587096826386028128471852377225525357348919204333121695432662339443004327748973224423132988376298843862056631045488285859621661802413201793962883794915513510467912312842687601478117040419013468059983777273699192408773551806581458197324620065210523913467414181480875280203580147077789063808832356486197271376615883221558265591069223727607585313240243619515521180600435114131162272519949101464089935441251751426683447701142156416866113627126765919641034042927519834229168536331952275698122511502745177547569813354280565828372968703810158857859460406828090199683324760956105682902577189283246483314689365570862217407333103243336691401424548702387876409228977278498691200028282744239512091373110111792177228979867318546462714521296256938374618636206565791541769138267080789842400796973226733816939794717596194090232425688504890234304977612220790858557639246367437740975495450011676714198668471438814299689325208882261918460708833888406187912527346628912894921059735420931656953236560178909180587372589456926690219114173193202048332172538564489660440225377822914097420807957784201785024166011709377791129]
'''

题解

易得，n的所有因子均为素数

小e，起初想把除p、q外的因子合并集体忽略一试，后发现m很大m = bytes_to_long(os.urandom(500) + flag),无果

后使用不太熟悉的脚本来有限域开方,得解

#脚本2
#Sage
import libnum


e = 2
p, q, r, s, t, c = (145332367700944303747548912160113939198078051436029477960348968315913956664143693347226702600438608693933768134575289286283267810723137895903153829001826223446477799895493265422562348917012216790077395795861238257357035152687833639085415763850743538206986781418939737511715957738982536382066693822159860701263,
116660458253067608044065523310547233337730583902133756095473339390057738510707447906971188577217274861047379404014140178165569604404468897712846876108444468370709141219302291601408652742006268186059762087155933131837323952675627966299810891805398890428420575425160696531236660480933905879208166090591482794763,
157931722402853245421436270609912823260313730941283152856444641969403238646482562190531038393124087232554754746464603598717356255570166081501573727336977292059427220330169044611674973569766966838498453232642731737958791706086957762244686953294662693939604300864961637325536379321027705854708492453330690705531,
100973451687449518854742673778783266158999451072058606348222018797891147675959983616210003484476577612134482311993701677242007759556951494382833070563369964294544839433671087037596159753825249018950693369209927951667775267086896180395776150188902057785214767230658487267587289809918132337927575673868568976679,
93960345071948255233882121683650797512129333868351496468898834736770441398743300745703393838320587998953678254272245400344928586394089488734271897540051673996675973642347859306921527430850673334243441180183460927865980713929789963587608547554858491264614271309608925634272282292964002897650355047792764365447,
9144597920381774885442906257311149465702295057238600973973598305004391534618770363098565074541384771979931799878381439264848137810353858418200992191234142740194489573540381681161219332611454834544291634628456257670178843484698324641739324687497388018406214041657278323855749902661752448796122517061920880552011343608609622885787617238758769398972009949575526258430282648817039091284796330585349957724522615105102735930258969562103112238020133587096826386028128471852377225525357348919204333121695432662339443004327748973224423132988376298843862056631045488285859621661802413201793962883794915513510467912312842687601478117040419013468059983777273699192408773551806581458197324620065210523913467414181480875280203580147077789063808832356486197271376615883221558265591069223727607585313240243619515521180600435114131162272519949101464089935441251751426683447701142156416866113627126765919641034042927519834229168536331952275698122511502745177547569813354280565828372968703810158857859460406828090199683324760956105682902577189283246483314689365570862217407333103243336691401424548702387876409228977278498691200028282744239512091373110111792177228979867318546462714521296256938374618636206565791541769138267080789842400796973226733816939794717596194090232425688504890234304977612220790858557639246367437740975495450011676714198668471438814299689325208882261918460708833888406187912527346628912894921059735420931656953236560178909180587372589456926690219114173193202048332172538564489660440225377822914097420807957784201785024166011709377791129)


P.<a>=PolynomialRing(Zmod(p),implementation='NTL')
f=a^e-c
mps=f.monic().roots()

P.<a>=PolynomialRing(Zmod(q),implementation='NTL')
g=a^e-c
mqs=g.monic().roots()


# r
P.<a>=PolynomialRing(Zmod(r),implementation='NTL')
f=a^e-c
mrs=f.monic().roots()

# s
P.<a>=PolynomialRing(Zmod(s),implementation='NTL')
f=a^e-c
mss=f.monic().roots()

# t
P.<a>=PolynomialRing(Zmod(t),implementation='NTL')
f=a^e-c
mts=f.monic().roots()




for mpp in mps:
    A = mpp[0]
    for mqq in mqs:
        B = mqq[0]
        for mrr in mrs:
            C = mrr[0]
            for mss in mss:
                D = mss[0]
                for mtt in mts:
                    E = mtt[0]
                    solution = CRT_list([int(A), int(B), int(C), int(D), int(E)], [p, q, r, s, t])
                    flag = str(libnum.n2s(int(solution)))
                    if 'ctfshow' in flag:
                        print(flag)
                        break
                break
            break
        break
    break
print('恭喜！')

ctfshow{D0_y0u_R3aLly_Kn0w_Ra8IN_alg0RI7HM?}’

惭愧，e=2确实应该优先考虑rabin的🤔

安徽省赛·Cross_Fire

题目与题解来自Sentry_InkCity 师傅

题目

from gmpy2 import *
from libnum import s2n,n2s
from Crypto.Util.number import *
from flag import plaintext

assert(len(plaintext)>128)
e=65537

m=s2n(plaintext)
p=getPrime(500)
q=getPrime(1024)
r=getPrime(1024)
hint1=p*q*r
hint2=next_prime(p)*next_prime(q)*next_prime(r)
n=next_prime(123*p+456)*next_prime(233*q+233)*next_prime(666*r+666)
c=pow(m,e,n)

print("hint1=",hint1)
print("hint2=",hint2)
print("e=",e)
print("n=",n)
print("c=",c)


'''
hint1= 66597706438052968602907975635364474124624609040691375744383573309100970537667852695911406578339583406993354597653539587007399024156000284162006381513057917653763467490913961403796256103799712489840324677890516295291754752667080587689619591977796148937147026181153407872286012339573004262967216008992456987530280248046317633785368985937352761743401538167742790063446090181640923337990535120783172231525752911772643973809736013911022053243030289179238536988831429875919863032051710061637295482848897179403927441453047333367742504111531477527219109139209305898423562329209375385774722090035022238350104808001927840789351874748994613148197348389169808276135120368108948370654768586592518609889834086412071206692748953099899446867217942417300125520378227882738726940028929
hint2= 66597706438052968602907975635364474124624609040691375744383573309100970537667852695911406578339583406993354597653539587007399024156000284162006381519250037838090700817357286993539595751890863552857025186501118668940000586180857161834771657275281213521087010590085823066429019242511957345355841205805490396285530197202608369351669705515187871274740384884445010749950651326231261308185878145343225072286358030343013074077614396504748731540529394175170653286604110001303387433196918194353309815286558369700754725062771941489664316582212235229725924291159030267475029526286194732206037792356401019048507530494720324382797923052122766854647054667572207470351698834488250064200327557388850421313632751275068766021705342276955127790709872384961830995521889674866200643581197
e= 65537
n= 1271143363426234578109032622706784368982452702551117975547220359092039459949589311614475250751670324493441017909825758822014002389769016887770094631267325830636300148439767061540517538240094507617502786636783685853116121519909167755693185341466272016646232460012649033718198945340871434729792726475237884312244749128647675044166254114409979208613136490968091271215324179363007030770031883104198634577994666369930225951242263540549447415742095183638116238138212512007206154136596565735565134655180583298422538746349678634986942613303728294063886412713958813109459261894779056221585991240656450995515329105180293668452080201635903397760758605883754955173299769359099672851020901544947845931039456152020654355740641530636597180573996251235682717406311406638139251493213898068501
c= 1216485134271178449567116916754420573073303455397620989326464150108908572336526711707238151485187836142308657852844139181641136164876989706372528330194558764108985905734554870749686706876362171680539349216110583849976294434959121174943229853669205013854742739444539161076289486434305028669545715151531610132849739705231210851708893517910447015945450432744842995436173783966889593804335503774508824344205419870078981016701436069437155486571657204182510954434683255699530711440688659074538879785922444601494725802905576491078834520957416860895991743319707987718280613091465577249499325647665822748760483739502978877174961037108839466736686647462799492964587695553596641935803152814769663732674949417986994233658218593205643014847168221928973615157533648368075119704854913178864
'''

题解

太🥬了，没有任何思路

看了师傅题解后，发现搁置的知识点突然攻击我

以连分素数为基础的维纳攻击

连分素数分解出p

from Crypto.Util.number import *
from gmpy2 import *


N1= 66597706438052968602907975635364474124624609040691375744383573309100970537667852695911406578339583406993354597653539587007399024156000284162006381513057917653763467490913961403796256103799712489840324677890516295291754752667080587689619591977796148937147026181153407872286012339573004262967216008992456987530280248046317633785368985937352761743401538167742790063446090181640923337990535120783172231525752911772643973809736013911022053243030289179238536988831429875919863032051710061637295482848897179403927441453047333367742504111531477527219109139209305898423562329209375385774722090035022238350104808001927840789351874748994613148197348389169808276135120368108948370654768586592518609889834086412071206692748953099899446867217942417300125520378227882738726940028929
N2= 1271143363426234578109032622706784368982452702551117975547220359092039459949589311614475250751670324493441017909825758822014002389769016887770094631267325830636300148439767061540517538240094507617502786636783685853116121519909167755693185341466272016646232460012649033718198945340871434729792726475237884312244749128647675044166254114409979208613136490968091271215324179363007030770031883104198634577994666369930225951242263540549447415742095183638116238138212512007206154136596565735565134655180583298422538746349678634986942613303728294063886412713958813109459261894779056221585991240656450995515329105180293668452080201635903397760758605883754955173299769359099672851020901544947845931039456152020654355740641530636597180573996251235682717406311406638139251493213898068501



def continuedFra(x, y): #不断生成连分数的项
    cF = []
    while y:
        cF += [x // y]
        x, y = y, x % y
    return cF
def Simplify(ctnf): #化简
    numerator = 0
    denominator = 1
    for x in ctnf[::-1]: #注意这里是倒叙遍历
        numerator, denominator = denominator, x * denominator + numerator
    return (numerator, denominator) #把连分数分成分子和算出来的分母
def getit(c):
    cf=[]
    for i in range(1,len(c)):
        cf.append(Simplify(c[:i])) #各个阶段的连分数的分子和分母
    return cf #得到一串连分数

def wienerAttack(e, n):
    cf=continuedFra(e,n)
    for (Q2,Q1) in getit(cf):#遍历得到的连分数，令分子分母分别是Q2，Q1
        if Q1 == 0:
            continue
        if N1%Q1==0 and Q1!=1:#满足这个条件就找到了
            return Q1
    print('not find!')
Q1=wienerAttack(N1,N2)
print(Q1)

相邻素数爆破求解q、r

from sympy import *

q = Symbol('q')
r = Symbol('r')

qr = 24000465830725710567609789107532324217407562259754653134149621603287774548503009977306790950765445986759457303910590756566445763189685864660421027894624160496364130162710203056019260859349197460287247433237333855820008311336990774902044072459096643794460636549390819914523204123744097150936438700304426418945328341075502713761684579112067780970129462407486292351679441221444463557410246953331098106055732155261630435421138374418050504535474800628754964367103623724936338041432343848497819682915988508211563927368529558866912220856126132024687748646133065560766894641603193094511181987021442275364527221213343560893411
qr1 =  24000465830725710567609789107532324217407562259754653134149621603287774548503009977306790950765445986759457303910590756566445763189685864660421027894624160496364130162710203056019260859349197460287247433237333855820008311336990774902044072459096643794460636549390819914523204123744097150936438700304426419195181206357035254463948831711777035126077563377919684721062749439252724456974588213705559491260601777470792467850627398598289093915869715222818079606170004475810187367332322557611964471968738992807153326972570559359950761752890888829934863609591544119615229826879764045397320279541476417371138268264031865992001

for i in range(1,2000):
    if i %2 != 0:
        continue
    for j in range(1,5000):
        if j %2 != 0:
            continue
        if solve([q * r -qr,(q + i) * (r + j) - qr1],[q,r]) != []:
            print(solve([q * r -qr,(q + i) * (r + j) - qr1],[q,r]))
        if j % 100 == 0:
            print("i=",i,"   j=",j)

疑惑

连分素数（维纳攻击）的适用条件与具体原理
相邻素数爆破可太久了，有没有更好的解决方式？

BUU·[INSHack2017]rsa16m

题目

给了组巨大的n、c
e=65537

题解

由$m^e \mod n= c$且m较小可知：

$m^e < n$,所以：$c = m^e$,即：$m = c^{1/e}$

import gmpy2
import libnum

with open('rsa_16m.txt') as f:
    data = f.readlines()
    n = int(data[0].split('= ')[-1], 16)
    c = int(data[1].split('= ')[-1], 16)
    e = int(data[2].split('= ')[-1], 16)
    # m^e = c
    m = int(gmpy2.iroot(c, e)[0])
    print(libnum.n2s(m))

总结

17年出的题，当时应该挺新颖有趣的哈哈。

而解题思路在低e攻击中有所体现

Common

题目(大致)

m1 = flag[21:]
m2 = flag[:21]
c1 = pow(m1, e1, n)
c2 = pow(m2, e2, n)
# e1 =  28720970875923431651096339432854172528258265954461865674640550905460254396153781189674547341687577425387833579798322688436040388359600753225864838008717449960738481507237546818409576080342018413998438508242156786918906491731633276138883100372823397583184685654971806498370497526719232024164841910708290088581
# e2 =  131021266002802786854388653080729140273443902141665778170604465113620346076511262124829371838724811039714548987535108721308165699613894661841484523537507024099679248417817366537529114819815251239300463529072042548335699747397368129995809673969216724195536938971493436488732311727298655252602350061303755611563
# n =  159077408219654697980513139040067154659570696914750036579069691821723381989448459903137588324720148582015228465959976312274055844998506120677137485805781117564072817251103154968492955749973403646311198170703330345340987100788144707482536112028286039187104750378366564167383729662815980782817121382587188922253
# c1 =  125774545911886560112703402972153322080506025378797523936708278181480201146872577291738201370911792392950418121767343486509724963000477466590009600240375221563806039364611362947152096656513910712238094956240996452246301471555709823003175801134035094856941903678067489942047840663479442285170087613352040341832
# c2 =  125874844114757588984441500491946737723620819049276461078841545869549114013042058416210220287667061892072831243333341942699313440553285306436999725802970995457080384300690875762412008576026273931144721166609563493297003298586115510199518494430188305644317422640652955882264990001338974742192006748451975507803

题解

看到common，脑子里只有共模攻击，可悲

仔细看会发现，有两个m，不满足共模攻击（n, m相同）

去la佬RSA总结里找，找对了代码，居然只会照搬，事后看wp觉得自己连个合格的脚本小子都不是😢

先贴一下题解

多组低解密指数攻击

求phi

from sage.all import *
import gmpy2
e1 =  28720970875923431651096339432854172528258265954461865674640550905460254396153781189674547341687577425387833579798322688436040388359600753225864838008717449960738481507237546818409576080342018413998438508242156786918906491731633276138883100372823397583184685654971806498370497526719232024164841910708290088581
e2 =  131021266002802786854388653080729140273443902141665778170604465113620346076511262124829371838724811039714548987535108721308165699613894661841484523537507024099679248417817366537529114819815251239300463529072042548335699747397368129995809673969216724195536938971493436488732311727298655252602350061303755611563
N =  159077408219654697980513139040067154659570696914750036579069691821723381989448459903137588324720148582015228465959976312274055844998506120677137485805781117564072817251103154968492955749973403646311198170703330345340987100788144707482536112028286039187104750378366564167383729662815980782817121382587188922253
c1 =  125774545911886560112703402972153322080506025378797523936708278181480201146872577291738201370911792392950418121767343486509724963000477466590009600240375221563806039364611362947152096656513910712238094956240996452246301471555709823003175801134035094856941903678067489942047840663479442285170087613352040341832
c2 =  125874844114757588984441500491946737723620819049276461078841545869549114013042058416210220287667061892072831243333341942699313440553285306436999725802970995457080384300690875762412008576026273931144721166609563493297003298586115510199518494430188305644317422640652955882264990001338974742192006748451975507803
for i in range(1):
    alpha2 = i/1000
    M1 = int(gmpy2.mpz(N)**0.5)
    M2 = int( gmpy2.mpz(N)**(1+alpha2) ) 
    D = diagonal_matrix(ZZ, [N, M1, M2, 1])
    B = Matrix(ZZ, 
               [ [1, -N,   0,  N**2],
                 [0, e1, -e1, -e1*N],
                 [0,  0,  e2, -e2*N],
                 [0,  0,   0, e1*e2] ]) * D
    L = B.LLL()
    v = Matrix(ZZ, L[0])
    x = v * B**(-1)
    phi = (x[0,1]/x[0,0]*e1).floor()
    print(phi)

求m1、m2

import gmpy2
import libnum

e1 =  28720970875923431651096339432854172528258265954461865674640550905460254396153781189674547341687577425387833579798322688436040388359600753225864838008717449960738481507237546818409576080342018413998438508242156786918906491731633276138883100372823397583184685654971806498370497526719232024164841910708290088581
e2 =  131021266002802786854388653080729140273443902141665778170604465113620346076511262124829371838724811039714548987535108721308165699613894661841484523537507024099679248417817366537529114819815251239300463529072042548335699747397368129995809673969216724195536938971493436488732311727298655252602350061303755611563
n =  159077408219654697980513139040067154659570696914750036579069691821723381989448459903137588324720148582015228465959976312274055844998506120677137485805781117564072817251103154968492955749973403646311198170703330345340987100788144707482536112028286039187104750378366564167383729662815980782817121382587188922253
c1 =  125774545911886560112703402972153322080506025378797523936708278181480201146872577291738201370911792392950418121767343486509724963000477466590009600240375221563806039364611362947152096656513910712238094956240996452246301471555709823003175801134035094856941903678067489942047840663479442285170087613352040341832
c2 =  125874844114757588984441500491946737723620819049276461078841545869549114013042058416210220287667061892072831243333341942699313440553285306436999725802970995457080384300690875762412008576026273931144721166609563493297003298586115510199518494430188305644317422640652955882264990001338974742192006748451975507803
phi = 159077408219654697980513139040067154659570696914750036579069691821723381989448459903137588324720148582015228465959976312274055844998506120677137485805781092330556185082570865052488981154655643850588559740031994465378408628749828052127213663711396922494795088638471519778995496857305118321851028470398469453660
d1 = int(gmpy2.invert(e1, phi))
d2 = int(gmpy2.invert(e2, phi))
print(libnum.n2s(int(pow(c1, d1, n))).decode() + libnum.n2s(int(pow(c2, d2, n))).decode())

总结

因为$d = inv(e, phi)$，所以$ed = k•\phi + 1$，即：$d = \frac{k•\phi +1}{e}$

而e真的很大（正常就65537），想来d就大不了，即：低解密指数

低加密指数广播攻击需要给出e
多组低解密指数攻击不需要（也不能给出d）

CBCTF · check in

题目

from gmpy2 import *
from sympy import isprime,nextprime
from Crypto.Util.number import getPrime as getprime ,long_to_bytes,bytes_to_long,inverse
from vanish import flag
import random


def Getprime(g):
 while True:
     p=g*random.randint(1,g)+1
     if isprime(p):
         return p

m=bytes_to_long(flag)

g=getprime(512)
p=Getprime(g)
q=Getprime(g)

e=65537
def lcm(a,b):
 return (a*b)/gcd(a,b)

print 'lcm(p-1,q-1): %d'%(lcm(p-1,q-1))
print 'n: %d'%(p*q)
print 'c: %d'%(pow(m,e,p*q))


'''
lcm(p-1,q-1): 29222879530390785742605477742453420902991175027283185502224574005903986263169096240656898659768251131170153243355896585116206546809026765977240398343841844413932022486239027317290376878970267549705130293352356070399197681533774641809920245792277386418338948725614463605422608450981946445029718369662946357705499281823362508397007696635982211082237545037851621498721235291885337720080893169582699780294708804334786758878624750037193583886404728146815380945201540
n: 2228582814888322539771891137733971181257097900700884269780928959802985615275288341111620316685788511492461651695428697100554113037555468881895905318207963274537589532345166133820089694201148988443496514751074857966136041157336680322417272183777409351597268908625677512781049274972325769500959755298004643407023188886359792411648183582888979219785653927285023667015990929441992061367448365123092899330885934801013411132173550954938961520075931155848843991824723727187297663420031211934554344568933171179175237722716971390081142435747796272698118097337803559316319210494963021258386613285360239662354953552369582646607
c: 2201106853018581355094419701171997731036843750081916703504266002782698731288317690546242336345890702261049147276084047271293227314969153138029180802403349980519050857699472720333400348342466190619778247784674359271736569275019018808569614566880813745619585529292155639979431043005511905548345767685472340763230813956617014122768477272236518467064016133244646900977041959848793579834848773548018337874928875046550721154575652528641850315494384644468806058021812603748441246192757443085386516155814337307681275922473564325028703523754319072117202083218199961250157611091952832038366393322275194833927035639232266868638
'''

题解

lcm=29222879530390785742605477742453420902991175027283185502224574005903986263169096240656898659768251131170153243355896585116206546809026765977240398343841844413932022486239027317290376878970267549705130293352356070399197681533774641809920245792277386418338948725614463605422608450981946445029718369662946357705499281823362508397007696635982211082237545037851621498721235291885337720080893169582699780294708804334786758878624750037193583886404728146815380945201540
n=2228582814888322539771891137733971181257097900700884269780928959802985615275288341111620316685788511492461651695428697100554113037555468881895905318207963274537589532345166133820089694201148988443496514751074857966136041157336680322417272183777409351597268908625677512781049274972325769500959755298004643407023188886359792411648183582888979219785653927285023667015990929441992061367448365123092899330885934801013411132173550954938961520075931155848843991824723727187297663420031211934554344568933171179175237722716971390081142435747796272698118097337803559316319210494963021258386613285360239662354953552369582646607
c=2201106853018581355094419701171997731036843750081916703504266002782698731288317690546242336345890702261049147276084047271293227314969153138029180802403349980519050857699472720333400348342466190619778247784674359271736569275019018808569614566880813745619585529292155639979431043005511905548345767685472340763230813956617014122768477272236518467064016133244646900977041959848793579834848773548018337874928875046550721154575652528641850315494384644468806058021812603748441246192757443085386516155814337307681275922473564325028703523754319072117202083218199961250157611091952832038366393322275194833927035639232266868638
e = 65537

import gmpy2

d=gmpy2.invert(e,lcm)  # 事实上，lcm乘多少都可以
m=pow(c,d,n)
print(bytes.fromhex(hex(m)[2:]))

同态加密

参考

from Crypto.Util.number import getPrime as getprime ,long_to_bytes,bytes_to_long,inverse
from vanish import flag
from sympy import isprime,nextprime
import random

m=bytes_to_long(flag)
p=getprime(512)  # 酱紫写？？
q=nextprime(512)
n=p*q

r=random.randint(1,n)
g=random.randint(1,n)

c=(pow(g,m,n*n)*pow(r,n,n*n))%(n*n)

print "c=%d"%(c)
print "n=%d"%(n)
print "g=%d"%(g)

'''
c=14643617840485727260687883789514337554960495078025159182484344940901600090810578182116617501128323641882943106663241094886209190199404002314247096613925999812837877843566116787148411743428714726661042213165729562285577768043368385746666607442372252641495230532588344276427261824205414379772728577442269620217619275
n=5650215343715484415924649393302012617620686312875699289646188186788806118580423414401283971780836312947326343790326120926819026727018136169739576760024802083
g=786539430846729749998127835613552594423101498023741082894370020014675937062722533682541592019332908209917194089077366019472368764411032602494945304850258108

'''

$c = （g^m \mod n^2）*（r^n \mod n^2）\mod n^2 = g^m * r^n \mod n^2$

给c、n、g

Paillier密码，于1999年由Pascal Paillier发明，是一种用于公钥加密的概率非对称算法。该算法具有加法同态的性质 ; 这意味着，仅给出公钥和m1、m2加密，可以计算出m1 + m2

模式1

大素数p、q满足$gcd(pq, (p-1)*(q-1)) = 1$
$n=p\cdot q，λ = lcm(p-1, q-1) = \frac{(p-1)\cdot (q-1) }{ gcd(p-1,q-1)}$
选g, $0<g<n^2$
$L(x) = \frac{x-1}{n}$
$μ = (L(g^λ \pmod {n^2} ))^{-1} \pmod n$
公钥：（n, g）
私钥：（λ，μ）

模式2

在模式1的基础上，改写g，λ，μ

$g=n+1$
$λ = φ(n) = (p-1)\cdot (q-1)$
$μ = φ(n)^{-1} \pmod n$

加密

明文m需要满足$0≤m＜n$
选择随机 r，且满足$gcd(r,n)=1$
密文：$c=g^m⋅r^n(\mod n^2)$

解密

$m = ( L( c^λ \pmod {n^2} ) \cdot μ ) \pmod n$

题解

分解n,得到p、q

然后跟着解密步骤解就完事了

🤔但p的bit数好像根题目不符

import gmpy2
import libnum


def L(x):
    return (x - 1) // n


c = 14643617840485727260687883789514337554960495078025159182484344940901600090810578182116617501128323641882943106663241094886209190199404002314247096613925999812837877843566116787148411743428714726661042213165729562285577768043368385746666607442372252641495230532588344276427261824205414379772728577442269620217619275
n = 5650215343715484415924649393302012617620686312875699289646188186788806118580423414401283971780836312947326343790326120926819026727018136169739576760024802083
g = 786539430846729749998127835613552594423101498023741082894370020014675937062722533682541592019332908209917194089077366019472368764411032602494945304850258108
# print(factor(n))
p = 521
q = 10844943078148722487379365438199640340922622481527253914867923583087919613398125555472713957352852807960319277908495433640727498516349589577235272092178123
la = ((p - 1) * (q - 1)) // int(gmpy2.gcd(p - 1, q - 1))
tmp = L(int(pow(g, la, n ** 2)))
miu = int(gmpy2.invert(tmp, n))
m = (L(int(pow(c, la, n ** 2)) * miu)) % n
print(libnum.n2s(int(m)))

总结

同态加密基于rsa的大素数分解难题，能得到p、q又有公钥就可解

HZNUCTF校赛·math1

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from Crypto.Util.number import getPrime


e = 0x10001
p = getPrime(1024)
q = getPrime(1024)
n = p * q
phi = n - p - q + 1

m = p * getPrime(135)
c = pow(m, phi * getPrime(69) + 1, n)
flag = b"HZNUCTF{" + hashlib.md5(hex(m).encode()).hexdigest().encode() + b'}'

print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
print(f"p ^ q ^ x = {p ^ q ^ getPrime(100)}")
# n = 27963651181285314865245223420841376949170358907033350824157378307987529217967991046373794961962733982506983121192630829109141085046224889488610665139200726263728575086325474153370048617139175155262273813416260466529090140061623799460692881049637337480902401228983124051195350877685069281198499676151295387541487095621386248400085706944431571931100086046020193927566333993198580530464009149542183771408158783932309677038461604312997489255869750091721432213923367520176509845949128808520689563162109940702067960753814992404492253609346481785015501090495665364667572730774672925265663102438782954524410643148314614834421
# e = 65537
# c = 4112542234772265176907045140450105601374470669674397930575891050044126457030160166683760719042621526735064403906550294282692637793834725289405872203962576032128609572771779107747278189191796105964591794849874405525188273203917555992638684936192155868595119909648305108899175081741865334855359578531440348739274118813283368968474494522365300464616479
# p ^ q ^ x = 20322403539370874641338228395838205584791500136939852001791339832796937713367291083719519539069010591274070142977525555745107989472468046373764089233806857920378983806258439075231320039084798858470920027262481032484629504006942867681413153495094107614132308526877912014998940951049975837247629492037044418733

题解

将phi * getPrime(69) + 1当作e，由逆元定义，易得：d=1

import hashlib
n = 
c = 
e = 

m = int(pow(c,1, n))
print(m)
flag = b"HZNUCTF{" + hashlib.md5(hex(m).encode()).hexdigest().encode() + b'}'
print(flag)
# b'HZNUCTF{a664dad27b1a4bf0dd56f71bba4a8b1d}

Cop! Run!!

题目

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

n = 1 << 8
p = getPrime(n)
print(p)

P.<t> = PolynomialRing(Zmod(p))
f = t * t + randrange(p)
print(f)

x = [randrange(p)]
x += [f(x[0])]
print([x_ >> (n - ceil(5 * n / 7)) for x_ in x])

flag = bytes_to_long(flag)
y = f(x[-1])
for i in range(7):
    y = f(y)
    flag ^^= int(y)
print(flag)

'''
92946459607669937513774102250057295249718593723232674702212854287358873135783
t^2 + 43844336985235863734419631630425915388298791521868754583032904718644333115590
[3248642833056635029095920782095626337949113592116495266, 4883935221919623989344404485025479346028101682781790392]
193207529097125793778662519051231322609402866155819915933598367395102313904490702547833
'''

题解

二元Coppersmith乱杀

（根据题目构造好函数求低位就可以利用二元Coppersmith求得x列表

flag解密过程与加密过程一致

# SageMath
load('coppersmith.sage')
import libnum
n = 1 << 8
bits = n - ceil(5 * n / 7)
p = 92946459607669937513774102250057295249718593723232674702212854287358873135783
P.<x0_0, x1_0> = PolynomialRing(Zmod(p))
tmp = 43844336985235863734419631630425915388298791521868754583032904718644333115590
x0_1 = 3248642833056635029095920782095626337949113592116495266 << bits
x1_1 = 4883935221919623989344404485025479346028101682781790392 << bits
f = (x0_1+x0_0)**2 + tmp - (x1_1+x1_0)
x0_0, x1_0 = small_roots(f, (2^bits, 2^bits), 3)[0]
x0 = x0_1 + int(x0_0)
x1 = x1_1 + int(x1_0)
x = [x0, x1]
flag = 193207529097125793778662519051231322609402866155819915933598367395102313904490702547833
P.<t> = PolynomialRing(Zmod(p))
f = t * t + tmp
y = f(x[-1])
for i in range(7):
    y = f(y)
    flag ^^= int(y)
print(libnum.n2s(int(flag)))

NSSCTF·[强网杯 2019]copperstudy

模版套娃题

（NSSCTF复现的有些问题，可能存在代码对了没结果的情况，做的颇为费时

题目

只给了靶机地址与端口, 连接后开始挑战

题解

sha256爆破

(base) wenhui@Harrys-MacBook-Pro ~ % nc 1.14.71.254 28406
[+]proof: skr=os.urandom(8)
[+]hashlib.sha256(skr).hexdigest()=67328fdbc950d58d6194a09ca7ad2751d5cdef2e75d4bd57cd9f06d5813f0ad0
[+]skr[0:5].encode('hex')=e2130d4e25
[-]skr.encode('hex')=
e2130d4e254fd917
proof completed

import socket
import hashlib
from itertools import product


def decry(data):
    s = hashlib.sha256()  # Get the hash algorithm.
    s.update(data)  # Hash the data.
    b = s.hexdigest()  # Get he hash value.
    return b


sha = '323b72a6cd69d0b7780ec5a7f5ca467888cab27ddd2e4aa4e60b73a94e12c77d'
hex5 = '190a2e347c'
hex5 = hex5.decode('hex')

table = [chr(i) for i in range(256)]
skr = ''
for i in product(table, repeat=3):
    i = ''.join(i)
    skr = hex5 + i
    print(skr)
    skr_ = decry(skr)
    if skr_ == sha:
        print('OK')
        print(skr.encode('hex'))
        break

已知m高位

[+]Generating challenge 1


[+]n=24356325449465878008573189069822683605566325207916003425572312871257434066735339351419022606651978564409319854124040390674260674732564840194350117020415343008229943042334102640238880933567550793561550749967150961083366558936482352374990331852259346471621770085261320898538402590645945335446391581595043991636430048371479572927936823346342473370679940627084184474965268493672815645510317544641300573456793341459261030239478468256474697145442446703874239050652733363969490084736015234648029721030296379935311207385820508381103059781709196062980850466538106046617857536788261456423074851392626599614225296568220684082233

[+]e=3

[+]m=random.getrandbits(512)

[+]c=pow(m,e,n)=279116358436840581010075391425636114595316473734626962378925974945912936713312369021195130534903624351919224866669072204225138654025018245713127331395303380222577110932576056933575781802632335925559470076545360667419161465650880040669969136201922200324547177017394013299202303169894435173

[+]((m>>72)<<72)=653524334392227601010919065348707977696937791058152587391549467964777834749978354872413711237120

[-]long_to_bytes(m).encode('hex')=

4e53534354467b39323534303365663262613837316331313365623038353131363636356631347d
challenge1 completed

# sage
from Crypto.Util.number import *

n = 17641791540530228694286135185364074270246417140538172343866345466143247980659455424376045685494166279876110132203178803899115680922576583783724143783790241934890713111735488241729348106606502962464794620278410346388397359673075821123140990941942289674002895075430115017639376231448894324816030053817634283366169122125231411123494823295007054961127500058834017497105743260495984200175488365511990260484741462938371341033116032935020587367904271953619183649263518669540687237751562870973258276042987062056763970912250995314217713966476714492906919554248815811082015216774212685970371820986012163337575801128737022100901
mbar = 653524334392227600317610369760395325667407883325756386751869881379847068844170310055337360621568
c = 279116358436840580121751323591931874995783037840229208462822785113356478604601761572940996937612929433055849494515561733423792677427130977192018567922037737644911574834397373382160864107212935056196095912820832399095116695115669158974901004546975979648317608777413620402597811562020634469
e = 3
kbits = 72

PR.<x>=PolynomialRing(Zmod(n))
f = (mbar + x) ^ e - c
x0 = f.small_roots(X=2^kbits, beta=1)[0]  # find root < 2^kbits with factor = n

print(long_to_bytes(int(mbar) + int(x0)).hex())

已知p高位

[+]Generating challenge 2


[+]n=23411615301291435655477801748625769339716407033511189983098780086891046009303028158463324140747944603588215418067393823094137876411379397381410031095697696292166476032512871410272768379677559567972276031538034846795245203959238906540111544506685078584531349272589770893813281618844530003255759935566936903284897174521506447857387462971045194978917820434934738691829707246515997926007217221181797932139498440604926293194444820566068160382363378745057906848008922430323300850797214158795943526446652900363836595788985435156443232660016272234951129406706808949692152532652106869678988356843173692120312556632060687880277

[+]e=65537

[+]m=random.getrandbits(512)

[+]c=pow(m,e,n)=20816687484629729248358599515200912090054626605187551167120440993080422432047195669753081296607778685789965152636292757077874182391701553297762409167922636195265302544331699555007035722696233758502329524496584833047661025920311619881120186355000799849110094937608332808435206343994582498338158558465886308617345046792992841949660056279285857662920319320845051388660815881694032340263668979130325615050235744767268030400030419743994149379045928464190406672664167865665901137911387554138311249666942277285098274888564033164491871776333496136941304304822482118466906618116810675882818933948662360186284886643033894106033

[+]((p>>128)<<128)=168129018477669834191979662452833171533865381169326621445539439928300089595715365788571138946327251430738085293790548033554213639388233113347470851361022852297671479442101374855849510028550686558156349265097691151737089307186764069936608051965694418753664327625349371264720709116711249000736290817929925099520

[-]long_to_bytes(m).encode('hex')=

4e53534354467b63653832653937626262333535616338353030303563306234336335306232357d
challenge2 completed

# sage
import libnum, gmpy2
c = 11137144779427596512325170685147473562579382171362503478475347640064577221517156636753228911996179961656510854973657786717656831471849897729940758053634217813748772532744785202527028799463823823951772911580724026290152964384253894559215344542770992252528792774895912147793520115570149507132169954672432261296536921008916861400631531765187550047503023916993544848424696991248835704817941853830044856268328430457918271247908784305049525074525029765749136180181560277025886732703297510912964179476813614319822496848845364727714491057767489809429555415276322397248388069790294482714516847353457868720649928392324385783659
n = 20830947925132665202608201476543152873707285891221124190904503664462033960785788367156025547382844076879484108425075427999117558274080485370433894095168224986681460752870638969251201797984438385751454853811849334656135699018814782166761946734037568555000233999876021096147306660374648595995387615158849254147278615137349869283097560770056763007765458447973952497550521101298016814755832737137678555795393691003900822094504217885765408832692854710255311214322215461040107114896262753620554174647040295543768855026488354367051909095849614827812242316337627929542206753163951992499102075017588133211511519442589868399209
e = 65537
kbit = 128
p0 = 118940119210016317990045155801100877489358068423123091575907183556540755690934705051716625103536230858583816920450205621200746207520769560428951671838067737785302213169572869149358081263673577776906772000439883491594209298392583037331881591354747527243747594112438728757721325095719043772720836197132036734976
PR.<x> = PolynomialRing(Zmod(n))
f = p0+x
x = f.small_roots(X=2^kbit, beta=0.4)
# [1543502407706049247756460709245532058042364294454474880044105, 420644368256035122521364007269668769246032840480767531547935]
p = p0+int(x[0])
q = n // p
d = int(gmpy2.invert(e, (p-1)*(q-1)))
m = int(pow(c, d, n))
print(libnum.n2s(m).hex())

给了d低位，但跑不出来，用低e攻击秒出

[+]Generating challenge 3


[+]n=89773856865647532789133848688372646776565366548252598781217905632498934212599593153200577780255807845681796915152934480943076563244617360693170810625153463474211910134539180021228359564467810301969996364868063052147561336853528490258438355476747407405146293273491444021091430384405451231994292618908534380557

[+]e=3

[+]m=random.getrandbits(512)

[+]c=pow(m,e,n)=279116358436840586974709590248388946576516187502518179576988811874767402972588315731516153520734651957821612329831372799017402780741995987375258636667865079100987795289407232620878830630802280166734640423706695819192808948526182697434731647473235541700077832678666281560894630034271897701

[+]d&((1<<512)-1)=49802280372024724635830244988989932315803129085391269518611260496201496486820364910639967526858055384357625463893876156338160967361580798877826917845419

[-]long_to_bytes(m).encode('hex')=

4e53534354467b61663735633934373838343032666637646236383865613739623062383562617d
challenge3 completed

import gmpy2
import libnum
# m越长越不利于爆破出结果
"""
a,b = gmpy2.iroot(mm, e)
a 为 mm开e次方的结果，b为是否刚好开得出来（True/False）
"""

def de(c, e, n):
    k = 0
    while True:
        print(k)
        mm = c + n*k
        result, flag = gmpy2.iroot(mm, e)
        if True == flag:
            return result
        k += 1
n=91046679824709970162166510393984349436507160355504054099795745710843918232291158893173392345202539943129024459721861867023537200311589378076393008186869632816007290025155710690087286079985123881126900629981074014645167000252730113633981429235819837855381591602381430468841314334641325933457672374936644601001
e=3
c=279116358436840580418940102891469361711985570618086638410015681467792988932869992663175128601830997392899009434533165482291158081783499352092021651217760633821487767077178436162836170197174297227386919476479085259086862455979023948465984342333447127816627669958590898325507691223787985253
m=de(c,e,n)
print(libnum.n2s(int(m)).decode())

低加密指数广播攻击

[+]Generating challenge 4


[+]e=3

[+]m=random.getrandbits(512)

[+]n1=124563768792509416008021985841989981753081792478825800792286148435153131654283140323871125343656088446362263151697679035960009773023601459103303176772978649138999131316408093332655524416277152851939729963632286727238149879320579508735328790324506013446484343697799236052707784724755318248649291652344571831589

[+]c1=pow(m,e,n1)=279116358436840587566517694780928913487931485947614234823704404472617434263815671470444622266041047403738401080570039104060390493635635368662340875816838891757569305641456773339288967618075926659958357128374510362586125506882728421087631651655548042939805790783968753171259731111234177125

[+]n2=84561797704957266384491892654217513080694101006520363876005508497555421491740438708265907215897849175263004958278087751419225733590045477508001930670477095753833707256639507434950981063366889326293773824286487630076834730686515093065667286594656088214885435486297779174231374502701401724440519010791267672247

[+]c2=pow(m,e,n2)=279116358436840587566517694780928913487931485947614234823704404472617434263815671470444622266041047403738401080570039104060390493635635368662340875816838891757569305641456773339288967618075926659958357128374510362586125506882728421087631651655548042939805790783968753171259731111234177125

[+]n3=68490468751767969355094121227532448791974100305463186385862867801481483238694557331841003069191634601446560572940776531299769320776951684806416392460319020564810717065235353421959188531834413019658113978451922955896227028787460869516167582878879171620869415099300899129116470300679216567233807270409324443567

[+]c3=pow(m,e,n3)=279116358436840587566517694780928913487931485947614234823704404472617434263815671470444622266041047403738401080570039104060390493635635368662340875816838891757569305641456773339288967618075926659958357128374510362586125506882728421087631651655548042939805790783968753171259731111234177125

[-]long_to_bytes(m).encode('hex')=

4e53534354467b65636238363236376433663162623736363732373431646635353930613463617d
challenge4 completed

import gmpy2
from functools import reduce
import libnum


def CRT(ai, mi):
    assert (reduce(gmpy2.gcd, mi) == 1)
    assert (isinstance(mi, list) and isinstance(ai, list))
    M = reduce(lambda x, y: x * y, mi)
    ai_ti_Mi = [a * (M // m) * gmpy2.invert(M // m, m) for (m, a) in zip(mi, ai)]
    return reduce(lambda x, y: x + y, ai_ti_Mi) % M


e = 3
n = [108736816241175665148273398258758080018960946338287263364569374726302196169162605670881735552997454446042995869651449282714639817085183228827146377987324938368188209657339192168670905752630070180008635819292194863047273313500409087217920196986541427006384815578060250088479783691454217221007011624615314023899, 125311072436452106223310243651666447263593613934983230425360328449529562394786242626857578081604150972806837244925660405048300400604492591126681020111390674731777377449723245786875368033901438466732844507365503701957616443294592677795315630591380298492356628165441987010153245453234081489921029340196899395331,
     145952553475400806121889743433836062205241126114628994131042124255411306520718902459725859533701853065633604102288257122762822143440371454643188884668825711330843803637043792113112949317335498541040720711359198080384919545170988381565195230298044019615673547840211274883413248354873966128295173063309521168793]
c = [279116358436840587095249496686254280407332053342087519248181392057376438009454609418875798499072335086788124425593780862179185140902876002463710935769268790619149829113441912759030007987894680912774697528843208252759906296795513540716051082272447068540992498830366255300897173712420417125, 279116358436840587095249496686254280407332053342087519248181392057376438009454609418875798499072335086788124425593780862179185140902876002463710935769268790619149829113441912759030007987894680912774697528843208252759906296795513540716051082272447068540992498830366255300897173712420417125,
     279116358436840587095249496686254280407332053342087519248181392057376438009454609418875798499072335086788124425593780862179185140902876002463710935769268790619149829113441912759030007987894680912774697528843208252759906296795513540716051082272447068540992498830366255300897173712420417125]





"""
#  五进制转十进制
n1 = []
c1 = []
for each in n:
    n1.append(int(str(each), 5))
for each in c:
    c1.append(int(str(each), 5))
n = n1
c = c1
"""

# 利用中国剩余定理求解
m = gmpy2.iroot(CRT(c, n), e)[0]
print(libnum.n2s(int(m)).hex())

明文线性相关

[+]Generating challenge 5


[+]n=21429425398210967707909628859942973537224436647532980230726493099305742824766270853929975972690303041909526001733991446303871137522439503328925032466304256374647359518452449746921513559066080682460078094776752212082321993409045104876731233286545426838926300103834290157528384506385481519688666000782856609900851612966748184414791450182758413018973605263391254135754688148513923482024316942640211588559652059925484962822975577587275910085801634523858135106240262529639244908508123451583901185630426915824725575396390698386609888739848106462455208373547256248127515773962595744124798303915247122445176133387866920105233

[+]e=7

[+]m=random.getrandbits(512)

[+]c=pow(m,e,n)=3913355162506843667079312859018190210750453812024216931887013212736340446942162694100894791135119403317486675866999568493278124809272327516322633309413823913596448870616331557266099673907258759210921465394812506017015841046660045982292478544487202676877585076443587857982785230839097210888481000514300634948079175019815712503927918346384686657080274822468346123329902364959230990767464857544305639690661300813431789147490002490485680400671384441342427462071211423204456959983657856469034361843518906932742755839477892090867737525818438595032896123389082695556216022212240001190090281258165331416657932822805874602168

[+]x=pow(m+1,e,n)=3913355162506843667079312859018190210750999153615046231990422792509829450409212168507688057410976245834264140419108113476107790991506117144211120541710779587327967147999832294267428915095580485615923712261506555190257352674496596197869320069747269797902622599010051829852374293544522141824192458083264555499712388195731657971351737292981358503624428934337287306553109606196697224316949028722924520843757990451867544386438405893429648867504042574932635621879182744390170108609387296218948392041657682468255953226052675102710060363708081291924114406497165841292907447536561975232950061358289722917586138566490502779459

[-]long_to_bytes(m).encode('hex')=

4e53534354467b66373736396634343634313131323264393431613034303630663635643966617d
challenge5 completed

#脚本1
#Sage
import libnum
def attack(c1, c2, n, e):
    PR.<x>=PolynomialRing(Zmod(n))
    # replace a,b,c,d
    g1 = (x)^e - c1
    g2 = (x+1)^e - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()
    return -gcd(g1, g2)[0]
c1 = 7418469310902085437902845069810907325748187977112113013220980112424442407226613760137761252552648007440383331950784228115986488475925283144593824500894571405880353340364207514694865844222508784001099834491784492065366210845193614581254153562661925385483663311199429650248093515309902747077140513942599407673983337470272240847775515213386498877652829223938536140405276402077587122957982174528164436480795702083875459915633643501521880665049597701799478311622533919864653221378168651815325375699506672607343438523384457249220358586701209073706415789620321939705636356508188823859264169488961318134313316063366665910206
c2 = 7418469310902085437902845069810907325748733318702942313324389630211155769858788619682593335606609874466071236380121906106667783380907883818266786633397419722492444714853781910785481012125683973018650974770499567295703842779905172289953314716678797071300101083018194616487898334829834287716319231206235032949259157514750919737173561247151807407433293665350985762009700294101008050532709741770671530046518254092265430246868161574567969187502303931582046841847862821179049361509293491493411427903204699783947564964113915141948898374580142274167217290438324911526116560240686491037292687977366065861177410333052288211017
n = 15369301775722059379429609723694490645255566936766905366291805492170763202593417656003920322518507848926288093010156491021125903284959504824779141231360967938816670520213388416181376350025270847161283019625359588420327428720596770506411481513335537892798306797489759059676798449378078117722107191381693669966064104766048590386108378235589500841522523925342214114615411024645758263462037005808907358130815114751124039909396193753673415118331184548463083765708917853412605088824688043832076082343772226366300855419378276186462741799922089994387916401407026411238770214496917807205333955808483034512681150324952200389371
e = 7
m1 = attack(c1, c2, n, e)
print(libnum.n2s(int(m1)).hex())

大e，Boneh Durfee攻击

[+]Generating challenge 6


[+]n=28433765123193272413937762328478900250760726527540970528301125490692394193031349424192977308025178980197573233532541331581039212649482368461209698222920253798119078082671456554327106356072755216440255350551249872704198183911243201154461425078130834820720266808857878403255335514633434963386337641056957575165904599192527874783819857605968879265626890622973853987796385119695123510693355367524397097570051202427674198944461737328738571947837456929308212464789234856571770942917129100514149090445032962309425666609028922888756077436344010090550110050333505553564704195272515880559514315921553383277840399836719879267731

[+]d=random.getrandbits(1024*0.270)

[+]e=invmod(d,phin)

[+]hex(e)=811064441382390422335857185171964973819180142301034110312988812579005103329415811219397407236358334135487556791344847049720438309636553312944761097650405633450388819857262840347127104523831328363719063788724868945425984301234811155086117303272342049043287977725138042272369408683842806781452249258950318980189467107669120017021224184673163673234831941754189977759548338864842058620085924302835065610153298473720275399826055185583261279983714863993762808707903048297439473962219973732254616170084914227048491750377156055199702452409838475535269005815857545489975713790116627357389141915361080713898345310344819398011

[+]m=random.getrandbits(512)

[+]c=pow(m,e,n)=2215549666936383194009635202892010085709856759041385283571550251738688341878837204412349600843761936463943527306046381600377509428569282671471506183509982449074173134639828628105390619414363248600509852727320877722437239205741142553919197277254271177715138457833445878021907118662246369477491944116273889264876060672674938035936224599859202705638000108999326600486767306332492774808128640611101750088219310107966545884546610768651618457937614209194972795161283251661411131762647432150736155121251925910033554158554435962239917000949778234952957874313580236210225985749573493184918938295299027272872552712367286649836

[-]long_to_bytes(m).encode('hex')=

4e53534354467b35336232333561643933383663343862633564316639333961663233306130357d
challenge6 completed

NSSCTF{43de032b-1431-4082-a701-a198cc3dbe8e}

# Boneh Durfee代码已分享过，此处略
# 但需要注意NSSCTF复现的有些问题，偶尔会分不出d，需要重开 ：  （
import libnum
d = 5415090862251732317442024436621547096348588561944422740935945311625453350444967843
n=28433765123193272413937762328478900250760726527540970528301125490692394193031349424192977308025178980197573233532541331581039212649482368461209698222920253798119078082671456554327106356072755216440255350551249872704198183911243201154461425078130834820720266808857878403255335514633434963386337641056957575165904599192527874783819857605968879265626890622973853987796385119695123510693355367524397097570051202427674198944461737328738571947837456929308212464789234856571770942917129100514149090445032962309425666609028922888756077436344010090550110050333505553564704195272515880559514315921553383277840399836719879267731
e=0x811064441382390422335857185171964973819180142301034110312988812579005103329415811219397407236358334135487556791344847049720438309636553312944761097650405633450388819857262840347127104523831328363719063788724868945425984301234811155086117303272342049043287977725138042272369408683842806781452249258950318980189467107669120017021224184673163673234831941754189977759548338864842058620085924302835065610153298473720275399826055185583261279983714863993762808707903048297439473962219973732254616170084914227048491750377156055199702452409838475535269005815857545489975713790116627357389141915361080713898345310344819398011
c=2215549666936383194009635202892010085709856759041385283571550251738688341878837204412349600843761936463943527306046381600377509428569282671471506183509982449074173134639828628105390619414363248600509852727320877722437239205741142553919197277254271177715138457833445878021907118662246369477491944116273889264876060672674938035936224599859202705638000108999326600486767306332492774808128640611101750088219310107966545884546610768651618457937614209194972795161283251661411131762647432150736155121251925910033554158554435962239917000949778234952957874313580236210225985749573493184918938295299027272872552712367286649836
m=int(pow(c,d,n))
print(libnum.n2s(m).hex())