勉強とボウリングを両立させてた昔話

皆さん、こんにちは！　Ken.Sです！

少し前に関東学生ボウリング連盟OBの先輩が、学生時代の話をtwitterに載せていました。その方は、ジュニアの頃からボウリングをしていて東大に現役合格、卒業後ナショナルチームに在籍する等文武両道という言葉がすごく似合う私の尊敬している方の一人です。その方のツイートがすごい反響していて、学歴やボウリングの腕などはその方に劣りますがニーズがあればいいな、ということでどう勉強していたかなど自分の昔話を書いていこうと思います(二番煎じとか言わないで)。

この話を書くもう一つの理由として、早稲田大学に進学したいと思うジュニアボウラーが少しでも多くなればいいなという思いもあります。学部生時代、早稲田に入りたいけど勉強はしたくない、できないといったお声を何回か頂きました。確かに簡単に入れる大学ではないかもしれません。しかし、ボウリングを続けながらも入れるということを皆さんにお伝えできればいいなと思い、ブログにまとめさせてもらいます。私も中学の頃には落ちこぼれを経験しました。しかし私は成長した時には環境の変化がありました。これが読んでくださってる方へ良いアドバイスになればいいなと思っています。

特にジュニアボウラーの方や、お子さんがボウリングをしているという親御さんに読んでいただけたら幸いです。

小学生時代

勉強面

低学年の頃は、授業中積極的に発言し問題を答える優秀な生徒だったと思います。好奇心旺盛だったので、それが活きたのかなと思います。クラスの何人かは塾に通っていたみたいですが、私はこの頃はまだ通っていなかったです。「塾に行ってないのに、この問題解けるのすごい！」と褒められたのが嬉しかったのを今でも覚えています。その頃自分は頭が良いものだと思っていました。

高学年になると、集団指導と個別指導の塾二つに通い始め、5年生くらいからは個別指導(明光義塾)一つにしました。しかしそこで受けた小学生模擬試験で洗礼を受けます。偏差値60はいくだろ、とか思ってました(その難しさすら知らない子供だったなぁ)。しかし結果は50すらいかない平均以下。文系科目に至っては40もいってなかった記憶があります。気付けば小学校のクラスでもこの人は自分より上だ、と思う生徒がどんどん増え、落ち込むこともありました。自尊心が高かったなぁ。

ただ、ボウリング部のある青稜中学に入りたいと思うようになってからは、あまり周りの事は気にならなくなった感じです。青稜に行ければいいや、って感じです。行ってた塾が中学生や高校生もいたので、その人達と話すのも楽しいということで塾に結構入り浸ってました。塾に行きだしたのが一つの環境の変化でした。人生で一番勉強したのはこの時期だと思います(今もっとやれ)。しかし自主的に勉強したということはあまりなく、学校や塾の宿題をこなすのがほとんどでした。放課後～塾間も多少遊んでいましたし、塾後も宿題が終わればテレビを見てました。印象に残っている塾での勉強法は、解けなかった問題を講師の方ともう一回解く復習です。定期的に模試があって、解けない問題も多かったので良い勉強法だったなと思います。

中学受験は高校受験や大学受験と違い、複数回受験できます。青稜は確か最大5回受けられました。受験が近くなってもいいとこ50%かなくらいの成績でしたが、2回目の受験で合格しました。

この時に大事だったなと思うことは、自分はできるもんだと思い込んでたことです。確かに小3くらいまではテストは大体満点で理解できないということは無かったと思います(大体の子がそうでした)。低学年での一番の壁は九九と言われていますが、私は天才バカボンのソフト？があり、歌で覚えたり、九九の問題をPCで回答するのをやっていたのであまり苦にしなかったです。しかし、学年が上がるにつれ周りとの差を感じました。ちょっと前は出来てたというのと、勉強ができないとは思われたくないという見栄で勉強してました。今思うと、小さい見栄ですがそれが活力になったのは良かったと思います。そしてこの見栄が後にも活きています。一番仲良かった友達が「俺は絶対一橋大学に入る」と言ってて実現したかは分かりませんが、一緒に勉強を頑張る友達がいたというのも大きかったです。

ボウリング面

地元のボウリング場のスクールが小3から入れるということで、それを知った小1から2年間待ちに待ってそのスクールに入りました。知識面や技術など教わりましたが、基本は投げて遊ぶといった環境でした。中古ボールを頂いてボールを作り、小6の最後に初めて200点いったのを覚えています。けど今は小学生でも2000/9Gとか出してる子がいてすごいなぁと思います。この頃は、狙うスパットはいつでも同じところだしレーン変化なんて知らなかったです。今の子よりかは全然知らないと思います。

ボウリングを続けた大きな要因は、やってて楽しかったことです。スクールも少し上のお兄さんお姉さんに可愛がってもらい、祖母の家の近くにある六甲ボウルの方にも大変よくしてもらいました。大学生になって新人戦で六甲行った時は嬉しかったなあ。

中学生時代

勉強面

中学で勉強に対する環境と意識の変化がありましたので、ここは長くなります。

中1の頃は、定期試験に対して勉強するということを全くしてませんでした。得意な理系科目や、小6の最後に塾で習った英語はなんとかなってました(平均点はギリクリアするくらい)。しかし文系科目は一切できず、地理は20点台を二回出しました。一年前の中学受験ではあれだけ勉強したのに全く勉強せず、何をしていたのかすら覚えてません…。50位/250人程だった順位も下から数えた方が早いくらいまで落ちこぼれました。成績が悪い生徒が強制的に受けさせられる基礎講習に引っかかるくらいになりました。

青稜は中2になると、一つのクラスに成績優秀者を集めた優クラス(約40人)を作ります。当然そのクラスに入れるわけもなく、一般クラスに割り振られます。その頃から、定期試験で良い成績(クラスで何位、学年何位)を取ると小遣いボーナスが支給される制度が我が家でできました。

