文章目录
- 前言
- simpleSignin
- NumberTheory
前言
大半年以来写的第一篇文章！！！
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根据题目名字，顾名思义:数论
已知等式， h i n t + 233 k = 233 k p 已知等式，hint+233k=233kp 已知等式，hint+233k=233kp
⇒ 233 k × ( p − 1 ) = h i n t \Rightarrow 233k\times(p-1)=hint ⇒233k×(p−1)=hint
那么，则有,任意正整数a
a h i n t = a 233 k × ( p − 1 ) a^{hint} = a^{233k\times(p-1)} ahint=a233k×(p−1)
此时，在模上一个p的情况下
a h i n t m o d p = a 233 k × ( p − 1 ) m o d p a^{hint} mod \space p = a^{233k\times(p-1)} mod \space p ahintmod p=a233k×(p−1)mod p
根据费马小定理,可得
a h i n t m o d p ≡ 1 m o d p a^{hint} mod \space p \equiv 1 \space mod \space p ahintmod p≡1 mod p
a h i n t m o d p − 1 = k p a^{hint} mod \space p -1 = kp ahintmod p−1=kp
∵ n = p × q \because n = p\times q ∵n=p×q
∴ g c d ( a h i n t , n ) = p \therefore gcd(a^{hint},n)=p ∴gcd(ahint,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)
下午应该还上了一个格的题目，以后有空再写
)
