ポタージュを垂れ流す。

マイペースこうしん(主に旅行)

情報処理安全確保支援士試験に合格しました

タイトルの通りですが、情報処理安全確保支援士試験に合格しました。

情報処理安全確保支援士試験とは

長ったらしい名前の試験ですが、セキュリティスペシャリストとか、セキスペとか言われている試験です。国内で受けれるセキュリティ系の試験の中だと最難関らしい。

詳しい話はここを読んでもらう方がいいかも

www.sc-siken.com

登録セキスペとかいうのになればそれを士業にして独立してセキュリティコンサルタントとかできるらしい。登録料高いしならんけど。セキュリティキャンプフォーラム行った時にIPAの人に会う機会があったけど登録料高いから例えば学生さん向けに学割みたいな制度作ればいいのにって言ってた。

受験動機

セキュリティキャンプに参加したとはいえ、セキュリティのことなんもわからんな〜となったから。

実際これきっかけでセキュリティに関することは色々と知ることができた。個人的にはAPの時より学習効果を感じた。

したこと

3月上旬 中旬

勉強らしい勉強はあんまりしてない。とりあえず本を読んでた。あんまり頭には入ってない気がする。

マスタリングTCP/IP 情報セキュリティ編 | Ohmsha←最近第2版でたね

www.sbcr.jp

3月下旬

とりあえず本格的な対策本を買った。

www.seshop.com

とりあえず全部読む気でいたけど1/3くらい読んだところで4月が見えてきて、どう考えても時間足りんなとなったので辞書的な使い方をすることになった。

3/28〜4/2

いわゆる緑本を買った。APの時もかなり良い参考書だったので。3/30くらいからやり始めた。

2022 情報処理安全確保支援士「専門知識+午後問題」の重点対策 | IT資格試験の取得、IT人材育成は株式会社アイテック(iTEC)

午前Ⅱ対策もこれくらいに始めた気がする。午前Ⅱは過去問と同じ問題が半分出るので、過去問さえやっておけばOKと判断して過去問道場を隙間時間にやってた。

4/3〜4/9

緑本をとにかく進める。問題を解いてると本読んでるだけだとふ〜んってなってたことが、だんだんわかってくる。

なんとか緑本を1周する。

4/10〜4/16

緑本の2週目に入る。緑本に入ってない過去問をR03秋から遡って解いていった。

4/11にこの本を買って一気読みした。めっちゃ分かりやすくて初めからこれ買えば良かったになった。個人的には暗号技術入門より好き。

gihyo.jp

4/17

本番当日。会場はまさかの京大。部屋も情報数学か振動波動論かで使ったことある部屋だった。

手応え

  • 午前Ⅰ

AP持ってるので免除

  • 午前Ⅱ

15/25わかってたので通過

  • 午後Ⅰ

  • 午後Ⅱ

合格

次はネットワークかデータベース取るのがいいですかね

第2次スマートホーム化計画

potaxyz.hatenablog.jp

これから約3年

当時もswitchbotは存在したけど、hubとしては雲の形のやつしか売ってなくてデザインが嫌いだなあ、となってnature remoを選んだ記憶がある。

が、月日が流れ、主張してこないデザインのswitchbot hub miniが発売され、switchbot製品が充実してきた昨今、ただの汎用リモコンでしかないremoではカーテン自動操作したいとか玄関の鍵の開け閉めも自動化したいとなると、別の会社の製品を買わないといけなくなるのが嫌だなあという感じに。

そこで、いっそswitchbotエコシステムに乗り換えてしまおうということで、一気に製品を購入。

購入

一式購入
一式購入

  • switchbot hub mini (x2)
  • switchibot hub mini専用 echo flexコネクタ
  • switchbot ボット
  • switchbot 湿温度計プラス
  • switchbot カーテン
  • switchbot ロック

計: 27,230yen

amazonのタイムセールの時に買ったので普通に買うよりは安くなっているはず。

やりたかったこと

  • リビングのシーリングライトの操作自動化(remoからの乗り換え)
  • エアコンの操作自動化(remoからの乗り換え)
  • カーテンの開閉の自動化
  • 玄関の開閉自動化
  • 玄関のでんき自動化
  • 部屋の温度と湿度の確認

自動化って言ってるけどタイマー設定したら自動で動くとか、スマホで操作できるとか、alexa経由で声で操作するとか、ちょっと広い意味でのそういうことを指しています。

設置

リビングのhub

nature remoが刺さってたusbのとこをそのままswichbot hub miniに変更。まだテープとか貼ってなくて放置されているのでそのうち良い感じにする。

シーリングライトとエアコン

シーリングライトはリモコンの赤外線を学習させた。エアコンはswitchbot側が用意してるデータベースに製品があったみたいで赤外線学習させずに設定が完了した。風向きは変えれないみたいでその点はnature remoに劣るが、そこまで気にならない気もする。スマホからのリモコンメニューの見やすさはnature remoの方が優れている気がするが、どうせalexa経由で声でしか操作しないし、細かい操作はそんなにしないので気にならないと思う。

switchbotとnature remoとのスマホのリモコン比較

ライトのリモコン(switchbot)
ライトのリモコン(nature remo)
エアコンのリモコン(switchbot)
エアコンのリモコン(nature remo)

温湿度計プラス

nature remo miniでは温度しかわからなかったけど、温湿度計を買ったので温度も湿度も確認できるようになったのは嬉しい(alexa経由で声で温度の確認もできる。湿度は無理?)。1分ごとにデータを取ってるみたいで、csvでエクスポートできたりするのも嬉しい。温度は0.1度刻み、湿度は1%刻み。

ちなみにプラスと普通のやつの違いは値段と、サイズと、快適度マークが出るか、あと記録が残る期間がちょっと長いとかくらいらしい。

nature remoであれば本体があるだけで温度(miniを使っていたので湿度は測れなかった)が確認できたが、やっぱり目で確認できるものがあるといいなという気持ちになった。

温湿度計プラス
温湿度の履歴が見れる

カーテン

カーテンの開閉が自動でできるようになったので、1日中カーテンは閉めっぱなしみたいな状況は防げる気がする。とりあえず朝タイマーで開くようにして昼夜逆転が解消することを祈る。夕方になったらタイマーに自動で閉めるようにして閉め忘れてたみたいなのも防げそう。スマホからだと開き具合もパーセントで指定できるのが良い。alexaで操作する場合は全開か全閉しかできない。

GIF画質悪いな

カーテン

カーテン操作

玄関のhub

リビングのhubからだと位置的に玄関内のやつには届かない気がしたので購入。もしかしたら不要だったかもしれないが...

玄関に設置されていたecho flexに専用コネクタでくっつけた。

玄関のドア

設置する向きを迷って2、3回つけたりはずしたりしてたので粘着力弱まっててそのうち取れてしまう気がするが今のところ大丈夫そう(3Mテープで接着するようになっている)。ドライヤーで熱すれば普通に跡なくはがせる。正直いつも鍵は持ち歩くしなくてもいいと思ったが、スマホで施錠状況が確認できるし、鍵の閉め忘れがあれば通知してくれるし、家入った時にalexa鍵閉めてみたいなこと言えば鍵閉まるし、便利。旅行行く時に閉め忘れの心配をしなくてよくなったのがかなり良いかも。

GIF画質悪いな2

ドア

玄関のでんき

玄関のでんきは賃貸備え付けのスイッチでしか操作できないので、switchbotボットで直接スイッチを押してもらうことにした。たまに消し忘れるので声で消せるので便利になったと思う。

alexaに認識させるときにタイプが照明かスイッチかで選べるが、ここではスイッチを選んでおく方がよい。照明を選んでしまうとシーリングライトの方と競合して、シーリングライトに「でんき」と名前をつけていた場合に素直に言うこときいてくれなくなってしまう。

玄関のでんきはどう名前つければいいんだろう?と思ってとりあえず玄関ライトにしてある。(でんきというフレーズのせいで競合が発生するため。)

直接

「安全ではないデシリアライゼーション」についてpythonのpickleから少しだけ理解する

例によってリレーブログの時間です!前の僕の記事はこれ、前回の方のブログはこちらになります。

amame.hateblo.jp

今回のテーマは「安全ではないデシリアライゼーション」です。

リアライゼーション / デシリアライゼーションとは