定期試験前は部活は無かったので、中2以降基本的に部屋に籠って対策してました。中3くらいから近くのボウリング場に行って練習して、その後勉強してました。定期試験前でなくても、試合でない限り勉強しない日はあまり作ってなかったです。1~2時間宿題か分からない範囲を潰して、授業中に話が一切分からないということは避けました。反省として、文系科目はもっと授業の話を聞いて「流れ」を理解するようにすればよかったなと思っています。勉強方法としては、最初30分はYouTube流しながらやって、机に向かう理由を作りました。

結果として中2後半の定期試験で、学年7位に入る結果が出ました！小遣いという小さいインセンティブが、大きな成長に繋がりました。一回良い成績を取ると、まぐれだと思われたくないのでまた頑張り、中3の頃には優クラスに入るまでになりました。ここの環境の変化が自分は一番大きいと思っています。

中2の時、実はあまり優クラスに入りたくないなと思ってました(今だから言えることかも)。レベル高い中に入って劣等感を感じたくないという小さい見栄です。それだったら一般クラスでクラス一位取って満足してたいとか思ってました。しかし実際に優クラスに入ると、落ちたくないので頑張ります。そして、クラスメイトみんな勉強ができるので、質問したり教えてもらったり勉強するには最適な環境でした。また、そんなクラスなのでクラス平均点は異常に高かったです。得意科目も苦手科目もそこが良い目標になっていました。得意科目では平均点以下は取りたくないし、苦手科目なら平均点越えれば自身になります。この良い点数取りたいという見栄と優クラスでありたいというプライドが作るプレッシャーが、勉強するモチベーションになってました。優クラスに入ってよかったなと本当に思います。

この期間は、落ちこぼれから優クラスまで幅広い経験をしました。環境の違いを多く感じ、それがまた活きたのかなと思います。

ボウリング面

中1で都大会5位になって初めてそしてそこから3年間全国大会に出ました。が、これといった成績は無く、中3最後に関東3位になったくらいです(ボウラー人口は少ない)。

ボールの違いやレーン変化もまだ分からず、中3最後の都大会で遅くなったレーンに対応できず4の字したのを覚えています。最後に思いきり内に寄ったらよかったけどその景色が初めてで対応が難しかった記憶があります。曲がるボールが良いという勘違いもあり、多少のコントロールとハマれば打てる(けど長続きしない)程度のボウラーでした。

しかし、中3の途中から支部リーグに参加したことにより第一次成長期に入ります。経験豊富な方が多くいたので、基本的なレーン対応や1ゲーム勝負の流れ運びなどを学ばせてもらいました。私が一番大きい学びと思うのは、負けず嫌いな方が多くいたので本気で勝負する楽しさと負けた悔しさを知ったことです。そんな本気の勝負を毎週できたのは、とても大きい経験になりました。ビアがかかったフレームになるたびに皆さんが集まってきたのは懐かしいなぁ。

高校生時代

勉強面

高2から文理でクラスが分かれましたが、なんとか理系優クラスを維持しました。高校生になると模試が多くなり、定期試験対策に加えて幅広く勉強しなければなりません。定期試験対策で成り上がった身なので、模試対策もちゃんとやらねばなりません。定期試験前では青チャートや重要問題集、単語帳などをやってました。休みの日にはセンター試験を解いたりなど、基本的には勉強に打ち込んでました。高2まではこの大学に行きたい、とかはあまりなく名の知れたところに行ければいいなくらいに思っていたのですが、高3になって定期試験などの学校の成績や部活動や生徒会への取り組みなどが評価される「指定校推薦」があることを知りました(遅い)。やっとどういう大学に行くかを考えるようになって、情報系の勉強がしたいなと思い早稲田大学へ行くことを決意しました。評定などの規準はクリアしていたのでその指定校推薦を利用しました。普段の勉強に加え志望理由書や面接練習などもしてました。

面接当日は最初の説明会から面接までの間、受験生が多かったこともあり結構長い時間待たされました。面接は緊張して上手く話せず、動揺して帰りの電車で逆方向に乗ってしまったりなどありましたが、なんとか合格しました。赤羽のナショナルトレーニングセンターにいる時に結果をもらったのが懐かしいです。

ボウリング面

定期試験前以外には基本的に毎日田町ハイレーンで練習してました。高1の高校対抗で結果を残すようになってからより一層練習するようになり、田町ハイレーン様のご厚意により様々なコンディションで練習させていただきました。ウッドとアーマーの二種類のレーンがあるセンターなんてもう無いんじゃないかな…。スタッフの方には本当によくしていただき、そんな環境があったからこそボウリングを続けられたと思います。

大学生時代

勉強面

正直、勉強はあんまりしてませんでした。両立はしてませんでしたね。テスト前に詰め込んで普通の成績を取るということを繰り返してました。ただプログラミングの授業だけは意欲的に受けてました(javaは分からなかった…)。学年が上がるにつれてだんだん難しくなるのに他の人は余裕そうにしているので焦りもありつつ、最初からちゃんとやっとけと定期的に反省してました(今もそう)。

就職は全く考えてなく、大学院の推薦を何とか取れたので修士課程に進学することを3年の終わりに確定させました。4年次に配属された研究室の先輩や同期がみんなすごかったので、ちゃんと勉強や研究するようになりました。これも環境の変化がもたらした大きな成長です。これらが今に繋がってます。例えば、日本からアメリカへ環境を変えることで成長できると思い留学を決意しました。変化を好むことができる人になりたいんなぁ。

ボウリング面

