simpleRSA

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import *
import gmpy2

p, q, r = [getPrime(512) for i in range(3)]
n = p * q * r
phi = (p - 1) * (q - 1) * (r - 1)
d = getPrime(256)
e = gmpy2.invert(d , phi)

flag = b"flag{xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx}"

c = pow(bytes_to_long(flag), e, n)

print(e, n)
print(c)

task.txt

1
2
1072295425944136507039938677101442481213519408125148233880442849206353379681989305000570387093152236263203395726974692959819315410781180094216209100069530791407495510882640781920564732214327898099944792714253622047873152630438060151644601786843683746256407925709702163565141004356238879406385566586704226148537863811717298966607314747737551724379516675376634771455883976069007134218982435170160647848549412289128982070647832774446345062489374092673169618836701679 1827221992692849179244069834273816565714276505305246103435962887461520381709739927223055239953965182451252194768935702628056587034173800605827424043281673183606478736189927377745575379908876456485016832416806029254972769617393560238494326078940842295153029285394491783712384990125100774596477064482280829407856014835231711788990066676534414414741067759564102331614666713797073811245099512130528600464099492734671689084990036077860042238454908960841595107122933173
1079929174110820494059355415059104229905268763089157771374657932646711017488701536460687319648362549563313125268069722412148023885626962640915852317297916421725818077814237292807218952574111141918158391190621362508862842932945783059181952614317289116405878741758913351697905289993651105968169193211242144991434715552952340791545323270065763529865010326192824334684413212357708275259096202509042838081150055727650443887438253964607414944245877904002580997866300452

典型的 Wiener_attack，网上都有脚本。

网上的脚本解出了 p 和 q，但题目的 n 是由 p，q，r 组成的，我们可以选择不分解，求出 d 的集合，爆破 d 即可得到 flag。

exp.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
from __future__ import print_function
import libnum
from Crypto.Util.number import *
def continued_fractions_expansion(numerator,denominator):#(e,N)
	result=[] 
	divident = numerator % denominator
	quotient = numerator / denominator
	result.append(quotient) 
	while divident != 0:
		numerator = numerator - quotient * denominator 
		tmp = denominator
		denominator = numerator
		numerator = tmp
		divident = numerator % denominator
		quotient = numerator / denominator
		result.append(quotient) 
	return result
 
def convergents(expansion):
	convergents=[(expansion[0], 1)]
	for i in range(1, len(expansion)):
		numerator = 1
		denominator = expansion[i]
		for j in range(i - 1, -1, -1):
			numerator += expansion[j] * denominator
			if j==0:
				break
			tmp = denominator
			denominator = numerator
			numerator = tmp
		convergents.append((numerator, denominator)) #(k,d)
	return convergents
 
def newtonSqrt(n):
	approx = n / 2
	better = (approx + n / approx) / 2
	while better != approx:
	    approx = better
	    better = (approx + n / approx) / 2
	return approx
 
if __name__ == "__main__":
    n = 1827221992692849179244069834273816565714276505305246103435962887461520381709739927223055239953965182451252194768935702628056587034173800605827424043281673183606478736189927377745575379908876456485016832416806029254972769617393560238494326078940842295153029285394491783712384990125100774596477064482280829407856014835231711788990066676534414414741067759564102331614666713797073811245099512130528600464099492734671689084990036077860042238454908960841595107122933173
    e = 1072295425944136507039938677101442481213519408125148233880442849206353379681989305000570387093152236263203395726974692959819315410781180094216209100069530791407495510882640781920564732214327898099944792714253622047873152630438060151644601786843683746256407925709702163565141004356238879406385566586704226148537863811717298966607314747737551724379516675376634771455883976069007134218982435170160647848549412289128982070647832774446345062489374092673169618836701679 
    c = 1079929174110820494059355415059104229905268763089157771374657932646711017488701536460687319648362549563313125268069722412148023885626962640915852317297916421725818077814237292807218952574111141918158391190621362508862842932945783059181952614317289116405878741758913351697905289993651105968169193211242144991434715552952340791545323270065763529865010326192824334684413212357708275259096202509042838081150055727650443887438253964607414944245877904002580997866300452
    expansion = continued_fractions_expansion(e, n)
    cons = convergents(expansion) #(k,d)的数组集合，进行爆破
    for tt in cons:
        m = pow(c, tt[1], n)
        try:          
            if(long_to_bytes(m)[0:4]=='flag'):
                print(long_to_bytes(m))
                exit()
        except:
            continue

flag{1c40fa8a-6a9c-4243-bd83-cd4875ea88cc}

RSAssss

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *
import gmpy2

p = getPrime(512)
q = getPrime(512)

n = p * q * next_prime(p) * next_prime(q)
e = 0x10001

flag = b"flag{xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx}"
cipher = pow(bytes_to_long(flag), e, n)

print(n, cipher)

task.txt

