前言

大半年以來寫的第一篇文章！！！

simpleSignin

題目：

from Crypto.Util.number import *
from gmpy2 import *
import osflag = b'xxx'
p = next_prime(bytes_to_long(os.urandom(128)))
q = next_prime(bytes_to_long(os.urandom(128)))
r = next_prime(q)
n = p * q * r
e = 0x10001
print(f"n = {n}")
print(f"c = {pow(bytes_to_long(flag), e, n)}")
print(f"gift1 = {p % (2**10)}")
print(f"gift2 = {(p >> 20) % 2 ** 800}")
# n = 91717197306065801430692774296739087369692505805873730729014813677164858033475119219496549179322145782790263228034134781592967028480301579462111507372893508636592832600206391905790511488678949157112322777098684707325311891056750963286494634489093620270797637437274546909400418496263799669541769586017282231886023275686719495040493703402244867906367008837217453500300992995258096509545406775279177918160331853363991834113918051468978309081085686108283547874975768959542753094631595260890420558364636303078263220001513817844063960023424429484568985727987064710176511050208253838039386390968276801658300795687804601169987051671314061987254212363117325786734328360418591971610392966867659045907550755979167652038093091970078722854251659581538266806207906127491377972897441916942048136016416739633568604447564119372465662628724153812001753748410162478969725179843125714619352895967577899670208386148053595763674920185320834513587
# c = 53725206995000716522893276595058419071990290621803579636161714383330892673055811337947487241701642126496591685585109862245420917684160662867863785840324861826954623093740844326627026833476771622577100464186879804184565843869885634004202583123814660253474988365767802371596929119773493402264073966760818738577604694066757843772483509464516822006312737285138313587227005339175914335841617310097530993158296079585719772401849963001042345007495440110071538584261056055469925721208755935971137618873034799819342505088130217626174789908762309465751064851354313099531229991764250968313733026934453793364342598912519963653648573385780950148182927905527658001218917373163825532068287661941387464083148002185635404194796699532320249403305428191157038659625440168989244227207215946636349083290983113055351713899941081154804665455470002453942340935361232121886299764516109079270616076269084847241248414373185392810503507977061708566426
# gift1 = 513
# gift2 = 5077110719426498428662246006638349628986894614097694065336047422264042823893900747327210766546701290926253205743419412459378571920759093322149140413682875156857171051511499793127787270654329155934268596972449238336868326196360992252498463385

根據代碼可知，gift2和gift1分別為p的低820-20bit和低10bit，因此當我們通過爆破獲取到低20-10bit的時候，此時為一個p的低位泄露問題。對于1024bit的p,泄露820bit完全夠copper了，我們可以通過copper計算出高204bit即可還原p

from Crypto.Util.number import *
import gmpy2
from tqdm import *
n = 91717197306065801430692774296739087369692505805873730729014813677164858033475119219496549179322145782790263228034134781592967028480301579462111507372893508636592832600206391905790511488678949157112322777098684707325311891056750963286494634489093620270797637437274546909400418496263799669541769586017282231886023275686719495040493703402244867906367008837217453500300992995258096509545406775279177918160331853363991834113918051468978309081085686108283547874975768959542753094631595260890420558364636303078263220001513817844063960023424429484568985727987064710176511050208253838039386390968276801658300795687804601169987051671314061987254212363117325786734328360418591971610392966867659045907550755979167652038093091970078722854251659581538266806207906127491377972897441916942048136016416739633568604447564119372465662628724153812001753748410162478969725179843125714619352895967577899670208386148053595763674920185320834513587
c = 53725206995000716522893276595058419071990290621803579636161714383330892673055811337947487241701642126496591685585109862245420917684160662867863785840324861826954623093740844326627026833476771622577100464186879804184565843869885634004202583123814660253474988365767802371596929119773493402264073966760818738577604694066757843772483509464516822006312737285138313587227005339175914335841617310097530993158296079585719772401849963001042345007495440110071538584261056055469925721208755935971137618873034799819342505088130217626174789908762309465751064851354313099531229991764250968313733026934453793364342598912519963653648573385780950148182927905527658001218917373163825532068287661941387464083148002185635404194796699532320249403305428191157038659625440168989244227207215946636349083290983113055351713899941081154804665455470002453942340935361232121886299764516109079270616076269084847241248414373185392810503507977061708566426
leak = 5077110719426498428662246006638349628986894614097694065336047422264042823893900747327210766546701290926253205743419412459378571920759093322149140413682875156857171051511499793127787270654329155934268596972449238336868326196360992252498463385
e = 65537
PR.<x> = PolynomialRing(Zmod(n))
for i in trange(2**10):p_low = (leak<<20)+(i<<10)+513f = x*2**820+p_lowroot = f.monic().small_roots(X=2^204,beta=0.33)if root:p = int(root[0]*2**820+p_low)if n%p==0:phi = p-1d = inverse_mod(e,phi)m = pow(c,d,p)flag = bytes.fromhex(hex(m)[2:])print(flag)break