高校でできなかった全国タイトルを取ることに努力してました。中でも4年次の後半は一番悩んだけど自分の全盛期だったなと思います。大学時のボウリングの話をするととても長くなるので割愛しますが、自分の第二次成長期はこの時期で特に佐取プロに教わったことが大きいです。これも環境の変化かなと思います。今思うと一緒にジャパンオープンに出させてもらったことがこれだけの良い変化をもたらしたのかと、出会いってすごいなと思います。欠員が出たから代打お願いLINEに即答して良かったです。

私は漫画暗殺教室の「第二の刃」という言葉が大好きです。落ちこぼれのE組生徒が殺せんせーを暗殺できればいいから勉強しない、と言うとそれに殺せんせーが怒るというシーンです。優秀な暗殺者はメインの計画は上手くいかない方が多いからサブプランをいくつも用意する、などというエピソードから私も勉強とボウリング両方やっていて良かったと思います。特にジュニアボウラーの方にはボウリングはもちろんのこと、ボウリングだけでいいとはならずに他の分野(勉強に限らず)も取り組んでみてほしいと思います。ボウリングを行っている方は多いですがもう一つの分野も続けているってかなり珍しく個性が出ます。自分という一人の人間を形成するにはそういうことが重要なんだなと、就活を通じてですが感じました。

長くなりましたが、自分の人生を振り返ってみました。これがジュニアボウラーの方に少しでも刺さってくれたらいいなと思います。そして、早稲田に入学したいと思ってくれたらいいなと思います。

それでは！

See you next time!

TokyoWesterns CTF 6th 2020 一問も解けなかった話

皆さん、こんにちは！　Ken.Sです！

今日の朝9時まで開催されてたTokyoWesterns CTF 6th 2020に参加しました！ 結果はタイトルの通り、一問も解けませんでした…。一問あと一歩のとこまで行けたので、その問題のwriteupを書いていこうと思います。

score.ctf.westerns.tokyo

問題概要

問題名：twin-d

分野：crypto

得点：172pt (68 solves)

問題ファイル

• task.rb
• output

task.rb

解法

まずは、問題ファイルから見ていきましょう。rubyプログラムは久しぶりですが、特段変わったことはしてません。流れはこんな感じです。

p,q <- 1024bitsの素数
phi_n = (p-1)*(q-1) とする
while:
  d <- 1024bitsの素数
  gcd(phi_n,d) == 1 and gcd(phi_n,d+2) == 1 ならbreak
e1 = d^-1 mod phi_n
e2 = (d+2)^-1 mod phi_n
//e1*d = 1 mod phi_n
//e2*(d+2) = 1 mod phi_n
msg <- flag.txt
enc = pow(msg,e1,n)
p*q,e1,e2,encを出力

phi_nについて秘密鍵dの逆数e1と、d+2の逆数e2が与えられており、出力された結果がoutputに入っています。

k,k'を正整数とすると、

e1*d = k*phi_n+1　・・・①

e2*(d+2) = k'*phi_n+1　・・・②

となります。

②をdの式にすると、

