2022宁波市第五届网络安全大赛密码方向wp

时间：2023-04-07 19:07:00 ross高继电器e12

2022宁波市第五届网络安全大赛密码方向wp

CrackCi4er

题目

n1 = 11176298870415783282835275600061588657241463221871815491519552463408222565848079182034726185553217300689834006691472991129441397322597826835250447941841691221722446721416543093739804095340289908080867514473017079450311811803390124042848711639790285918640813661662931152276554784900720865966499111108283873361431767904939435365613871971085278398890357112336497323679975134482016115656435362909033743450396163540000606741105863043851991894541522258647025814542415404601472738921699995816713634130792482175987161484763035331960944948454215703767860312632963837039408460375085094414827681771078520774697140944693853984807 e1 = 65537 c1 = 2049142135212658273552941633440876974261753950640752177129652784905850352983432165679473874335026848351759145400964320244625330038089105524551008485108728021427824946995632603255126856753379578506783543964229942691440283255564049755866340136558644811545593331062075012791047810799296947253097390153311675026488654024461487543916802274460814350607787642849014894123082002047937769332643099034647856519147303533346991657725362212257992947710783698461322996483407717614984051267795550326657436918537790720050369514765616726515746420611017668922783549766178919288340405167353735762652502730158055821103551775066192064940  n2 = 14628452939723832473083511588210968910703852366589447308951932044211910559763838916687688620001947054794920424786224454850360778661660629608440528771433740169617993746720487612895876527947146072847716801945896849734515808742075452921890154367709390274374214553338701757577794537605478287979768372097249554390580052172699840182271033424438872211305351156295892595685726305130041874916916020353812984449226411372273954813167019471238042495646276279660976339456926385932462006559332070335515545249174455248514776056358317967032302203257464029754343434591788379595459973195410239904214340484044230212500028487107907195511  e2 = 257 c2 = 11943205429311148875261223425325670018169389197701624890446423663741223099186719632396529960156133015204496469625640992919935968122637192599196371711838810220085238215262686806595336187870118202291530645896788972981251362909696182206907049609819898202930423639770839482639933302200456662731930250303528462910052641021629680394116429930827997772982263970377753077015400323639702289539464290789532346689721249411805236223494026306249551854876805588677162485280664852101462907768951836328019109252702022466487857197139878204830652768250506210934257536926923356529983555063859891380882309438020999240607414375022018574614 p = 115029281281327319478312273262547551232149347339152298613802043883616186127373503864718776300282011779430631165087540701383833715478966593119583810183229480085566336065572594175474108340243383796065963680102431448681064855644562286888210537914211937657283957362425776976579690645671574964758042320552022092267

脚本

from Crypto.Util.number import * from gmpy2 import *  n1 = 1117629887041578328283527560006158865724146322187181549151955246340822256584807918203472618555321730068983400669147299112944139732259782683525044794184169122172244672141654309373980409534028990808086751447301707945031181180339012404284871163979028591864081366166293115227655478490072086596649911110828387336143176790493943536561387197108527839889035711233649732367997513448201611565643536290903374345039616354000060674110586304385199189454152225864702581454241540460147273892169999581671363413079248217598716148476303533196094494845421570376786031263296383703940846037508509441427681771078520774697140944693853984807
e1 = 65537
c1 = 2049142135212658273552941633440876974261753950640752177129652784905850352983432165679473874335026848351759145400964320244625330038089105524551008485108728021427824946995632603255126856753379578506783543964229942691440283255564049755866340136558644811545593331062075012791047810799296947253097390153311675026488654024461487543916802274460814350607787642849014894123082002047937769332643099034647856519147303533346991657725362212257992947710783698461322996483407717614984051267795550326657436918537790720050369514765616726515746420611017668922783549766178919288340405167353735762652502730158055821103551775066192064940

n2 = 14628452939723832473083511588210968910703852366589447308951932044211910559763838916687688620001947054794920424786224454850360778661660629608440528771433740169617993746720487612895876527947146072847716801945896849734515808742075452921890154367709390274374214553338701757577794537605478287979768372097249554390580052172699840182271033424438872211305351156295892595685726305130041874916916020353812984449226411372273954813167019471238042495646276279660976339456926385932462006559332070335515545249174455248514776056358317967032302203257464029754343434591788379595459973195410239904214340484044230212500028487107907195511

e2 = 257
c2 = 11943205429311148875261223425325670018169389197701624890446423663741223099186719632396529960156133015204496469625640992919935968122637192599196371711838810220085238215262686806595336187870118202291530645896788972981251362909696182206907049609819898202930423639770839482639933302200456662731930250303528462910052641021629680394116429930827997772982263970377753077015400323639702289539464290789532346689721249411805236223494026306249551854876805588677162485280664852101462907768951836328019109252702022466487857197139878204830652768250506210934257536926923356529983555063859891380882309438020999240607414375022018574614
p = 115029281281327319478312273262547551232149347339152298613802043883616186127373503864718776300282011779430631165087540701383833715478966593119583810183229480085566336065572594175474108340243383796065963680102431448681064855644562286888210537914211937657283957362425776976579690645671574964758042320552022092267
q1 = n1//p
phi = (p-1)*(q1-1)
d1=inverse(e1,phi)
print(long_to_bytes(pow(c1,d1,n1)))
q2 = n2//p
phi = (p-1)*(q2-1)
print()
d2=inverse(e2,phi)
print(long_to_bytes(pow(c2,d2,n2)))
# b'You found the first piece :flag{0df31ff-b12f-097a-b7'
# b'You found the second piece :ab-fe1a4bfb12e5}'

Cr4ck2

题目

