您现在的位置是:首页 >学无止境 >[2023-DAS x SU战队2023开局之战] crypto-sign1n网站首页学无止境

[2023-DAS x SU战队2023开局之战] crypto-sign1n

Emmaaaaaaaaaa 2023-07-21 00:00:03
简介[2023-DAS x SU战队2023开局之战] crypto-sign1n

题目描述:

from secret import r, t
from Crypto.Util.number import *

flag = b'xxx'
flag = bytes_to_long(flag)
e = 0x10001

def gen_keys():
    p = getPrime(1024)
    q = getPrime(1024)
    phi = (p-1)*(q-1)
    d = inverse(e,phi)
    n = p*q
    print(f'n = {n}')
    WHATF = (d ** 3 + 3) % phi
    print(f'WHATF= {WHATF}')
    return d, n, WHATF

def easy_sign(n,d):
    m = flag * pow(r,e**2+d**2,n) % n
    s = pow(m,d,n)
    return s
from secret import r, t
def gift():
    assert t > 0
    gift = pow(r,t) - 1
    #print(t)
    print(isPrime(gift))

d,n,WHATF = gen_keys()
gift()
sign = easy_sign(n,d)
print(f'sign = {sign}')
import gmpy2
from Crypto.Util.number import *
'''
e = 65537
n = 17501785470905115084530641937586010443633001681612179692218171935474388105810758340844015368385708349722992595891293984847291588862799310921139505076364559140770828784719022502905431468825797666445114531707625227170492272392144861677408547696040355055483067831733807927267488677560035243230884564063878855983123740667214237638766779250729115967995715398679183680360515620300448887396447013941026492557540060990171678742387611013736894406804530109193638867704765955683067309269778890269186100476308998155078252336943147988308936856121869803970807195714727873626949774272831321358988667427984601788595656519292763705699
W = 7550872408895903340469549867088737779221735042983487867888690747510707575208917229455135563614675077641314504029666714424242441219246566431788414277587183624484845351111624500646035107614221756706581150918776828118482092241867365644233950852801286481603893259029733993572417125002284605243126366683373762688802313288572798197775563793405251353957529601737375987762230223965539018597115373258092875512799931693493522478726661976059512568029782074142871019609980899851702029278565972205831732184397965899892253392769838212803823816067145737697311648549879049613081017925387808738647333178075446683195899683981412014732
1
s = 12029865785359077271888851642408932941748698222400692402967271078485911077035193062225857653592806498565936667868784327397659271889359852555292426797695393591842279629975530499882434299824406229989496470187187565025826834367095435441393901750671657454855301104151016192695436071059013094114929109806658331209302942624722867961155156665675500638029626815869590842939369327466155186891537025880396861428410389552502395963071259114101340089657190695306100646728391832337848064478382298002033457224425654731106858054291015385823564302151351406917158392454536296555530524352049490745470215338669859669599380477470525863815
'''

题目分析:

  • 已知:

    W = (d ** 3 + 3) % phi
    m = flag * r ^ (e ^ 2 + d ^ 2) % n
    s = m ^ d % n
    
  • 推导:

    m = flag * r ^ (e ^ 2) * r ^ (d ^ 2) % n
    
    两端同时*d
    
    m ^ d = flag ^ d * r ^ e * r ^ (d ^ 3) % n
    
    已知 s = m ^ d, 故
    
    s = flag ^ d * r ^ (e + d ^ 3) % n
    
    两端同时*e
    
    s ^ e = flag * r ^ [e * (e + d ^ 3)] % n
    
    对 r ^ [e * (e + d ^ 3)] 求逆元,记为 d'
    有 r ^ [e * (e + d ^ 3)] * d' = 1 mod n
    则:
    d' * s ^ e = flag 
    flag  = d' * s ^ e % n (保证不越界)
    
  • 所以要求到d’则要求出r
    d’ = gmpy2.invert( r ^ [e * (e + d ^ 3)] , n)

  • 不难看出,r 即为此题关键,在此则要看gift()函数

def gift():
    assert t > 0
    gift = pow(r,t) - 1
    #print(t)
    print(isPrime(gift))

t = 1已经给出
在这里插入图片描述
讲得很有道理,所以t = 2
自此所有参数均已得知,flag也就出来了
解题代码如下:

import gmpy2
from Crypto.Util.number import *
e = 65537
n = 17501785470905115084530641937586010443633001681612179692218171935474388105810758340844015368385708349722992595891293984847291588862799310921139505076364559140770828784719022502905431468825797666445114531707625227170492272392144861677408547696040355055483067831733807927267488677560035243230884564063878855983123740667214237638766779250729115967995715398679183680360515620300448887396447013941026492557540060990171678742387611013736894406804530109193638867704765955683067309269778890269186100476308998155078252336943147988308936856121869803970807195714727873626949774272831321358988667427984601788595656519292763705699
W = 7550872408895903340469549867088737779221735042983487867888690747510707575208917229455135563614675077641314504029666714424242441219246566431788414277587183624484845351111624500646035107614221756706581150918776828118482092241867365644233950852801286481603893259029733993572417125002284605243126366683373762688802313288572798197775563793405251353957529601737375987762230223965539018597115373258092875512799931693493522478726661976059512568029782074142871019609980899851702029278565972205831732184397965899892253392769838212803823816067145737697311648549879049613081017925387808738647333178075446683195899683981412014732
t = 1
s = 12029865785359077271888851642408932941748698222400692402967271078485911077035193062225857653592806498565936667868784327397659271889359852555292426797695393591842279629975530499882434299824406229989496470187187565025826834367095435441393901750671657454855301104151016192695436071059013094114929109806658331209302942624722867961155156665675500638029626815869590842939369327466155186891537025880396861428410389552502395963071259114101340089657190695306100646728391832337848064478382298002033457224425654731106858054291015385823564302151351406917158392454536296555530524352049490745470215338669859669599380477470525863815
r = 2
'''
r = 2
m = f * r ^ (e ^ 2 + d ^ 2)
  = f * r ^ (e ^ 2) * r ^ (d ^ 2)
m ^ d = f ^ d * r ^ e * r ^ (d ^ 3) % n
                      * r ^ (W - 3) % n
s = f ^ d * r ^ (e + W - 3) % n
s ^ e = f * r ^ [e * (e + W - 3)] % n
'''
a = pow(r,e * (e + W - 3),n)
d_a = gmpy2.invert(a,n)
f = pow(s,e,n) * d_a % n
print(long_to_bytes(f))

# DASCTF{RSA_Bl1nd_Signatur3_With_M4th}
  • 另一种解法,异曲同工
e = 65537
n = 17501785470905115084530641937586010443633001681612179692218171935474388105810758340844015368385708349722992595891293984847291588862799310921139505076364559140770828784719022502905431468825797666445114531707625227170492272392144861677408547696040355055483067831733807927267488677560035243230884564063878855983123740667214237638766779250729115967995715398679183680360515620300448887396447013941026492557540060990171678742387611013736894406804530109193638867704765955683067309269778890269186100476308998155078252336943147988308936856121869803970807195714727873626949774272831321358988667427984601788595656519292763705699
W = 7550872408895903340469549867088737779221735042983487867888690747510707575208917229455135563614675077641314504029666714424242441219246566431788414277587183624484845351111624500646035107614221756706581150918776828118482092241867365644233950852801286481603893259029733993572417125002284605243126366683373762688802313288572798197775563793405251353957529601737375987762230223965539018597115373258092875512799931693493522478726661976059512568029782074142871019609980899851702029278565972205831732184397965899892253392769838212803823816067145737697311648549879049613081017925387808738647333178075446683195899683981412014732
s = 12029865785359077271888851642408932941748698222400692402967271078485911077035193062225857653592806498565936667868784327397659271889359852555292426797695393591842279629975530499882434299824406229989496470187187565025826834367095435441393901750671657454855301104151016192695436071059013094114929109806658331209302942624722867961155156665675500638029626815869590842939369327466155186891537025880396861428410389552502395963071259114101340089657190695306100646728391832337848064478382298002033457224425654731106858054291015385823564302151351406917158392454536296555530524352049490745470215338669859669599380477470525863815
r = 2

from Crypto.Util.number import *
f_d = s * pow(pow(r,e+W-3,n),-1,n)
flag = pow(f_d,e,n)
print(long_to_bytes(int(flag)))

#DASCTF{RSA_Bl1nd_Signatur3_With_M4th}

收获与体会:

  • 从两种解法中不难看出求逆元的两种方法:
假设a * d = 1 mod n,其中a已知,d未知
1. d = gmpy2.invert(a,n)
2. d = pow(a,-1,n)
联想:e * d = 1 mod phi
1. d = gmpy2.invert(e,phi)
2. d = pow(e,-1,phi)
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。