[ctfshow]NOeasyRSA

目录

1.题目

2.分析

3.解题

4.参考

---

1.题目

from Crypto.Util.number import long_to_bytes
from Crypto.Util.strxor import strxor
from random import randint
from flag import FLAG
 
def f(x, n):  
    return (pow(u,n,p)*x + v*(1-pow(u,n,p))*pow(1-u, -1, p)) % p  
 
p = 97201997431130462639713476119411091922677381239967611061717766639853376871260165905989218335681560177626304205941143288128749532327607316527719299945637260643711897738116821179208534292854942631428531228316344113303402450588666012800739695018334321748049518585617428717505851025279186520225325765864212731597
u = 14011530787746260724685809284106528245188320623672333581950055679051366424425259006994945665868546765648275822501035229606171697373122374288934559593175958252416643298136731105775907857798815936190074350794406666922357841091849449562922724459876362600203284195621546769313749721476449207319566681142955460891977927184371401451946649848065952527323468939007868874410618846898618148752279316070498097254384228565132693552949206926391461108714034141321700284318834819732949544823937032615318011463993204345644038210938407875147446570896826729265366024224612406740371824999201173579640264979086368843819069035017648357042
v = 16560637729264127314502582188855146263038095275553321912067588804088156431664370603746929023264744622682435376065011098909463163865218610904571775751705336266271206718700427773757241393847274601309127403955317959981271158685681135990095066557078560050980575698278958401980987514566688310172721963092100285717921465575782434632190913355536291988686994429739581469633462010143996998589435537178075521590880467628369030177392034117774853431604525531066071844562073814187461299329339694285509725214674761990940902460186665127466202741989052293452290042871514149972640901432877318075354158973805495004367245286709191395753
w = 30714296289538837760400431621661767909419746909959905820574067592409316977551664652203146506867115455464665524418603262821119202980897986798059489126166547078057148348119365709992892615014626003313040730934533283339617856938614948620116906770806796378275546490794161777851252745862081462799572448648587153412425374338967601487603800379070501278705056791472269999767679535887678042527423534392867454254712641029797659150392148648565421400107500607994226410206105774620083214215531253544274444448346065590895353139670885420838370607181375842930315910289979440845957719622069769102831263579510660283634808483329218819353
a = randint(0, 2**2048)
b = randint(0, 2**2048)
A = f(w, a)
B = f(w, b)
key = long_to_bytes(f(B, a))[:len(FLAG)]
enc = strxor(FLAG, key)
print(f"{A = }")
print(f"{B = }")
print(f"{enc = }")
 
"""
A = 19000912802080599027672447674783518419279033741329820736608320648294849832904652704615322546923683308427498322653162857743332527479657555691849627174691056234736228204031597391109766621450008024310365149769851160904834246087493085291270515883474521052340305802461028930107070785434600793548735004323108063823
B = 73344156869667785951629011239443984128961974188783039136848369309843181351498207375582387449307849089511875560536212143659712959631858144127598424003355287131145957594729789310869405545587664999655457134475561514111282513273352679348722584469527242626837672035004800949907749224093056447758969518003237425788
enc = b'\xfd\xc1\xb7\x9d"$\xc2\xb0\xb5\xee\xf89\xa4V\x8e\x17\x01K9\xbc.\x92=\x85\x80\xd4\x03\xefAl"\xbd\x8b\xcdL\xb5\xa3!'
"""

2.分析

enc是由flag和key异或得到的，所以我们如果能求得key，就只用异或运算就能够得到flag

函数f如下，里面进行的运算看起来比较复杂:

def f(x, n):  
    return (pow(u,n,p)*x + v*(1-pow(u,n,p))*pow(1-u, -1, p)) % p  

根据函数的表达式，我们得到有关A，B的式子，我们需要注意的是这两个式子是模p意义上的等式，所以我们可以省略掉对p取模的部分：

式1

式2

关于a的式子还有一个：

式3

注意到上式与key有关：

key = long_to_bytes(f(B, a))[:len(FLAG)]

求解出式3左边即可得到key的值

我们对这三个式子进行观察，发现只需要式1、式3就能够求解出所要的值,而不需要求解出a，b的值，因为求解a，b的值是一个求解离散对数的问题，这个问题是困难的，而且题目所给数据很大，不能暴力求解

事实上由式1可得：

?式4

由式3可得：

式5

式4中借助gmpy2库，直接进行运算再将结果代入式5，再进一步处理即可得到结果

3.解题

对关键量的获取：

from gmpy2 import invert
from Crypto.Util.strxor import strxor
from Crypto.Util.number import long_to_bytes
p = 97201997431130462639713476119411091922677381239967611061717766639853376871260165905989218335681560177626304205941143288128749532327607316527719299945637260643711897738116821179208534292854942631428531228316344113303402450588666012800739695018334321748049518585617428717505851025279186520225325765864212731597