n = 14571489544273684681632745165173941757355029852967262639728000988042839386897493030097099884895386115482493694058873038502860513888769546717076461092157274631880422404640774568976816310850151976919429837061384758878560393916832880369835035094654445542998583110983141044252629041042005200028747437532412882541760701913277010315019696176276304794162940731256361777150089869864848752521412637555443729084762017260965056626550279092491606837302796652497491465469860146607791410672793656097187677222298486237121302232907875363012059539134811841994652897489100941594071086553725267695160318463265760189436211892048571831049
e1 = 18181
e2 = 19937
c1 = 14086932244393217502907224674408736488830849146214227184918262698062675736724337554446711585503734671616977407523947180439538475650652413419679106435434870038055027980301567294772290568083578726775663339768961737480740922223388718943787094330870471886171540256870630059797491648906275021947443613254535459415614412289718705188895798826235866579862681303315446414825328707142227744471707921742768342732559562524019443552187374960675403256064296192626351031408014769594350992074453942709110651276633951009115468620886310509692671361261934324842739148921650085982490562922669906835464674323688759465709626540284576889210
c2 = 9788755099571270122752620318833990768386552453915390611782202313009843880011885989102462216813557305415919308702993594866012255516635580308442538867800280824955615413443022611149710694144180395588528536827198061901961298781041399064307258829088210698947995786806886824892341393690873854230422832064661235313593912677068722144241580197984421905987499008664508485233509643273752098892825326153287135195132848517181638343515469682704077797334084053581822968060796475866168907228760199308163970477417979781603099935953389513751241815586854968725454388470460653618696872424888914546835979441528674579794525553550639554293

脚本

n = 14571489544273684681632745165173941757355029852967262639728000988042839386897493030097099884895386115482493694058873038502860513888769546717076461092157274631880422404640774568976816310850151976919429837061384758878560393916832880369835035094654445542998583110983141044252629041042005200028747437532412882541760701913277010315019696176276304794162940731256361777150089869864848752521412637555443729084762017260965056626550279092491606837302796652497491465469860146607791410672793656097187677222298486237121302232907875363012059539134811841994652897489100941594071086553725267695160318463265760189436211892048571831049
e1 = 18181
e2 = 19937
c1 = 14086932244393217502907224674408736488830849146214227184918262698062675736724337554446711585503734671616977407523947180439538475650652413419679106435434870038055027980301567294772290568083578726775663339768961737480740922223388718943787094330870471886171540256870630059797491648906275021947443613254535459415614412289718705188895798826235866579862681303315446414825328707142227744471707921742768342732559562524019443552187374960675403256064296192626351031408014769594350992074453942709110651276633951009115468620886310509692671361261934324842739148921650085982490562922669906835464674323688759465709626540284576889210
c2 = 9788755099571270122752620318833990768386552453915390611782202313009843880011885989102462216813557305415919308702993594866012255516635580308442538867800280824955615413443022611149710694144180395588528536827198061901961298781041399064307258829088210698947995786806886824892341393690873854230422832064661235313593912677068722144241580197984421905987499008664508485233509643273752098892825326153287135195132848517181638343515469682704077797334084053581822968060796475866168907228760199308163970477417979781603099935953389513751241815586854968725454388470460653618696872424888914546835979441528674579794525553550639554293

import gmpy2 as gp


def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)


s = egcd(e1, e2)
s1 = s[1]
s2 = s[2]
if s1 < 0:
    s1 = - s1
    c1 = gp.invert(c1, n)
elif s2 < 0:
    s2 = - s2
    c2 = gp.invert(c2, n)

m = pow(c1, s1, n) * pow(c2, s2, n) % n
print(bytes.fromhex(hex(m)[2:]))
# b'flag{afe12ec-c1be-421f-c0fa-ea2f6ceb10a0}'

n_n

题目

ucnd fclsmn.rmjy.irdapc jdsncm zpmscjdp, almph_mn_yniz
ucnd hpfcpm jdsncm uyvz
jdsncm zdsl2

s = zpmscjdp(1024)
x = zpmscjdp(1024)
i = s * x
p = 0g130u7u3
k = zdsl2.jiwpcm(p, (s-1)*(x-1))
jiws_x = zdsl2.jiwpcm(s, x)
jiwx_s = zdsl2.jiwpcm(x, s)

d = almph_mn_yniz(uyvz)
f = zdsl2.snbdnk(d, p, i)

scjim(p)
scjim(k)
scjim(jiws_x)
scjim(jiwx_s)
scjim(f)

脚本

from Crypto.Util.number import *
from gmpy2 import *

e = 19986419
d = 3246030980112569716252525489178402976566547966168594693884910274513154299462041341004375201921016318938426026345098668299377474330375073434720935772407207944175167323817898036516011079576927822972280584550642421759163857196487310343842151887753901290056007928776238985151298531470667875043069631236869106891057021962478109360022955201129953336276429238305672598460147562806963064866859947227329083491706302615233310732434276569920504055705370558759864687603230396302816302264528911561986103345422868194300484993924394687653074699941027740263298870609889050004072341364150017277319759241334188164360195703910784166355
invp_q = 23389236347134283235213306702183810016424721867486963556461081084876520502820941836694411695676757754191365637169094291954507615676165999068189562213594619012687252636744435260033076208286475321060918985189871377901228212667433573382718485160649112811594950994116619369682212010587535385364596418447338709974
invq_p = 102920556609507191536438498232122774923059359709189772008951429751731499708926283579532737890030392620334257693429608011647339365489651578950937878926965514185822024062626226427621775843089345409431424163821245825850075741313035783453477904427927137045546100973267423868918950101645341426259141920145517101346
c = 1553892238198363827492950017785469649883078335860404183601470514633985702148771439291915519584864956768837128975747502834867950051639396112333353729920983641277214334076161962538797900388907160490701194265684200572530520821773449401826082542234651817152190240489004982304794568360099499384170323027423530546020874791949260720440971235829841009999271630682762487975448340845503303511707467319967171026472363519627299488034799105120005884793797012235913877429590605758066993126024240880065915024533204819606519268788794771634158963247834960191894770256479582799808670787421459015846778168822826961225790849202125973374

