Crypto-RSA(二)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import long_to_bytes
from gmpy2 import iroot
'''
flag = b'NSSCTF{******}'
p = getPrime(5120)
q = getPrime(5120)
n = p*q
e = 97
phi = (p-1)*(q-1)
m = bytes_to_long(flag)
c = powmod(m, e, n)
print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')
'''
n = 1392208858696945158251408085300402884210409327605255122395601049457847957306648819174395014931778575812308192875319127224095733396726388842605854427013313599830150182564652493067830031524869535522568868597852507293377043240832819715539722122306829543983051745406887140154364256267942350230636870212935356815475345989038318923389132101208917912083817520799490534351545373438629367819085151041702754019127891155542476560972125790519584018715794669416759039955180436830478697704458250990786586357019211642837879273967620287257818400267757312623543898635740200839249361087580046496969637043238450499583879116276661827372750638403042213043389905183760455450595752578482968202040860053524276678108325784161897719093223308370971388068813420487879756084379519128232693549989942550047529174783976176943482484756074638704076740157397067892580297182979526978967352014250386678155843772313996171396582929433057131989693861316408604436872931427368192437680361830753162284661119995125858203931094922686321756465463988790748131178263745308042820480140189644732824717255521633534750635979508673908361269979175726073254050574688259969290376926807033728165164896588540691889207252105903436659968119091774687841336252628343233161941187968365128093917171537997137001140227677728923114895809278926486615010954871408034272872411042537353956193868948909981683850857262457369506288525323882308421700421661036191853577105238753230479541719001794464585534292774768292358961920606891227776349593589481547577148801600196035588544512224775960892265021565124673788852875005526313525709353599584812394138968970647681759439523307392275602626903789154682706839530654070108096741181206975334567778238856983205004289416400671597321919876279909765650782227834097342294844294386380646928266942749144240020420237153276705785759403019072953506982997681174635673907151856644499332322321579088035719680421458310273802481031746012298208449699089203065699598926690947025679591160106357130634946357609420125223580319677387654711233585375013067828291928349946599077331636017784447090096340360087970540477975170379810969501197027775838769222713506443846417124839450184827707739588007707714623211453528342755023849716924694572679150284882978804641986457119009272574734697043321033091757474387114449914271460113979531460465175717705674905568446670579332667139075523255580471183372714211547822093365025438653384719374474230360983878837077517864405475258349436531094649276628214288499716485354283135575921258757214288792410583835467572916298688718758374714560819702413058421373661892101033513816116981698045524150518509405086125781764762145577981637953775680403132163846782252745029783387112660812179706752454175492501665442704630131729362621965258498471247871904163412798544329515689112368523703890083138721480476796720323855371775568097188216621368341228806795058046403892301673157631331636430392885315997250027372621883549649614866115616619234953579196607399899485002042456482969222428121605212017146571466818179341621066715472184636758016242256725063854155219754299817717414423725704356940589670902509021070871847017199593680033
e = 97
c = 79418540691422578656139651796213224829563266521211325595707569487401417030874358531413674275017334363641194166574500833916574827523075402219754470871728896772312056257743844227927800121160288525434484105786180547178403828613331285574461293211150728313415280329153597549251599876668080073528625299164784405291297754331374420687599875173508778209038236713812747215157059659564867241144529476211694011692007565732793105429228730285249025627762831080251661835294067942958070742202862164086250986988784472568266652325462247009294865764533077164470382743735937483173523682749295196383707694876943634298051820105410771024861599560176707940488888601355473498847493259474613261665538825299531665650233837474894442826242097663456648233384047622152817959729025415665280499618951478005159820575701483220155180955748454167435711033379910310483689839303198822665341421591234243891877857520663120183063591818656508336831518527692847950877186870610083654117153248336928856886934232488927132245720058243202637258025864487122393335118118013444397135476780564523166548571927547341556616683070253790368891423731046742936358877118104790084195711730135202600692806999992373490439385845158780392894927697171401722699273071306493916233696254958735540772870249139252741670476667099529502282392011715616110876451102234600267482991583515122052976378641894214562203326290939184469206074418127906704847146567350085797480500249400491003993809769407575997740985283755035509654310797061339563655229926356893455738361409861102662109994984398860070584568014471082484198504331014073023689622378943694856212172718725529473812336321642429261822836311084518735006587545920946664595488768239633950124822001162595168106106356115962424210028401369438479550293237915944302351566624339603616714683958384871326105542659559877758488581425288668613061792514360263277530824203967659102107889148367539858141289229124274098921748855341045565232484417195620758495861456624842263649414501657786484816662971421962216348340311859717286253287173293151613310383128702607971580042308515018120559903265609733911340589091613087560931098833849573462572181625894166772788435459280323623477689159384354671220634694792005231505741029567734616435905915192606539962414882105254409847885996949466940350184140166614950171110955365828033747003120697209120916652982201967537088553504504252785632280900095976870510754563400828951684036526240669112248351928072177486091157562600003336544767896806392523395037345770580482363058065676920013089896399387769312374871419827762872050800055872960573607645266626972865053489632548224840580503746879607167797904430560935476705014800973841917939689270919224595772574781478285359220463175042728750523639669204218676238297875644055563803457896409252533724486937378974745777400567080239687055154021761534918106133195512030935957251049812753269173090858930245212145938555697547499155977225759702066548720079477737104010668116693232798415289735481194922014811945312893853446826780868861295203942063380964100360870361328125
m=iroot(c,e)[0]
print(long_to_bytes(m))

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
from Crypto.Util.number import long_to_bytes
from gmpy2 import iroot
'''
flag = b'NSSCTF{******}'
p = getPrime(512)
q = getPrime(512)
n = p*q
e = 3
phi = (p-1)*(q-1)
m = bytes_to_long(flag)
c = powmod(m, e, n)
print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')
'''
n = 111573371787314339229652810703380127177507745009618224416171957526984270337589283887959174610818933914845556276472159360153787395638087723501889651641965684241070152541291185349571453536221312112508437223801640552330390095266644485311958102687735113533739324296417077804219395793942670324182191309872918900717
e = 3
c = 90782646242308381145716338972639920044710403094882163620436540965475107006005657722222634294458956650085252212452241377251397323707019480880284004845674260662647720809672266571040936376737882878688872281858048646517100139303896804340224961592424635124272549514473232731744884837572128596217771005209683966262
k=0
while True:
    m=iroot(c+k*n,e)
    if m[1]:
        print(long_to_bytes(m[0]))
        break
    k+=1

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
from Crypto.Util.number import inverse, long_to_bytes
from gmpy2 import *
'''
flag = b'NSSCTF{******}'
p = getPrime(256)
q = getPrime(256)
assert p%4 == 3 and q%4 == 3
n = p*q
e = 2
m = bytes_to_long(flag)
c = powmod(m, e, n)
print(f'p = {p}')
print(f'q = {q}')
print(f'e = {e}')
print(f'c = {c}')
'''
p = 67711062621608175960173275013534737889372437946924512522469843485353704013203
q = 91200252033239924238625443698357031288749612243099728355449192607988117291739
e = 2
c = 5251890478898826530186837207902117236305266861227697352434308106457554098811792713226801824100629792962861125855696719512180887415808454466978721678349614
n=p*q
p1=pow(c,(p+1)//4,p)
q1=pow(c,(q+1)//4,q)
p2=-p1
q2=-q1
t1=inverse(p, q)
t2=inverse(q,p)
m1=(p*q1*t1+q*p1*t2)%n
m2=(p*q2*t1+q*p1*t2)%n
m3=(p*q1*t1+q*p2*t2)%n
m4=(p*q2*t1+q*p2*t2)%n
print(long_to_bytes(m1))
print(long_to_bytes(m2))
print(long_to_bytes(m3))
print(long_to_bytes(m4))

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
63
64
65
66
67
68
69
70
71
72
73
74
75
from Crypto.Util.number import long_to_bytes
import gmpy2

def wiener_attack(e, n):
    # 计算 e/n 的连分数展开
    def continued_fraction(e, n):
        cf = []
        while n:
            cf.append(e // n)
            e, n = n, e % n
        return cf

    # 生成收敛分数列表
    def convergents(cf):
        convergents = []
        for i in range(len(cf)):
            numerator, denominator = 1, 0
            for j in range(i, -1, -1):
                numerator, denominator = cf[j] * numerator + denominator, numerator
            convergents.append((numerator, denominator))
        return convergents

    cf = continued_fraction(e, n)
    convergents_list = convergents(cf)

    # 遍历所有收敛分数，寻找可能的 d
    for numerator, denominator in convergents_list:
        if denominator == 0:  # 避免分母为 0
            continue
        if numerator == 0:  # 避免分子为 0
            continue
        if (e * denominator - 1) % numerator != 0:  # 检查是否整除
            continue

        phi = (e * denominator - 1) // numerator

        # 解二次方程 x^2 - (n - phi + 1)x + n = 0 得到 p 和 q
        a = 1
        b = n - phi + 1
        c = n
        discriminant = b * b - 4 * a * c

        if discriminant < 0:  # 判别式小于 0，跳过
            continue

        sqrt_disc = gmpy2.isqrt(discriminant)
        if sqrt_disc * sqrt_disc != discriminant:  # 判别式不是完全平方数，跳过
            continue

        p = (b + sqrt_disc) // 2
        q = (b - sqrt_disc) // 2

        if p * q == n:  # 验证 p 和 q 是否正确
            return denominator, p, q

    return None, None, None

# 输入参数
n = 6969872410035233098344189258766624225446081814953480897731644163180991292913719910322241873463164232700368119465476508174863062276659958418657253738005689
e = 3331016607237504021038095412236348385663413736904453330557803644384818257225138777641344877202234881627514102078530507171735156112302207979925588113589669
c = 1754994938947260364311041300467524420957926989584983693004487724099773647229373820465164193428679197813476633649362998772470084452129370353136199193923837

# 调用 Wiener 攻击函数
d, p, q = wiener_attack(e, n)

if d is not None:
    '''
    print(f'd = {d}')
    print(f'p = {p}')
    print(f'q = {q}')
    '''
    m = pow(c, d, n)
    print(long_to_bytes(m))
else:
    print("Wiener attack failed.")

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
from gmpy2 import iroot,invert
from pwn import *
from Crypto.Util.number import long_to_bytes
'''
import os
flag = os.getenv('FLAG')
m = bytes_to_long(flag.encode())
e = 127
def enc():
    p = getPrime(512)
    q = getPrime(512)
    n = p*q
    c = pow(m, e, n)
    print(f"n: {n}")
    print(f"c: {c}")
def main():
    while True:
        opt = int(input('input> '))
        if opt == 1:
            enc()
main()
'''
def crt(n_list, c_list):
    n = 1
    for i in n_list:
        n *= i
    N = []
    for i in n_list:
        N.append(n//i)
    t = []
    for i in range(len(n_list)):
        t.append(invert(N[i], n_list[i]))

    summary = 0
    for i in range(len(n_list)):
        summary = (summary + c_list[i]*t[i]*N[i]) % n
    return summary


io = remote('node4.anna.nssctf.cn', 28533)
e = 127
n_list = []
c_list = []
for i in range(127):
    io.sendlineafter(b'input> ', b'1')  # 等待收到input> 后发送1
    n = int(io.recvline().decode()[2:])  # 接收一行数据 即 n: xxxx
    c = int(io.recvline().decode()[2:])  # 接收一行数据 即 c: xxxx
    n_list.append(n)
    c_list.append(c)
    
M = crt(n_list,c_list)
m = iroot(M,e)[0]
flag = long_to_bytes(m)
print(flag)

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
from Crypto.Util.number import *
from random import choice
from gmpy2 import gcd,invert
'''
flag = b'NSSCTF{******}'
def getMyPrime(nbits):
    while True:
        p = 1
        while p.bit_length() <= nbits:
            p *= choice(sieve_base)
        if isPrime(p+1):
            return p+1
p = getMyPrime(256)
q = getMyPrime(256)
n = p*q
e = 65537
m = bytes_to_long(flag)
c = pow(m, e, n)
print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')

'''
n = 53763529836257082401813045869248978487210852880716446938539970599235060144454914000042178896730979463959004404421520555831136502171902051936080825853063287829
e = 65537
c = 50368170865606429432907125510556310647510431461588875539696416879298699197677994843344925466156992948241894107250131926237473102312181031875514294014181272618
a=2
m=2
while True:
    a = pow(a,m,n)
    p = gcd(a-1,n)
    if p!=1 and p!=n:
        break
    m+=1
q=n//p
phi=(p-1)*(q-1)
d=invert(e,phi)
m=pow(c, d, n)
print(long_to_bytes(m))