<<EnableMathJax(doller)>>
= Square =
渡されたプログラムはフラグを部分文字列に分解し、各文字列をstr2hexしたものを16進数と見做し2乗した総和を出力するプログラムである。
（プログラム上は部分文字列は区間を重複することも出来るはずだが、重複はないとして考えた。）

フラグは'ASIS_md5(hoge)'の形式なので、37文字で'A','S','I','_','0'-'9','a-f'の文字のみ含まれている。

問題で与えられた整数の平方根は
{{{
0x5260fac0e4ee9973db5b68d9a4
}}}
となり16進数で26文字であることから、部分文字列の最大超は13であることが分かる。（12文字だと文字列がたくさん必要となり37文字を越える)

次に最大長の部分文字列の個数を考える。
 1. 13文字の部分文字列が3個加算されたものだとする。
  * sqrt('0'**2 * 3) > 0x52よりありえない
 2. 13文字の部分文字列が2個加算されたものだとする。
  * 'a' > 0x52より'a'-'f'はどちらの先頭にも出現しない。
  * sqrt('9'**2 * 2) < 0x50 より、どちらの先頭も'0'-'9'ということはありえない。
  * sqrt('S'**2 + '0' ** 2) > 0x53より、片方の先頭が'S'ということはありえない。
  * sqrt('I'**2 + '0' ** 2) > 0x53より、片方の先頭が'I'ということはありえない。
  * sqrt('_'**2 + '0' ** 2) > 0x53より、片方の先頭が'_'ということはありえない。
  * sqrt('A'**2 + '0' ** 2) < 0x53, sqrt('A'**2 + '9' ** 2) > 0x53より片方の先頭が'A'にはなりうる
 3. 13文字の部分文字列が1個加算されたものだとする。
  *12文字の部分文字列による影響を考えても、一番左の文字列は'R','Q','P'のどれかとなるはずで、このような文字は含まれないのでありえない。
以上より、13文字の部分文字列は2つ加算されており、片方は'A'で始まる文字列である。

'A'で始まる文字列というのはフラグの先頭部分`"ASIS_..."`しかありえない。
そこで、それぞれ"ASIS_00000000"及び"ASIS_ffffffff"を2乗したものを引いて平方根を求めると、
{{{
ASIS_00000000 => 0x323038399890c92765bac161a8
ASIS_ffffffff => 0x32303839984a3939e7f3467c9d
}}}
それぞれの共通部分を見てみると"32303839"となっている。これはASCII文字列に直すと、"
2089"となっていて、これは2つ目の13文字の部分文字列の先頭4文字であると分かる。
ここで、13文字ではない部分文字列の最大の長さが10だったとすると、5文字目の情報まで失なうことはないため、13文字でない部分文字列の最大の長さは11となる。13+13+11=37より部分文字列は3つしか存在しない。

ここで、問題の数値をN, "ASIS_"から始まる部分文字列を`A`、もう一つの13文字の部分文字列をB、11文字の部分文字列をCとする。
以下のプログラムを用いてA,Bについて、先頭5文字を探索し、ありえるパターンを列挙した。
{{{#!highlight ruby
require 'gmp'
N = 42598113503607816275290739917038018215431555012399274191982894
def squ(str)
    str.unpack("H*")[0].to_i(16)**2
end
def sqr(f)
    GMP::Z(f).sqrt.to_i
end
T = ARGV[0].to_i
C = '0123456789abcdef'
CS = C.chars.map{|a|a.unpack("H*")[0]}
def maxs(s)
  s + 'f' * (13-s.size)
end
def mins(s)
  s + '0' * (13-s.size)
end
def search(a,b,k)
  c1 = sqr(N - squ(maxs(a)) - squ(maxs(b)))
  c2 = sqr(N - squ(mins(a)) - squ(mins(b)))
  c1 = c1.to_s(16)
  c2 = c2.to_s(16)
  c = ''
  11.times do |i|
    if c1[i*2,2] == c2[i*2,2]
      return unless CS.include?(c1[i*2,2])
      c += c2[i*2,2]
    else
      ok = false
      ((c1[i*2,2].to_i(16))..(c2[i*2,2].to_i(16))).each do |a|
        if CS.include?(a.to_s(16))
          ok = true
        end
      end
      return unless ok
      break
    end
  end
  c += "?" * (22 - c.size)
  if k == T
    p [a,b,c,c1,c2]
    return 
  end
  C.each_char do |p|
    C.each_char do |q|
      na,nb = a,b
      if a.size <= k
        na += p
      end
      nb += q
      search(na,nb,k+1)
    end
    break unless a.size <= k
  end
end

search('ASIS_', '2089', 4)
}}}
{{{
$ ruby search.rb
["ASIS_", "20890", "66????????????????????", "661e43919a7868b989823e", "665b83e6d702233e1451ac"]
["ASIS_", "20892", "65????????????????????", "6521682750d179b510739c", "655f41452e7391bbac68c4"]
["ASIS_", "20894", "64????????????????????", "64220e407533845d65dece", "646084b4ff1a6ace4e2e66"]
["ASIS_", "20896", "63????????????????????", "63202296bd2332187225ec", "635f3b2b1b974255ae086f"]
["ASIS_", "20898", "62????????????????????", "621b90e67ee1308c7c7dff", "625b50a33f97773353c4c1"]
}}}
探索結果よりBの5文字目は'0', '2', '4', '6', '8'であると分かる。

