Anime Festival Asia 2015 in Singapore。一応これが主目的。コミケの企業ブース（一部同人エリアもあったけど）＋ライブ。ライブに行くのは初めてだけど楽しかった。レーザーがかっこいい。せっかくなので光る棒も買ってみた。中にはLEDがびっしりというのを想像していたけれど、光るのは持ち手の部分だけで、棒は光を拡散させているだけなのか。
p = 195589859419604305972182309315916027436941011486827038011731627454673222943892428912238183097741291556130905026403820602489277325267966860236965344971798765628107804393049178848883490619438682809554522593445569865108465536075671326806730534242861732627383004696136244305728794347161769919436748766859796527723
指数の底を任意に指定できる場合、位数の小さな底を渡すと逆算が可能になるという問題がある。例えば、p-1の位数は2（(p-1)^2=1となる）ので、x=p-1とすると、x^flagの値はflagが偶数ならば1、奇数ならばp-1となる。同様に、位数がkの整数を底に指定すると、kが総当たり可能な程度に小さければ、flag mod kの値が分かる。
位数kを持つ底が存在する条件は、p-1が約数にkを持つこと。この問題の場合は、k = 2, 3, 6, 9, …などに対して、flag mod kの値が分かる。最初は中国人の剰余定理を使うのかなと思い、小さな素因数が2と3しかないので、法が互いに素という中国人の剰余定理の条件を満たさなあと悩んでいた。よくよく考えてみると、flag mod 3^kの値が分かっているときに、flag mod 3^(k+1)の値を求めるのは簡単だった。
(00:02) gp > p = 195589859419604305972182309315916027436941011486827038011731627454673222943892428912238183097741291556130905026403820602489277325267966860236965344971798765628107804393049178848883490619438682809554522593445569865108465536075671326806730534242861732627383004696136244305728794347161769919436748766859796527723
%3 = 195589859419604305972182309315916027436941011486827038011731627454673222943892428912238183097741291556130905026403820602489277325267966860236965344971798765628107804393049178848883490619438682809554522593445569865108465536075671326806730534242861732627383004696136244305728794347161769919436748766859796527723
(00:02) gp > for (i=0, 336, sqrtn(Mod(1,p), 3^i, &z); print(z))
1
Mod(104014548352862869844938168699037346159667005020653232215280909315013887004134868071692786470598745196869723476863259041566021786143181633190908349324551845723794609926567304576385405504723391936863098403039412007235326783702521959959990403821231826220564014204004925465542563989453628264120514916708791295289, 195589859419604305972182309315916027436941011486827038011731627454673222943892428912238183097741291556130905026403820602489277325267966860236965344971798765628107804393049178848883490619438682809554522593445569865108465536075671326806730534242861732627383004696136244305728794347161769919436748766859796527723)
Mod(184652117342066002125654235724672107296479548524944232819111563903191006442841910870258588328187042859006937684077703029415354169137811839089174205147468046219075692488717893872876980963114118329358013489256502574078197180921037431791591430810377557558530731446903392174481754139833226637153091225821181459427, 195589859419604305972182309315916027436941011486827038011731627454673222943892428912238183097741291556130905026403820602489277325267966860236965344971798765628107804393049178848883490619438682809554522593445569865108465536075671326806730534242861732627383004696136244305728794347161769919436748766859796527723)
Mod(184703592399630395992436694563840651821345959648882665358650769365293715003098677483460150685414076439977481202237026725692730858348800757738575025587940041796479236394368440075581490376984436883703286883100998351356645756513111907638957133347344001275568620875776030118946807467426690617366314494522903230861, 195589859419604305972182309315916027436941011486827038011731627454673222943892428912238183097741291556130905026403820602489277325267966860236965344971798765628107804393049178848883490619438682809554522593445569865108465536075671326806730534242861732627383004696136244305728794347161769919436748766859796527723)
Mod(110911870833244863188457786643721493610784303513579129522393811396028723726659740858323669743224481525481653274103693005011435072682119191684346088511737934950819776631108869567490910585606931573400726494033281267128656345029354355593639402681259953259490212087559197723833793933264120796188614403292964375754, 195589859419604305972182309315916027436941011486827038011731627454673222943892428912238183097741291556130905026403820602489277325267966860236965344971798765628107804393049178848883490619438682809554522593445569865108465536075671326806730534242861732627383004696136244305728794347161769919436748766859796527723)
:
下記のコードで、x=3^kに対してのflag mod xが手に入る。前半のSHA-1の計算はブルートフォース防止の問題を解くため。
p = 195589859419604305972182309315916027436941011486827038011731627454673222943892428912238183097741291556130905026403820602489277325267966860236965344971798765628107804393049178848883490619438682809554522593445569865108465536075671326806730534242861732627383004696136244305728794347161769919436748766859796527723
p3 = [1,
104014548352862869844938168699037346159667005020653232215280909315013887004134868071692786470598745196869723476863259041566021786143181633190908349324551845723794609926567304576385405504723391936863098403039412007235326783702521959959990403821231826220564014204004925465542563989453628264120514916708791295289,
60596460703939283816039205007643327134157148193137267625175827451053986819941320545425174147667596081382708012312681744811027758187030913123958296233100508255282449193369626634505358810006112813774496917212618041107392205938556674774459583844872217984025489695097001179157787176195328504655348838631849663942,
10441323002096004510770587886741164350611625346463303011098537719084211549367934812572712892322805795870488891233845379359846218253172487403746893055076258863370778801037982921324392236506419913883778765063307635117884863379930809028657037691697264628883957391135108525171201634495578625408183792572214453266,
:
]
from socket import *
from time import *
from hashlib import *
s = socket(AF_INET, SOCK_STREAM)
s.connect(("52.69.244.164", 9003))
sleep(1)
t = s.recv(1024)
print t
prefix = t[99:99+11].replace(" ","").decode("hex")
try:
for a inrange(32,256):
for b inrange(32,256):
for c inrange(32,256):
for d inrange(32,256):
w = prefix+chr(a)+chr(b)+chr(c)+chr(d)
if sha1(w).hexdigest()[:6]=="000000":
raiseexcept:
passfor i inrange(len(p3)):
s.send("%s\n"%p3[i])
sleep(0.1)
print"<%s>"%i, s.recv(10240)
あとは、返ってきた値からflagを求めれば良い。
flag = 0for i inrange(1,len(p3)):
for j inrange(3):
ifpow(root3[i], flag+j*3**(i-1), p) == res[i]:
flag += j*3**(i-1)
print flag
print ("%x"%flag).decode("hex")