def inv(n):
    return invert(n, p)

u = 14011530787746260724685809284106528245188320623672333581950055679051366424425259006994945665868546765648275822501035229606171697373122374288934559593175958252416643298136731105775907857798815936190074350794406666922357841091849449562922724459876362600203284195621546769313749721476449207319566681142955460891977927184371401451946649848065952527323468939007868874410618846898618148752279316070498097254384228565132693552949206926391461108714034141321700284318834819732949544823937032615318011463993204345644038210938407875147446570896826729265366024224612406740371824999201173579640264979086368843819069035017648357042
v = 16560637729264127314502582188855146263038095275553321912067588804088156431664370603746929023264744622682435376065011098909463163865218610904571775751705336266271206718700427773757241393847274601309127403955317959981271158685681135990095066557078560050980575698278958401980987514566688310172721963092100285717921465575782434632190913355536291988686994429739581469633462010143996998589435537178075521590880467628369030177392034117774853431604525531066071844562073814187461299329339694285509725214674761990940902460186665127466202741989052293452290042871514149972640901432877318075354158973805495004367245286709191395753
w = 30714296289538837760400431621661767909419746909959905820574067592409316977551664652203146506867115455464665524418603262821119202980897986798059489126166547078057148348119365709992892615014626003313040730934533283339617856938614948620116906770806796378275546490794161777851252745862081462799572448648587153412425374338967601487603800379070501278705056791472269999767679535887678042527423534392867454254712641029797659150392148648565421400107500607994226410206105774620083214215531253544274444448346065590895353139670885420838370607181375842930315910289979440845957719622069769102831263579510660283634808483329218819353
A = 19000912802080599027672447674783518419279033741329820736608320648294849832904652704615322546923683308427498322653162857743332527479657555691849627174691056234736228204031597391109766621450008024310365149769851160904834246087493085291270515883474521052340305802461028930107070785434600793548735004323108063823
B = 73344156869667785951629011239443984128961974188783039136848369309843181351498207375582387449307849089511875560536212143659712959631858144127598424003355287131145957594729789310869405545587664999655457134475561514111282513273352679348722584469527242626837672035004800949907749224093056447758969518003237425788


temp = (A - v * inv(1-u))*inv(w-v*inv(1-u))
f_B_a = (temp *(B - v * inv(1-u))+v*inv(1-u))%p#只用在最后一个位置对p进行取余

print(temp)
print(f_B_a)

#temp = -117987953724490173837160773166175804758130081396163650261929190742596783265421692239329302507235659641200231277402212886572813367296408139077139396763922446596420869967227956578206068635768551707201096604951910737882262901445567773527318001669311958814006583282389793472506612790130507743987789173805913707169827789433971727465605297964133341949580668911451069547850741721199202206453988057049551898572490734510656367168154385910157247936065898371536630890254202940513015874455857846156705982267749054709367508456404179035574707563678207337789798698294156906312697526807696803229317672730247266248746036449580234919350488622411898342294558567023082141945693061555875482211674509553079031994500232714544018377446834426654783565849173520971167086433818256602457908887548357016595851634496768899449949099674214651560328197196684372926166704826413073140176026976737374865060217252511822253467126664053021685487257133830908732275608279328545456913899757471575763782201789634067245663322790144904380682175170601298996934922607634977290604340768331049565184770255543977824414907846086017710858614668135199948598520205481787927631715335497153102862923455306003098963986789571301538190026388123596244421932893461223457310749726037822862189784
#f_B_a = 435352018837215968071638947408094253993693298351735293754906141730857486016652555369779215973161531363670071940905337913460566920598533890149989388830899224373370332026768626378390165078425086013845846999259412364768635883571406644310056572286382320032106442178154000774924574035093847055439528170625194012

剩余的简单异或运算即可得到flag：

from Crypto.Util.strxor import strxor
from Crypto.Util.number import long_to_bytes
p = 97201997431130462639713476119411091922677381239967611061717766639853376871260165905989218335681560177626304205941143288128749532327607316527719299945637260643711897738116821179208534292854942631428531228316344113303402450588666012800739695018334321748049518585617428717505851025279186520225325765864212731597


enc = b'\xfd\xc1\xb7\x9d"$\xc2\xb0\xb5\xee\xf89\xa4V\x8e\x17\x01K9\xbc.\x92=\x85\x80\xd4\x03\xefAl"\xbd\x8b\xcdL\xb5\xa3!'

