BUU刷题日记20221021

RSA2

题目给定n、e、dp、c

非预期解：直接分解n

下面考虑n不能分解的情况

推导过程

dp ≡ d mod (p-1)

ed ≡ 1 mod (p-1) * (q-1)

ed = 1 + k2(p-1)(q-1)

对1式两端同乘e，得

e * dp ≡ ed mod (p-1)

e * dp = k1(p-1) + ed

代入ed得

e * dp = k1(p-1) + 1 + k2(p-1)(q-1)

由于两个未知数略显麻烦，发现公因子(p-1)，等式两边同时取余p-1，即可消掉n

e * dp ≡ 1 mod (p-1)

e * dp =k(p-1) + 1

得到这个式子后，其实真正意义上的未知数只有我们要求的p，但是还存在一个k。

针对k，我们判断一下他的范围，看看能否采用爆破的方式。

k = (e * dp - 1)/(p-1)

因为dp < p-1

所以k < e

通过遍历k然后找到(e * dp - 1)可以整除k的情况即可。

(跑了一下发现限制条件还不够)

因此再加一个n能否整除p即可。

EXP

import gmpy2
from Crypto.Util.number import long_to_bytes
e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657
c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751
# p = 13468634736343473907717969603434376212206335187555458742257940406618189481177835992217885676243155145465521141546915941147336786447889325606555333350540003
# q = 18432009829596386103558375461387837845170621179295293289126504231317130550979989727125205467379713835047300158256398009229511746203459540859429194971855371
for k in range(1,e):
    if (e*dp-1)%k == 0:
        p=(e*dp-1)//k + 1
        if n%p == 0:
            print(p)
            break
q=n//p
phi= (p-1)*(q-1)
d= gmpy2.invert(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))
#flag{wow_leaking_dp_breaks_rsa?_98924743502}

RSA3

给定n、e1、c1、e2、c2。

m ≡ c1^e1 mod n

m ≡ c2^e2 mod n

这里采用共模攻击，详细原理如下：

扩展欧几里得算法：给定两个整数a、b，必定存在x、y，使得gcd(a,b)=ax+by

对应到本题当中，由于e1、e2互为素数，因此gcd(e1,e2)=1，从而存在s1、s2使得:

s1 * e1 + s2 * e2 = 1

推导过程

m = m % n

m = m^(s1 * e1 + s2 * e2)^ % n

m = m^(e1 * s1)^ * m^(e2 * s2)^ % n

m = (m^(e1 * s1)^ % n) * (m^(e2 * s2)^ % n) % n

m = (c1^s1 % n) * (c2^s2 % n) % n

EXP

import gmpy2
from Crypto.Util.number import long_to_bytes
c1=22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361
n=22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801
e1=11187289
c2=18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397
e2=9647291

r,s1,s2=gmpy2.gcdext(e1,e2)
m=(pow(c1,s1,n) * pow(c2,s2,n)) %n
print(long_to_bytes(m))
#flag{49d91077a1abcb14f1a9d546c80be9ef}