d+2 = (k'*phi_n+1)/e2

d = (k'*phi_n+1)/e2 - 2　・・・③

となります。

③を①に代入すると、

e1*( (k'*phi_n+1)/e2 - 2 ) = k*phi_n+1

phi_nの式に変形します。まず、両辺にe2を掛け、

e1*(k'*phi_n+1-2*e2) = e2*k*phi_n+e2

e1*k'*phi_n + e1 - 2*e1*e2 = e2*k*phi_n+e2

e1*k'*phi_n - e2*k*phi_n = e2 + 2*e1*e2 - e1

phi_n*(e1*k' - e2*k) = e2 + 2*e1*e2 - e1

となり、

e2 + 2*e1*e2 - e1 = 0 mod phi_n　・・・⑤

ということが分かりました。

ここまでは導出できました！！

ここから、左辺を素因数分解してphi_nの候補を出してやろうと思いましたが、数がデカすぎて無理でした…。ここで、他の方法が思い浮かばず断念しました。

では、続きを。

式⑤を変形すると、

2*e1*e2 = e1-e2 mod phi_n

となります。

ここから、同じ平文を違う公開鍵で暗号化した暗号文を導出します。

enc = m^e1 mod n

enc^(2*e2) = m^(e1*2*e2) mod n = m^(e1-e2) mod n

新しい暗号文を手に入れることができました。

gcd(e1,e1-e2) = 1より、common modulus attackが可能です。やり方はこの記事を見てみてください。

partender810.hatenablog.com

new_enc = enc^(2*e2) mod n とすると

e1*s1+(e1-e2)*s2 = 1となるs1,s2を求めればOKです。

TWCTF{even_if_it_is_f4+e}

最後のcommon modulus attackへの導き方はこちらを参考にさせていただきました。

qiita.com

この方、sqrtも解かれててすごい…！自分も挑戦はしてみましたが、一切歯が立たず…。最近のCTFはかなり難しくなっている気がします。

github.com

それでは！

See you next time!

InterKosenCTF 2020 ciphertexts writeup

皆さん、こんにちは！　Ken.Sです！

丁度本日9/6の22時に終わったInterKosenCTFの問題の一つのciphertextsのwriteupを書いていきます！

InterKosenCTF

score.kosenctf.com

問題概要

問題名：ciphertexts

分野：crypto warmup

得点：201pt (33 solves)

問題文

Since there are two ciphertexts, it is easy to solve, isn't it?

問題ファイル

• main.py
• output.txt

github.com

(writeupも掲載しています。)

main.py

解法

本番ではtar.gzファイルで渡されて、解凍してみると上の二つのファイルが手に入ります。

main.pyを実行したものがoutput.txtに出力されています。

main.pyについて、512bitの素数p,q,rの内、n1はp,qの積、n2はp,q,rの積となっています。次に、20bitの素数e1とそのe1の次に小さい素数e2を格納し、それらを公開鍵としてbytes_to_longしたflagを基に暗号文c1,c2を形成します。最後にn,e,cを出力します。(某企業名みたい)

n2がq,rの積だったら、n1とn2の最小公倍数からqを求めて、そのqでn1,n2を割ればp,rは得られるなぁと思いつつ、p,qを求める方法を探しましたが見つからず断念。同じ平文を暗号化しているのでここになにかヒントがあるのだろうと、いつものslideshareを閲覧。

RSA暗号運用でやってはいけない n のこと #ssmjp from sonickun

www.slideshare.net

その8にあるcommon modulus attackがそれっぽい！(最初はその次のページの方法かなとも思ったけど、e個も暗号文を与えられてないので諦め)

けど、同一のnを用いて暗号文が形成されている必要があるので、ここを上手くやらないといけません。つまり、

c'1 = m^e1 mod n2    or     c'2 = m^e2 mod n1

を求める必要があります。

n2 = r * n1 なので、なんか行けそうな気がするなぁと考えてたらやはりいけました。

c2 = m^e2 mod n2より

m^e2 = k*n2 + c2 (kは整数) = k*r*n1 + c2 = c2 mod n1

∴ c'2 = c2 mod n1 と簡単に求まりました。

では、この求めたc'2やc1,e1,e2,n1を使ってcommon modulus attackを行っていきます。

common modulus attackはこのサイトが分かりやすかったですが、ここでも噛み砕いて説明します。

elliptic-shiho.hatenablog.com

拡張ユークリッドの互除法を用います。簡単に言うと、

a*x + b*y = c (a,b,c : 既知)

となる、x,yの解の一つを求めるやつです。

mathtrain.jp

このサイトの「一次不定方程式への応用」ってところを読むと分かるはずです。

e1*s1 + e2*s2 = 1 となるs1,s2を求めます。そのs1,s2を使うと、

c1^s1*c'2^s2

= (m^e1)^s1*(m^e2)*s2 mod n1 = m^(e1*s1+e2*s2) mod n1 = m^1 = m

と平文mが求まります！

では、s1,s2を拡張ユークリッドの互除法でどうプログラムしていくかというと、このサイトを活用(丸パクリ)します。

tech.camph.net

こんな感じで平文mを求めてlong_to_bytesするとflagが出ました。

KosenCTF{HALDYN_D0M3}

solverも先のgithubに掲載しています。

このInterKosenCTFは昨日10時から始まったのですが、気付かず今日の夕方にやり始めてなんとかこの問題は解けたけど結局他の問題は解けなかったです。多分時間かけても変わらない結果だったと思います(笑)

それでは！

See you next time!

罰ゲーム ～愛の不時着3話視聴～

皆さん、こんにちは！　Ken.Sです！

さて、皆さん8/9のインスタライブ見ていただけましたでしょうか。トビタテ生とコラボしたのですが、その中で「外国語やカタカナ」禁止ゲームをやって見事に負けました(笑) その罰ゲームとしまして、韓流ドラマ「愛の不時着」を見てそのレポート500字をまとめろとなりました…。3話まで見たので気の乗る方読んでください。

先に言っておきます。愛の不時着好きの方からは大変面白くないレポートになっています！

※以降、ネタバレ注意！

3話までのあらすじ

すごい財閥の娘セリは、ファッションブランドを立ち上げるほどの経営者として優秀だった。末娘であるにも関わらず、父親の後継者として二人の兄貴を差し置いて選ばれる。選ばれた翌日(?)に自身の会社のパラグライダースーツのテストで空に飛び立つ。無事、事故に遭う。発生した竜巻に吹き飛ばされ北朝鮮に不時着しそこで軍人リに会う。まあこの二人がきっと結ばれるのでしょうが、軍人としては逮捕しないといけないので、まずここでセリは逃げます。軍人のミスやセリの幸運(?)もあり何とか韓国まで戻れた、と思ったらリの家付近で結局匿ってもらうことになりました。リをよく思わない上司、というか違法なことをしまくってる上司から目を付けられセリを匿っていることがバレ、セリを婚約者ということとします。そうなると当然本物のリの婚約者が現れるわけで、おそらく4話以降でかき回す存在になるのでしょう。他にもセリをよく思わない兄貴二人や、その片方と繋がっている詐欺師クや、そのクと密談しているリの上司など障害がいっぱい出てくるのでしょう。3話の最後は、船で違法出国しようとするが政府(?)に見つかり停止させられます。船の運転手が上手くはぐらかそうとするが結局二人が見つかるのですが、その瞬間キスして終わります。

3話までのレポート(感想)

疑問点というかあり得ないことが多すぎる！！

• なぜ末娘を後継者に選ぶのか。いくら兄貴が無能だからといってそれはないだろう。(1話)
• なぜ危険なパラグライダースーツのテストを社長自ら行うのか。(1話)
• ファッションブランドがなぜパラグライダースーツを開発しているのか。(1話)
• なぜ竜巻が起こることを予測できなかったのか。警報が出ているはずだ。(1話)
• 竜巻に巻き込まれて生きているのが不思議。(1話)
• 地雷一帯を駆け抜けて無事であるセリ(1話)
• セリを見つけた途端なぜ拘束しないほど甘い奴が中隊長になっているのか。(1話)
• ミスしたら死刑どころか末代までの恥、となるくらい軍人は厳しいものなのに勤務中に酒飲んだり韓流ドラマ見てセリを見逃すなんてことがあるのか。(1話)
• 北朝鮮で韓流ドラマを見ても良いのか(1話)
• 宿泊検査の時にキムチ倉に隠れている奴が婚約者なわけ無かろう(2話)
• 北朝鮮の軍人に韓国製品を売ったらその時点で軍人に殺されるはずでは？(2話)
• 指向性マイクがあんなに性能良いわけない(3話)
• キスであの修羅場を乗り切れるわけ(3話)

と、疑いまくりの眼差しで視聴してました(笑) ただ、パラグライダー関連のことは2話でなんとなく明かされました。安楽死を望むほど精神的に弱ってたセリが、スイスで死のうとしてました。安楽死センター(?)の人にスイスを観光したら7割の人はそのまま家に帰るからという理由で、雪山の絶景を見た時に飛んでいるパラグライダーに感動したという経緯からパラグライダーが好きなのだろう。そしてそこにリもいたことから結ばれる伏線バリバリあるなぁと思いました。他の疑問は見続けたら解決されるのでしょうか

あと初めて知ったこととして、地雷は踏んだ瞬間に爆発するのではなく踏んで足を話したら爆発するのかと1話の描写から分かりました。

さてこれから、二人はまぁ結ばれるだろうから二人で韓国に行くのか北朝鮮に残るのかが気になります。その場合財閥やファッションブランド会社はどうなるのでしょうか…。それとも二人は離れ離れに…？ でも女性陣があれだけ盛り上がっていることからそんなバッドエンディングではないでしょう(笑) 1話が1時間以上もありかつ全16話…。残りを見るかは気分次第です(笑)

と、懐疑心たっぷりでお届けした愛の不時着ですが、韓流ドラマにハマる方の気持ちは分かったつもりです。ここがすごい、というポイントは分からないのですが日本のものと遜色ないなと思っています。演技は上手いしセットもキレイで映像に関する疑問点は一切なかったです。あとは話が今後どうなるのか…。話の内容に関して少し否定的でありましたが、新しい分野を開拓できたのは良かったと思ってます！それに、話の続きも気になっているので、たまに続きを見ようかなと思います。

それでは！

See you next time!

knight tour problem を解いてみた

皆さん、こんにちは！　Ken.Sです！

毎週トビタテ生とオンライン飲み会をしているのですが、そこでオセロや将棋などボードゲームの話になりました。インドに留学していた友達が、将棋をインド人に教えた話を聞かせてくれました。そのインド人はチェスは分かるようなのでそれを基に教えたそうなのですが、桂馬をknightのように動かしたそうなのです。友達は桂馬はknightの1/4しか動かせない、前2マスと横1マスしか行けないとちゃんと伝えたそうなのですがそのインド人に噓つき呼ばわりされてしまったそうです(笑) たしかにknightって特殊な駒で、子供のころに教えられて桂馬より動く幅が4倍になる！とかなり印象的だったことを今でも覚えています。

knightだけはqueenで代替できない駒

そんなknightに関する大学の課題で記憶に残っているのが「knight tour problem」ナイト・ツアー - Wikipedia です。

8×8のチェス盤においてknightが全てのマスを一回だけ訪れることは可能か、という問題です。解けることは知られており、それを示せというのが2年前にあった課題でした。この問題の事をそのトビタテ生に話したときに、「どのマスから始めても可能なのか」と質問してもらったのですが、その課題のレポートには角から始めた結果しかありませんでした。気になって調べた結果を書いていきますので、興味のある方是非読んでください！ 反論はいくらでも受け付けます(笑)

まず初めに、c++で書いてみました。競プロでやはりc++の速さが強いので、pythonやgoに比べると書きにくさは感じるのですが勉強ということでc++を利用しました。深さ優先探索で実行しどこにも行けなかったらfalseを返し、1通りでも見つけたらtrueを返して終了するというプログラムを書いたのですが、c++の速さをもってしてもなかなか終わらない…。明らかに1周できないと判断できる場合(あるマスから行けるマスが全て既に訪れていてそのマスに行けない等)にfalseを返していなく、訪れたマスからどこにも行けなくなるまで計算を続けているので範囲の絞りが甘いのもあるのですが、丸2日かかっても終わりません…。総計算量を考えると、あるマスからチェス盤からはみ出さず行くことができるマス数の平均は5.25マス。その内の1マスはそのマスへ訪れる前に訪れているのでその分を引く。これを64回繰り返すので概算で(5.25-1)^64≒10^40となります。c++が1秒で100万通り計算できたとしても、約10^29日かかってしまう…。実際はもっと小さいですが、終わらないわけです。プログラム内にバグがありそれで遅くなっている可能性もありますが、直しても時間がかかりそうなので別の方法を考えます。

そもそも2年前はどう解いていたのか、もう一度提出したレポートを確認しました。充足可能性問題 充足可能性問題 - Wikipedia を解くSAT solverの一つ minisatを利用して解いており、なんと1分程度で解の一つを出していました！

いくつかのリテラル(真か偽となる変数のようなもの)の論理和(クローズ)の論理積がTrueとなるようなリテラルの真と偽の選び方はあるのか、といった問題です。例題は上記のwikiなど見てください。

このsolverであるminisatは以下のコマンドで簡単にインストールできます。

Linux : sudo apt-get install minisat

Mac OS : brew install minisat

minisatはDLLアルゴリズムを採用しています。二分探索でリテラルを真or偽と決め、その場合全てのクローズが真となるかを計算していきます。全て真であるならばクローズの論理積も真となり、その充足可能性問題が解けたということになります。

ではこの問題の核となる、knight tour problemを解くためにどのような充足可能性問題を作るかを考えていきます。

• 時間i(1~64)において、リテラル( (i-1)*64+1 ~ i*64)を用意する(時間1(初手)は1~64, 時間2は65~128, ...)。※この64個はチェス盤の64マスに該当し、時間iは何手目に対応します。knightがいるマスに対応するリテラルを真、そうでないリテラルを偽とする。

時間1の時

前提を決めたところで、クローズを作る条件を作っていきます。

1. knightは1つしか存在しない = 時間iに対応するリテラル( (i-1)*64+1 ~ i*64)のうち真は1つだけ。
2. knightは移動距離3かつ縦横の距離は1以上で動く = 例えばリテラル1が真の(knightがそのマスにいる)場合、75(=64+11), 82(=64+18)のどちらかが真となる。
3. 同じマスには1回しか行けない = 64で割った余りでグループ分けした時に(リテラル番号 mod 64)、真は1つだけ。

この条件1~3を満たすよう命題論理式を組んでいきます。

knightは1つしか存在しない = 時間iに対応するリテラル( (i-1)*64+1 ~ i*64)のうち真は1つだけ。

1-i) ある時間iにおいてknightは1個以上存在する、1-ii) ある時間iにおいてknightは1個以下存在する、と条件1を二つに分けて考えます。

1-i)

時間iにおけるリテラル64個の論理和は真となる。

リテラル1つでも真であれば、論理和は真となります。偽となる場合は時間iのリテラル全てが偽となり、knightが時間iにおいて存在しないこととなります。故にこの論理式が真の場合、時間iにおいてknightが1個以上存在することとなります。

1-ii)

時間iにおいてリテラル64個の内2つ選び、その2つの否定の論理和は真となる。

例えば、マス1にknightがいるとします。1の否定=偽, 2の否定=真となりその論理和は真となります。マス3にいる場合も1,2の否定の論理和は真です。偽となる場合は、1,2が共に真の場合です。となると、knightが時間iにおいて2個以上存在することとなります。故にこの論理式が真の場合、時間iにおいてknightが1個以下存在することとなります。

1-i),1-ii)の式で、ある時間iにおいてknightが一つ存在している命題論理式が立てられました。これは条件3の時にも利用します。

