over 9 years ago
沒什麼好說的,就是個正常的 ICPC BFS 題。
前面要先做一個滿足某條件 hash 的 proof of work,可以用 hashcat 輕鬆解決。
import socket
import hashlib
import struct
import sys
import subprocess
import time
st = socket.socket(socket.AF_INET,socket.SOCK_STREAM)
st.connect(('218.2.197.243',6000))
print st.recv(4096)
s = st.recv(4096)
print s
s = s[s.find('SHA1'):]
salt = s[6:22]
sha1 = s[45:45+40]
f = open('hash','w')
f.write(sha1+":"+salt)
f.close()
s = subprocess.check_output("./hashcat-0.47/hashcat hash -m 120 -a 3 -1 '?l?d?u' '?1?1?1?1'",shell=True)
s = s[s.find(salt):][17:21]
print s
st.send(s+'\n')
print st.recv(4096)
s = st.recv(4096).split('\n')[1]
try:
for tt in range(10000):
print '('+s+')'
f = open('input','w')
f.write(s+'\n')
f.close()
subprocess.check_output("./solve")
ss = open('sol','r').read().split('\n')
for i in range(len(ss)-1):
if i==len(ss)-2 and ss[i-1]==ss[i]:
break
s = ss[i]
print '# '+s+']'
st.send(s+'\n')
print st.recv(4096)
s = None
while s == None:
zzz = st.recv(4096)
print zzz
for x in zzz.split('\n'):
if 'L' in x:
s = x
break
except:
while True:
print st.recv(4096)
time.sleep(1)
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
char str[30];
int dis[1<<21][21];
int pre[1<<21][21][2];
int que[30000000][2];
int n,sr;
int sol[100][2];
inline void add(int U,int x,int &p,int pu,int px){
if(dis[U][x]==-1){
dis[U][x] = dis[pu][px]+1;
pre[U][x][0] = pu;
pre[U][x][1] = px;
que[++p][0] = U;
que[p][1] = x;
}
}
[66/172]
void print(int U,int x){
for( int i=n-1; i>=0; i-- ){
if(i==n-x-1){
if((U>>i)&1){
puts("ERROR");
while(1);
}
printf(" ");
}else{
printf("%c","LR"[(U>>i)&1]);
}
}
puts("");
}
int calc(int S,int x,int T){
int p,q,sx=x;
int U,d,dU,l1,l2,r1,r2,m;
dis[S][x] = 0;
p = 0;
q = -1;
que[0][0] = S;
que[0][1] = x;
while(p!=q){
q++;
U = que[q][0];
x = que[q][1];
//print(U,x);
if(U==T){
m = dis[T][x];
sr = 0;
while(U!=S || x!=sx){
sol[sr][0] = U;
sol[sr++][1] = x;
dU = U;
U = pre[dU][x][0];
x = pre[dU][x][1];
}
sol[sr][0] = U;
sol[sr++][1] = x;
return m;
}
m = 1<<(n-1-x);
l1 = m<<1;
l2 = m<<2;
r1 = m>>1;
r2 = m>>2;
if(x>0){
dU = ((U&l1)>>1)|(U&(~l1));
add(dU,x-1,p,U,x);
if(x>1){
dU = ((U&l2)>>2)|(U&(~l2));
add(dU,x-2,p,U,x);
}
}
if(x<n-1){
dU = ((U&r1)<<1)|(U&(~r1));
add(dU,x+1,p,U,x);
if(x<n-2){
dU = ((U&r2)<<2)|(U&(~r2));
add(dU,x+2,p,U,x);
}
}
}
return -1;
}
int main(){
int x,d,xl,xr;
FILE *fi = fopen("input","r");
fgets(str,sizeof(str),fi);
fclose(fi);
d = 0;
xl = xr = 0;
for( int i=0; str[i]!='\n'; i++ ){
d<<=1;
if(str[i]==' '){
x = i;
}else if(str[i]=='L'){
xl++;
}else{
d++;
xr++;
}
}
n = xl+xr+1;
memset(dis,-1,sizeof(dis));
calc(d,x,((1<<xr)-1)<<(xl+1));
printf("%d\n",sr);
FILE* fs = fopen("sol","w");
for( int i=sr-1; i>0; i-- ){
print(sol[i][0],sol[i][1]);
fprintf(fs,"%d\n",sol[i-1][1]+1);
}
print(sol[0][0],sol[0][1]);
fprintf(fs,"%d\n",xl+1);
fclose(fs);
return 0;
}
$ python solve.py
Welcome to the game server!
Proof of work to start the game.
SHA1("efJcaYiCX7AyV7nY" + X).hexdigest() == "ce486d471280a169930efdd1512c85d81e28df72", X is a string of alphanumeric
Input X:
HRVN
Hey, shall we play a game?
Give me a solution to help them get their destination and I will send you your precious.
Please wait while we're generating new round for you
(RRLR LRRLRLLLRL)
# 6]
RRLRL RRLRLLLRL
# 7]
RRLRLR RLRLLLRL
# 5]
RRLR RLRLRLLLRL
# 3]
RR RLRLRLRLLLRL
# 4]
RRR LRLRLRLLLRL
# 6]
RRRRL LRLRLLLRL
# 8]
RRRRLRL LRLLLRL
# 10]
RRRRLRLRL LLLRL
# 12]
RRRRLRLRLLL LRL
# 14]
RRRRLRLRLLLRL L
# 13]
RRRRLRLRLLLR LL
# 11]
RRRRLRLRLL RLLL
# 10]
RRRRLRLRL LRLLL
# 12]
RRRRLRLRLRL LLL
# 11]
RRRRLRLRLR LLLL
# 9]
RRRRLRLR RLLLLL
# 7]
RRRRLR RLRLLLLL
# 5]
RRRR RLRLRLLLLL
# 6]
RRRRR LRLRLLLLL
# 8]
RRRRRRL LRLLLLL
# 10]
RRRRRRLRL LLLLL
# 9]
RRRRRRLR LLLLLL
# 7]
RRRRRR RLLLLLLL
# 8]
Congratulations
[Please wait while we're generating new round for you
Round 2
LRLRRLRRLLR LRL
(LRLRRLRRLLR LRL)
...
(After 100 rounds of game)
...
Congratulations
Your flag is BCTF{wh0-s4ys-h4cke7s-c4nn0t-d0-4lg0rIthm}
(100 輪真的好久...)