1
8030860507195481656424331455231443135773524476536419534745106637165762909478292141556846892146553555609301914884176422322286739546193682236355823149096731058044933046552926707682168435727800175783373045726692093694148718521610590523718813096895883533245331244650675812406540694948121258394822022998773233400623162137949381772195351339548977422564546054188918542382088471666795842185019002025083543162991739309935972705871943787733784491735500905013651061284020447578230135075211268405413254368439549259917312445348808412659422810647972872286215701325216318641985498202349281374905892279894612835009186944143298761257 3304124639719334349997663632110579306673932777705840648575774671427424134287680988314129312593361087606243819528298610131797078262351307396831985397555390640151391138633431951746748156610463582479645561779194981806129898009876517899450840875569675976765155608446799203699927448835004756707151281044859676695533373755798273892503194753948997947653100690841880925445059175494314198605475023939567750409907217654291430615102258523998394231436796902635077995829477347316754739938980814293304289318417443493019704073164585505217658570214989150175123757038125380996050761572021986573934155470641091678664451080065719261207

先 yafu 分解出两个数 n1，n2

建立等式：

p(q+y)=n1

q(p+x)=n2

（可以转换成一元二次方程）

（根据素数定理，素数的平均间隔为：x/π(x)≈lnx，因此常见的下一个素数比当前素数大一点，一般不会超过1500，因此x，y不是很大）

所以通过爆破x，y求解一元二次方程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
e=0x10001
c=3304124639719334349997663632110579306673932777705840648575774671427424134287680988314129312593361087606243819528298610131797078262351307396831985397555390640151391138633431951746748156610463582479645561779194981806129898009876517899450840875569675976765155608446799203699927448835004756707151281044859676695533373755798273892503194753948997947653100690841880925445059175494314198605475023939567750409907217654291430615102258523998394231436796902635077995829477347316754739938980814293304289318417443493019704073164585505217658570214989150175123757038125380996050761572021986573934155470641091678664451080065719261207
n=8030860507195481656424331455231443135773524476536419534745106637165762909478292141556846892146553555609301914884176422322286739546193682236355823149096731058044933046552926707682168435727800175783373045726692093694148718521610590523718813096895883533245331244650675812406540694948121258394822022998773233400623162137949381772195351339548977422564546054188918542382088471666795842185019002025083543162991739309935972705871943787733784491735500905013651061284020447578230135075211268405413254368439549259917312445348808412659422810647972872286215701325216318641985498202349281374905892279894612835009186944143298761257 
n1=89615068527538836315602124154008300286636934599617334867509053076622715365809371740037316558871796433906844464070995869293654082577887578197182408045175035339285085728002838220314068474670975228778464240088084331807420720121364486765011169669747553393661650912114228227308579940164269877101973728452252879383
n2=89615068527538836315602124154008300286636934599617334867509053076622715365809371740037316558871796433906844464070995869293654082577887578197182408045172781798703173650574737644914515591522256758848089955578713458715234536664415216526830967831862301518636586702212189087959136509334102772855657664091570630079
n2_n1=n2-n1
def rsa():
    for x in range(1,5000):
        for y in range(1,5000):
            if(gmpy2.iroot((n2_n1+x*y)**2+4*y*(x*n1),2)[1]==True):
                try:
                    p=((-(n2_n1+x*y)+gmpy2.iroot((n2_n1+x*y)**2+4*y*(x*n1),2)[0]))/(2*y)
                    print(p)
                    q1=n1/p
                    q=q1-y
                    p1=p+x
                    m=long_to_bytes(gmpy2.powmod(c,gmpy2.invert(e,(p-1)*(q-1)*(p1-1)*(q1-1)),n))
                    if(m[0:4]=="flag"):
                        print(m)
                        return 0
                except:
                    continue
        print(x)
    return 0
rsa()

另一种思路：费马因式分解

参考：https://www.dazhuanlan.com/2020/03/08/5e646a3c752c9/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
from Crypto.Util.number import GCD, inverse, long_to_bytes as l2b
import gmpy2


def fermat_factorization(n):
    factor_list = []
    gmpy2.get_context().precision = 2048
    a = int(gmpy2.sqrt(n))

    a2 = a * a
    b2 = gmpy2.sub(a2, n)

    while True:
        a += 1
        b2 = a * a - n

        if gmpy2.is_square(b2):
            b2 = gmpy2.mpz(b2)
            gmpy2.get_context().precision = 2048
            b = int(gmpy2.sqrt(b2))
            factor_list.append([a + b, a - b])

        if len(factor_list) == 2:
            break

    return factor_list