knightは移動距離3かつ縦横の距離は1以上で動く = 例えばリテラル1が真の(knightがそのマスにいる)場合、75(=64+11), 82(=64+18)のどちらかが真となる。

この例を使うと、リテラル1が真ならばリテラル75と82のどちらかが真とならなければなりません。リテラル1,75,82の論理和だと、マス1にknightがいたら真となりマス75,82にknightがいなくても真となってしまいます。なので、リテラル1の否定と75,82の論理和を取ることとします(￢1⋁75⋁82)。リテラル1が真ならば￢1は偽となるので75,82のどちらかが真となる必要があります。これは条件2そのままですね。つまり、時間iのリテラルの一つの否定と、そのリテラル(マス)から行くことができる時間(i+1)の全てのリテラルの論理和全ての論理積が条件2となります。つまり、この論理式が真となる場合、knightが正しく動いていることとなります。

同じマスには1回しか行けない = 64で割った余りでグループ分けした時に(リテラル番号 mod 64)、真は1つだけ。

3) 64で割った余りでグループ分けし、そのグループのリテラル64個の内2つ選び、その2つの否定の論理和は真となる。

条件3では条件1でknightは1個以下を示す命題論理式を真似ます。つまり、1 mod 64のグループの場合、リテラル1,65の否定の論理和を取ります。偽となる場合はマス1,65にknightが訪れ同じマスを2回訪れていることになります。このやり方ではあるマスに1回以下訪れていることになる、ということを示しています。しかし条件1より時間iにおいてknightが1つだけ存在する命題論理式を立てたので、あるマスを訪れていないとしても他のマスに2回訪れたことにもなるので、1回以下の訪問という論理式で本問題は解けます。