for k in range(1,2**25):
    pp = []
    if (e * d - 1) % k != 0:
        continue
    phi = (e * d - 1) // k
    if len(bin(phi)) > 2053:
        continue
    x = invq_p * phi - invq_p + 1
    if x < 0:
        continue
    keyp = x
    for i in range(2, 10):
        keyp = gcd(keyp, pow(i, phi, keyp) - 1)
    if isPrime(keyp) and b'flag' in long_to_bytes(pow(c, inverse(e, keyp - 1), keyp)):
        print(long_to_bytes(pow(c, inverse(e, keyp - 1), keyp)))
        break
# b'flag{e171892fdcccfc5b0c390806b975a72c}'

PRNG

~~做了一部分，求出 $e 1$ 后面就不知道怎么做了。~~

题目

给了PRNG.ipynb附件，然后cmd下jupyter nbconvert --to script PRNG.ipynb转成py文件

源码

#!/usr/bin/env python
# coding: utf-8

# In[1]:
get_ipython().run_line_magic('display', 'latex')
# In[6]:

from Crypto.Util.number import *
import random

p0 = 115792089210356248762697446949407573530086143415290314195533631308867097853951
a = 115792089210356248762697446949407573530086143415290314195533631308867097853948
b = 41058363725152142129326129780047268409114441015993725554835256314039467401291
E = EllipticCurve(GF(p0), [a, b])
P0 = E(0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296,
       0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5)
n = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551
rlist1 = []
for j in range(624):
    rlist1.append(random.getrandbits(32))
print(rlist1)
s0 = random.getrandbits(256)
RMT = random.getrandbits(256)
s0 = s0 % n
p = getPrime(256)
q = getPrime(256)
assert p != q
x0 = int(inverse_mod(q, n))
e1 = (p * x0) % n


# print("e1",hex(e1))
def GenRNG():
    si = s0
    p_point = p * P0
    q_point = q * P0
    Random_i = 0
    for j in range(8):
        si = int((p_point * si)[0])
        ri = int((q_point * si)[0])
        Random_i = ri & (0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff)
    r_point = si * p_point
    return hex(Random_i), r_point


rand, point = GenRNG()
print(int(rand, 16) ^ ^ RMT)


def genPrime():
    while True:
        a = random.getrandbits(256)
        b = random.getrandbits(256)
        if b % 3 == 0:
            continue
        p = int(a ** 2 + 3 * b ** 2)
        if p.bit_length() == 512 and p % 3 == 1 and isPrime(p):
            return p


def add(P, Q, mod):
    m, n = P
    p, q = Q
    if p is None:
        return P
    if m is None:
        return Q
    if n is None and q is None:
        x = m * p % mod
        y = (m + p) % mod
        return (x, y)
    if n is None and q is not None:
        m, n, p, q = p, q, m, n
    if q is None:
        if (n + p) % mod != 0:
            x = (m * p + 2) * inverse(n + p, mod) % mod
            y = (m + n * p) * inverse(n + p, mod) % mod
            return (x, y)
        elif (m - n ** 2) % mod != 0:
            x = (m * p + 2) * inverse(m - n ** 2, mod) % mod
            return (x, None)
        else:
            return (None, None)
    else:
        if (m + p + n * q) % mod != 0:
            x = (m * p + (n + q) * 2) * inverse(m + p + n * q, mod) % mod
            y = (n * p + m * q + 2) * inverse(m + p + n * q, mod) % mod
            return (x, y)
        elif (n * p + m * q + 2) % mod != 0:
            x = (m * p + (n + q) * 2) * inverse(n * p + m * q + r, mod) % mod
            return (x, None)
        else:
            return (None, None)


def power(P, a, mod):
    res = (None, None)
    t = P
    while a > 0:
        if a % 2:
            res = add(res, t, mod)
        t = add(t, t, mod)
        a >>= 1
    return res


def random_pad(msg, ln):
    pad = bytes([random.getrandbits(8) for _ in range(ln - len(msg))])
    return msg + pad


p, q = genPrime(), genPrime()
N = p * q
phi = (p ** 2 + p + 1) * (q ** 2 + q + 1)
print(f"N: { 
          N}")
d = getPrime(400)
e2 = inverse(d, phi)
k = (e * d - 1) / phi
print("e2:", e2)
to_enc = long_to_bytes(e1)
ln = len(to_enc)
print(f"Length: { 
          ln}")