A,Bの下8文字について探索することを考える。
A,B,Cの下の桁から2乗した値が一致するかを確認しながら探索すると、
16 ** 24(探索しなきゃいけないパターン数) / 16 ** 16(枝刈りされるはずのパターン数)より2 ** 32程度の計算で全て探索することが出来る。A,Bの下8文字が求まったら、上5桁の5パターンについて、C = sqrt(N - A ** 2  - B ** 2)を考え、Cが'0'-'9','a'-'f'で表される文字列になるようなものを探せば、A,B,Cを特定することが出来る。

以下のプログラムで実際に探索した所、1時間程度で解が得られた。
{{{#!highlight c++
#include <stdio.h>
#include <unistd.h>
#include <gmp.h>
#include <sys/wait.h>
#include <stdlib.h>
#define BASE 10

mpz_t A,B,C,N,D;
mpz_t AA,BB,CC,NN,DD;
mpz_t KK;
mpz_t ADD;
mpz_t ADD1;
mpz_t ADD2;
mpz_t ADD3;
mpz_t ADD4;
mpz_t ADD5;
#define ulong unsigned long long


ulong n = 17577079109955850542ULL;
ulong numbers[] = {48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 97, 98, 99, 100, 101, 102};
char strs[64];
void check2() {
  mpz_sub(DD, N, A);
  mpz_sub(NN, DD, B);
  if(mpz_cmp_si(NN, 0) < 0) return;
  mpz_sqrt(CC, NN);
  mpz_mul(KK, CC, CC);
  if(mpz_cmp(NN, KK) == 0) {
     mpz_out_str(stdout, 16, AA);puts("");
     mpz_out_str(stdout, 16, BB);puts("");
     mpz_out_str(stdout, 16, CC);puts("");
     fflush(stdout);
  }
}
void check(ulong a, ulong b) {
  sprintf(strs, "%llu", a);
  mpz_set_str(A, strs, 10);
  sprintf(strs, "%llu", b);
  mpz_set_str(C, strs, 10);
  mpz_add(AA, A, ADD);
  mpz_mul(A, AA, AA);
  mpz_add(BB, C, ADD1); mpz_mul(B, BB, BB);
  check2();
   mpz_add(BB, C, ADD2); mpz_mul(B, BB, BB);
  check2(); 
  mpz_add(BB, C, ADD3); mpz_mul(B, BB, BB);
  check2();
  mpz_add(BB, C, ADD4); mpz_mul(B, BB, BB);
  check2();
  mpz_add(BB, C, ADD5); mpz_mul(B, BB, BB);
  check2();
}
void search(ulong a, ulong b, ulong c, ulong k) {
  if(k == 8) {
    check(a,b);
    check(b,a);
    check(a,c);
    check(c,a);
    check(b,c);
    check(c,b);
  }else{
    ulong mask = (1ULL << ((k + 1) << 3)) - 1;
    if(k == 7) mask = -1;
    int shift = k << 3;
    for(int i = 0; i < 16; i++) {
      ulong na = a | (numbers[i] << shift);
      for(int j = 0; j < 16; j++) { 
        ulong nb = b | (numbers[j] << shift);
        for(int l = 0; l < 16; l++) { 
          ulong nc = c | (numbers[l] << shift);
          if((na*na+nb*nb+nc*nc-n)&mask){

          }else{
            search(na,nb,nc,k+1);
          }
        }
      }
    }
  }
}

int main() {
  int a,b,c;
  if(fork() == 0) {
    a = 101;
    b = 102;
    c = 57;
  }else if(fork() == 0) {
    a = 101;
    b = 55;
    c = 98;
  }else if(fork() == 0) {
    a = 102;
    b = 49;
    c = 51;
  }else if(fork() == 0) {
    a = 49;
    b = 98;
    c = 99;
  }else if(fork() == 0) {
    a = 53;
    b = 54;
    c = 55;
  }else if(fork() == 0) {
    a = 53;
    b = 57;
    c = 98;
  }else{
    int t;
    wait(&t);
    wait(&t);
    wait(&t);
    wait(&t);
    wait(&t);
    wait(&t);
  }
  mpz_init2(A, 256);
  mpz_init2(B, 256);
  mpz_init2(C, 256);
  mpz_init2(N, 256);
  mpz_init2(D, 256);
  mpz_init2(AA, 256);
  mpz_init2(BB, 256);
  mpz_init2(CC, 256);
  mpz_init2(NN, 256);
  mpz_init2(DD, 256);
  mpz_init2(KK, 256);
 
  mpz_init2(ADD, 256);
  mpz_init2(ADD1, 256);
  mpz_init2(ADD2, 256);
  mpz_init2(ADD3, 256);
  mpz_init2(ADD4, 256);
  mpz_init2(ADD5, 256);
  mpz_set_str(ADD, "5175606464536044217397227290624", 10);
  mpz_set_str(ADD1, "32303839300000000000000000", 16);
  mpz_set_str(ADD2, "32303839320000000000000000", 16);
  mpz_set_str(ADD3, "32303839340000000000000000", 16);
  mpz_set_str(ADD4, "32303839360000000000000000", 16);
  mpz_set_str(ADD5, "32303839380000000000000000", 16);
  mpz_set_str(N, "42598113503607816275290739917038018215431555012399274191982894", 10);
  search(a,b,c,1);
}
}}}
{{{
$ g++ search.cpp -O3 -march=native -lgmp -osearch
$ ./search
415349535f6531326635373339
32303839303330346266353365
6638316230386334373066
}}}

後は、B,Cの並び方について両方試せばフラグを得ることが出来る。