temp= -117987953724490173837160773166175804758130081396163650261929190742596783265421692239329302507235659641200231277402212886572813367296408139077139396763922446596420869967227956578206068635768551707201096604951910737882262901445567773527318001669311958814006583282389793472506612790130507743987789173805913707169827789433971727465605297964133341949580668911451069547850741721199202206453988057049551898572490734510656367168154385910157247936065898371536630890254202940513015874455857846156705982267749054709367508456404179035574707563678207337789798698294156906312697526807696803229317672730247266248746036449580234919350488622411898342294558567023082141945693061555875482211674509553079031994500232714544018377446834426654783565849173520971167086433818256602457908887548357016595851634496768899449949099674214651560328197196684372926166704826413073140176026976737374865060217252511822253467126664053021685487257133830908732275608279328545456913899757471575763782201789634067245663322790144904380682175170601298996934922607634977290604340768331049565184770255543977824414907846086017710858614668135199948598520205481787927631715335497153102862923455306003098963986789571301538190026388123596244421932893461223457310749726037822862189784
f_B_a = 435352018837215968071638947408094253993693298351735293754906141730857486016652555369779215973161531363670071940905337913460566920598533890149989388830899224373370332026768626378390165078425086013845846999259412364768635883571406644310056572286382320032106442178154000774924574035093847055439528170625194012

key = long_to_bytes(f_B_a)[:len(enc)]
flag = strxor(key, enc)
print(flag)

#b'ctfshow{This_Is_Really_Not_So_Smooth!}'

在sagemath中利用有限域的特性，代码可以稍微简化如下：

p = 97201997431130462639713476119411091922677381239967611061717766639853376871260165905989218335681560177626304205941143288128749532327607316527719299945637260643711897738116821179208534292854942631428531228316344113303402450588666012800739695018334321748049518585617428717505851025279186520225325765864212731597

u = R(14011530787746260724685809284106528245188320623672333581950055679051366424425259006994945665868546765648275822501035229606171697373122374288934559593175958252416643298136731105775907857798815936190074350794406666922357841091849449562922724459876362600203284195621546769313749721476449207319566681142955460891977927184371401451946649848065952527323468939007868874410618846898618148752279316070498097254384228565132693552949206926391461108714034141321700284318834819732949544823937032615318011463993204345644038210938407875147446570896826729265366024224612406740371824999201173579640264979086368843819069035017648357042)
v = R(16560637729264127314502582188855146263038095275553321912067588804088156431664370603746929023264744622682435376065011098909463163865218610904571775751705336266271206718700427773757241393847274601309127403955317959981271158685681135990095066557078560050980575698278958401980987514566688310172721963092100285717921465575782434632190913355536291988686994429739581469633462010143996998589435537178075521590880467628369030177392034117774853431604525531066071844562073814187461299329339694285509725214674761990940902460186665127466202741989052293452290042871514149972640901432877318075354158973805495004367245286709191395753)
w = R(30714296289538837760400431621661767909419746909959905820574067592409316977551664652203146506867115455464665524418603262821119202980897986798059489126166547078057148348119365709992892615014626003313040730934533283339617856938614948620116906770806796378275546490794161777851252745862081462799572448648587153412425374338967601487603800379070501278705056791472269999767679535887678042527423534392867454254712641029797659150392148648565421400107500607994226410206105774620083214215531253544274444448346065590895353139670885420838370607181375842930315910289979440845957719622069769102831263579510660283634808483329218819353)
A = R(19000912802080599027672447674783518419279033741329820736608320648294849832904652704615322546923683308427498322653162857743332527479657555691849627174691056234736228204031597391109766621450008024310365149769851160904834246087493085291270515883474521052340305802461028930107070785434600793548735004323108063823)
B = R(73344156869667785951629011239443984128961974188783039136848369309843181351498207375582387449307849089511875560536212143659712959631858144127598424003355287131145957594729789310869405545587664999655457134475561514111282513273352679348722584469527242626837672035004800949907749224093056447758969518003237425788)
enc = b'\xfd\xc1\xb7\x9d"$\xc2\xb0\xb5\xee\xf89\xa4V\x8e\x17\x01K9\xbc.\x92=\x85\x80\xd4\x03\xefAl"\xbd\x8b\xcdL\xb5\xa3!'


from Crypto.Util.strxor import strxor
from Crypto.Util.number import long_to_bytes

def inv(n):
    return pow(n, -1)

R = GF(p)
temp = (A - v * inv(1-u))*inv(w-v*inv(1-u))
f_B_a = (temp *(B - v * inv(1-u))+v*inv(1-u))
key = long_to_bytes(int(f_B_a))[:len(enc)]
flag = strxor(key, enc)
print(flag)

#b'ctfshow{This_Is_Really_Not_So_Smooth!}'

得到flag：

ctfshow{This_Is_Really_Not_So_Smooth!}

4.参考

文章1