pt1, pt2 = random_pad(to_enc[: ln // 2], 127), random_pad(to_enc[ln // 2:], 127)
M = (bytes_to_long(pt1), bytes_to_long(pt2))
E = power(M, e2, N)
print(f"E: { 
          E}")
flag = b"flag{**********}"
m = bytes_to_long(flag)
c = m ^ ^ int(point[0])
print("c:", c)

# In[ ]:

output

[2649107920, 3718918278, 1293796385, 2993412573, 1128027079, 2817681927, 175665405, 22757199, 1950544764, 1367466971, 2608399162, 1331311756, 630828409, 271222867, 3751491244, 3062371842, 2201179718, 3497761904, 2468786064, 1096066084, 1761566820, 2854482504, 4035873469, 1779959344, 2857614734, 926629520, 3659355052, 2819809842, 46180849, 1349796232, 2181282048, 1560508798, 1377902391, 855474873, 3733440415, 83116319, 425599064, 94108847, 2401125958, 2960319408, 3239951307, 2589420422, 3387333496, 1602792675, 3055418988, 3048944848, 2701820010, 2230751267, 3689416136, 1661509326, 1272349365, 4150246442, 215652757, 1770109497, 2753719140, 952362721, 251729654, 1485633260, 2218378603, 3450325565, 3872128821, 3262389385, 3450923558, 4117748487, 3202235977, 1348653715, 2287971884, 3471815520, 4098795399, 61869169, 2265060268, 3328118538, 247040131, 3073623484, 1801745773, 3319269873, 345558059, 1686836905, 1986511144, 1467102382, 2092623270, 1088659274, 2013127334, 3866110172, 2396660010, 3825703213, 2907172541, 3365589281, 2465776809, 34051336, 4008622079, 2491015758, 243138927, 2387048905, 586184224, 3508986796, 3019738634, 238751644, 3828554805, 3749497319, 2110199571, 2021772008, 3927874184, 4004430409, 2366174455, 2406024347, 749820930, 3369316670, 2129784660, 3316851742, 1185053702, 2372975397, 1793853478, 2751994198, 2545956297, 265433403, 963248956, 4099167847, 2607292752, 2752417760, 4261829607, 1600622346, 1900293739, 382080379, 3677886149, 3521746268, 2201570072, 784583969, 4152679298, 2337961014, 11760366, 1953830538, 1530465604, 2749937228, 686870460, 4025363927, 1247621893, 3195807102, 1104479108, 2658169429, 1907555883, 328093376, 1654857869, 2089376659, 3223559118, 2507005361, 4140676008, 3304381424, 3698320404, 1334950764, 2547453065, 2439164659, 2266515310, 708825664, 2372105496, 1954598931, 1990296520, 1767744374, 2889513098, 2002322631, 2807523729, 492807165, 1650818571, 348254657, 4247891060, 3430316530, 3107382620, 1190132397, 1733308978, 2507362107, 3979894314, 2913469366, 2680021807, 477946889, 2441146892, 2704823343, 3159555968, 1281326792, 1009052805, 1160544500, 4218115001, 4128862731, 161528336, 2535945107, 2693581075, 4173610913, 2951516980, 386979855, 112689674, 633839095, 1877780847, 1302267610, 696215209, 958468035, 1230043992, 299372509, 2751703758, 2916071904, 1621798188, 3177030048, 63169039, 3755474434, 1891910364, 2309674125, 3244359432, 2212323372, 615380700, 1733382300, 887868799, 3471473287, 2056322357, 2597866987, 3559636864, 2761955282, 526834167, 3561615033, 4108035066, 2260394431, 391201239, 2036013991, 3875599828, 1836127193, 1133423878, 3249544509, 3912088828, 2062988270, 511907089, 1277843042, 2066036595, 3129928878, 1204608018, 3232428891, 2431941968, 1551579046, 2860521509, 346826797, 2254581402, 3069118583, 2546001533, 83747752, 4284978631, 986828513, 1531621813, 3170524474, 3773095450, 345302981, 3992578984, 1394906834, 2452287011, 3949864273, 4101448922, 1282879470, 184421911, 3533026024, 2123198961, 597115028, 2350973912, 3265321304, 851516270, 651498271, 3353735208, 3618522372, 3137199192, 2471798989, 943417301, 441779143, 2799200751, 1131025987, 411434579, 545705159, 4221176025, 1067606819, 1372307469, 3479504104, 922191281, 3737822417, 417162429, 3310768653, 1820147411, 503094207, 3723890725, 1475842204, 710094980, 2506825073, 1854770226, 983670726, 75554282, 2772165110, 2899890522, 559689314, 2514650462, 3066861972, 388960158, 167763042, 2485844580, 3691977130, 3477551360, 2256695456, 777235357, 3378963128, 2479629979, 4101825127, 2593902790, 4045399740, 337515565, 359984091, 718775302, 4185023064, 3108099380, 3895001228, 1300697467, 2204566917, 4143943183, 3891781856, 1482239811, 2850522000, 2367589392, 395939851, 757492591, 1234911506, 3757199389, 1767497303, 2121694843, 366402593, 3821781044, 3172648384, 2374798182, 1961702664, 3411186233, 3038987255, 2242830507, 2047804043, 210550862, 2599094708, 784650810, 608331676, 2154892353, 60013204, 2611694892, 51195545, 3405159752, 1412478984, 2649008598, 2252480713, 3058218157, 1215210222, 721752183, 3394181927, 922630877, 3955372692, 4293581834, 2668489831, 1202488744, 2986085023, 1413157163, 2441408945, 3079587077, 1548650355, 3555611377, 1107319198, 205377586, 2358930304, 1605235639, 4131738376, 4022366509, 1786909697, 3365924126, 161791629, 2376738795, 972855702, 1665795874, 2741418911, 1603674507, 2117422452, 3105676762, 893301029, 2361579895, 1387184073, 1494475208, 1639705885, 2506009509, 4219539378, 1762250114, 1043041141, 2107650905, 805298955, 1340822034, 558466272, 702299476, 3641528608, 4131501350, 667544744, 945914125, 3614176503, 2347075883, 1571766236, 4186142268, 2686030831, 394007469, 4094566341, 900899037, 4047815010, 2283597149, 2377669845, 1741586069, 3432610521, 3004611501, 3086573642, 2052006381, 1743383075, 2809434379, 999156405, 318625887, 3274017998, 2382148362, 1551640073, 2133167542, 756454446, 2382150534, 1767836229, 4028608226, 2528864384, 1911752831, 4187592213, 3883760643, 3599002588, 2228741310, 2686536297, 377978727, 1308068013, 2711419284, 1584862620, 1266478314, 1872964221, 1685792166, 4136018623, 4216864666, 2261474782, 3048701172, 1365819623, 152690157, 1903940456, 1349603529, 1312875117, 303818997, 2552362600, 1935992503, 2776123566, 445793901, 4126182136, 1359326068, 1290896442, 1688334478, 4227207758, 3052167210, 350041107, 1748244697, 3512572161, 3179945120, 2572685107, 1916691533, 536352673, 4096843606, 747328423, 3068797660, 2730521393, 2401168309, 3730899706, 2403397021, 1142613736, 3546159456, 4255691617, 1457956570, 27132771, 705687788, 2364472155, 2806899395, 102583200, 3827511785, 259195349, 2977520603, 51317784, 2301120865, 2887278318, 4178004503, 3940204235, 4198946277, 1146850598, 3676433837, 1856987329, 1985706453, 594367207, 450145835, 3868103872, 590371876, 1940558304, 244258478, 2437994221, 1705962435, 1241721616, 1477298476, 40725997, 4171935621, 1284029510, 1737818042, 1109275735, 2165479848, 3482420403, 2363356869, 1749552401, 1084047251, 1531439097, 1356054312, 1592483365, 3115933606, 2487385492, 3559413369, 1886760336, 1536489002, 160519058, 1980989510, 1012874382, 790062127, 190325425, 613800060, 381407145, 839201630, 316361449, 3424780592, 3596536681, 4037866820, 2076517258, 1344072106, 1360650756, 2503423788, 292251611, 1690384024, 1049854483, 2079497775, 731393465, 2904871831, 764137721, 570893518, 1642053135, 110034397, 3137920450, 2466873101, 3751284852, 2209474627, 2389893380, 709559520, 1577372327, 2426343943, 772334859, 2725315279, 3646757142, 2149600021, 3704715876, 3290065622, 2308687321, 3471875911, 2064021266, 701023386, 3368311370, 3957157673, 2213098995, 1711811184, 555256104, 1371167590, 3197186886, 1106557143, 1235351297, 3940070975, 3832458798, 1530313869, 292793906, 3291164435, 3264549869, 491777038, 2415656621, 1555426652, 1002713984, 1457036264, 1070829452, 2920703456, 801852574, 1832712227, 684995704, 981864896, 1733874940, 2779691022, 20969618, 1552560019, 268030210, 2497495479, 1743409267, 1337706282, 2180486058, 2201268060, 506419529, 3012952628, 1261022813, 3146087759, 1673235926, 2866158450, 251488145, 3383720258, 2410917394, 2755226258, 1332249063, 3100192132, 3375557066, 396505688, 3903706621, 3813926014, 3540978625, 3237205507, 1956295676, 923322753, 438255910, 935054181, 1393846637, 233488185, 886720638]
15413179760135621403725462857877073293432061496500333151288436066464402199771
N: 87811466002403541211466069732380338782951981556683987472266035211298697180402048582047134212064438239192707350521538313227117974899431385511137268385193135184708929764902190728623057508121156354339737170533649025877917378068712975546719832330593126242697571716943143262085563599807075989540865968486224112617
e2: 2254957067475755019550415914608016768703930383956285801090813013715944981752805897447305201948474063065918080510930880083612802828769936589013242072375199367550539171277233385414094642162728109438371752145170748286533779974341009385827527742920020401473537428204643142118637484944130693113274118749300255304010038246938555169686084772220345938890705867553626822565946116629301911301470146023937512076849666921904843781172721693345403317735157783705124674650816989135540941441021816742842244690834494658979196992211576351654238623150467933398465411027016285609059065579576392124937460694966454649168545004932868127210
Length: 32
E: (57253039862440584068170638480826563426074700468093945009042114942872422709097291475786777666248563584697439202927519076361175668304344667472416212554444744722153168817829992064787695655459926900916806019471941698892835924641119274847799201730969297309238147015012295575459346410653384053435458656791853141827, 87686284887945792171883742283241944215819437420798673102139888250267420633084403055519581613755904217608675217833924981645767016339808970078518414995129553303229955906862109718687174816212445723843906895237301432506417931865052382908425803059076305607383739816216332882871097586474657359047785131047721324475)
c: 102142395297355599263711282096409499793839297954163650187476221737435864789860

思路

该题可以分成两部分，一个是后半部分的mt19937predictor，另一个是前半部分的ECC

讲讲mt19937

安装库：pip install mersenne-twister-predictor

for j in range(624):
    rlist1.append(random.getrandbits(32))
print(rlist1)

白给的624个 $g e t r a n d i b i t s (32)$ 来计算出后面的随机数， $genPrime()和random\_pad（）$ 这两个函数都是通过 $r a n d o m . g e t r a n d b i t s ()$ 来给出返回值，我们已经拿下了624个 $g e t r a n d i b i t s (32)$ 自然而然能拿下上面的那两个函数。

已知 $p$ ， $q$ ， $e 2$ 后，求出 $p h i = (p * * 2 + p + 1) * (q * * 2 + q + 1)$ ，那么 $d = i n v e r s e (e 2, p h i)$ ，这样就求出了 $M = p o w e r (E, d, N)$ 。不过这个原理我不懂，但可以验证一下 $M = p o w e r (p o w e r (M, e 2, N), d, N)$ 是成立的。这样就出了 $e 1$ 。

import mt19937predictor

def random_pad(msg, ln):
    pad = bytes([pre.getrandbits(8) for _ in range(ln - len(msg))])
    return msg + pad

def genPrime():
    while True:
        a = pre.getrandbits(256)
        b = pre.getrandbits(256)
        if b % 3 == 0:
            continue
        p = int(a ** 2 + 3 * b ** 2)
        if p.bit_length() == 512 and p % 3 == 1 and isPrime(p):
            return p
        
pre = mt19937predictor.MT19937Predictor()
for i in range(624):
    pre.setrandbits(rlist1[i], 32)
s0 = pre.getrandbits(256)
RMT = pre.getrandbits(256)
s0 = s0 % n
p, q = genPrime(), genPrime()
phi = (p ** 2 + p + 1) * (q ** 2 + q + 1)
d = inverse(e2, phi)
M = power(E, d, N)
m1 = long_to_bytes(M[0])
m2 = long_to_bytes(M[1])
e1 = bytes_to_long(m1[:16]+m2[:16])

后面的 $E C C$ ，~~还不会做不过~~有一点点的想法。

首先给了 $r i$ 低位异或 $R M T$ 的值，而 $R M T$ 的值我们是知道的，这样有了 $r i 的低 240 位$ ，而 $r i$ 是256，也就是说可以爆破 $r i$ 的高16位，其实很小(2¹⁶)，完全有可能。

然后因为有

x0 = int(inverse_mod(q, n))
e1 = (p * x0) % n
p_point = p * P0
q_point = q * P0

那么 $p\_point = q\_point * e1$ ,（原理？问我原理？我也不懂，只会靠数据验证）

~~在数据库原理实践课上想到的：（可不能被发现了，狗头保命）~~

因为 $y^2 = x^3+a*x+b$ ,已知 $a, b, x$ ，有限域开方求出 $y$ ，即可以求出最后一轮的 $q\_point * si$

$r\_point = si * p\_point = q\_point * si * e1$ ,介样就求出了 $r\_point$ ，就有了 $f l a g$

# SageMath
for i in range(2**15,2**16):
    print(i)
    ri = rand + i*2**240
    P.<y>= Zmod(p0)[]
    f = y^2-(ri^3+a*ri+b)
    o = f.roots()
    if o:
        for j in o:
            r_point = E(ri,int(j[0])) * e1
            m = c ^^ int(r_point[0])
            if b'flag' in long_to_bytes(m):
                print(long_to_bytes(m))
                exit()

脚本

mt19937部分

from Crypto.Util.number import *
from gmpy2 import *

rlist1 = [2649107920, 3718918278, 1293796385, 2993412573, 1128027079, 2817681927, 175665405, 22757199, 1950544764, 1367466971, 2608399162, 1331311756, 630828409, 271222867, 3751491244, 3062371842, 2201179718, 3497761904, 2468786064, 1096066084, 1761566820, 2854482504, 4035873469, 1779959344, 2857614734, 926629520, 3659355052, 2819809842, 46180849, 1349796232, 2181282048, 1560508798, 1377902391, 855474873, 3733440415, 83116319, 425599064, 94108847, 2401125958, 2960319408, 3239951307, 2589420422, 3387333496, 1602792675, 3055418988, 3048944848, 2701820010, 2230751267, 3689416136, 1661509326, 1272349365, 4150246442, 215652757, 1770109497, 2753719140, 952362721, 251729654, 1485633260, 2218378603, 3450325565, 3872128821, 3262389385, 3450923558, 4117748487, 3202235977, 1348653715, 2287971884, 3471815520, 4098795399, 61869169, 2265060268, 3328118538, 247040131, 3073623484, 1801745773, 3319269873, 345558059, 1686836905, 1986511144, 1467102382, 2092623270, 1088659274, 2013127334, 3866110172, 2396660010, 3825703213, 2907172541, 3365589281, 2465776809, 34051336, 4008622079, 2491015758, 243138927, 2387048905, 586184224, 3508986796, 3019738634, 238751644, 3828554805, 3749497319, 2110199571, 2021772008, 3927874184, 4004430409, 2366174455, 2406024347, 749820930, 3369316670, 2129784660, 3316851742, 1185053702, 2372975397, 1793853478, 2751994198, 2545956297, 265433403, 963248956, 4099167847, 2607292752, 2752417760, 4261829607, 1600622346, 1900293739, 382080379, 3677886149, 3521746268, 2201570072, 784583969, 4152679298, 2337961014, 11760366, 1953830538, 1530465604, 2749937228, 686870460, 4025363927, 1247621893, 3195807102, 1104479108, 2658169429, 1907555883, 328093376, 1654857869, 2089376659, 3223559118, 2507005361, 4140676008, 3304381424, 3698320404, 1334950764, 2547453065, 2439164659, 2266515310, 708825664, 2372105496, 1954598931, 1990296520, 1767744374, 2889513098, 2002322631, 2807523729, 492807165, 1650818571, 348254657, 4247891060, 3430316530, 3107382620, 1190132397, 1733308978, 2507362107, 3979894314, 2913469366, 2680021807, 477946889, 2441146892, 2704823343, 3159555968, 1281326792, 1009052805, 1160544500, 4218115001, 4128862731, 161528336, 2535945107, 2693581075, 4173610913, 2951516980, 386979855, 112689674, 633839095, 1877780847, 1302267610, 696215209, 958468035, 1230043992, 299372509, 2751703758, 2916071904, 1621798188, 3177030048, 63169039, 3755474434, 1891910364, 2309674125, 3244359432, 2212323372, 615380700, 1733382300, 887868799, 3471473287, 2056322357, 2597866987, 3559636864, 2761955282, 526834167, 3561615033, 4108035066, 2260394431, 391201239, 2036013991, 3875599828, 1836127193, 1133423878, 3249544509, 3912088828, 2062988270, 511907089, 1277843042, 2066036595, 3129928878, 1204608018, 3232428891, 2431941968, 1551579046, 2860521509, 346826797, 2254581402, 3069118583, 2546001533, 83747752, 4284978631, 986828513, 1531621813, 3170524474, 3773095450, 345302981, 3992578984, 1394906834, 2452287011, 3949864273, 4101448922, 1282879470, 184421911, 3533026024, 2123198961, 597115028, 2350973912, 3265321304, 851516270, 651498271, 3353735208, 3618522372, 3137199192, 2471798989, 943417301, 441779143, 2799200751, 1131025987, 411434579, 545705159, 4221176025, 1067606819, 1372307469, 3479504104, 922191281, 3737822417, 417162429, 3310768653, 1820147411, 503094207, 3723890725, 1475842204, 710094980, 2506825073, 1854770226, 983670726, 75554282, 2772165110, 2899890522, 559689314, 2514650462, 3066861972, 388960158, 167763042, 2485844580, 3691977130, 3477551360, 2256695456, 777235357, 3378963128, 2479629979, 4101825127, 2593902790, 4045399740, 337515565, 359984091, 718775302, 4185023064, 3108099380, 3895001228, 1300697467, 2204566917, 4143943183, 3891781856, 1482239811, 2850522000, 2367589392, 395939851, 757492591, 1234911506, 3757199389, 1767497303, 2121694843, 366402593, 3821781044, 3172648384, 2374798182, 1961702664, 3411186233, 3038987255, 2242830507, 2047804043, 210550862, 2599094708, 784650810, 608331676, 2154892353, 60013204, 2611694892, 51195545, 3405159752, 1412478984, 2649008598, 2252480713, 3058218157, 1215210222, 721752183, 3394181927, 922630877, 3955372692, 4293581834, 2668489831, 1202488744, 2986085023, 1413157163, 2441408945, 3079587077, 1548650355, 3555611377, 1107319198, 205377586, 2358930304, 1605235639, 4131738376, 4022366509, 1786909697, 3365924126, 161791629, 2376738795, 972855702, 1665795874, 2741418911, 1603674507, 2117422452, 3105676762, 893301029, 2361579895, 1387184073, 1494475208, 1639705885, 2506009509, 4219539378, 1762250114, 1043041141, 2107650905, 805298955, 1340822034, 558466272, 702299476, 3641528608, 4131501350, 667544744, 945914125, 3614176503, 2347075883, 1571766236, 4186142268, 2686030831, 394007469, 4094566341, 900899037, 4047815010, 2283597149, 2377669845, 1741586069, 3432610521, 3004611501, 3086573642, 2052006381, 1743383075, 2809434379, 999156405, 318625887, 3274017998, 2382148362, 1551640073, 2133167542, 756454446, 2382150534, 1767836229, 4028608226, 2528864384, 1911752831, 4187592213, 3883760643, 3599002588, 2228741310, 2686536297, 377978727, 1308068013, 2711419284, 1584862620, 1266478314, 1872964221, 1685792166, 4136018623, 4216864666, 2261474782, 3048701172, 1365819623, 152690157, 1903940456, 1349603529, 1312875117, 303818997, 2552362600, 1935992503, 2776123566, 445793901, 4126182136, 1359326068, 1290896442, 1688334478, 4227207758, 3052167210, 350041107, 1748244697, 3512572161, 3179945120, 2572685107, 1916691533, 536352673, 4096843606, 747328423, 3068797660, 2730521393, 2401168309, 3730899706, 2403397021, 1142613736, 3546159456, 4255691617, 1457956570, 27132771, 705687788, 2364472155, 2806899395, 102583200, 3827511785, 259195349, 2977520603, 51317784, 2301120865, 2887278318, 4178004503, 3940204235, 4198946277, 1146850598, 3676433837, 1856987329, 1985706453, 594367207, 450145835, 3868103872, 590371876, 1940558304, 244258478, 2437994221, 1705962435, 1241721616, 1477298476, 40725997, 4171935621, 1284029510, 1737818042, 1109275735, 2165479848, 3482420403, 2363356869, 1749552401, 1084047251, 1531439097, 1356054312, 1592483365, 3115933606, 2487385492, 3559413369, 1886760336, 1536489002, 160519058, 1980989510, 1012874382, 790062127, 190325425, 613800060, 381407145, 839201630, 316361449, 3424780592, 3596536681, 4037866820, 2076517258, 1344072106, 1360650756, 2503423788, 292251611, 1690384024, 1049854483, 2079497775, 731393465, 2904871831, 764137721, 570893518, 1642053135, 110034397, 3137920450, 2466873101, 3751284852, 2209474627, 2389893380, 709559520, 1577372327, 2426343943, 772334859, 2725315279, 3646757142, 2149600021, 3704715876, 3290065622, 2308687321, 3471875911, 2064021266, 701023386, 3368311370, 3957157673, 2213098995, 1711811184, 555256104, 1371167590, 3197186886, 1106557143, 1235351297, 3940070975, 3832458798, 1530313869, 292793906, 3291164435, 3264549869, 491777038, 2415656621, 1555426652, 1002713984, 1457036264, 1070829452, 2920703456, 801852574, 1832712227, 684995704, 981864896, 1733874940, 2779691022, 20969618, 1552560019, 268030210, 2497495479, 1743409267, 1337706282, 2180486058, 2201268060, 506419529, 3012952628, 1261022813, 3146087759, 1673235926, 2866158450, 251488145, 3383720258, 2410917394, 2755226258, 1332249063, 3100192132, 3375557066, 396505688, 3903706621, 3813926014, 3540978625, 3237205507, 1956295676, 923322753, 438255910, 935054181, 1393846637, 233488185, 886720638]
n = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551
N = 87811466002403541211466069732380338782951981556683987472266035211298697180402048582047134212064438239192707350521538313227117974899431385511137268385193135184708929764902190728623057508121156354339737170533649025877917378068712975546719832330593126242697571716943143262085563599807075989540865968486224112617
e2 = 2254957067475755019550415914608016768703930383956285801090813013715944981752805897447305201948474063065918080510930880083612802828769936589013242072375199367550539171277233385414094642162728109438371752145170748286533779974341009385827527742920020401473537428204643142118637484944130693113274118749300255304010038246938555169686084772220345938890705867553626822565946116629301911301470146023937512076849666921904843781172721693345403317735157783705124674650816989135540941441021816742842244690834494658979196992211576351654238623150467933398465411027016285609059065579576392124937460694966454649168545004932868127210
E = (
    57253039862440584068170638480826563426074700468093945009042114942872422709097291475786777666248563584697439202927519076361175668304344667472416212554444744722153168817829992064787695655459926900916806019471941698892835924641119274847799201730969297309238147015012295575459346410653384053435458656791853141827,
    87686284887945792171883742283241944215819437420798673102139888250267420633084403055519581613755904217608675217833924981645767016339808970078518414995129553303229955906862109718687174816212445723843906895237301432506417931865052382908425803059076305607383739816216332882871097586474657359047785131047721324475)


def genPrime():
    while True:
        a = pre.getrandbits(256)
        b = pre.getrandbits(256)
        if b % 3 == 0:
            continue
        p = int(a ** 2 + 3 * b ** 2)
        if p.bit_length() == 512 and p % 3 == 1 and isPrime(p):
            return p


def add(P, Q, mod):
    m, n = P
    p, q = Q
    if p is None:
        return P
    if m is None:
        return Q
    if n is None and q is None:
        x = m * p % mod
        y = (m + p) % mod
        return (x, y)
    if n is None and q is not None:
        m, n, p, q = p, q, m, n
    if q is None:
        if (n + p) % mod != 0:
            x = (m * p + 2) * inverse(n + p, mod) % mod
            y = (m + n * p) * inverse(n + p, mod) % mod
            return (x, y)
        elif (m - n ** 2) % mod != 0:
            x = (m * p + 2) * inverse(m - n ** 2, mod) % mod
            return (x, None)
        else:
            return (None, None)
    else:
        if (m + p + n * q) % mod != 0:
            x = (m * p + (n + q) * 2) * inverse(m + p + n * q, mod) % mod
            y = (n * p + m * q + 2) * inverse(m + p + n * q, mod) % mod
            return (x, y)
        elif (n * p + m * q + 2) % mod != 0:
            x = (m * p + (n + q) * 2) * inverse(n * p + m * q + r, mod) % mod
            return (x, None)
        else:
            return (None, None)


def power(P, a, mod):
    res = (None, None)
    t = P
    while a > 0:
        if a % 2:
            res = add(res, t, mod)
        t = add(t, t, mod)
        a >>= 1
    return res


def random_pad(msg, ln):
    pad = bytes([pre.getrandbits(8) for _ in range(ln - len(msg))])
    return msg + pad


import mt19937predictor

pre = mt19937predictor.MT19937Predictor()
for i in range(624):
    pre.setrandbits(rlist1[i], 32)
s0 = pre.getrandbits(256)
RMT = pre.getrandbits(256)
s0 = s0 % n
p, q = genPrime(), genPrime()
phi = (p ** 2 + p + 1) * (q ** 2 + q + 1)
d = inverse(e2, phi)
M = power(E, d, N)
m1 = long_to_bytes(M[0])
m2 = long_to_bytes(M[1])
e1 = bytes_to_long(m1[:16] + m2[:16])
print('e1 =', e1)
print('RMT =', RMT)
# e1 = 101563087737026898438873514001560446261182370289831109397693402244341405045329
# RMT = 15413276086551791042520799942819006956759549580618927382644779919795326151715

ECC部分

虽然2**16不大，但跑起来很慢，有限域开方好慢

#SageMath
from Crypto.Util.number import *
import tqdm
p0 = 115792089210356248762697446949407573530086143415290314195533631308867097853951
a = 115792089210356248762697446949407573530086143415290314195533631308867097853948
b = 41058363725152142129326129780047268409114441015993725554835256314039467401291
E = EllipticCurve(GF(p0), [a, b])
P0 = E(0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296,
       0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5)
rmt = 15413179760135621403725462857877073293432061496500333151288436066464402199771
c = 102142395297355599263711282096409499793839297954163650187476221737435864789860
e1 = 101563087737026898438873514001560446261182370289831109397693402244341405045329
RMT = 15413276086551791042520799942819006956759549580618927382644779919795326151715
rand = RMT ^^ rmt
flag = 0
P.<y>= Zmod(p0)[]
highnum = 2^240
for i in tqdm.tqdm(range(2**14,2**15)):# 这个范围在（1，2**16）之间，运气好的话一下子就跑出来了（实际上i=16721）
    if flag:break
    ri = rand + i*highnum
    f = y^2-(ri^3+a*ri+b)
    o = f.roots()
    if o:
        for j in o:
            r_point = E(ri,int(j[0])) * e1
            m = c ^^ int(r_point[0])
            if b'flag{' in long_to_bytes(m):
                print(i, long_to_bytes(m))
                flag = 1
                break
# 16721 b'flag{i_love_PRNG_ivgyb_jijn}'

锐单商城拥有海量元器件数据手册、IC替代型号，打造电子元器件IC百科大全！

2022宁波市第五届网络安全大赛密码方向wp

相关文章