coppersmith铜匠入门

字数统计: 2.4k字   |   阅读时长≈ 12分

芝士就是力量

芝士

SageMath简明教程 | tl2cents blog (tanglee.top)

1
2
3
4
5
6
7
8
9
10
PR.<x> = PolynomialRing(Zmod(n))   # x是规定下面方程的自变量， PolynomialRing()是与环有关，Zmod规定了环的模数

f = (x + 1) ^ 2   	# 定义了一个式子

f = f.monic()    	# 将多项式首项的系数化为一

res = f.roots()   	# 或者small_roots()  # res现在是列表

res = int(res[0]) 	# 把res的sage.rings.integer.Integer环域改成int，或者用ZZ(res[0])也行
...

步骤

  1. 先把最少能small_roots()的未知数界限推出来，用这个：coppersmith small_roots未知位数检测.ipynb 保险起见，算出来的位数实际用减一，例如在1024位pq下算出455，用454；在512位pq下算出227，用226
  2. 查看coppersmith small_roots()所需要的位数是否满足，有时候需要爆破几位
  3. 编写脚本，确定f 方程（本人目前不会，解多项式原理不懂，一开始以为是把类似x*2 + 2\x + 1 = 0 左边当成f方程来解方程，但是在下面遇到了右边单独放了p并不是0）
  4. 得到缺陷q本身，解rsa

例题

NSSCTF工坊[RSA4]P8

  • 题目

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

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

    flag = b'NSSCTF{******}'

    n = p*q
    m = bytes_to_long(flag)

    e = 3
    c = pow(m, e, n)

    print(f'n = {n}')
    print(f'm = {m>>100}')
    print(f'c = {c}')

    '''
    n = 1527542955109141740955682973826193262775892499957309448026045241470857728195657663426381459817190647872750820593934305392986732687654051540838628636529717414135863605586498459487983117670942529496973140251670874510207985224170313618738268651184582186637089407746738836054395760157095709388670653150429457223183161697730087281761369404956762102465246289770300941300936135728738323821631682286737786472020790680432476428922187234364341215016265407571963282147129157
    m = 2214226572250613833249705195927505959981823363137633354626532745196588970707
    c = 22113876206623661468496987580282614626160320529328454393375952035910523390370709980915981609422504775420007441257006956611997263223244837790238493516238723139514158563675396731542096229586616735753203254810465452822757959264870210654015436735165961713016222816604825816304606749448517022584926571828009062411578367333
    '''

  • 解析

    m缺少了低位100位，也就是高位泄露了，那么原本完整的m可以构成这个式子

    x为m的低位，而m_high用上面的m乘上2**100提高到原本的高位(演示如下)

    1
    2
    3
    	 m = 10101010111010100010101  	# 原本的m	
    	 m = 10101010111  				# m右移一定位数后
    m_high = 10101010111000000000000    # 乘上对应的数，让对应的10到达原本的未知，剩下后面我们补上的0就由x来补上

    综上，问题就转移到求x身上，我们来用已知条件和式子来构造一个方程式

    已知 m， c，n，e

    那么有

    m展开得到

    这下我们获得了所有解题思路，接下来写代码

  • exp

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

    n = 1527542955109141740955682973826193262775892499957309448026045241470857728195657663426381459817190647872750820593934305392986732687654051540838628636529717414135863605586498459487983117670942529496973140251670874510207985224170313618738268651184582186637089407746738836054395760157095709388670653150429457223183161697730087281761369404956762102465246289770300941300936135728738323821631682286737786472020790680432476428922187234364341215016265407571963282147129157
    m = 2214226572250613833249705195927505959981823363137633354626532745196588970707
    c = 22113876206623661468496987580282614626160320529328454393375952035910523390370709980915981609422504775420007441257006956611997263223244837790238493516238723139514158563675396731542096229586616735753203254810465452822757959264870210654015436735165961713016222816604825816304606749448517022584926571828009062411578367333

    m_high = m<<100

    PR.<x> = PolynomialRing(Zmod(n))
    f = (m_high + x)**3 - c
    f = f.monic()
    m0 = f.small_roots()
    print(m0)
    m = m_high + m0[0]
    flag = long_to_bytes(int(m)).decode()
    print(flag) # NSSCTF{688404a6-c408-4196-bc43-7f18317a9170}

