CRYTPO 24.8第一周刷题记录

Posted on Edited on

[SWPUCTF 2021 新生赛]crypto3

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

flag  = '******************'

p = getPrime(512)
q = getPrime(512)
m1 = bytes_to_long(bytes(flag.encode()))

n = p*q

flag1 = pow(m1,p,n)
flag2 = pow(m1,q,n)
print('flag1= '+str(flag1))
print('flag2= '+str(flag2))
print('n= '+str(n))


#flag1= 17893542812755845772427795161304049467610774531005620109503081344099161906017295486868699578946474114607624347167976713200068059018517606363517478396368430072890681401898145302336139240273132723451063402106360810413024642916851746118524166947301681245568333254648265529408446609050354235727237078987509705857
#flag2= 95580409405085606847879727622943874726633827220524165744517624606566789614499137069562997931972825651309707390763700301965277040876322904891716953565845966918293178547100704981251056401939781365264616997055296773593435626490578886752446381493929807909671245959154990639046333135728431707979143972145708806954
#n= 140457323583824160338989317689698102738341061967768153879646505422358544720607476140977064053629005764551339082120337223672330979298373653766782620973454095507484118565884885623328751648660379894592063436924903894986994746394508539721459355200184089470977772075720319482839923856979166319700474349042326898971

https://www.osgeo.cn/sagemath/tutorial/index.html

得到 由费马小定理，因为 为质数，故 则有 即 可以得到，在 下，有 可以消去 得到式子

代码：

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

h1= 
h2= 
n= 

PR.<m> = PolynomialRing( Zmod(n) )
f = m^2 - (h1+h2)*m + h1*h2
a = int(str(f.small_roots( X=2^400 )[0]))

print( flag )
print( long_to_bytes(flag) )

output:

1
2
1920535408007397834236393374892057067669865609963495845501
b'NSSCTF{why_gongmo_again}'

flag:NSSCTF{why_gongmo_again}

[BUUCTF·V&N2020 公开赛]easy_RSA

tag.暴力分解 小技巧

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
from random import randint
from gmpy2 import *
from Crypto.Util.number import *

def getprime(bits):
    while 1:
        n = 1
        while n.bit_length() < bits:
            n *= next_prime(randint(1,1000))
        if isPrime(n - 1):
            return n - 1

m = bytes_to_long(b'flag{************************************}')

p = getprime(505)
q = getPrime(512)
r = getPrime(512)
assert m < q

n = p * q * r
e = 0x10001
d = invert(q ** 2, p ** 2)
c = pow(m, 2, r)
cipher = pow(c, e, n)

print(n)
print(d)
print(cipher)

使用factordb分解得到的数值

c = pow(m, 2, r)已知 求

求 的解的方法：

1
2
from sympy.ntheory.residue_ntheory import nthroot_mod
x=nthroot_mod(a,n,p)

exp:

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

n = 
d = 
m = 
e = 0x10001
p = 102634610559478918970860957918259981057327949366949344137104804864768237961662136189827166317524151288799657758536256924609797810164397005081733039415393
q = 7534810196420932552168708937019691994681052660068275906973480617604535381306041583841106383688654426129050931519275383386503174076258645141589911492908993
r = 10269028767754306217563721664976261924407940883784193817786660413744866184645984238866463711873380072803747092361041245422348883639933712733051005791543841

d1 = gmpy2.invert( e , (p-1)*(q-1)*(r-1) )
c1 = pow( m , d1 , n )

from sympy.ntheory.residue_ntheory import nthroot_mod
c = nthroot_mod( c1 , 2 , r )
print( c )
print( long_to_bytes( c ) )

