Pebble Coding

ソフトウェアエンジニアによるIT関連技術や数学の備忘録

secp256k1 の有理点のxの小さい方から100個の点の座標を求める

SageMathを使います。
計算の都合上x一つに付きy一つの点のみとしています。(※1)

q = 2**256 - 2**32 - 977
K = GF(q)
i = 1
for x in range(0, 1000):
    try:
        n = (x ** 3 + 7) % q
        y = K(n).nth_root(2)
        print("P"+str(i)+": ("+str(x)+","+str(y)+")")
        if i == 100:
            break
        i = i + 1
    except:
        continue

結果です。

P1: (1,29896722852569046015560700294576055776214335159245303116488692907525646231534)
P2: (2,69211104694897500952317515077652022726490027694212560352756646854116994689233)
P3: (3,94471189679404635060807731153122836805497974241028285133722790318709222555876)
P4: (4,40508090799132825824753983223610497876805216745196355809233758402754120847507)
P5: (6,19112057249303445409876026535760519114630369653212530612662492210011362204224)
P6: (8,91736135629086734185706894124002126994554994840140056297753929940646699135966)
P7: (12,84723224514829953401809146057688111907524826729556536824205543511930558249867)
P8: (13,20267456347483554069520440766283645831919514026818877192810320909941447705364)
P9: (14,44647516152956573151520437476900496747965187933683819148138195218441524686495)
P10: (16,6086653149631013477190265492692874244435390487330439650246572165529255539543)
P11: (20,95115947350322555212584100192293494006877237570979160767752142956238074546829)
P12: (22,17384355509374335117451332188362459136087449825697451396219196747631138909398)
P13: (25,1102551495006820024539592786237854453433258304779672753607085440481650452602)
P14: (27,12150456207077715994570159310959166905435600970349836880310459338926638464144)
P15: (32,25427332243426016000490343799988059539558736656305693852522166340470154069724)
P16: (33,64618998789929410072971405095796020845782142124983079040927463271003622964781)
P17: (38,106145726091087639576918429578805985238991830721588061052426755453285228903782)
P18: (39,87594776024815059699030748919067222200504084624697134229334555487465463311740)
P19: (43,56572214809736663028893280596571268084211571988499307500846727553699476699834)
P20: (44,29878230023088480380896492456768186169213097553238389007631075402030495033678)
P21: (45,105978877815417851567166712846705530007205922360413831304178054752470591328234)
P22: (47,78147825867760401860578288863817851446318924408445916221924839163422634707265)
P23: (48,22158093920271983590355401047321466603843412217042649359409719523363101162922)
P24: (52,78997889189756411106941252110931487807776144035164876735116852230938645586520)
P25: (56,95541328231815356462088403204571346175467036471721334730890062756437520343284)
P26: (57,16126426625268342173634307711482698754358966789324582000857220705151137930603)
P27: (59,12245536361095272910087472248479369148509156736435015023685030300635209335102)
P28: (61,25270374652325280933307573940512180705163720025169208881196733176640262360419)
P29: (63,14631233241205570604624867624666259369859500034128256869409978744684584439094)
P30: (64,74529452721430324654261982022569327733134098544027914004662099577149337772241)
P31: (66,14779399129217284135610310829698658541051988533957713820949226047895356614426)
P32: (69,6923775779868485217762607244436976560652201840399471812857499468401171296105)
P33: (73,54907475477521138395229158123468413368816289595132406362385533965637734491444)
P34: (74,114380274801440699082328907046881771241565654526423586227071669808220106320695)
P35: (76,60513384677472748153923895107278041544833690532893999158483851387624685874502)
P36: (77,84669453674537876923117716638673640065728879686235383227412957732284813661080)
P37: (81,49012209150113709371835725887055463076111894487880039524941615877017615862906)
P38: (82,87943007296251000094382859383389939705064257616707427130018255956497843815507)
P39: (83,14188645264569469460365394943888951885112534878260215841654539259065656715341)
P40: (85,107304282111137147817454781128669352342470237708690917393406579075463918077979)
P41: (88,53061446105460497717807555474027751324223996312098290814318490145303573712991)
P42: (89,61097743811784699873728449979717846056705876687172320472067202479472185748700)
P43: (90,89788577593170654276830283214109858198095867634620648175434900753133217262405)
P44: (91,40897304184061110284907038906202277296031261174736384771453214644384923613309)
P45: (95,688789352197113499076049312979033824648773101793096832709722005065204122614)
P46: (97,28569413528911037896230748681412572483094387181915787404727087450632032344600)
P47: (102,89096260648168769153443369932159207773099122177111644266889254477118918710120)
P48: (104,23928123570632691833923828433532569434131217995444098565375569416622497677351)
P49: (106,31811420021597375731483990613985580149755987883034459459417503329105922656642)
P50: (107,783527093017323088338513914230062436194869842248098283036413563538514224361)
P51: (110,60733069748740950274056211591149380995397338515912582423254050027038049926848)
P52: (111,110020423816543951948138174357929621064214669117893252455581053961287533632517)
P53: (112,97247282039545203036959806020602085188458822064494255908043067021181940477881)
P54: (115,110707770666289307617412702325557697988427612659123904719985478881347063051227)
P55: (118,83058871138355219277744056845545322058825853094823607070971486608950355864468)
P56: (119,107815022335031147085982197295510594014734550970189390092913893895742950156734)
P57: (123,57446492628264891784098775050622253460841288276710978755323331825353875991360)
P58: (126,84439711104802970371780436902152255571369879619679725749203843186061205030154)
P59: (129,55382725319340986888522609697951815268763759969391327927057118210002780622384)
P60: (130,9123603035745374080544160827831106070854195244622192181912474875422694409252)
P61: (132,27878627357612944239112480322615202395851793400230770052703076851048311242027)
P62: (133,57514958619396135678924169196799329427239659158618407279359350024748346920028)
P63: (136,19606405313553580439175451758609055712772036390920901988534771743236378854438)
P64: (137,39937832376125809212637893608782136324981379584442211291654470603964834740125)
P65: (140,31420078610453549982143967626654262649226467832587157382682677745492192743881)
P66: (142,54257118809577631281939512996230583384257691566260297242720612195005404291078)
P67: (144,25776051354870503006711914731185823845954010309911880648590880631299315913904)
P68: (145,503894958834222656188179298325373410260676632844238747986299863102522289637)
P69: (148,68392982707972684488511735093940088887832592032621774288327508606346682038398)
P70: (151,18206104144051037209003969929736611937506472572747666614539949127421881980154)
P71: (152,32901534134581269467036343873227028362005868597802254174192178217562048560643)
P72: (153,100258595487377496042828811449501242516621792476003201519533917116364915159215)
P73: (154,12829677589848770304283687569476252586434394978234077126302661925735769507119)
P74: (157,74650170988155147069923824921440590660846321867968600300630118483349008680944)
P75: (158,95583608550631801372314627928336742308305029464857142595147167214336944495636)
P76: (159,27847704817649963818910683684538122983708108147429377922030012318690415837647)
P77: (160,15603611746335556165638982107429119651874675958060836303217774430168147728000)
P78: (162,41233174264602231837770201338790950505705158133650454445549741077566897072524)
P79: (169,58610407706730698129150370489050085031076017082621560954739918336343795203911)
P80: (170,109846390884199808474705298006681832693844853876227397913078636025714610699686)
P81: (172,16432653490075421148213357179274965580989872527404044312644758101932256510194)
P82: (173,18195958960176378009675983661168542694217510151965239250502777833101226629409)
P83: (174,102838152938020495275627715135822013368927890952638047198924787507115704430269)
P84: (176,83255033799210580107885596650082833785474305537680027341899369923544726496316)
P85: (178,25903468968916508753101614623568444253493834591911962625473618166017204872889)
P86: (179,50495885141706989393286227761766239601272496418559053800514307002432044967292)
P87: (180,100317095055984511289453827191998368019802377185013608127983912402021032927930)
P88: (181,103658198162600322158548294324760153658937014446883622008781272417799838616591)
P89: (182,16282128946545978831215095307580948972883418475150172085857552937267877938406)
P90: (184,110995224041361994779337655930957689081709325594017679662082289792389870444129)
P91: (185,44825212923901322733542244621164394810708544299976708306078474488594692723089)
P92: (186,74041085468902377859852301044344378105035553848130610981724775599288353190777)
P93: (188,98253882464971568807687998830644461521397949236485240657411911488878202083693)
P94: (189,29901408830347733690317097638935208907896964460009749246565641359198742113056)
P95: (191,73603897213503191337902441752810529295101777743606615028633478945843107839830)
P96: (192,66196502803641849052174308350964712726727789435174285700743714766719725929868)
P97: (193,76607261284139079955159175237538797904483083270675936566107785120066323926945)
P98: (194,41599341540216012423927390212328664773986337468799944906477570373245911903366)
P99: (195,28855234683370786274551907761390706377221609265149612861996482880393649968935)
P100: (196,53087547995258991769195514843190516403462571390225420284090480718465980060492)

かかった時間は4秒です。 全ての点を表示するのは時間的に不可能です。 1日=86400秒なので、1日で2,160,000個の点のx,y座標が手に入りますが、ECDSAの署名がこの小さい範囲に入る確率はかなり低く、
攻撃を行うには難しすぎることがわかります。
 2^{256} = 10^{77} に比べて  10^{6} なので、この方法でやったのでは、宇宙の年齢かかっても無理そうです。

※1 楕円曲線の有理点に関しては、一つのxの値に対してyは0個,1個,2個のいずれかしかないことが分かっています。
2個の場合は y2 = - y1 mod q を満たします。
1個の場合は y = 0 となります。
 y^{2} = x^{3} + 7 \ne 0 に対してはyは0個,2個のどちらかです。

プライバシーポリシー

お問い合わせ

スポンサーリンク