NSSCTF工坊[RSA4]P9（构造多项式不懂，为什么右边不是0，而是p）

  • 题目

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

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

    flag = b'NSSCTF{******}'

    n = p*q
    m = bytes_to_long(flag)

    e = 65537
    c = pow(m, e, n)

    print(f'n = {n}')
    print(f'p = {p>>100}')
    print(f'c = {c}')

    '''
    n = 64335017257291288694879798080666629573501118113377179370850991421806469826103134483305987256497147128148330360834028920504233940886960965527818740354522230977284177508093687651712761343376265176857120577153061490788347779327206437787594150381508592990273475278503352979893670354730287704989079247190299342871
    p = 7550547038897825994210519739007596111285476244196123253081036462313916767780871742001683690783926938603422562506786339392389
    c = 63156227746402147833665215816432368072100003179308515827461336094419526246728847463629131014545663919689064970828884371592840335299717484415279040662500514230579275586231051576688620810169339105201465431624989678170362157914366609856305650090630980489686792938272599406165204410721499875713189193728688835223
    '''

  • 解析

    p高位泄露

    Crypto系列——RSA（四） | NSSCTF

  • exp

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

    n = 64335017257291288694879798080666629573501118113377179370850991421806469826103134483305987256497147128148330360834028920504233940886960965527818740354522230977284177508093687651712761343376265176857120577153061490788347779327206437787594150381508592990273475278503352979893670354730287704989079247190299342871
    p = 7550547038897825994210519739007596111285476244196123253081036462313916767780871742001683690783926938603422562506786339392389
    c = 63156227746402147833665215816432368072100003179308515827461336094419526246728847463629131014545663919689064970828884371592840335299717484415279040662500514230579275586231051576688620810169339105201465431624989678170362157914366609856305650090630980489686792938272599406165204410721499875713189193728688835223
    e = 65537

    p_high = p<<100  # 乘上2**100一样作用

    PR.<x> = PolynomialRing(Zmod(n))

    f = p_high + x
    f = f.monic()
    out_p = f.small_roots(2^100,0.4)
    print(out_p)
    p = int(p_high + out_p[0])
    assert n % p == 0
    q = n // p
    phi = (p-1)*(q-1)
    d = inverse(e, phi)
    m = pow(c, d, n)
    flag = long_to_bytes(int(m)).decode()
    print(flag) # NSSCTF{36a5ae48-f281-4576-8d1f-acab0666bff2}

BaseCTF2024 [Week2]铜匠

  • 题目

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    from Crypto.Util.number import getPrime, bytes_to_long
    #from secret import flag
    flag=b'XXXX'

    p = getPrime(1024)
    q = getPrime(1024)
    n = p * q
    e = 65537
    hint1 = p >> 721
    hint2 = q % (2 ** 266)
    ct = pow(bytes_to_long(flag), e, n)
    print(hint1)
    print(hint2)
    print(n)
    print(ct)
    '''
    hint1 = 14439249591349619691972392177790365247490839237199085979433418493254022567815148979672690178
    hint2 = 90063199151369157959005663017593053931871580139169245885113098598755909124764417
    n = 18347545778876678838092757800261556931131930866012101566000425608407193858675622059415995283684230959320874387944052648148677918542763633503231962873204645415818139345588988936580526094727943067102768943117592654029397879665312089518191052154267343886226820785206334238961064175118262578895847281575656290248049404047727756356910896332939145136942219317065063060070725033146788186604738271846183709127655298440696824683099637827282095133642324657860714680107691622056420045091586609974536644773286992447027164350612852922016376888380895187804771279035652496676089183636450028327097084911908336202253562671798012457461
    ct = 15659576879410368237140555530527974801613150473447768911067611094143466009251385693099110691602954207905029692682380253595062935017486879899242785756448973466690818942065250284891341066578689696180061755610538867770441139827574063212967027249650509215685566103350688284041405586915563454117672061141919712416360596137520514412607512596079964611672166435592936417138352662031529414118312166411150736015788925026636845744110093161894267707446937939130745326244186579516665160036229715964182962542836836457885170975474737620430886449029488829662146456489724775166105816909257516908496172172266375617868819982791477888289
    '''

  • 解析

    下面鹤城杯的简易版，把p的未知位数改小了，刚好可以不用爆破得到p