故にこの論理式が真となる場合は、knightが全てのマスを1回ずつ訪れていることになります。

これらの条件1~3が真となればこのknight tour problemは解けたことになります！

充足可能性問題の命題論理式を立てられたので、今度はminisatで検証できるようcnfファイルをpythonで作成します。以下の命題論理式はこのようにcnfファイルに記述します。

命題論理式

(￢1⋁￢2⋁￢3) ⋀ (￢1⋁2⋁￢4) ⋀ (1⋁￢3⋁4) ⋀ (2⋁3⋁4)

test.cnf

論理和のクローズを0と改行で区切り、否定はマイナスで表現します。これを以下のコマンドで実行します。

minisat test.cnf ans.cnf

実行画面

実行すると色んな文字が出力され、最後に「SATISFIABLE」or「UNSATISFIABLE」と出ます。「SATISFIABLE」と出れば充足可能となり、その解の一つをans.cnfに出力します。

ans.cnf

これは、リテラル4が真、1~3が偽となる場合が解の1つとなります。

別解として{(1,2,-3,4),(1,2,-3,-4),(1,-2,3,-4),(-1,2,3,4),(-1,2,-3,4),(-1,2,-3,-4),(-1,-2,3,4)}があります。

では、先程の条件1~3を表す命題論理式をcnfファイルに記述するpythonプログラムを作ります。

このまま実行すると、1分程で結果が出ます。しかし、これだと開始地点を自力で決められません。先のチェス盤を1~64で表したように、開始地点のマスのリテラルをcnfファイルに追加します(マス1から始めたい場合にはcnfファイルに「1 0」を追加します)。

線対称、点対称を考えると以下の10マスを開始地点とし全てSATISFIABLEであれば、目的であったどの地点からでもknightがtourできるということになります。

開始地点候補の10マス

結果は開始地点によらず巡回できることが分かりました！！

裏でc++のプログラムも回していたので遅くなったのかもしれませんが、一番計算に時間がかかったのが10番マスからのスタートで約22時間かかりました…。朝起きたら終わっているだろうと思ったら計算途中だった時は不安になりました(笑)

開始地点のそれぞれの結果はGithubに載せておきます。

github.com

(githubに掲載するの初めてで不安…。これで合ってるかな、閲覧だけで編集できないようになっているかな…。)