NumberTheory

題目：

from Crypto.Util.number import *
import hintflag=b'xxx'
e=65537
p=getPrime(512)
q=getPrime(512)
n=p*q
m=bytes_to_long(flag)
c=pow(m,e,n)
k=getPrime(1024)
assert hint + 233 * k == 233 * k * p
print(n)
print(c)
print(hint)# 105531804094410236294687082475828411218788143973352026416392542762437103918840861241726193253936370648195682452618343195471719649394086997793137653518966739212122830015579955183805636213883066694989610003565432493653164047938048521354525623612253955387430773546124647105772639376194421783783651686606080214099
# 6838127295540107402282470465780599628759317234806902778570348919850980664834107227012249617036087381075344016550381137159643512672239826438903241091658619314078921936719784123522758604349399440232971511649918093228288847534685526358191804172060250409498531941883162873696671060909325234109062997554795436940
# 225457129615945961139095949356083106510992163176770860368085043522677811094793442173512565115313130227614423196268240217775831118417780318014842280209747426271227826513967791945116378179885000662888744992914390207196310600996050316737090999399962338133222370745589250853315876818226312453376340282748842779666176953455553054310328901299083159029050169950812885486884682347263045764918907196922313892044095742248895091717187372068779768743879411865275203496650858608

根據題目名字，顧名思義:數論
$已知等式，hint+233k=233kp$
$?233k\times (p?1)=hint$
那么，則有,任意正整數a
$a^{hint}=a^{233k\times (p?1)}$
此時，在模上一個p的情況下
$a^{hint}modp=a^{233k\times (p?1)}modp$
根據費馬小定理,可得
$a^{hint}modp\equiv 1modp$
$a^{hint}modp?1=kp$
$\because n=p\times q$
$\therefore gcd(a^{hint},n)=p$
求出p之后，直接RSA解密即可

from Crypto.Util.number import *
import gmpy2n =  105531804094410236294687082475828411218788143973352026416392542762437103918840861241726193253936370648195682452618343195471719649394086997793137653518966739212122830015579955183805636213883066694989610003565432493653164047938048521354525623612253955387430773546124647105772639376194421783783651686606080214099
c =  6838127295540107402282470465780599628759317234806902778570348919850980664834107227012249617036087381075344016550381137159643512672239826438903241091658619314078921936719784123522758604349399440232971511649918093228288847534685526358191804172060250409498531941883162873696671060909325234109062997554795436940
hint = 225457129615945961139095949356083106510992163176770860368085043522677811094793442173512565115313130227614423196268240217775831118417780318014842280209747426271227826513967791945116378179885000662888744992914390207196310600996050316737090999399962338133222370745589250853315876818226312453376340282748842779666176953455553054310328901299083159029050169950812885486884682347263045764918907196922313892044095742248895091717187372068779768743879411865275203496650858608
e = 65537
p = gmpy2.gcd(pow(5,hint,n)-1,n)
q = n//p
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
flag = long_to_bytes(m)
print(flag)

下午應該還上了一個格的題目，以后有空再寫