在查small_root()参数要求时，找到了原题**鹤城杯2021，babyrsa**

文章[RSA中coppersmith定理的应用条件_sagemath coppersmith-CSDN博客](https://blog.csdn.net/qq_51999772/article/details/123620932)

测试一下在pq均为1024位下，未知量需要控制在多少一下才能使得small_root()有解


1
2
3
4
5
6
7
8
9
10
# sagemath 9.3
from Crypto.Util.number import getPrime
p = getPrime(int(1024)) # 1024可根据题意修改，若p，q不同位，请访问https://blog.csdn.net/qq_51999772/article/details/123620932
q = getPrime(int(1024))
n = p * q
test_bits = 455 # 调节未知数大小
p_h = p >> test_bits
R.<x> = PolynomialRing(Zmod(n))
f = (p_h << test_bits) + x
f.small_roots(2**test_bits,0.4)

​ 这里关于f 方程 等号右边为什么不是0还是存有疑惑

  • exp

    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
    # sagemath 9.3
    from Crypto.Util.number import *
    hint1 = 14439249591349619691972392177790365247490839237199085979433418493254022567815148979672690178
    hint2 = 90063199151369157959005663017593053931871580139169245885113098598755909124764417
    n = 18347545778876678838092757800261556931131930866012101566000425608407193858675622059415995283684230959320874387944052648148677918542763633503231962873204645415818139345588988936580526094727943067102768943117592654029397879665312089518191052154267343886226820785206334238961064175118262578895847281575656290248049404047727756356910896332939145136942219317065063060070725033146788186604738271846183709127655298440696824683099637827282095133642324657860714680107691622056420045091586609974536644773286992447027164350612852922016376888380895187804771279035652496676089183636450028327097084911908336202253562671798012457461
    ct = 15659576879410368237140555530527974801613150473447768911067611094143466009251385693099110691602954207905029692682380253595062935017486879899242785756448973466690818942065250284891341066578689696180061755610538867770441139827574063212967027249650509215685566103350688284041405586915563454117672061141919712416360596137520514412607512596079964611672166435592936417138352662031529414118312166411150736015788925026636845744110093161894267707446937939130745326244186579516665160036229715964182962542836836457885170975474737620430886449029488829662146456489724775166105816909257516908496172172266375617868819982791477888289
    e = 65537

    p_high = hint1
    q_low = hint2
    mod = 2 ** 266
    q_low_lnv = inverse(q_low, mod)
    p_low = n*q_low_lnv % mod

    i = 721 - 266 - 455 # i是p距离small_root成功所需要的位数还缺的位数（用来爆破），455是用另一个py文件推出来的
    print(i)
    PR.<x> = PolynomialRing(Zmod(n))
    if i != 0:
        for j in range(2**i):
            f = p_high * (2**721) + p_low + (x*32  + j) * mod # 这里的32是步长
            f = f.monic()
            out_p = f.small_root(2**455,0.4)
            if(len(out_p) != 0): 
                print(out_p)
                break
        p = (out_p[0]*32 + j) * mod + p_high * (2**721) + p_low

    else:
        f = p_high * (2**721) + p_low + (x*32) * 2**266
        f = f.monic()
        out_p = f.small_roots(2**455,0.4)
        p = p_high * (2**721) + p_low + (out_p[0]*32) * 2**266
        


    p = int(p)
    assert n%p == 0
    q = n//p
    phi = (p-1)*(q-1)
    d = inverse(e, phi)
    m = pow(ct, d, n)
    flag = long_to_bytes(int(m))
    print(flag.decode())

鹤城杯2021 babyrsa

  • 题目

    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 getPrime, bytes_to_long
    from secret import flag

    p = getPrime(1024)
    q = getPrime(1024)
    n = p * q
    e = 65537
    hint1 = p >> 724
    hint2 = q % (2 ** 265)
    ct = pow(bytes_to_long(flag), e, n)
    print(hint1)
    print(hint2)
    print(n)
    print(ct)
    """
    hint1 = 1514296530850131082973956029074258536069144071110652176122006763622293335057110441067910479
    hint2 = 40812438243894343296354573724131194431453023461572200856406939246297219541329623
    n = 21815431662065695412834116602474344081782093119269423403335882867255834302242945742413692949886248581138784199165404321893594820375775454774521554409598568793217997859258282700084148322905405227238617443766062207618899209593375881728671746850745598576485323702483634599597393910908142659231071532803602701147251570567032402848145462183405098097523810358199597631612616833723150146418889589492395974359466777040500971885443881359700735149623177757865032984744576285054725506299888069904106805731600019058631951255795316571242969336763938805465676269140733371287244624066632153110685509892188900004952700111937292221969
    ct = 19073695285772829730103928222962723784199491145730661021332365516942301513989932980896145664842527253998170902799883262567366661277268801440634319694884564820420852947935710798269700777126717746701065483129644585829522353341718916661536894041337878440111845645200627940640539279744348235772441988748977191513786620459922039153862250137904894008551515928486867493608757307981955335488977402307933930592035163126858060189156114410872337004784951228340994743202032248681976932591575016798640429231399974090325134545852080425047146251781339862753527319093938929691759486362536986249207187765947926921267520150073408188188
    """

  • 解析

    有5位需要爆破，如果你用上面的脚本，会发现test_bits=455也是可以出结果的，但是我在实际应用中发现455并不能出结果，所以要减一

  • exp

    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
    # sagemath 9.3
    from Crypto.Util.number import *

    hint1 = 1514296530850131082973956029074258536069144071110652176122006763622293335057110441067910479
    hint2 = 40812438243894343296354573724131194431453023461572200856406939246297219541329623
    n = 21815431662065695412834116602474344081782093119269423403335882867255834302242945742413692949886248581138784199165404321893594820375775454774521554409598568793217997859258282700084148322905405227238617443766062207618899209593375881728671746850745598576485323702483634599597393910908142659231071532803602701147251570567032402848145462183405098097523810358199597631612616833723150146418889589492395974359466777040500971885443881359700735149623177757865032984744576285054725506299888069904106805731600019058631951255795316571242969336763938805465676269140733371287244624066632153110685509892188900004952700111937292221969
    ct = 19073695285772829730103928222962723784199491145730661021332365516942301513989932980896145664842527253998170902799883262567366661277268801440634319694884564820420852947935710798269700777126717746701065483129644585829522353341718916661536894041337878440111845645200627940640539279744348235772441988748977191513786620459922039153862250137904894008551515928486867493608757307981955335488977402307933930592035163126858060189156114410872337004784951228340994743202032248681976932591575016798640429231399974090325134545852080425047146251781339862753527319093938929691759486362536986249207187765947926921267520150073408188188
    e = 65537

    p_high = hint1
    q_low = hint2
    mod = 2 ** 265

    q_low_lnv = inverse(q_low, mod)
    p_low = n*q_low_lnv % mod

    k = 724 - 265 - 455 + 1  # 要加一
    print(k)
    PR.<x> = PolynomialRing(Zmod(n))

    for i in range(2**k):
        f = p_high*(2**724) + p_low + (x*32 + i)*mod
        f = f.monic()
        out_p = f.small_roots(2**454, 0.4)  # small_roots别写错成small_root啦
        if len(out_p) != 0:
            print(out_p[0])
            break

    p = p_high*(2**724) + p_low + (out_p[0]*32 + i)*mod
    p = int(p)
    assert n%p==0
    q = n//p
    phi = (p-1)*(q-1)
    d = inverse(e, phi)
    m = pow(ct, d, n)
    flag = long_to_bytes(int(m)).decode()  # 记得把m 给int()
    print(flag) # flag{ef5e1582-8116-4f61-b458-f793dc03f2ff}

NSSCTF工坊[RSA4]P10（原理未解）

  • 题目
  • 解析
  • exp

XYCTF2024 铜匠 #9/19更新

  • 题目

    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
    from Crypto.Util.number import *
    from secrets import flag

    m = bytes_to_long(flag)
    m1 = getRandomRange(1, m)
    m2 = getRandomRange(1, m)
    m3 = m - m1 - m2


    def task1():
        e = 149
        p = getPrime(512)
        q = getPrime(512)
        n = p * q
        d = inverse(e,(p-1)*(q-1))
        return (pow(m1, e, n), d >> 222 << 222, n)


    def task2():
        e = 65537
        p = getPrime(1024)
        q = getPrime(1024)
        n = p * q
        return (pow(m2, e, n), (p + q) & ((1 << 624) - 1), n)


    def task3():
        e = 65537
        p = getPrime(512)
        q = getPrime(512)
        n = p * q
        return (pow(m3, e, n), (p ^ q) >> 200, n)


    c1, leak1, n1 = task1()
    c2, leak2, n2 = task2()
    c3, leak3, n3 = task3()
    print(c1, leak1, n1)
    print(c2, leak2, n2)
    print(c3, leak3, n3)
    # (89623543982221289730635223555830551523170205418976759060541832483843039074358160566735322009158596405712449020903311144480669706226166537602750967447480664875090686428406188847601970724994074417752345460791736191511081890913041143570455636020205647345764692062144226011846336769477026234106683791286490222089, 138474880017294332349992670187778287774153347391371789199005713563195654993662610111557185709277805165708109047494971468100563949333712521647405765501704478862377527360106399421209690341743821320754482338590671565510629203215009008479290995785318405211007685664887994061938667418220613430135743123498167435264, 146331610798417415036517077006943013321623040860385791423062775325646472298267580898028515394910588437521335092742913111680737790430660749825981979147191282007208147041227246620008377726207734522466015971515317594545750944838673018946440525615131606652748549901880641896940968837669894325535750125282351577689)
    # (5473961166821344576614003060897848014482672788904094340704447882490091115468180944569409159343222459801235179587721232166576530621751748850763430788036935832653535110975154800191323351333883661451331971042214143454441651165718504131976920077768864850035471790911190772583977173388975105970866592974077361193822302653046511418190410043729876062517148438923211673300268277037622337403526399584759202097925983596261279676101079771530118525540842499517622478819211528345668513680064744443628779623340175578509413636950545134641050948185944279029949957748464529075830770617236599864271566534714755373562527112224962839980,62964793504732923650344975634773688108135580826064134090114181449607062497690184718845295432644650580930430061411603385577783897575232298084007041511817031640186953023971498914096209984730,20748652069632848434897928314437138341436264859802586939154590237186029244907936870477844563166827587536149170710720365760129683024401957095447466056746469055173897234659911291443605912459271248059341147358511860537769587963189092648473894868209838600346115919726589891777340166174017389513260737891557712152871714337946675533597049874155202056200170954033849176655928144354665553271709442011723088448485570394208728775665739819536229908847043007472178803394055783543378990699834066614262050119443421709878598533329555838915158259138297060574425019923291353077080236769586821808150397875920110335669136563171420068201)
    # (34640310217688693418173336791306022698488916505988760907493665070072623574363578354500529023855888624978101429772253437880445815006839767802433777006836665709335479076676231470534690281412388704665083311568028710188940132495410474044569100181764053297307413009214044407982980600917158732129850605715306726034, 3763587651775261955566046684899146246387485307521708557610018711932791630073528010801142052497, 94848869174430082173244966077736519396702141299429965725051314270443078621842166791082354594193554380275167898342497998871366256044865879909218309960595691008663632410356093966762639308253848450178310347612630814852054763933063313537694449475061227647475480417779126252294793767003555255527593551612032661749)

  • 解析

    三个挑战，

    task1是d的高位泄露，看了眼NSS工坊，里面提及的是d低位泄露，在网上找到了Emmaaaaaaaaaa师傅的wp，用的式子和d低位泄露是同一个（如下），高位就不用模$2^a$（在低位模$2^a$是因为要构造$d \equiv d_low \mod {2^a}$，a为d泄露的位数）

    这个式子是由

    展开推导得到的

    其中还有一个p和k未知，因为ed与k·phi相近，d本身小于phi，则k小于e，task1的e为149，在可爆破范围内。

    task2

    已知p+q（后称low）的624低位，p、q是1024位的，通过解这个式子n==X*(low - X)，得到相对应的p或q的624低位，再copper一下就能出

    task3

    参考2023-鹏城杯-wp-crypto | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)和2024XYCTF | DexterJie’Blog

    p^q异或部分泄露，通过复现师傅的exp，大概理解了代码运行原理

    从异或结果入手，如果是1，那么p和q在对应的位置是相反的，在这个位置（p_，q_）赋予（0，1）或者（1，0），如果是0，那么就是相同的，（p_，q_）赋值（0，0）或者（1，1），得到311位的部分p后尝试copper

  • exp

    task1

    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
    #sagemath 9.3
    from Crypto.Util.number import *
    from gmpy2 import *
    from tqdm import trange

    #task1
    c1, leak1, n1 = (89623543982221289730635223555830551523170205418976759060541832483843039074358160566735322009158596405712449020903311144480669706226166537602750967447480664875090686428406188847601970724994074417752345460791736191511081890913041143570455636020205647345764692062144226011846336769477026234106683791286490222089, 138474880017294332349992670187778287774153347391371789199005713563195654993662610111557185709277805165708109047494971468100563949333712521647405765501704478862377527360106399421209690341743821320754482338590671565510629203215009008479290995785318405211007685664887994061938667418220613430135743123498167435264, 146331610798417415036517077006943013321623040860385791423062775325646472298267580898028515394910588437521335092742913111680737790430660749825981979147191282007208147041227246620008377726207734522466015971515317594545750944838673018946440525615131606652748549901880641896940968837669894325535750125282351577689)
    e1 = 149
    dh = leak1

    def get_full_p(ph, n, bits):
        PR.<x> = PolynomialRing(Zmod(n))
        f = x + ph
        f = f.monic()
        res = f.small_roots(2**(bits + 4),0.4)
        if res != []:
            x = res[0]
            p = gmpy2.gcd(int(x +  ph), int(n))

            return int(p)
        
    def get_ph(e, n, dh, bits):
        PR.<x> = PolynomialRing(RealField(1000))
        for k in trange(e+1,1,-1):
            f = e*dh*x - k*x*(n-x+1) + k*n - x
            f = f.monic()
            results = f.roots()
            if results != []:
                for res in results:
                    ph = int(res[0])
                    p = get_full_p(ph, n, bits)
                    if p  and p != 1 and p != n:
                        return int(p)




    p1 = get_ph(e1, n1, dh, 222)
    q1 = n1//p1
    phi1 = (p1-1)*(q1-1)
    d1 = inverse(e1, phi1)
    m1 = pow(c1, int(d1), n1)
    print(m1) #330832831022331738585526807955460379454479582944171598101657085161515577868902054403372251911101864207527977700861276537342074608974192943774940351816501776943795657416

    task2

    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
    # sagemath 9.3
    from Crypto.Util.number import *
    def get_full_p2(p_low, n):
        PR.<x> = PolynomialRing(Zmod(n))
        nbits = n.nbits()
        p_lowbits = p_low.nbits()
        f = 2^p_lowbits*x + p_low
        f = f.monic()
        roots = f.small_roots(X=2^(nbits//2-p_lowbits), beta=0.4)
        if roots != []:
            x = roots[0]
            p = gmpy2.gcd(int(2^p_lowbits*x + p_low), int(n))
            return int(p)

    def find_p2_low(low, n):
        X = var('X')
        results = solve_mod([n==X*(low - X)],2^low.nbits())
        for x in results:
            p_low = ZZ(x[0])
            p = get_full_p2(p_low, n)
            if p and p != 1 and p != n:
                return int(p)

    c2, leak2, n2 = (5473961166821344576614003060897848014482672788904094340704447882490091115468180944569409159343222459801235179587721232166576530621751748850763430788036935832653535110975154800191323351333883661451331971042214143454441651165718504131976920077768864850035471790911190772583977173388975105970866592974077361193822302653046511418190410043729876062517148438923211673300268277037622337403526399584759202097925983596261279676101079771530118525540842499517622478819211528345668513680064744443628779623340175578509413636950545134641050948185944279029949957748464529075830770617236599864271566534714755373562527112224962839980,62964793504732923650344975634773688108135580826064134090114181449607062497690184718845295432644650580930430061411603385577783897575232298084007041511817031640186953023971498914096209984730,20748652069632848434897928314437138341436264859802586939154590237186029244907936870477844563166827587536149170710720365760129683024401957095447466056746469055173897234659911291443605912459271248059341147358511860537769587963189092648473894868209838600346115919726589891777340166174017389513260737891557712152871714337946675533597049874155202056200170954033849176655928144354665553271709442011723088448485570394208728775665739819536229908847043007472178803394055783543378990699834066614262050119443421709878598533329555838915158259138297060574425019923291353077080236769586821808150397875920110335669136563171420068201)
    e2 = 65537
    p2 = find_p2_low(leak2, n2)
    q2 = n2//p2
    d2 = inverse(e2, (p2-1)*(q2-1))
    m2 = pow(c2, d2, n2)
    print(m2) # 637474741382124491125351127892971159828342019036405954553729272346832023284163998914076056292480317209934960796148267118196288511438260371617371342378683017480560448795

    task3

    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
    # sagemath 9.3
    from gmpy2 import *
    c3 = 34640310217688693418173336791306022698488916505988760907493665070072623574363578354500529023855888624978101429772253437880445815006839767802433777006836665709335479076676231470534690281412388704665083311568028710188940132495410474044569100181764053297307413009214044407982980600917158732129850605715306726034
    leak3 = 3763587651775261955566046684899146246387485307521708557610018711932791630073528010801142052497
    n3 = 94848869174430082173244966077736519396702141299429965725051314270443078621842166791082354594193554380275167898342497998871366256044865879909218309960595691008663632410356093966762639308253848450178310347612630814852054763933063313537694449475061227647475480417779126252294793767003555255527593551612032661749
    e3 = 65537

    leak3 = leak3<<200
    leak3 = bin(leak3)[2:].zfill(512)
    leakbits = 200

    def solve_leak(pp, qq,k):
        p_min = int(pp+"0"*(512-k), 2)
        p_max = int(pp+"1"*(512-k), 2)
        q_min = int(qq+"0"*(512-k), 2)
        q_max = int(qq+"1"*(512-k), 2)

        if(k == 512 - leakbits):
            PR.<x> = PolynomialRing(Zmod(n3))
            ph = p_min
            f3 = ph + x
            res = f3.small_roots(X=2^leakbits, beta = 0.4)
            if res != []:
                p3 = ph + int(res[0])
                q3 = n3//p3
                d3 = invert(e3, (p3-1)*(q3-1))
                m3 = pow(c3, d3, n3)
                print(m3)
                
        
        if (p_max*q_max < n3) or (p_min * q_min > n3):
            return
        
        if leak3[k] == "0":
            solve_leak(pp+'1', qq+'1',k+1)
            solve_leak(pp+'0', qq+'0',k+1)
        if leak3[k] == "1":
            solve_leak(pp+'1', qq+"0", k+1)
            solve_leak(pp+'0', qq+'1', k+1)

    m3 = solve_leak("1","1",1) # 334132319136130454419386550847309794306389604470819859736266178647538718607667083644497296078054806893307642673035506225568447967643224450929477875810797878149197295514

    flag

    1
    2
    3
    4
    5
    6
    7
    from Crypto.Util.number import *
    m1 = 330832831022331738585526807955460379454479582944171598101657085161515577868902054403372251911101864207527977700861276537342074608974192943774940351816501776943795657416
    m2 = 637474741382124491125351127892971159828342019036405954553729272346832023284163998914076056292480317209934960796148267118196288511438260371617371342378683017480560448795
    m3 = 334132319136130454419386550847309794306389604470819859736266178647538718607667083644497296078054806893307642673035506225568447967643224450929477875810797878149197295514


    print(long_to_bytes(m1+m2+m3))
主要涉及技术：
Crypto、Web
一位23级大学牲

联系QQ:2146983392

欢迎@我，交流闲聊，交换友链

技术只学到一些皮毛
谢谢师傅们的关照