リアライゼーションとは、プログラムの実行状態や複雑なデータ構造などを、バイト列やjsonといった直列化された形式で表現することです。今回紹介するpickle形式もその形式の1つです。pythonではdump()とかdumps()関数を呼び出して直列化することが多いと思います。

逆に、デシリアライゼーションとは、シリアライゼーションされたデータを元の状態や形式に復元することです。

pickle

pythonでは、pickleモジュールを利用することでオブジェクトをバイナリ形式でpickleファイルとして保存することができます。利用用途としては、例えば、機械学習などでモデルを学習している途中の状態をpickleファイルで保存したり、学習済モデルのpickleファイルを読み込んで利用する、なんてことに使われています。

pickleめっちゃ便利やん!とはなるのですが、pickleファイルをデシリアライズする際にセキュリティ面の考慮がなされておらず、シェルコードの実行ができてしまいます。悪意のあるpickleファイルであればリモートコード実行とか色々できてしまいます。

pythonのdocumentのpickleの項目にも、

警告 pickle モジュールはエラーや不正に生成されたデータに対して安全ではありません。信頼できない、あるいは認証されていないソースから受け取ったデータを非pickle化してはいけません。

との記述があります。

また、昔はDjangoのセッション管理にpickleが使われていたようで、SECRET_KEYが第三者に漏れると悪意のあるpickleが作れて、悪意のあるcookieが作れてしまうとかそういう脆弱性があったようです。

やってみる

試しに、中身が以下のようになっているExample_bad.pickleを用意しました。