add.在其他师傅的wp上摘到的Tonelli–Shanks算法 求解二次平方根

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
56
57
58
59
60
61
62
import gmpy2
from Crypto.Util.number import *
def legendre(a, p):
    return pow(a, (p - 1) // 2, p)


def tonelli(n, p):
    assert legendre(n, p) == 1
    q = p - 1
    s = 0
    while q % 2 == 0:
        q //= 2
        s += 1
    if s == 1:
        return pow(n, (p + 1) // 4, p)
    for z in range(2, 10000):
#    for z in range(2, p):
        if p - 1 == legendre(z, p):
            break
    c = pow(z, q, p)
    r = pow(n, (q + 1) // 2, p)
    t = pow(n, q, p)
    m = s
    t2 = 0
    while (t - 1) % p != 0:
        t2 = (t * t) % p
        for i in range(1, m):
            if (t2 - 1) % p == 0:
                break
            t2 = (t2 * t2) % p
        b = pow(c, 1 << (m - i - 1), p)
        r = (r * b) % p
        c = (b * b) % p
        t = (t * c) % p
        m = i
    return r
n=7941371739956577280160664419383740967516918938781306610817149744988379280561359039016508679365806108722198157199058807892703837558280678711420411242914059658055366348123106473335186505617418956630780649894945233345985279471106888635177256011468979083320605103256178446993230320443790240285158260236926519042413378204298514714890725325831769281505530787739922007367026883959544239568886349070557272869042275528961483412544495589811933856131557221673534170105409
d=gmpy2.mpz(7515987842794170949444517202158067021118454558360145030399453487603693522695746732547224100845570119375977629070702308991221388721952258969752305904378724402002545947182529859604584400048983091861594720299791743887521228492714135449584003054386457751933095902983841246048952155097668245322664318518861440)
cipher=1618155233923718966393124032999431934705026408748451436388483012584983753140040289666712916510617403356206112730613485227084128314043665913357106301736817062412927135716281544348612150328867226515184078966397180771624148797528036548243343316501503364783092550480439749404301122277056732857399413805293899249313045684662146333448668209567898831091274930053147799756622844119463942087160062353526056879436998061803187343431081504474584816590199768034450005448200

#python2 -m primefac -vs -m=p+1  7941371739956577280160664419383740967516918938781306610817149744988379280561359039016508679365806108722198157199058807892703837558280678711420411242914059658055366348123106473335186505617418956630780649894945233345985279471106888635177256011468979083320605103256178446993230320443790240285158260236926519042413378204298514714890725325831769281505530787739922007367026883959544239568886349070557272869042275528961483412544495589811933856131557221673534170105409
p=gmpy2.mpz(102634610559478918970860957918259981057327949366949344137104804864768237961662136189827166317524151288799657758536256924609797810164397005081733039415393)

q2=gmpy2.invert(d,p**2)
for i in range(1000000):
	q=gmpy2.iroot(q2+i*p**2,2)
	if(q[1]==1):
		print q[0],i
		break
q=q[0]
r=n//p//q

e=0x10001
phi=(p-1)*(q-1)*(r-1)
D=gmpy2.invert(e,phi)
c=pow(cipher,D,n)
print c

m=tonelli(c,r)
print m
print long_to_bytes(m)
#flag{fd462593-25e4-4631-a96a-0cd5c72b2d1b}

[De1CTF2019]babyrsa

tag: 共膜攻击 | 低密度指数攻击 | 暴力分解 | e,phi不互质pro

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
import binascii
from data import e1,e2,p,q1p,q1q,hint,flag

n =  [20129615352491765499340112943188317180548761597861300847305827141510465619670536844634558246439230371658836928103063432870245707180355907194284861510906071265352409579441048101084995923962148527097370705452070577098780246282820065573711015664291991372085157016901209114191068574208680397710042842835940428451949500607613634682684113208766694028789275748528254287705759528498986306494267817198340658241873024800336013946294891687591013414935237821291805123285905335762719823771647853378892868896078424572232934360940672962436849523915563328779942134504499568866135266628078485232098208237036724121481835035731201383423L, 31221650155627849964466413749414700613823841060149524451234901677160009099014018926581094879840097248543411980533066831976617023676225625067854003317018794041723612556008471579060428898117790587991055681380408263382761841625714415879087478072771968160384909919958010983669368360788505288855946124159513118847747998656422521414980295212646675850690937883764000571667574381419144372824211798018586804674824564606122592483286575800685232128273820087791811663878057827386379787882962763290066072231248814920468264741654086011072638211075445447843691049847262485759393290853117072868406861840793895816215956869523289231421L, 29944537515397953361520922774124192605524711306753835303703478890414163510777460559798334313021216389356251874917792007638299225821018849648520673813786772452822809546571129816310207232883239771324122884804993418958309460009406342872173189008449237959577469114158991202433476710581356243815713762802478454390273808377430685157110095496727966308001254107517967559384019734279861840997239176254236069001453544559786063915970071130087811123912044312219535513880663913831358790376650439083660611831156205113873793106880255882114422025746986403355066996567909581710647746463994280444700922867397754748628425967488232530303L, 25703437855600135215185778453583925446912731661604054184163883272265503323016295700357253105301146726667897497435532579974951478354570415554221401778536104737296154316056314039449116386494323668483749833147800557403368489542273169489080222009368903993658498263905567516798684211462607069796613434661148186901892016282065916190920443378756167250809872483501712225782004396969996983057423942607174314132598421269169722518224478248836881076484639837343079324636997145199835034833367743079935361276149990997875905313642775214486046381368619638551892292787783137622261433528915269333426768947358552919740901860982679180791L]
c =  [19131432661217908470262338421299691998526157790583544156741981238822158563988520225986915234570037383888112724408392918113942721994125505014727545946133307329781747600302829588248042922635714391033431930411180545085316438084317927348705241927570432757892985091396044950085462429575440060652967253845041398399648442340042970814415571904057667028157512971079384601724816308078631844480110201787343583073815186771790477712040051157180318804422120472007636722063989315320863580631330647116993819777750684150950416298085261478841177681677867236865666207391847046483954029213495373613490690687473081930148461830425717614569L, 15341898433226638235160072029875733826956799982958107910250055958334922460202554924743144122170018355117452459472017133614642242411479849369061482860570279863692425621526056862808425135267608544855833358314071200687340442512856575278712986641573012456729402660597339609443771145347181268285050728925993518704899005416187250003304581230701444705157412790787027926810710998646191467130550713600765898234392350153965811595060656753711278308005193370936296124790772689433773414703645703910742193898471800081321469055211709339846392500706523670145259024267858368216902176489814789679472227343363035428541915118378163012031L, 18715065071648040017967211297231106538139985087685358555650567057715550586464814763683688299037897182845007578571401359061213777645114414642903077003568155508465819628553747173244235936586812445440095450755154357646737087071605811984163416590278352605433362327949048243722556262979909488202442530307505819371594747936223835233586945423522256938701002370646382097846105014981763307729234675737702252155130837154876831885888669150418885088089324534892506199724486783446267336789872782137895552509353583305880144947714110009893134162185382309992604435664777436197587312317224862723813510974493087450281755452428746194446L, 2282284561224858293138480447463319262474918847630148770112472703128549032592187797289965592615199709857879008271766433462032328498580340968871260189669707518557157836592424973257334362931639831072584824103123486522582531666152363874396482744561758133655406410364442174983227005501860927820871260711861008830120617056883514525798709601744088135999465598338635794275123149165498933580159945032363880613524921913023341209439657145962332213468573402863796920571812418200814817086234262280338221161622789516829363805084715652121739036183264026120868756523770196284142271849879003202190966150390061195469351716819539183797L]
f=lambda m,e,n,c:pow(m,e,n)==c
assert(sum(map(f,[p]*4,[4]*4,n,c))==4)

ee1 = 42
ee2 = 3
ce1 =  45722651786340123946960815003059322528810481841378247280642868553607692149509126962872583037142461398806689489141741494974836882341505234255325683219092163052843461632338442529011502378931140356111756932712822516814023166068902569458299933391973504078898958921809723346229893913662577294963528318424676803942288386430172430880307619748186863890050113934573820505570928109017842647598266634344447182347849367714564686341871007505886728393751147033556889217604647355628557502208364412269944908011305064122941446516990168924709684092200183860653173856272384
ce2 =  13908468332333567158469136439932325992349696889129103935400760239319454409539725389747059213835238373047899198211128689374049729578146875309231962936554403287882999967840346216695208424582739777034261079550395918048421086843927009452479936045850799096750074359160775182238980989229190157551197830879877097703347301072427149474991803868325769967332356950863518504965486565464059770451458557744949735282131727956056279292800694203866167270268988437389945703117070604488999247750139568614939965885211276821987586882908159585863514561191905040244967655444219603287214405014887994238259270716355378069726760953320025828158
tmp =  864078778078609835167779565982540757684070450697854309005171742813414963447462554999012718960925081621571487444725528982424037419052194840720949809891134854871222612682162490991065015935449289960707882463387
n  =  15911581555796798614711625288508309704791837516232122410440958830726078821069050404012820896260071751380436992710638364294658173571101596931605797509712839622479368850251206419748090059752427303611760004621378226431226983665746837779056271530181865648115862947527212787824629516204832313026456390047768174765687040950636530480549014401279054346098030395100387004111574278813749630986724706263655166289586230453975953773791945408589484679371854113457758157492241225180907090235116325034822993748409011554673180494306003272836905082473475046277554085737627846557240367696214081276345071055578169299060706794192776825039
assert(pow(e1,ee1,n)==ce1)
assert(pow(e2+tmp,ee2,n)==ce2)

e = 46531
n = 16278524034278364842964386062476113517067911891699789991355982121084973951738324063305190630865511554888330215827724887964565979607808294168282995825864982603759381323048907814961279012375346497781046417204954101076457350988751188332353062731641153547102721113593787978587135707313755661153376485647168543680503160420091693269984008764444291289486805840439906620313162344057956594836197521501755378387944609246120662335790110901623740990451586621846212047950084207251595169141015645449217847180683357626383565631317253913942886396494396189837432429078251573229378917400841832190737518763297323901586866664595327850603
c = 14992132140996160330967307558503117255626925777426611978518339050671013041490724616892634911030918360867974894371539160853827180596100892180735770688723270765387697604426715670445270819626709364566478781273676115921657967761494619448095207169386364541164659123273236874649888236433399127407801843412677293516986398190165291102109310458304626261648346825196743539220198199366711858135271877662410355585767124059539217274691606825103355310348607611233052725805236763220343249873849646219850954945346791015858261715967952461021650307307454434510851869862964236227932964442289459508441345652423088404453536608812799355469
hint=int(binascii.hexlify(hint),16)
assert(q1p*q1q==n)
assert(q1p<q1q)
assert(c==pow(hint,e,n))

flag=int(binascii.hexlify(flag),16)
q1=q1p
q2 =  114401188227479584680884046151299704656920536168767132916589182357583461053336386996123783294932566567773695426689447410311969456458574731187512974868297092638677515283584994416382872450167046416573472658841627690987228528798356894803559278308702635288537653192098514966089168123710854679638671424978221959513
c1 =  262739975753930281690942784321252339035906196846340713237510382364557685379543498765074448825799342194332681181129770046075018122033421983227887719610112028230603166527303021036386350781414447347150383783816869784006598225583375458609586450854602862569022571672049158809874763812834044257419199631217527367046624888837755311215081173386523806086783266198390289097231168172692326653657393522561741947951887577156666663584249108899327053951891486355179939770150550995812478327735917006194574412518819299303783243886962455399783601229227718787081785391010424030509937403600351414176138124705168002288620664809270046124
c2 =  7395591129228876649030819616685821899204832684995757724924450812977470787822266387122334722132760470911599176362617225218345404468270014548817267727669872896838106451520392806497466576907063295603746660003188440170919490157250829308173310715318925771643105064882620746171266499859049038016902162599261409050907140823352990750298239508355767238575709803167676810456559665476121149766947851911064706646506705397091626648713684511780456955453552020460909638016134124590438425738826828694773960514221910109473941451471431637903182205738738109429736425025621308300895473186381826756650667842656050416299166317372707709596
assert(c1==pow(flag,e1,p*q1))
assert(c2==pow(flag,e2,p*q2))

对于第一部分：使用共膜攻击即可

前置知识：

  1. lambda:相当于一个函数，表达式为 函数名=lambda 输入值:函数式，常搭配map使用
  2. map:表达式为map(函数名,输入值)，返回函数名对应的函数式的结果

翻译一下，原式相当于

通过四组 利用中国剩余定理即可求出 ，然后开根即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def CRT( r , p ):
    M = 1
    for i in p:
        M *= i
    m = []
    for i in p:
        m.append( M // i )
    ans = 0
    for i in range( len(p) ):
        ans += r[i] * m[i] * invert( m[i] , p[i] )
        ans %= M
    return ans

#part1 共膜攻击
def part1():
    n =  
    c =  
    p4 = CRT( c , n )
    p = iroot( p4 , 4 )[0]
    #print( p )
    return p

对于第二部分：使用低密度指数攻击

很小，所以可以直接爆破

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import gmpy2
k = 0
while True:
    if gmpy2.iroot( ce1 + n*k , ee1 )[1] == True:
        e1 = gmpy2.iroot( ce1 + n*k , ee1 )[0]
        break
    k += 1
print( e1 )
k = 0
while True:
    if gmpy2.iroot( ce2 + n*k , ee2 )[1] == True:
        e2 = gmpy2.iroot( ce2 + n*k , ee2 )[0] - tmp
        break
    k += 1
print( e2 )

得到

1
2
e1 = 15218928658178
e2 = 381791429275130

也可以使用先估计 范围的做法

已知

发现ee2=3，考虑低密度指数攻击

计算print( tmp**3 / n )

得到40545.874109734694

因而可以穷举k，可以得到

对于前一半，运行print( len(str(ce1)) , len(str(n)) )；发现相差五十多位，是个小概率事件；所以认为与n无关，可以直接开根

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#part2 低密度指数攻击
def part2():
    ee1 = 42
    ee2 = 3
    ce1 = 
    ce2 =  
    tmp =  
    n  =  
    print( tmp**3 / n ) 
    for k in range( 40000 , 41000 ):
        if iroot( ce2 + k*n , ee2 )[1]:
            e2 = iroot( ce2 + k*n , ee2 )[0] - tmp 
            break
    #print( e2 )
    
    #print( len(str(ce1)) , len(str(n)) )
    e1 = iroot( ce1 , ee1 )[0]
    #print( e1 )
    return e1 , e2

对于第三部分：直接分解即可

1
2
3
4
5
6
7
8
9
10
11
def part3():
    e = 
    n = 
    c = 
    p = 
    q = 
    phi = (p-1)*(q-1)
    d = invert( e , phi )
    hint = pow( c , d , n )
    print( long_to_bytes( hint ) )
    return min( p , q )

得到hint:b'orz...you.found.me.but.sorry.no.hint...keep.on.and.enjoy.it!'（和flag并无关系）

对于第四部分：

已知p , q1 , q2 , e1 , e2，但是 e1 , e2 和 phi1 , phi2 不互质，无法正常求私钥 d

一般来说遇到这种情况都是让 除去其与欧拉函数的最大公约数，让这两个数重新互质，然后求 的值

1
2
3
a = gcd( e1 , (p-1) * (q1-1) )
b = gcd( e2 , (p-1) * (q2-1) )
print( a , b )

得到 ，发现 的幂次比较高，不好处理

组成一个新的rsa解密，

reference:

https://blog.csdn.net/a5555678744/article/details/117308377

https://blog.csdn.net/qq_57235775/article/details/131167215

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
n =  [ q1, q2 ]
a = gmpy2.gcd(e1,(p-1)*(q1-1))
b = gmpy2.gcd(e2,(p-1)*(q2-1))
c = [ gmpy2.powmod(c1,gmpy2.invert(e1//a,(p-1)*(q1-1)),q1)
    , gmpy2.powmod(c2,gmpy2.invert(e2//b,(p-1)*(q2-1)),q2)]
M = n[0] * n[1]
m = [0]*2
inv = [0]*2
x = 0
for i in range(2):
    m[i]=M//n[i]
    inv[i]=gmpy2.invert(m[i],n[i])
    x+=(c[i]*inv[i]*m[i])
x = x % M
e=7
d=gmpy2.invert(e,(q1-1)*(q2-1))
flag=gmpy2.iroot(gmpy2.powmod(x,d,q1*q2),2)[0]
print(long_to_bytes(flag))

flag:de1ctf{9b10a98b-71bb-4bdf-a6ff-f319943de21f}

[DASCTF Sept X 浙江工业大学秋季挑战赛]签到

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from Crypto.Util.number import *
import random
flag=b'flag{******************}'
n = 2 ** 256
flaglong=bytes_to_long(flag)
m = random.randint(2, n-1) | 1
c = pow(m, flaglong, n)
print('m = ' + str(m))
print('c = ' + str(c))

# m = 73964803637492582853353338913523546944627084372081477892312545091623069227301
# c = 21572244511100216966799370397791432119463715616349800194229377843045443048821

discrete_log()使用示例：

1
2
3
>>> from sympy.ntheory import discrete_log
>>> discrete_log(41, 15, 7)
3

即 

1
2
3
4
5
6
7
import sympy
import binascii
m = 73964803637492582853353338913523546944627084372081477892312545091623069227301
c = 21572244511100216966799370397791432119463715616349800194229377843045443048821
n = 2 ** 256
flag=sympy.discrete_log(n,c,m)
print(binascii.unhexlify(hex(flag)[2:]))

flag:flag{DASCTF_zjut}