cnfファイルを作るpythonプログラムもこのgithubに載せてあります。コメントでどの条件の命題論理式を記述しているか書いてあります。

ということで、knight tour problemは充足可能性問題として解いてみました。2年前の自分のレポートを読み返して、こう書いた方が分かりやすいのに等2年間で自分の国語力が変わっているなぁと実感させられることが多く良い経験になりました。こんなの解いて何になるんだ、と思われた方。御尤もです。ですが、情報系学生としてはこういう課題の方が面白く、身近なものが扱われる課題は稀なので新鮮でした。いずれはこの経験が何かに繋がるかも…？こういった問題を楽しめる方は情報系に向いているのかもしれません。つまらないと感じた方はここまで読んでいないと思うので、ここまで読んでいる方は情報系向きかもしれません(笑) 

こんな感じで解いてて面白いと感じた問題はまたブログに載せようと思います！他にもこんな方法があるよ、こっちの方が速いよ！などの意見も待ってます。

それでは！

See you next time!

競技ボウラー中断2年目になってしまいました

皆さん、こんにちは！　Ken.Sです！

前回の記事の更新から気付いたら1ヶ月半も経ってました。実はSNSには載せていなかったのですがCTFのWrite upをいくつか載せてあります。CTFや暗号に興味ある方は少し覗いてみてはいかがでしょうか。

この一ヶ月の間に何してたか何を考えていたかつらつら書いていこうと思います。よければ読んでください。

• 研究、トビタテ

研究する場が変わってもう5ヶ月か、といった感じです。そのままアメリカに残れていたらどんな風になっていたんだろう、とたまに考えたりしています。やはり英語力が大きく違っているのかなぁ。日本にいると英語喋る機会ってほとんどないですから、TOEFL対策してた時より落ちていそうです。維持しなければ…！

研究というか留学活動について、トビタテへオンラインでも活動するという変更申請を提出しました。通らないかもしれません。そしたら、トビタテを辞退することになってしまいます。一度アメリカに行ってから自分の考え方って大きく変わったなと思うことが一つあって、これで辞退になってもあまりネガティブな気持ちになる感じがしないんですよね。アメリカからの一時帰国の時もこんな気持ちで、悲観的に考えることが多かった自分が変わったなと思いました。なんででしょう(笑) トビタテのコミュニティには入れるからかな。トビタテコミュニティ本当に面白いです。食料の事や結婚の事、自分の知らないことをたくさん知れました。話がずれましたね。何にせよ、良いことだと思うので続けていけたらな、と思います。

ただそんなポジティブに毎回なれないことの方が多いです。最近、というかここ1年バカにされることが多々ありました。「(留学前)まだ留学行けてなくて日本にいるのか」「あれだけ留学と騒ぎながらすぐ日本に戻ってきてる」「給付金の10万を全て寄付してるのバカみたい(笑)」etc... 「出る杭は打たれる」ってやつですか？でもこんなことわざって日本らしいですよね。海外じゃあ個性があったら伸ばして認めるというのがほとんどですよね。僕のメンタルは茹でる前の素麺くらいしかないので、簡単に折れます(笑) 気にしない、以外で効果的な対処方法知っている方教えてください！

今少し触れましたが、トビタテのコミュニティは本当に素晴らしいんです(n度目)。トビタテの勉強会のような会であったり、同じ11期で毎週オンライン飲み会して楽しんでます！ また、そのトビタテ生と先週インスタライブをやってみました！ 今週も来週もやる予定なので、留学や他の分野の大学生に興味のある方は是非見に来てください！

• 就活

そろそろ就活しなければならない時期になってしまいました。説明会を聞いてみたりESを書いたりWebテスト受けたり面接したり…。ESを書くたびに自分の文章力の無さを思い知らされます。面接でも言いたいことをまとめられず同じことを何回も言ったり…。唯一Webテストのコーディングテストや数学系問題だけ楽しくやれてます。内定を頂くのはまだまだ先になりそうです。

• 趣味

自粛期間で家にいることがほとんどなのでテレビを見る機会がすごく増えました。そのなかでもクイズバラエティーをよく見てます。頭使う系の番組は結構好きなんですよね。その繋がりで新聞にあるパズルであったり、オンラインでできる脱出ゲームなどやって遊んだりしてます。今年から始めた競技プログラミングもかなり頭使うので楽しいです。Webテストが好きな理由もこれかな？

もう一つの趣味としてプロ野球観戦があります。スポーツを見ると、ボウリングしてた時のことを思い出します。巨人ファンで巨人戦は毎試合見ているのですが、特に今期からトレードで移籍したウィーラー選手の試合中のパフォーマンスが大好きなんです。自身がホームラン打ったり良い守備したときの笑顔も素敵なのですが、チームメイトの好プレイに対する喜び表現が見ていて心暖かくなります。増田選手の「神走塁」が話題になった試合で岡本選手が勝ち越しHRを打った時に、ベンチ前でパーラ選手と派手に喜んでベンチに岡本選手が戻ってきたらひたすらペコペコしてた時、セカンドが少し難しいゴロをうまく捌いてアウトにした時に、思わず笑みがこぼれるほど満面の笑顔で「ナイスプレイ！」と言うところなど、ムードメーカーの存在の大きさを感じます。自分もこういう選手になりたかったなぁ。野球関連で、他にも野球選手のYoutubeであったり野球ゲーム実況や、自分のそのゲームをやったりしてます。マエケンと元西武の秋山選手の侍JAPANドラフトはめちゃくちゃ面白かったです！今はボウリングより野球の方が多く見ています(笑)

同じ趣味の方がいれば教えてください！

• コロナ関連で思ったこと