def main():
    c = 3304124639719334349997663632110579306673932777705840648575774671427424134287680988314129312593361087606243819528298610131797078262351307396831985397555390640151391138633431951746748156610463582479645561779194981806129898009876517899450840875569675976765155608446799203699927448835004756707151281044859676695533373755798273892503194753948997947653100690841880925445059175494314198605475023939567750409907217654291430615102258523998394231436796902635077995829477347316754739938980814293304289318417443493019704073164585505217658570214989150175123757038125380996050761572021986573934155470641091678664451080065719261207
    e = 65537
    n =8030860507195481656424331455231443135773524476536419534745106637165762909478292141556846892146553555609301914884176422322286739546193682236355823149096731058044933046552926707682168435727800175783373045726692093694148718521610590523718813096895883533245331244650675812406540694948121258394822022998773233400623162137949381772195351339548977422564546054188918542382088471666795842185019002025083543162991739309935972705871943787733784491735500905013651061284020447578230135075211268405413254368439549259917312445348808412659422810647972872286215701325216318641985498202349281374905892279894612835009186944143298761257
    factor_list = fermat_factorization(n)
    print factor_list
    [X1, Y1] = factor_list[0]
    [X2, Y2] = factor_list[1]
    assert X1 * Y1 == n
    assert X2 * Y2 == n

    p1 = GCD(X1,X2)
    q1 = X1/p1
    p2 = GCD(Y1,Y2)
    q2 = Y1/p2

    phi = (p1 - 1) * (q1 - 1) * (p2 - 1) * (q2 - 1)
    d = inverse(e, phi)
    flag = l2b(pow(c, d, n))

    print(flag)

if __name__ == "__main__":
    main()

more_calc

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import gmpy2
from Crypto.Util.number import *

flag = b"flag{xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx}"

p = getStrongPrime(2048)
for i in range(1, (p+1)//2):
    s += pow(i, p-2, p)
s = s % p
q = gmpy2.next_prime(s)
n = p*q
e = 0x10001
c = pow(bytes_to_long(flag), e, n)
print(p)
print(c)
#27405107041753266489145388621858169511872996622765267064868542117269875531364939896671662734188734825462948115530667205007939029215517180761866791579330410449202307248373229224662232822180397215721163369151115019770596528704719472424551024516928606584975793350814943997731939996459959720826025110179216477709373849945411483731524831284895024319654509286305913312306154387754998813276562173335189450448233216133842189148761197948559529960144453513191372254902031168755165124218783504740834442379363311489108732216051566953498279198537794620521800773917228002402970358087033504897205021881295154046656335865303621793069
#350559186837488832821747843236518135605207376031858002274245004287622649330215113818719954185397072838014144973032329600905419861908678328971318153205085007743269253957395282420325663132161022100365481003745940818974280988045034204540385744572806102552420428326265541925346702843693366991753468220300070888651732502520797002707248604275755144713421649971492440442052470723153111156457558558362147002004646136522011344261017461901953583462467622428810167107079281190209731251995976003352201766861887320739990258601550606005388872967825179626176714503475557883810543445555390014562686801894528311600623156984829864743222963877167099892926717479789226681810584894066635076755996423203380493776130488170859798745677727810528672150350333480506424506676127108526488370011099147698875070043925524217837379654168009179798131378352623177947753192948012574831777413729910050668759007704596447625484384743880766558428224371417726480372362810572395522725083798926133468409600491925317437998458582723897120786458219630275616949619564099733542766297770682044561605344090394777570973725211713076201846942438883897078408067779325471589907041186423781580046903588316958615443196819133852367565049467076710376395085898875495653237178198379421129086523

exp.py

1
2
3
4
5
6
7
8
9
10
import gmpy2

p=27405107041753266489145388621858169511872996622765267064868542117269875531364939896671662734188734825462948115530667205007939029215517180761866791579330410449202307248373229224662232822180397215721163369151115019770596528704719472424551024516928606584975793350814943997731939996459959720826025110179216477709373849945411483731524831284895024319654509286305913312306154387754998813276562173335189450448233216133842189148761197948559529960144453513191372254902031168755165124218783504740834442379363311489108732216051566953498279198537794620521800773917228002402970358087033504897205021881295154046656335865303621793069
c=350559186837488832821747843236518135605207376031858002274245004287622649330215113818719954185397072838014144973032329600905419861908678328971318153205085007743269253957395282420325663132161022100365481003745940818974280988045034204540385744572806102552420428326265541925346702843693366991753468220300070888651732502520797002707248604275755144713421649971492440442052470723153111156457558558362147002004646136522011344261017461901953583462467622428810167107079281190209731251995976003352201766861887320739990258601550606005388872967825179626176714503475557883810543445555390014562686801894528311600623156984829864743222963877167099892926717479789226681810584894066635076755996423203380493776130488170859798745677727810528672150350333480506424506676127108526488370011099147698875070043925524217837379654168009179798131378352623177947753192948012574831777413729910050668759007704596447625484384743880766558428224371417726480372362810572395522725083798926133468409600491925317437998458582723897120786458219630275616949619564099733542766297770682044561605344090394777570973725211713076201846942438883897078408067779325471589907041186423781580046903588316958615443196819133852367565049467076710376395085898875495653237178198379421129086523
e=0x10001
c1=c%p
d1=gmpy2.invert(e,p-1)
m=pow(c1,d1,p)
flag = bytes.fromhex(hex(m)[2:])
print(flag)