cos
system
(Vecho I\'m gonna pickle you! > message.txt
tR.

これを読み込んでみます。

import pickle

with (open("Example_bad.pickle", "rb")) as f:
    p = pickle.load(f)

これを実行すると、アヤシイExample_bad.pickleを読み込んだだけで、カレントディレクトリに「I'm gonna pickle you!」の記述があるmessage.txtが作成(もしくは、存在していれば置換が)されてしまいます。「お前を漬物にしてやる!」、なんて怖いメッセージでしょうか。

この例はかなり簡単なものでしたが、システムに損害を与えてしまうようなコードが実行できてしまうことを想像するのは難しくないと思います。

まとめ

安全ではないデシリアライゼーションに気をつけよう!

次のブログはこちらです

qwerty11.hatenablog.com

KRACKs

例によってリレーブログの時間です!前の僕の記事はこれ、前回の方のブログはこちらになります。

potaxyz.hatenablog.jp

amame.hateblo.jp

今回のテーマは「KRACKs」です。

KRACKsとは

KRACKsとは、Key Reinstallation AttaCKs(鍵再インストール攻撃)の略称です。2017年10月に公表されました。

内容としては、スマホなどの無線LANクライアントがWPA2でアクセスポイントと接続する際の「4ウェイハンドシェイク」という処理の仕様における脆弱性です。

「4ウェイハンドシェイク」では、クライアントがアクセスポイントとの間で暗号化通信を行うために認証や暗号鍵に関するメッセージをやりとりします。名前の通り、4つのメッセージをやりとりするものです(話の都合上1つ目、2つ目のメッセージについては省略します。)3つ目のメッセージがアクセスポイントからクライアント側に送られるもので、このメッセージによってクライアントに鍵がインストールされ、4つ目のメッセージが3つ目のメッセージの確認応答となっています。

4つ目のメッセージを送った後、クライアントは暗号化通信を開始します。

ここで、最後の4つ目のメッセージを中間者攻撃によって意図的に止めると、アクセスポイントは3つ目のメッセージがクライアントに届かなかったと判断して再送します。

クライアントは、3つ目のメッセージを受け取るたびに鍵を再インストールして暗号化通信のための処理をやり直すので、暗号文を送るのに使われるナンス(Number used ONCE: nonce、本来は一度しか使われない数)に同じものが使われてしまいます。

この3つ目のメッセージを意図的に再送させ続けることで、クライアントからアクセスポイント側へは本来は時間とともに変わるはずであったのに同じナンス、同じ秘密鍵で暗号文が送られることになるので、暗号化されたフレームを解析すれば暗号化パターンがわかり、通信データを盗聴できてしまいます。

対策

この脆弱性が発覚してから、セキュリティパッチが配布されるなどして対策が進んでいます。

また、webサイトを見るときはHTTPS(このSはセキュリティのSで、暗号化通信がされる)で接続していれば、WPA2での暗号化が破られても、HTTPSの暗号化はされているので、安全性が高まります。(WPA2とHTTPSで二重の暗号化)

また、WPA2の脆弱性に対処したWPA3という規格も2018年に発表されました。

WPA3は、4ウェイハンドシェイクの前にSAEとよばれる楕円曲線を用いたハンドシェイクの仕組みが導入されたもので、仮にパスワードが漏洩しても、そのときの鍵共有の結果はわからないものになっており、これによってKRACKsを無効化できるようになりました。

とはいえ、WPA3にも脆弱性が発見され、それに対策して...というのは続いています。

参考文献

次回はこちらです。

qwerty11.hatenablog.com

計算機代数

3回生後期に志望にあぶれてやらされることになってやった話をどうせ他で使わないのでまとめておこうと思う.ちょっと雑かもしれないけれど.

以下では,体 $k$ の元を係数にもつ $x_1,\ldots,x_n$ の多項式の集合を $k[x_1,\ldots,x_n]$ とかく.

多変数多項式の割り算

まずは1変数の場合について考えてみると,以下のように割り算ができる.

$k[x]$ における割り算 2つの1変数多項式 $f,g\in k[x]$ があったとき, $f$ を $g$ で割ることができる: $$ \begin{align} f=qg+r \end{align} $$ この関係をみたす $\deg r<\deg g$ をみたす商 $q$ と余り $r$ が一意的に存在する.

例えば, $f=2x^2+3x-4$ , $g=x+1$ のときは $q=2x+1$ , $r=-5$ となる.

では,1変数ではなく $n$ 変数多項式の場合はどうなるのか?ということなのだが,変数に対して順序を定めれば割り算を定めることができる(ただし, $n=1$ の場合でも整合性のある順序であるようなものが採用されるべき).

単項式順序 $k[x_1,\ldots,x_n]$ 上の単項式順序とは, $k[x_1,\ldots.x_n]$ の単項式 $x^\alpha$ ( $\alpha\in\mathbb{Z}_{\geq 0}^n$ )の集合上の関係 $>$ で次の3つを満たすものである:
  • $>$ は全順序関係である.
  • $>$ は $k[x_1,\ldots,x_n]$ は乗法と両立する.すなわち $x^\alpha>x^\beta$ のとき,任意の単項式 $x^\gamma$ について $x^\alpha x^\gamma=x^{\alpha+\gamma}>x^{\beta+\gamma}=x^\beta x^\gamma$ が成り立つ.
  • $>$ は整列順序である.つまり,空でない任意の単項式の集合は $>$ に関する最小元をもつ.

一般化して書いているのでわかりにくいかもしれないが,1行目で $x^\alpha$ と書いているものは,上で $n=3$ , $\alpha=(2,1,3)$ とすれば, $x^\alpha=x_1^2 x_2^1 x_3^3$ といったものである.

なお,上の定義には $x_1,\ldots,x_n$ の順序についての言及がないことにも注意.

この単項式順序と呼ばれる順序 $>$ は,これまで慣れ親しんできた$k[x]$の単項式元で考えてみれば $1<x<x^2<x^3<\cdots$ のようになっており,これまで1変数多項式の場合に(高校などで自然に)考えていた順序も単項式順序の性質をもつことがわかる.

単項式順序の性質をもつ順序は複数ある.具体例の1つとして辞書式順序を挙げておく.

定義(辞書式順序 $>_{\mathrm{lex}}$ ) $x^\alpha,x^\beta\in k[x_1,\ldots,x_n]$ について,差 $\alpha-\beta\in\mathbb{Z}^n$ の最も左にある $0$ でない成分が正であるとき, $x^\alpha>_{\mathrm{lex}}x^\beta$ であると定義する.

多変数多項式の割り算を行うのに導入しておくと便利な記号として主項というものがあるのでここで導入する.なお,主係数,主単項式という概念もあるのであわせて紹介することにする.

定義(主項,主係数,主単項式) $k[x_1,\ldots,k_n]$ 上の任意の単項式順序 $>$ を固定し, $f=\sum_\alpha x_\alpha x^\alpha$ の項を考える.いま, $x^\alpha$ が $f$ に現れる順序 $>$ に関する最大の単項式であるとする.このとき $f$ の $>$ に関する主項とは,積 $c_\alpha x^\alpha$ のことであり,主係数とは $c_\alpha$ ,主単項式とは $x^\alpha$ のことである.記号としては以下を用いる:
  • 主項 $\textrm{LT}(f)=c_\alpha x^\alpha$
  • 主係数 $\textrm{LC}(f)=c_\alpha $
  • 主単項式 $\textrm{LM}(f)=x^\alpha$

単項式順序と主項の記号を導入したので,多変数多項式の割り算のアルゴリズムを紹介することができる.

$k[x_1,\ldots,x_n]$ における多項式の割り算 $k[x_1,\ldots,x_n]$ の任意の単項式順序を固定し, $F=(f_1,\ldots,f_s)$を$k[x_1,\ldots,x_n]$ の順序づけられた$s$個の多項式の組とする.このとき,任意の多項式 $f\in k[x_1,\ldots,x_n]$ は次のような表示をもつ: $$ \begin{align} f=a_1f_1+\cdots+a_sf_s+r \end{align} $$ ただし各文字は以下をみたす:
  • $a_i,r\in k[x_1,\ldots,x_n]$ ( $i=1,\ldots,s$ )
  • $a_if_i=0$ か $\mathrm{LT}_{>}(f)\geq\mathrm{LT}_{>}(a_if_i)$ ( $i=1,\ldots,s$ )
  • $r$は$0$ か $\mathrm{LT}_{>}(f_1),\ldots,\mathrm{LT}_{>}(f_s)$ のいずれでも割り切れないような単項式の線型結合
この $r$ を $f$ の $F$ による余りと呼び $$ \begin{align} r=\overline{f}^{F} \end{align} $$ と表す.

例として, $f=x^2y^6$ , $F=(x^2y^2-x^4,xy^3-y^4)$ を考えてみる.今回は単項式順序として $>_{\mathrm{lex}}$ を採用する.

  1. $x$ と $y$ の順序を $x>y$ として割り算を実行してみる.
    • $\mathrm{LT}_{>_\mathrm{lex}} (x^2y^2-x^4) =-x^4$
    • $\mathrm{LT}_{>_\mathrm{lex}} (xy^3-y^4)=xy^3$
    • $\mathrm{LT}_{>_\mathrm{lex}} (x^2y^2-x^4) >_\mathrm{lex} \mathrm{LT}_{>_\mathrm{lex}} (f)$ なので, $f$ を $x^2y^2-x^4$ で割ることはできない.
    • 一方, $\mathrm{LT}_{>_\mathrm{lex}}(f) >_\mathrm{lex} \mathrm{LT}_{>_\mathrm{lex}}(xy^3-y^4)$ なので, $f$ を $xy^3-y^4$ で割ることができる.
    • よって $$ \begin{align} f=0\cdot(x^2y^2-x^4)+(xy^3+y^4)(xy^3-y^4)+y^8 \end{align} $$ となる.
  2. $x$ と $y$ の順序を $x < y$ として割り算を実行してみる.
    • $\mathrm{LT}_{>_\mathrm{lex}} (x^2y^2-x^4)=-x^2y^2$
    • $\mathrm{LT}_{>_\mathrm{lex}} (xy^3-y^4)=y^4$
    • $\mathrm{LT}_{>_\mathrm{lex}} (f) >_\mathrm{lex} \mathrm{LT}_{>_\mathrm{lex}} (x^2y^2-x^4)$ なので, $f$ を $x^2y^2-x^4$ で割ることができる.
    • $\mathrm{LT}_{>_\mathrm{lex}} (f) >_\mathrm{lex} \mathrm{LT}_{>_\mathrm{lex}} (xy^3-y^4)$ なので, $f$ を $xy^3-y^4$ で割ることができる.
    • よって,どっちから割っても割り算が成立するので,割る順番を考慮することになる.
      • 先に $x^2y^2-x^4$ で割ると $$ \begin{align} f=(y^4+x^2y^2+x^4)(x^2y^2-x^4)+0\cdot(xy^3-y^4)+x^8 \end{align} $$
      • 先に $xy^3-y^4$ で割ると $$ \begin{align} f=(xy^3+y^4)(xy^3-y^4)-x^4(xy^3-y^4)+x^7y \end{align} $$
      となって,2通りの表示が得られる.

グレブナー基底を利用して連立方程式を解く

記号の定義

グレブナー基底を利用して連立方程式を解く方法を説明するのに必要な定義だけ並べる.

定義(多項式で生成される空間) 多項式$f\in k[x_1,\ldots,x_n]$に対して,$\langle f_1,\ldots,f_s\rangle$を
$$ \langle f_1,\ldots,f_s\rangle=\{p_1f_1+\cdots+p_sf_s:p_i\in k[x_1,\ldots,x_n],i=1,\ldots,s\} $$
とする.
定義(イデアル 空でない部分集合 $I\subset k[x_1,\ldots,x_n]$ がイデアルとは,以下が成り立つときにいう:
  • $f,g\in I\,\Rightarrow\, f+g\in I$
  • $f\in I\,\Rightarrow\, \forall p\in k[x_1,\ldots,x_n],pf\in I$
定義(消去イデアル $I\subset k[x_1,\ldots,x_n]$ をイデアルとするとき,第 $l$ 消去イデアル(または $l$ 次の消去イデアル)とは以下で定まる$I_l$のこと:
$$ I_l=I\cap k[x_{l+1},\ldots,x_n] $$

$I=\langle f_1,\ldots,f_s\rangle$ として $I_l=I\cap k[x_{l+1},\ldots,x_n]$ は連立方程式 $f_1=\cdots=f_s=0$ から変数 $x_1,\ldots,x_l$ を消去して得られる多項式全体である.

定義(アフィン多様体 $k$ を体, $f_1,\ldots,f_s\in k[x_1,\ldots,x_n]$ とする.アフィン多様体とは,連立方程式
$$ \begin{align} f_1(x_1,\ldots,x_n)&=0 \\ f_2(x_1,\ldots,x_n)&=0 \\ &\vdots \\ f_s(x_1,\ldots,x_n)&=0 \\ \end{align} $$
の解$(a_1,\ldots,a_n)\in k^n$全体の集合のことで,$\mathbf{V}(f_1,\ldots,f_s)$と表す.すなわち
$$ \mathbf{V}(f_1,\ldots,f_s)=\{(a_1,\ldots,a_n)\in k^n : f_i(a_1,\ldots,a_n)=0,i=1,\ldots,s\} $$
である.

なお,$I=\langle f_1,\ldots,f_s\rangle$のようになっている時,$f_1=\ldots=f_s=0$の解全体の集合を$\mathbf{V}(I)$のように略記する.

定義(グレブナー基底 $k[x_1,\ldots,x_n]$ 上の単項式順序 $>$ を固定, $I\subset k[x_1,\ldots,x_n]$ をイデアルとする.このとき, $I$ の $>$ に関するグレブナー基底とは,多項式の有限集合 $G=\{g_1,\ldots,g_t\}\subset I$ であって, $0$ でない任意の $f\in I$ について, $\mathrm{LT}(f)$ がある $\mathrm{LT}(g_i)$ で割り切れるようなものである.

グレブナー基底の構成法が気になるところだが,最も初歩的なものとしてはブッフベルガーのアルゴリズムと呼ばれているものがある.wikipedia等を参照してほしい.見て貰えばわかるが,ものすごく遅そうなアルゴリズムである.実際遅いらしい.これの改良版として,最近ではF4とかF5とかいうアルゴリズムが知られている.

グレブナー基底を利用して連立方程式を解く

グレブナー基底を利用した連立方程式の解き方 連立方程式
$$ \begin{align} f_1(x_1,\ldots,x_n)&=0 \\ f_2(x_1,\ldots,x_n)&=0 \\ &\vdots \\ f_s(x_1,\ldots,x_n)&=0 \end{align} $$
を解くことを考える.グレブナー基底を用いると以下のような手順で解くことができる.
  1. $I=\langle f_1,\ldots,f_s\rangle$のグレブナー基底$G=\{g_1,\ldots,g_t\}$を求める.
  2. $1\leq l\leq n$について第$l$消去イデアル$I_l$(のグレブナー基底$G_l$)を求める.
  3. $I_n$のグレブナー基底$G_n=\{g\}$について$g=0$を解き$\mathbf{V}(I_n)$を求める.
  4. $(a_{l +1},\cdots,a_n) \in \mathbf{V}(I_l)$とし,$I_{l -1}$ のグレブナー基底 $G_{l -1}$ から $G_l$ を取り除いた多項式たち $G_{l -1}\backslash G_l=\{g_{l -1,1},\ldots,g_{l -1,u}\}$ について$g_{l -1,1}(x_l,a_{l +1},\cdots,a_n)=\cdots=g_{l -1,u}(x_l,a_{ l +1},\cdots,a_n)=0$ とおいた式を(すべての $\mathbf{V}(I_l)$ の元について)解いて $\mathbf{V}(I_{l -1})$ を求める.これを繰り返す.
4.を$I_0=I$まで行えば,$\mathbf{V}(I)$,すなわち求めたかった解が求まっている.

手続き的に書いているのでわかりにくいかもしれないが,グレブナー基底を求め,変数の数が最も少ない$g_i\in G$を選んで解を求め,前段階で求めた解を順次代入していけば解が求められるということである.

例を挙げる.以下の連立方程式

$$ \begin{align} x^2+y^2+z^2&=4 \\ x^2+2y^2&=5 \\ xz&=1 \end{align} $$

グレブナー基底を用いて解く.

  1. グレブナー基底を計算すると,
    $$ G=\{2z^3-3z+x,-1+y^2-z^2,1+2z^4-3z^2\} $$
    となる.グレブナー基底を求めるには,例えばwolfram alpha
    GroebnerBasis[{x2 + y2 + z2 − 4, x2 + 2y2 − 5, xz − 1}, {x, y, z}]
    と打ち込んでやれば求めてくれる.
    GroebnerBasis[{x2 + y2 + z2 − 4, x2 + 2y2 − 5, xz − 1}, {x, y, z}] - Wolfram|Alpha
  2. $I_1=I\cap k[y,z]=\langle -1+y^2-z^2,1+2z^4-3z^2 \rangle$ , $I_2=I\cap k[z]=\langle 1+2z^4-3z^2 \rangle$ となる.($I=\langle G\rangle$であることを利用している.)
  3. $1+2z^4-3z^2=0$ をとく. $1+2z^4-3z^2=(z-1)(z+1)(2z^2-1)=0$ から $z=\pm 1,\pm 1/\sqrt{2}$ と求められる.
  4. $-1+y^2-z^2=0$に3.で求められた$z=\pm 1,\pm 1/\sqrt{2}$を代入して計算する.
    • $z=\pm 1$ の場合: $y^2-2=0$ をといて $y=\pm\sqrt{2}$ .
    • $z=\pm 1/\sqrt{2}$ の場合: $y^2-3/2=0$ をといて $y=\pm \sqrt{6}/2$ .
    次に$2z^3-3z+x=0$へ上で求められた$z=\pm 1,\pm 1/\sqrt{2}$を代入する.
    • $z=1$ の場合: $-1+x=0$ をといて $x=1$ .
    • $z=-1$の場合:$1+x=0$ をといて $x=-1$ .
    • $z=1/\sqrt{2}$ の場合: $-\sqrt{2}+x=0$ をといて $x=\sqrt{2}$ .
    • $z=- 1/\sqrt{2}$ の場合: $\sqrt{2}+x=0$ をといて $x=-\sqrt{2}$ .

以上より,解は $(x,y,z)=(1,\pm\sqrt{2},1),(-1,\pm\sqrt{2},-1),(\sqrt{2},\pm\sqrt{6}/2,1/\sqrt{2}),(-\sqrt{2},\pm\sqrt{6}/2,-1/\sqrt{2})$ となる.

ちなみに,wolfram alphaにGroebnerBasis以下を打ち込んでやると,それらの根まで求めてくれる.その値はこれに一致している.

これで求められる理由

イデアル $I$ とそのグレブナー基底 $G$ って関係なくない?って思われるかもしれないが,以下の関係があることが示せる.

イデアル $I$ とそのグレブナー基底 $G$ の関係 イデアル$I$のグレブナー基底$G=\{g_1,\ldots,g_t\}$とするとき,$I=\langle g_1,\ldots,g_t\rangle$である.

さらに,以下の関係もある.

多項式が張る空間と連立多項式の根の関係 $k[x_1,\ldots,x_n]$ において $\langle f_1,\ldots,f_s\rangle=\langle g_1,\ldots,g_t\rangle$ ならば $\mathbf{V}(f_1,\ldots,f_s)=\mathbf{V}(g_1,\ldots,g_t)$ である.

これによって,$I=\langle f_1,\ldots,f_s\rangle$の代わりにそのグレブナー基底$G={ g_1,\ldots,g_t}$をを使い,$g_1=\cdots=g_t=0$を考えても,元の$f_1=\cdots=f_s=0$の解と同じものが得られることがわかる.

下に紹介する消去定理と拡張定理が,グレブナー基底を使って順次解を求めていくという方法がうまくいくことを保証してくれているものになっている.

消去定理 $I\subset k[x_1,\ldots,x_n]$ をイデアルとし, $G$ を $I$ のlex順序 $x_1>x_2>\cdots>x_n$ に関するグレブナー基底とすれば,
$$ G_l=G\cap k[x_{l+1},\ldots,x_n] $$
は第 $l$ 消去イデアル $I_l$ のグレブナー基底である.
拡張定理 代数的閉体 $k$ について,部分解 $(a_{l+1},\ldots,a_n)\in\mathbf{V}(I_l)$ は, $I_{l -1}$ のlex順序 $ x_1 > x_2 > \cdots > x_n$ に関するグレブナー基底の元 $f$ で, $\mathrm{LC}_{x_l}(f)(a_{l +1},\ldots,a_n)\neq 0$ をみたすものが存在するならば, $(a_{l},a_{l+1},\ldots,a_n)\in\mathbf{V}(I_{l -1})$ に拡張できる.

消去定理によって $I_l=\langle G_l\rangle$ と書けることわかるので, $G_l=\{ g_{ l,1 },\ldots,g_{ l,u } \}$ としたとき$g_{ l,1 }=\cdots=g_{ l,u }=0$ を解くことで $V(I_l)$ の元を求められる.

その後,拡張定理を用いて$V(I_l)$を$V(I_{l -1})$に拡張する.拡張定理の仮定を満たさないものは解にならない可能性がある.この操作を進める時に,拡張定理から主係数が$0$でない場合は解が存在していることが保証される.これを繰り返して$V(I)$を求める.

このように順番に解いていけるのはグレブナー基底の性質のおかげである.イデアル $I$ が $x_n$ だけからなる多項式を元として持てば,辞書式順序 $x_1>x_2>\cdots>x_n$ によるグレブナー基底は $x_n$ だけからなる多項式を含む.すなわち,グレブナー基底の定義より,イデアル $I$ のグレブナー基底 $G={ g_1,\ldots,g_t } $ について,任意に $f\in I$ を取ってくると $\mathrm{LT}(f)$ はある $\mathrm{LT}(g_i)$ ( $g_i\in G$ )で割ることができる.したがって $f\in I$ が $\mathrm{LT}(f)= x_n^k $ であれば, $\mathrm{LT}(g_i)= x_n^l $ ( $ l \leq m $ )となっているはずである.

終結式(判別式の拡張)

多項式同士が共通因子を持つか判定する方法.

1変数多項式終結

2つの$k[x]$上の1変数多項式を考える:

$$ \begin{align} f&=a_0x^l+\cdots+a_l \quad (a_0\neq 0,l>0) \\ g&=b_0 x^m+\cdots+b_m \quad (b_0\neq 0,m>0) \end{align} $$

この $f,g$ が共通因子を持つか,つまり連立方程式$f=g=0$が解を持つか判定してくれる表式が次の終結式と呼ばれるものである.

定義(終結式) $f,g$ の終結式 $\mathrm{Res}(f,g)$ とは,$(l+m)\times (l+m)$ 行列式
$$ \begin{align} \mathrm{Res}(f,g)=\det \begin{pmatrix} a_0 & & & & b_0 & & & \\ a_1 & a_0 & & & b_1 & b_0 & & \\ a_2 & a_1 & \ddots & & b_2 & b_1 & \ddots & \\ \vdots & a_2 & \ddots & a_0 & \vdots & b_2 & \ddots & b_0 \\ a_l & \vdots & \ddots & a_1 & b_m & \vdots & \ddots & b_1 \\ & a_l & & a_2 & & b_m & & b_2 \\ & & \ddots & \vdots & & & \ddots & \vdots \\ & & & a_l & & & & b_m \end{pmatrix} \end{align} $$
のこと.$a$ 側は $ m $ 列,$b$ 側は $l$ 列.空白は $0$ .$x$ に依存していることを強調するときは $\mathrm{Res}(f,g,x)$ とかく場合もある.

なお,これはシルベスターの行列式といわれるものと同じ形をしている.

終結式には以下の3つの性質がある(証明はせず紹介にとどめる).

終結式の3つの性質
  • 多項式性: $\mathrm{Res}(f,g)$ は $f,g$ の係数についての整数係数の多項式である.
  • 共通因子性: $\mathrm{Res}(f,g)=0\,\Leftrightarrow\,$ $f,g$ が $k[x]$ において共通因子をもつこと.
  • 消去性: $Af+Bg=\mathrm{Res}(f,g)$ を満たす多項式$A,B\in k[x]$が存在する. $A,B$ の係数は $f,g$ の係数についての整数係数多項式
  • 多項式性が意味しているのは,ある多項式 $\mathrm{Res}_{l,m}\in\mathbb{Z}[u_0,\ldots,u_l,v_0,\ldots,v_m]$であって, $\mathrm{Res}(f,g)=\mathrm{Res}_{l,m}(a_0,\ldots,a_l,b_0,\ldots,b_m)$となるものがあるということ.
  • 共通因子性については,共通因子をもつということは, $f=g=0$ が共通の解を持つということである.
  • 消去性は,消去理論(消去定理)との対応がある.

上では定義としてシルベスターの行列式を利用したが,他の表式もある.

終結式のかきかえ $f,g\in k[x]$ の根を $ \alpha_1 , \ldots , \alpha_l , \beta_1 , \ldots , \beta_m $ とする(これらの根は$k$より大きな体にあるかもしれない).このとき終結式は
$$ \begin{align} \mathrm{Res}(f,g)&=a_0^mb_0^l\prod_{i=1}^l\prod_{j=1}^m(\alpha_i-\beta_j)\\ &=a_0^m\prod_{i=1}^l g(\alpha_i)\\ &=(-1)^{lm}b_0^l\prod_{j=1}^m f(\beta_j) \end{align} $$
と表示できる.

このことから, $ \mathrm{Res}(f_1f_2,g)=\mathrm{Res}(f_1,g)\mathrm{Res}(f_2,g) $ であることがわかる.

例を挙げる.

$ f =x^2-4x+3 $,$ g =2x-4 $とする.このとき

$$ \begin{align} \mathrm{Res}(f,g)=\det \begin{pmatrix} 1 & 2 & 0 \\ -4 & -4 & 2 \\ 3 & 0 & -4 \end{pmatrix} \end{align}=-4 $$

となって,共通根をもたないと判定できる.実際,$f=0$をとくと$x=1,3$,$g=0$をとくと$x=2$であり,共通根をもたない.

$f=(x-1)(x-3)$であることに注意すれば,$f_1=x-1,f_2=x-3$とみれば

$$ \begin{align} \mathrm{Res}(f_1,g)\mathrm{Res}(f_2,g)=\det \begin{pmatrix} 2 & 1 \\ -4 & -1 \end{pmatrix} \det\begin{pmatrix} 2 & 1 \\ -4 & -3 \end{pmatrix} \end{align}=2\cdot (-2)=-4 $$

となるので,$ \mathrm{Res}(f,g)=\mathrm{Res}(f_1,g)\mathrm{Res}(f_2,g) $が成立していることが確認できる.

なお,今回$g=f'$となっているが,一般に判別式 $D$ との関係として $\mathrm{Res}(f,f')=(-1)^{\deg f (\deg f -1)/2}\mathrm{LC}(f)D$ の関係があることが知られている.確かめてみると,$\deg f=2$,$\mathrm{LC}(f)=1$,$D=(-4)^2-4\cdot 3 = 4 $であることから,成立が確認できる.

2変数多項式終結

2つの$k[x,y]$上の2変数多項式を考える:

$$ \begin{align} F&=a_0x^l+ a_1 x^{ l - 1} y +\cdots+a_l y^l \quad (a_0\neq 0,l>0) \\ G&=b_0 x^m+ b_1 x^{ m - 1 } y +\cdots+b_m y^m \quad (b_0\neq 0,m>0) \end{align} $$

これに対する終結式$\mathrm{Res}(F,G)$は次で定義される.1変数の場合のものと同じである.

定義(終結式) $F,G$ の終結式 $\mathrm{Res}(F,G)$ とは,以下で定義される$(l+m)\times (l+m)$ 行列式である:
$$ \begin{align} \mathrm{Res}(F,G)=\det \begin{pmatrix} a_0 & & & & b_0 & & & \\ a_1 & a_0 & & & b_1 & b_0 & & \\ a_2 & a_1 & \ddots & & b_2 & b_1 & \ddots & \\ \vdots & a_2 & \ddots & a_0 & \vdots & b_2 & \ddots & b_0 \\ a_l & \vdots & \ddots & a_1 & b_m & \vdots & \ddots & b_1 \\ & a_l & & a_2 & & b_m & & b_2 \\ & & \ddots & \vdots & & & \ddots & \vdots \\ & & & a_l & & & & b_m \end{pmatrix} \end{align} $$

1変数の場合の性質が2変数の場合には以下のように言い換えられる(整多項式性と共通因子性).

なお, $F,G$ の形から, $y=1$ とすれば $f,g$ と一致するので1変数の場合を特殊な場合として含むことがわかる.

終結式の性質
  • $F,G$に対して,ある $\mathrm{Res}_{l,m}\in\mathbb{Z}[u_0,\ldots,u_l,v_0,\ldots,v_m]$ であって, $\mathrm{Res}(F,G)=\mathrm{Res}_{l,m}(a_0,\ldots,a_l,b_0,\ldots,b_m)$ となる多項式が存在する.
  • $\mathbb{C}$ 上で $\mathrm{Res}(F,G)=0\,\Leftrightarrow\,$$F=G=0$ が $\mathbb{C}^2/(0,0)$ に解をもつ.
    (この解を非自明解:nontrivial solutionという)

また,シルベスターの行列式の対角成分に注目することで,次のこともすぐにわかる.

終結式の性質
  • $\mathrm{Res}(x^l,y^m)=1$

多重多項式終結

このセクションの内容は日本語の文献がない.さらに,英語の文献もほとんどない気がする.し,ガチの証明をしようとすると微分幾何が必要になったりする.

多重多項式終結式とは,上で2つ紹介してきたものの一般化.

「変数 $x_0,\ldots,x_n$の$n+1$ 個の斉次多項式 $F_0,\ldots,F_n$ の終結式」について考える.

仮定として,各$F_i$は正の全次数をもち,$\mathbb{C}$上で考えることにする.

$n+1$ 個の斉次多項式 $F_0,\ldots,F_n \in \mathbb{C} [x_0,\ldots,x_n] $があったとき,方程式系$F_0=\cdots=F_n=0$が非自明解を持つためには,$F_0,\ldots,F_n$の係数はどのような条件を満たさなければならないだろうか.

以下,記号として$P(F_1,\ldots,F_n)$のようなものを使うことがある.これは,$P \in \mathbb{C}[u_{i,\alpha}] $があったとき,$P$の各変数$u_{i,\alpha}$を対応する$F_i$の係数 $c_{i,\alpha}$ に取り替えることで得られる数(このような$P$を$F_i$の係数の多項式という)である.以下では $P$ に $\mathrm{Res}$ があてはまって使われることが多い.

定理 正の次数$d_0,\ldots,d_n$を固定する.このとき,次の性質をもつ唯一の多項式$\mathrm{Res}\in\mathbb{Z}[u_{i,\alpha}]$が存在する:
  1. $F_0,\ldots,F_n\in\mathbb{C}[x_0,\ldots,x_n]$が次数$d_0,\ldots,d_n$の斉次多項式ならば,$F_0(x_0,\ldots,x_n)=\cdots=F_n(x_0,\ldots,x_n)=0$が$\mathbb{C}$上の非自明解を持つための必要十分条件は$\mathrm{Res}(F_0,\ldots,F_n)=0$
  2. $\mathrm{Res}(x_0^{d_0},\ldots,x_n^{d_n})=1$
  3. $\mathrm{Res}$は($\mathbb{C}[u_{i,d}]$の多項式としても)既約.
定義(終結式) 上の定理をみたす$\mathrm{Res}(F_0,\ldots,F_n)$を$F_0,\ldots,F_n$の終結という.(次数を明示して$\mathrm{Res}$を$\mathrm{Res}_{d_0,\ldots,d_n}$と書くこともある.)

このように定義された終結式は,2変数多項式終結式とも矛盾ないことが確認できる(既約かどうかは確認できないが...きっと既約なんだと思う).

例(n+1変数,n+1個の線形多項式

終結式の例として,$n+1$ 個の変数 $x_0,\ldots,x_n$,$n+1$ 個の線形多項式 $F_0,\ldots,F_n$ の終結式,すなわち各々が $F_i=\sum_{j=0}^n c_{ij}x_j$ のように書かれているものを考えてみる( $c_{ij}$ が定数で $x_j$ が変数).

このとき,

$$ \mathrm{Res}_{1,\ldots,1}(F_0,\ldots,F_n)=\det(c_{ij}) $$

となる.定理の内容を確認してみる.

  1. 方程式系
    $$ \begin{align} F_0&=c_{00}x_0+\cdots+c_{0n}x_n=0 \\ & \vdots \\ F_n&=c_{n0}x_0+\cdots+c_{nn}x_n=0 \end{align} $$
    が非自明解をもつことの必要十分条件は $\det(c_{ij})=0$.
  2. $F_i=x_i$ なので,$c_{ij}=\delta_{ij}$.つまり$\det(c_{ij})=\det(\delta_{ij})=\det I=1$.

例(3変数,3元2次式)

他の例として,

$$ \begin{align} F_0&=c_{01}x^2+c_{02}y^2+c_{03}z^2+c_{04}xy+c_{05}xz+c_{06}yz \\ F_1&=c_{11}x^2+c_{12}y^2+c_{13}z^2+c_{14}xy+c_{15}xz+c_{16}yz \\ F_2&=c_{21}x^2+c_{22}y^2+c_{23}z^2+c_{24}xy+c_{25}xz+c_{26}yz \end{align} $$

終結式を考えてみると,これは

$$ \mathrm{Res}_{2,2,2}(F_0,F_1,F_2)=-\frac{1}{512}\det \begin{pmatrix} c_{01} & c_{02} & c_{03} & c_{04} & c_{05} & c_{06} \\ c_{11} & c_{12} & c_{13} & c_{14} & c_{15} & c_{16} \\ c_{21} & c_{22} & c_{23} & c_{24} & c_{25} & c_{26} \\ b_{01} & b_{02} & b_{03} & b_{04} & b_{05} & b_{06} \\ b_{11} & b_{12} & b_{13} & b_{14} & b_{15} & b_{16} \\ b_{21} & b_{22} & b_{23} & b_{24} & b_{25} & b_{26} \end{pmatrix} $$

の形で表される.

なお,一般の終結式の構成法はこれに似ているらしい(ちゃんと見ていないが).

この$6\times 6$で表された行列式を展開すると21894個の項を持ち,とても書き下すことは難しい...

そこで,括弧式を使って簡略化をしようという考えがあったりする(次のセクション).

終結式の性質

終結式の次数

定理(終結式の次数) 固定した$j$($0\leq j\leq n$)について,$\mathrm{Res}$は$u_{j,\alpha}$($|\alpha|=d_j$)を変数とする次数$d_0\cdots d_{j-1}d_{j+1}\cdots d_n$の斉次多項式である.すなわち,
$$ \mathrm{Res}(F_0,\ldots,\lambda F_j,\ldots,F_n)=\lambda^{d_0\cdots d_{j-1}d_{j+1}\cdots d_n}\mathrm{Res}(F_0,\ldots,F_n) $$
である.さらに,$\mathrm{Res}$の全次数は$\sum_{j=0}^n d_0\cdots d_{j-1}d_{j+1}\cdots d_n$である.

ポアソンの公式

定理(ポアソンの公式) 終結式 $\mathrm{Res}(\overline{F}_0,\ldots,\overline{F}_{n-1})$ が $\mathrm{Res}(\overline{F}_0,\ldots,\overline{F}_{n-1})\neq 0$ を満たすならば,商環 $A=\mathbb{C}[x_0,\ldots,x_{n-1}]/\langle f_0,\ldots,f_{n-1}\rangle$は$\mathbb{C}$ 上のベクトル空間として $d_0\cdots d_{n-1}$ 次元であって,さらに
$$ \mathrm{Res} (F_0,\ldots,F_n)=\mathrm{Res} (\overline{F}_0,\ldots,\overline{F}_{n-1})^{d_n}\det (m_{f_n}:A\to A) $$
である.ただし, $m_{f_n}:A\to A$ は $f_n$ による乗法で定義される線形写像

証明には微分幾何の知識が必要なので省略.

終結式の対称性と積

定理(終結式の対称性と積)
  1. 多項式 $F_j=F_j'F_j''$ を,次数がそれぞれ $d_j',d_j''$ の斉次多項式の積とするとき,
    $$ \mathrm{Res}(F_0,\ldots,F_j,\ldots,F_n)=\mathrm{Res} (F_0,\ldots,F_j',\ldots,F_n)\cdot \mathrm{Res} (F_0,\ldots,F_j'',\ldots,F_n) $$
    である.ただし,右辺の終結式は $d_0,\ldots,d_j',\ldots,d_n$ と $d_0,\ldots,d_j'',\ldots,d_n$ の斉次多項式についての終結式.
  2. $i < j$ のとき,
    $$ \mathrm{Res}(F_0,\ldots,F_i,\ldots,F_j,\ldots,F_n)=(-1)^{d_0\cdots d_n}\mathrm{Res}(F_0,\ldots,F_j,\ldots,F_i,\ldots,F_n) $$
    である.ただし,右辺の終結式は次数が$d_0\ldots,d_j,\ldots,d_i,\ldots,d_n$である斉次多項式についての終結式.

その他

定理(多項式の線形結合,括弧での略記)
  1. $F_j$ が全次数 $d$ の斉次多項式であって, $G_i=\sum_{j=0}^n a_{ij}F_j$ (ただし, $A=(a_{ij})$ は $\mathbb{C}$ の元を成分とする可逆行列)であるとき,
    $$ \mathrm{Res}(G_0,\ldots,G_n)=(\det A)^{d^n}\mathrm{Res}(F_0,\ldots,F_n) $$
    が成り立つ.
  2. 全次数$d$の単項式全体を$x^{\alpha(1)},\ldots,x^{\alpha(N)}$とし,$n+1$個の異なる添字 $1\leq i_0 < \cdots < i_n\leq N $ について括弧$[i_0\ldots i_n]$を行列式を用いて以下のように定義する:
    $$ [i_0\ldots i_n]=\det(u_{i,\alpha(i_j)})\in\mathbb{Z}[u_{i,\alpha(j)}] $$
    このとき,$\mathrm{Res}$は括弧$[i_0\ldots i_n]$の多項式である.

再び前のセクションで考えていた3個の3元2次式

$$ \begin{align} F_0&=c_{01}x^2+c_{02}y^2+c_{03}z^2+c_{04}xy+c_{05}xz+c_{06}yz \\ F_1&=c_{11}x^2+c_{12}y^2+c_{13}z^2+c_{14}xy+c_{15}xz+c_{16}yz \\ F_2&=c_{21}x^2+c_{22}y^2+c_{23}z^2+c_{24}xy+c_{25}xz+c_{26}yz \end{align} $$

終結式を考えてみると,これは

$$ \mathrm{Res}_{2,2,2}(F_0,F_1,F_2)=-\frac{1}{512}\det \begin{pmatrix} c_{01} & c_{02} & c_{03} & c_{04} & c_{05} & c_{06} \\ c_{11} & c_{12} & c_{13} & c_{14} & c_{15} & c_{16} \\ c_{21} & c_{22} & c_{23} & c_{24} & c_{25} & c_{26} \\ b_{01} & b_{02} & b_{03} & b_{04} & b_{05} & b_{06} \\ b_{11} & b_{12} & b_{13} & b_{14} & b_{15} & b_{16} \\ b_{21} & b_{22} & b_{23} & b_{24} & b_{25} & b_{26} \end{pmatrix} $$

の形で表されるのだった.

全次数2の6個の単項式を$x^2,y^2,z^2,xy,xz,yz$と並べると括弧$[i_0i_1i_2]$は

$$ [i_0i_1i_2]=\det\begin{pmatrix} c_{0i_0} & c_{0i_1} & c_{0i_2} \\ c_{1i_0} & c_{1i_1} & c_{1i_2} \\ c_{2i_0} & c_{2i_1} & c_{2i_2} \end{pmatrix} $$

と表せる.これを用いると$\mathrm{Res}_{2,2,2}(F_0,F_1,F_2)$は

$$ \begin{align} \mathrm{Res}_{2,2,2}(F_0,F_1,F_2) = & \,[145][246][356][456] − [146][156][246][356] − [145][245][256][356] \\ & − [145][246][346][345] + [125][126][356][456] − 2[124][156][256][356] \\ & − [134][136][246][456] − 2[135][146][346][246] + [235][234][145][456] \\ & − 2[236][345][245][145] − [126]^2[156][356] − [125]2[256][356] \\ & − [134]^2[246][346] − [136]^2[146][246] − [145][245][235]^2 \\ & − [145][345][234]^2 + 2[123][124][356][456] − [123][125][346][456] \\ & − [123][134][256][456] + 2[123][135][246][456] − 2[123][145][246][356] \\ & − [124]^2[356]^2 + 2[124][125][346][356] − 2[124][134][256][356] \\ & − 3[124][135][236][456] − 4[124][135][246][356] − [125]^2[346]^2 \\ & + 2[125][135][246][346] − [134]2[256]2 + 2[134][135][246][256] \\ & − 2[135]^2[246]^2 − [123][126][136][456] + 2[123][126][146][356] \\ & − 2[124][136]2[256] − 2[125][126][136][346] + [123][125][235][456] \\ & − 2[123][125][245][356] − 2[124][235]2[156] − 2[126][125][235][345] \\ & − [123][234][134][456] + 2[123][234][346][145] − 2[236][134]^2[245] \\ & − 2[235][234][134][146] + 3[136][125][235][126] − 3[126][135][236][125] \\ & − [136][125]^2[236] − [126]^2[135][235] − 3[134][136][126][234] \\ & + 3[124][134][136][236] + [134]^2[126][236] + [124][136]^2[234] \\ & − 3[124][135][234][235] + 3[134][234][235][125] − [135][234]^2[125] \\ & − [124][235]^2[134] − [136]^2[126]^2 − [125]^2[235]^2 \\ & − [134]^2[234]^2 + 3[123][124][135][236] + [123][134][235][126] \\ & + [123][135][126][234] + [123][134][236][125] + [123][136][125][234] \\ & + [123][124][235][136] − 2[123]^2[126][136] + 2[123]^2[125][235] \\ & − 2[123]^2[134][234] − [123]^4 \end{align} $$

と書き表せる.$\mathrm{Res}_{2,2,2}$は$c_{ij}$について全次数が12,各括弧の全次数は3なので,$\mathrm{Res}_{2,2,2}$は括弧の全次数4の多項式とみなせる.上の式はかなり複雑だが,$c_{ij}$の多項式で表現した場合は21894個の項だったものが括弧を使うと68個の項で表現できているので,$c_{ij}$での表示と比較すると括弧での表示はかなり単純化されているといえる.

参考文献

[1] D. Cox, J. Little and D. O’Shea. Using Algebraic Geometry, 2nd edition, Springer-Verlag, 2005.

[2] I.R.Shafarevich. Basic Algebric Geometry 1. (Third Edition). Springer-Verlag, 2013.

[3] J.Jouanolou. Le formalisme du résultant, Advances in Math. 90 (1991), 117-263.

[4] B. Sturmfels. Algorithms in Invariant Theory, Springer-Verlag, 1993.

[5] D. Cox, J. Little and D. O’Shea. Ideals, Varieties, and Algorithms, 2nd edition, Springer-Verlag, 1996.

[6] 伊理 正夫,岩波講座応用数学1 基礎1 線形代数1, 岩波書店, 1993.

[7] 計算機代数ゼミ発表資料 - konn-san.com

POODLE攻撃

例によってリレーブログの時間です!前の僕の記事はこれ、前回の方のブログはこちらになります。

potaxyz.hatenablog.jp

amame.hateblo.jp

今回僕に与えられたテーマはPOODLE攻撃になります。かなりざっくりまとめます。(せっかくなら実装して検証したり...とかやろうと思っていたのですが全然時間が取れなかったのでまたいつか...!)

POODLE攻撃とは

POODLEとは、Padding Oracle On Downgraded Legacy Encryptionの略で、SSL3.0というインターネット上でデータを暗号化して送受信する仕組み(=プロトコル)を用いた中間者攻撃を実行するために悪用されうるセキュリティ上の欠陥です。

新しい暗号化方式の通信に対応しているサーバーであっても、サーバーが対応している古い暗号化方式の通信プロトコルに切り替え(=ダウングレード)、古い方式に有効なPadding Oracle攻撃を行うというものです。

Padding Oracle

暗号方式にも様々ありますが、その中でもブロック暗号方式では、特定のサイズ単位でデータを暗号化します。しかし、暗号化したい平文は必ずしも特定のサイズ単位になっているとは限りません。そこで、前回の僕の記事のように、特定のサイズ単位になるようにダミーデータを詰めてやる、ということをします。

例を出すと、64bit単位でデータを暗号化する方式だったとすると、平文が54bitであれば、残りの10bitはダミーデータで埋め(埋める=padding)、規格に合うようにします。

クライアントからサーバーに暗号文を送ると、暗号文を解析した結果をクライアントに返すときに、暗号文が正しく復号できたかどうかのみならず、パディングの一致不一致などをお知らせする場合があります(パディングのオラクル、オラクルは神託という意味)。

このPadding Oracleを攻撃者は利用して、例えば、正しいパディングを変えながら送信しまくって調べ、正しいパディングがわかれば暗号化途中の中間値が解析でき、と、これを繰り返せば最終的に暗号化前の平文を解析することができてしまうのです!

対策

対策としては、SSL3.0を無効にすること、と、いたってわかりやすいものになっています。現在ではSSLは使用が禁止されており、TLSというプロトコルが使われています。

実は、この脆弱性SSLだけでなくTLSの初期バージョン(1.0/1.1)にも存在することが報告されています。このため、2021年3月には、TLS1.0/1.1の使用禁止が求められています。なので、TLSTLSでもバージョン1.2以上のものを使うようにすればよいということになります。

参考文献

次の記事はこちらです。

qwerty11.hatenablog.com

KLab Server Side Camp(第2回)に参加しました

KLab(クラブ)さんの KLab Server Side Camp(第2回)に参加してきました。

このインターンに参加するまで失礼ながら知らなかったのですが、KLabさんは、スクフェスラブライブ)とか、最近だとラピライ(ラピスリライツ)とかのゲームを作ってる会社、というとイメージが湧きやすいのかなと思います。ICPCのスポンサーもやられているのは知らなかった...

人生初のインターンだったので、個人的にはとてもいい経験になったと思います。そんな参加記です。

告知

参加記に入る前に宣伝です。

<サマーインターン、エントリー受付中>

■「KLab Server Side Camp」(第3回)

https://klab-hr.snar.jp/jobboard/detail.aspx?id=Or4L6WIHlTI

日程:9/1(木)~7(水)※平日5日間

第1次応募締切:3/31(木)23:59まで

  • オリジナルの音ゲーを題材とした「サーバサイド」開発体験インターン

  • メンターは自社エンジニアのPythonコアコミッターが務めます

#KLabServerSideCamp

#サーバサイドキャンプ

リンク先で興味を持たれた方や、以下の参加記で興味を持たれた方は是非エントリーしてみてはどうでしょうか...

参加のきっかけ

twitter経由で第1回の参加記を読んだからです。この記事読んだんだと思います。

qiita.com

単純に面白そうだな〜ってなったのと、自分が趣味として使ってた技術(FastAPIもSQLこれで触ったことは一応あった)がどうやって実際のアプリケーションに使われているんだろうと興味があったというのが一番の理由でしょうか。pythonを使って、というのもあまり聞かない気もしたので(実際の開発でもpythonを使っているようです)。

あとは、こういうインターンに参加しないと、春休みコーディングしないだろうなあというのもありました。

ちなみに、僕がこのインターンの存在を知ったタイミングは第2次応募締め切りの直前くらいで、2次はお祈り確率が高くなっていたとのことなので、運が良かったようです。何事も早めにやるのが大事ですね。

スケジュールイメージ

3月の10,11,14,15,16日の5日間で開催されました。

ちなみに、12,13は土日でしっかり休んでね〜とのことでしたが、その土日は僕は東京に行っていました

なお、今回の製作物はこちらになっています(コードとして直すべきところはタイミングを見て直したいですね)。

github.com

1日目(3/10(木))

各参加者の自己紹介から始まり、環境構築、MySQLを触ってみる、SQLAlchemyを使ってpythonからSQLを実行してみる、音ゲーで遊んでみる、といったことをしていました(講義と実習)。

開発環境にはgithub codespacesというものを使っていて、僕自身はそれに初めて触れたので、こんな便利なものもあるんや〜と少し感動していました。

音ゲーはパソコン上で動くもので、6つのキーでやるものでした。弐寺beatmania IIDX)みたいな感じでしょうか。僕はipadでdeemoとかデレマスとかそういうタイプのキーを使わない音ゲーばかりやっていたのでなかなか苦戦していました。ちなみに、KLabさんのゲームはひとつもやったことがありませんでした...

さすがにSQLなど触った経験があるだけあって特に引っかかることもなくこなせたので、大部分の時間を音ゲーのプレイに費やしていました。

2日目(3/11(金))

1日目に最低限のSQLなどの知識を確認したので、FastAPIとかpydanticとかを触ってみようという感じになりました。まずはチュートリアル的な感じでuserのAPIを完成させてみて触り方を学習します。ここまでで以後実装に必要な知識は一応得られたことになります。

午後からは本キャンプの本題となるroom APIの実装に入ります。マルチプレイをするのにバックエンド側で必要な機能を実装していきます。具体的には、対戦部屋の作成、部屋の一覧表示、部屋への入室、開始待ち、ゲーム開始、結果の送信、結果の表示、途中退室、の機能の順です。マークダウンで書かれた仕様書があり、それを基づいてやっていきます。

2日目にはたしか、部屋への入室までは実装できていた気がします。部屋が満室だと入れないようにするとか、考慮することがいろいろあって、部屋への入室機能の実装には苦労しました。

3日目(3/14(月))

土日を挟みましたが、先週からの続きをやっていきます。以後は、実習のヒントとか、ポイントの解説的な講義はありましたが、基本はもくもくと実装です。

もくもくと実装したおかげか、一応目標としていた機能は全て実装できていたはずです。皆さんかなりもくもくと作業していたので、社員さんが寂しそうでした(笑)

4日目(3/15(火))

この日は他の参加者の方々と実際にマルチプレイをし合ってデバッグ作業でした。幸いなことに?僕の書いたプログラムは特に問題なく動いてくれました。

デバッグし合っていると、自分の実装で忘れていた点などが浮かび上がってきて、ちゃんと動いてくれてはいるけど問題があるなあといったところを修正できたり、機能の追加をすることができたりしました。

また、デバッグ作業をしていたら、マルチプレイではポーズ操作ができないはずなのにできてしまい、プレイ中にやめられない想定なのにプレイがやめられてしまうという、クライアントサイドのバグを思わぬところで見つけてしまったりもしました。

(これの何が問題かというと、退室した人がプレイ中のままと誤認されて、他の退室してないプレイヤーがプレイ終了しても、いつまでたってもリザルトの画面に辿り着けないということが起きてしまいます)

また、途中でエンジニアさんの座談会の時間が設けられていました。技術ってどうやって仕入れてますとか、リモートワークこんな感じですとか、色々話していただきました。

5日目(3/16(水))

この日は最終日ということで、成果発表資料の作成と簡単なコードの修正と、それから昨日見つけてしまったクライアントサイドのバグをサーバーサイド側でなんとかしてみるか〜ということで機能を追加していました(その機能の実装はできましたが、個人的にあまり納得いくコードの書き方ではありませんでした、成果発表会の時にこの点についてコメントをいただけることができたのでよかった)。

自分の成果発表会の後には、メンターさんからコメントがいただけて、全部実装できてていいですねとか、この作りだとデッドロックが起きてしまうかもしれないだとか、こういう実装はしなくて普段はこうしてるかなとか、関数の分け方がいいだとか、色々言っていただけで、学びもありました。

もちろん、他の方の成果発表からも得られるものがありました。UML図やER図書いてる方だとか、セキュリティ意識高くSHA256をかましていたりとか、データベースの正規形意識してる方だとかがいて、すげーとなっていました。

成果発表会後は懇親会ということで、昨日の座談会の続き(?)という面もありましたが、それよりはゆるい感じで、就活の話からそうでない話まで、こちらも色々と楽しい話が聞けました。深夜ラジオみたいな感じでした。

感想

技術面

メンターの方々のhelpがかなり手厚いと感じました。質問対応が早くてなおかつ親切です。自分はあまり質問することはありませんでしたが、他人の質問を見て勉強になるなあと感じたこともありました。ちなみに、メインメンターの方はpythonのコアコミッターの方ですごいと思う。

最終日に自分の書いたコードに対してコメントをいただけたのは本当にためになったと感じます。

課題は普通に難しいんだと思います。サブメンターのエンジニアさんがそうおっしゃっていました。僕は特につまずくことなく実装できてしまいましたが、それでも悩んだ部分はあります。参加者全員が最後まで実装できたわけではないです。仕様書があるとはいえ、逐一説明されているわけではなく、データベースのテーブルの設計から始めるため、なかなか自由度が高い課題になっているかなと思います。

他の参加者の方々について

みんながみんな情報系というわけではなく、例えば化学系の方もいました。また、情報系の中でも低レイヤーが専門という方や、普段はpythonじゃなくてgo書いてますとか様々でした。

サーバーサイドの経験があってバリバリやな〜って方もいれば、ない方もいました。僕は一応あるっぽいです(そういうことを意識せずに開発していました)。

志望理由もさまざまで、僕は(真剣な方にちょっと申し訳ないなと思いつつ)気になる〜って軽いノリで参加していて、似たような志望動機の方もいましたが、就活の一環で成長したいからという方もいらっしゃいました。

参加者11名中、バ美肉している参加者が2人もいらっしゃいました。

参加者の方々を見ていると、pythonが書けて(数値計算などでも可)、gitが使えれば参加のチャンスはあるのかなと思います。

雰囲気について

雰囲気はとても良く、エンジニアさんとも、他の参加者の方とも、ワイワイやることができました。本筋に関係ない雑談もできました。エンジニアを大切にしてくれる社風なんだなと感じました。会社の雰囲気を知れたというのは大きな収穫の1つだと思います。

ゲームについて

なんとこのインターンのためだけに作っていただいたようなのですが、普通にクオリティが高く驚きです。暇な時に遊ぼうと思います。ゲームのクライアントサイド自体はunityで作られているようです。

開発用(?)というだけあって、普通にプレイもできるのですが、オートプレイモードや、一瞬でリザルトに移行するモード等も用意されています。

f:id:potaxyz:20220318185250p:plain
楽曲・難易度選択画面

f:id:potaxyz:20220318185010p:plain
プレイ画面 キャラクターがかわいい

f:id:potaxyz:20220318185530p:plain
ゲーム開始画面 通常・オート・一瞬モードとシングル・マルチプレイの切替が可能

楽曲の例:

ノベルティなど

参加証をいただきました。ちなみに、twitterでもこのアイコン使ってますが、どっかからパクってきてるわけではなくて、自分で描いたものです。ホワイトボードに描いたやつを写真撮ってます。

f:id:potaxyz:20220318185917j:plain
参加証

5日間のお供にということで、段ボール1箱分のお菓子と、自己研鑽用の本などをいただきました。

f:id:potaxyz:20220318190028j:plain
お菓子や本や扇子など

また、懇親会用にということで、お酒やおつまみ類もいただきました。成城石井のいいおつまみでした。

f:id:potaxyz:20220318190108j:plain
お酒とおつまみ

最後には修了証もいただきました。

たくさんのノベルティ等本当にありがとうございます。まだたくさん残ってるのでゆっくりいただきます。

さいごに

自分自身、あまり企業のことや就職のことに興味を持てずにいたので、このような経験ができたのはとてもよかったと感じています。

KLabさん、5日間ありがとうございました。とても楽しかったです。