先週日本に帰国して初めて外食しました。久しぶりに店で食べるラーメンはめちゃくちゃ美味しかったです。しかし、最近になって感染者の数が増えてきているので何度も足を運ぼうとは思っていません。何でも20日連続で3桁だとか…。20日連続で3桁という事実よりも3桁を再び越えたのが20日も前かということに驚いてます(笑) 詳しい数は分からないですが検査する母数を増やした結果ですよね。良い方向に捉えると、母数を増やせるほど国が対策を取っているということだと思います。しかし感染者数は下り坂とは言えない状態です。確かにずっと自粛するのは疲れますが、外出を多くするとそれだけ感染リスクが増えてしまいます。正直なところ外出ばかりする人が感染するのは自業自得であると思いますが、その人と接触しやすい家族や必要な外出をしている人に移すリスクを考えるべきですよね。ずっと自粛している人が外出ばかりしている人に移されたらたまったもんじゃありません。特に若い人は感染しても気付きにくいらしく、無意識に移してしまう可能性が高いようです。自分もそうならないように気を付けなければ！

自粛ムードが少し薄れ外出する方が増えました。もちろん外出する方のおかげで成り立つ事業が多いことから経済活動をいい方向に向かっているとは思います。しかし、その目的のためにそんな遠いところまで行く？というのを何件か見ました。行動範囲を小さくすることで、感染拡大のリスクが減るのかなと思います。特に何県も跨いで電車で移動しているとそれだけ多くの人と接触するので危ないなと思います。意外とこんな人は多いんじゃないかと思います。

先日、免許更新(期限切れ)で免許センターへ行ったのですが、移動は親に頼み車で向かうことができたのですが、建物の中はかなり人がいました。特に列に並ぶ時、前の人と間を空けて並ぶのに少し違和感がありました。何人も並んでると、早くこの列から抜けたいという思いからなんとなく間を詰めたくなってしまいます。間に割り込まれてしまう、と思ってしまいます。なるべく空けて並んでいたのですが、何人かは少し狭い間隔になっていました。いくら免許センターが感染リスクを小さくしようとも、利用者の意識が無いと難しいのかなと感じました。なので、自粛警察になると人に不愉快な思いを与えてしまうのでそうならないようにしたいですが、今一度個人個人で感染リスクを考えて行動すべきだと思いました。

批判のような形になってしまいましたが、この1ヶ月の間こんなことを多く考えてました。恐らく自分は家族がそこまで外出しなくても生活が成り立っているおかげでこう思っているのですが、他の人にはどう見えているのでしょう。不快に思われたらすいません。一刻も早くこの状況が緩和されることを願ってます。

気付いたら前回の記事の更新から1ヶ月半が経ち、時の流れを早く感じます。それに流され何もしないまま年末を迎えないよう気を引き締めて研究活動に力を入れていきたいと思います！そして24歳の目標である「社会に貢献できる人になる」を忘れないように頑張っていきます。

それでは！

See you next time!

nahamcon ctf Raspberry Homecooked Write up

皆さん、こんにちは！　Ken.Sです！

今回もCTFのWrite upを書いていこうと思います。

Raspberry

与えられたprompt.txtはこうなってます。(前回の記事にはこういうの載せ忘れてました)

n = 7735208939848985079680614633581782274371148157293352904905313315409418467322726702848189532721490121708517697848255948254656192793679424796954743649810878292688507385952920229483776389922650388739975072587660866986603080986980359219525111589659191172937047869008331982383695605801970189336227832715706317
e = 65537
c = 5300731709583714451062905238531972160518525080858095184581839366680022995297863013911612079520115435945472004626222058696229239285358638047675780769773922795279074074633888720787195549544835291528116093909456225670152733191556650639553906195856979794273349598903501654956482056938935258794217285615471681

とりあえずRSAでないかとnを素因数分解してみます。どうせだめでしょうけど…。

と思ったら出来たんですこれが。けど素数2つの積ではなく、素数32個の積でした。こういう時はMulti-Prime RSAですね。Multi-Prime RSAは通常のRSAと何が違うかというとほとんど変わりません。秘密鍵dを手に入れるために必要なφ(n)をどう求めるか、くらいです。

そもそもオイラー関数とは、φ(n) = 1~nまでの整数の内, nと互いに素である整数の個数 です。nが素数である場合、1~n-1の全ての整数と互いに素であるのでφ(n)=n-1です。また、このオイラー関数は乗法的であるので、φ(nm) = φ(n) * φ(m)とできます。なので、通常のRSAの場合、n=pqなのでφ(n) = φ(p) * φ(q) = (p-1) * (q-1)となるのです。詳しくはWikiで。

オイラーのφ関数 - Wikipedia

では、nが3個以上の素数の積である場合はその(素数-1)の積を求めればいいのです。

n = Πp_i とすると、φ(n) = Π(p_i-1)です。

φ(n)が求まれば、あとはいつも通りです。

solver.py

flag{there_are_a_few_extra_berries_in_this_one}

RSAのP(rime)がvery(berry)存在しているよ…？という意味なのでしょうか。

Homecooked

この問題は、自分の解法よりも同じ研究室のメンバーの解法がキレイでびっくりしました。

decrypt.py

与えられたdecrypt.pyはこうなっています。関数a,bについてみると…

関数a : 素数判定

関数b : 回文判定

関数aが素数判定なのでsympy.isprimeに置き換えたり、i*i>nでbreakすれば簡単に解けます。

が、きれいな解法は関数a,bを判定しているif文の順番を変えるだけでした。

時間的計算量で考えると

関数a : O(N)

関数b : O(logN) 底:10

であるので関数bが通った整数だけ関数aに投げる方が早く終わります。

flag{pR1m3s_4re_co0ler_Wh3n_pal1nDr0miC}

今回はこの2問を紹介しました！

それでは！

See you next time!