Python

最近, cloudnetという学会に論文を投稿したのだが, そこでデータを集める際に制作したシミュレータがいい感じにできたのでそれについて書いてみる。 https://github.com/adshidtadka/server-allocation Parameterクラス まず良かった点としてParameter クラスを作ったことである。 import numpy as np import pandas as pd import itertools import sys import Constant class Parameter: USER_NUM_CONST = 500 SERVER_NUM_CONST = 10 CAPACITY_CONST = 50 def __init__(self, seed): np.random.seed(seed) self.USER_NUM = 500 self.SERVER_NUM = 10 self.DELAY_MAX = 10 self.DELAY_SERVER = 1 self.CAPACITY = 50 def create_input(self): # inputs self.e_u = list(itertools.product(range(self.USER_NUM), range(self.SERVER_NUM))) self.e_s = list(itertools.combinations(list(range(0, self.SERVER_NUM)), 2)) self.d_us = np.random.randint(1, self.DELAY_MAX, (self.USER_NUM, self.SERVER_NUM)) self.m_s = np.full(self.SERVER_NUM, self.CAPACITY) def set_param(self, var_name, consts, var): if var_name == 'user': self.USER_NUM = var self.SERVER_NUM = consts['server'] self.CAPACITY = consts['capacity'] elif var_name == 'server': self.USER_NUM = consts['user'] self.SERVER_NUM = var self.CAPACITY = consts['capacity'] elif var_name == 'capacity': self.USER_NUM = consts['user'] self.SERVER_NUM = consts['server'] self.CAPACITY = var else: sys.exit('invalid var_name = ' + str(var_name)) def get_const(var_name): if var_name == 'user': return Parameter.USER_NUM_CONST elif var_name == 'server': return Parameter.SERVER_NUM_CONST elif var_name == 'capacity': return Parameter.CAPACITY_CONST else: sys.exit('invalid var_name = ' + str(var_name)) これを作ることで1つのインスタンスが1つのパラメータに対応することになるので, 全部グローバル変数で書いていた前回のシミュレータよりめちゃめちゃわかりやすくなった。また, インスタンスメソッドを呼び出してパラ調整がしやすく, メソッドとしてパッケージ化することでエラーを極力避けれるようになった。 IlpクラスとMmdクラス class Ilp: def __init__(self, param): self.create_dataframe(param) self.set_input() def set_input(self): # optimization problem problem = LpProblem() # decision variables self.df_e_u['variable'] = [LpVariable('x_us%d' % i, cat=LpBinary) for i in self.df_e_u.index] self.df_e_s['variable'] = [LpVariable('x_st%d' % i, cat=LpBinary) for i in self.df_e_s.index] self.df_v_s['variable'] = [LpVariable('y%d' % i, cat=LpBinary) for i in self.df_v_s.index] self.D_u = LpVariable('D_u', cat=LpInteger) self.D_s = LpVariable('D_s', cat=LpInteger) # objective function problem += 2 * self.D_u + self.D_s self.problem = problem def create_dataframe(self, param): # dataframe for E_U df_e_u = pd.DataFrame([(i, j) for i, j in param.e_u], columns=['user', 'server']) df_e_u['delay'] = param.d_us.flatten() self.df_e_u = df_e_u # dataframe for E_S df_e_s = pd.DataFrame([(i, j) for i, j in param.e_s], columns=['server_1', 'server_2']) df_e_s['delay'] = param.DELAY_SERVER self.df_e_s = df_e_s # dataframe for V_S df_v_s = pd.DataFrame(list(range(0, param.SERVER_NUM)), columns=['server']) df_v_s['capacity'] = param.m_s self.df_v_s = df_v_s def solve_by_ilp(self, solver=None): t_0 = time.perf_counter() # solve try: # constraints self.problem = self.create_constraints(self.problem) if solver == 'cplex': self.problem.solve(GLPK_CMD(msg=0)) else: self.problem.solve(CPLEX_CMD(msg=0)) except PulpSolverError: print(CPLEX_CMD().path, 'is not installed') t_1 = time.perf_counter() return t_1 - t_0 def print_result(self): if self.problem.status == 1: print('objective function is ', value(self.problem.objective)) print('cpu time is ' + str(self.cpu_time) + ' sec') else: print('status code is ', self.problem.status) def create_constraints(self, m): # constraints # (1b) for k, v in self.df_e_u.groupby('user'): m += lpSum(v.variable) == 1 # (1c) for k, v in self.df_e_u.groupby('server'): m += lpSum(v.variable) <= self.df_v_s['capacity'][k] # (1d) for k, v in self.df_e_u.iterrows(): m += v.variable * v.delay <= self.D_u # (1e) for k, v in self.df_e_s.iterrows(): m += v.variable * v.delay <= self.D_s # (1f) for k, v in self.df_e_u.groupby('user'): for l, w in self.df_v_s.iterrows(): m += w.variable >= v.variable # (1g) for k, v in self.df_e_s.iterrows(): m += self.df_v_s.iloc[v.server_1].variable + \ self.df_v_s.iloc[v.server_2].variable - 1 <= v.variable # (1h) for k, v in self.df_e_s.iterrows(): m += v.variable <= self.df_v_s.iloc[v.server_1].variable # (1i) for k, v in self.df_e_s.iterrows(): m += v.variable <= self.df_v_s.iloc[v.server_2].variable return m class Mmd: def __init__(self, param): self.set_input(param) def set_input(self, param): # edges list edges = np.empty(3, dtype=int) for k, v in enumerate(param.d_us): for i, j in enumerate(v): edges = np.vstack((edges, np.array([k, i, j]))) self.edges = edges def start_algorithm(self, param): t_0 = time.perf_counter() L_1 = self.one_server_case(param) L_2 = self.multiple_server_case(param) D_u = min([L_1, L_2]) if D_u > param.DELAY_MAX: self.status = False else: self.status = True self.objective_function = D_u * 2 + param.DELAY_SERVER t_1 = time.perf_counter() return t_1 - t_0 def one_server_case(self, param): # step 1: consider one server case # allocate all user and get L_1 dic_l = dict() for k, v in enumerate(param.m_s): if v >= param.USER_NUM: D_u = param.d_us[:, k].max() dic_l[k] = D_u # search minimum D_u if bool(dic_l): return min(dic_l.values()) else: return Constant.INF def multiple_server_case(self, param): # step 2: consider multiple server case # initialize the bipartite graph added_server = param.SERVER_NUM for k, v in enumerate(param.m_s): for j in range(param.USER_NUM): delay = param.d_us[j][k] for i in range(added_server, added_server + v - 1): self.edges = np.vstack((self.edges, np.array([j, i, delay]))) added_server += v - 1 param.COPY_SERVER_NUM = added_server # search matching for i in range(1, param.DELAY_MAX): hc = HopcroftKarp(param.USER_NUM, param.COPY_SERVER_NUM) for j in np.where(self.edges[:, -1] <= i)[0]: hc.add_edge(self.edges[j][0], self.edges[j][1]) if hc.flow() == param.USER_NUM: return i return Constant.INF def print_result(self): if self.status: print('objective function is ', str(self.objective_function)) print('cpu time is ' + str(self.cpu_time) + ' sec') else: print('Error') inputを入れればoutputが出るツールとして2つのクラスを作った。これにさっき定義したParameterをそのままいれればいいので, ブラックボックスとして扱える。set_inputなんかのメソッドを共通化してもよかった。また Ilp ではPulpを使ってソルバを簡単に切り替えられるようにした。 ...

seccon beginners ctf前の最後の勉強会. 今回はアルゴリズムに関する問題が多かった. Math I RSAの公開鍵暗号に関する問題. ちなみに、 RSA暗号とは、桁数が大きい合成数の素因数分解問題が困難であることを安全性の根拠とした公開鍵暗号の一つである。 c(暗号文)とm(平文)は以下のようにして求める. c = m^e mod n m = c^d mod n よってdさえ求まれば復号できる. dを求める式は以下の通り. d = e^(-1)(mod(p-1)(q-1)) dを求めるには, n = pqを求める p-1とq-1の最大公倍数lcm(p-1, q-1) = (p-1)(q-1)/gcd(p-1)(q-1)を求める ed≡1(mod L)となるようなedの組みを求める 拡張ユークリッドの互除法が使われている. このサイトを参考にして実装した. import math e = 65537 n = 1517330236262917595314610888889322115651087080826711948897066340883208205571592392362650858571076247939805436226544833224526137582834770402681005343930059463684528957271778199162575053306238099823295117697031968370690372250916935800738698142103275969223264184374648246277564306900886005299731265812255274723175925185522344831066577166867786835955092059346244885587228196357297758371381557924676260190209536670230008561217008649261974735505203813478978893582292682827884118215872470401293272325715864815977064075988643101088355047954735427424641386870772845440782632933485165110172437511822736907550777817722248753671107339823410418938404382732079381329288400012929311347390423061254658780185245562668131009832293474920208834795460061115101364091252176594144096675899952570380792978037217747311595899301451192342027799533264325948876556110474850761538179748318187805312451895898751337975457949549497666542175077894987697085521882531938339334715190663665300179658557458036053188152532948734992896239950564081581184284728802682982779186068791931259198917308153082917381616147108543673346682338045309449569430550618884202465809290850964525390539782080230737593560891353558335337408957948041667929154230334506735825418239563481028126435029 c = 225549592628492616152632265482125315868911125659971085929712296366214355608049224179339757637982541542745010822022226409126123627804953064072055667012172681551500780763483172914389813057444669314726404135978565446282309019729994976815925850916487257699707478206132474710963752590399332920672607440793116387051071191919835316845827838287954541558777355864714782464299278036910958484272003656702623646042688124964364376687297742060363382322519436200343894901785951095760714894439233966409337996138592489997024933882003852590408577812535049335652212448474376457015077047529818315877549614859586475504070051201054704954654093482056493092930700787890579346065916834434739980791402216175555075896066616519150164831990626727591876115821219941268309678240872298029611746575376322733311657394502859852213595389607239431585120943268774679785316133478171225719729917877009624611286702010936951705160870997184123775488592130586606070277173392647225589257616518666852404878425355285270687131724258281902727717116041282358028398978152480549468694659695121115046850718180640407034795656480263573773381753855724693739080045739160297875306923958599742379878734638341856117533253251168244471273520476474579680250862738227337561115160603373096699944163 p = 34111525225922333955113751419357677129436029651245533697825114748126342624744832960936498161825269430327019858323450578875242014583535842110912370431931233957939950911741013017595977471949767235426490850284286661592357779825212265055931705799916913817655743434497422993498931394618832741336247426815710164342599150990608143637331068220244525541794855651643135012846039439355101027994945120698530177329829213208761057392236875366458197098507252851244132455996468628957560178868724310000317011912994632328371761486669358065577269198065792981537378448324923622959249447066754504943097391628716371245206444816309511381323 q = 44481453884385518268018625442920628989497457642625668259648790876723318635861137128631112417617317160816537010595885992856520476731882382742220627466006460645416066646852266992087386855491152795237153901319521506429873434336969666536995399866125781057768075533560120399184566956433129854995464893265403724034960689938351450709950699740508459206785093693277541785285699733873530541918483842122691276322286810422297015782658645129421043160749040846216892671031156465364652681036828461619272427318758098538927727392459501761203842363017121432657534770898181975532066012149902177196510416802134121754859407938165610800223 # step1 L = (p-1)*(q-1)//math.gcd(p-1, q-1) # step2 def ex_euclid(x, y): c0, c1 = x, y a0, a1 = 1, 0 b0, b1 = 0, 1 while c1 != 0: m = c0 % c1 q = c0 // c1 c0, c1 = c1, m a0, a1 = a1, (a0 - q * a1) b0, b1 = b1, (b0 - q * b1) return a0 d = ex_euclid(e, L) # step3 m = pow(c,d,n) print ("%0512x"%m).decode("hex") Math II モジュロ演算という割り算の余りを求める計算と関わっている. xの101乗根を普通に求めようとしてもオーバーフローが起きてしまうので, 二分探索を実装する. このサイトを参考にした. ...

今日は4人しかこなかった… 火曜の8:45からってのがきつすぎるんかな… 31 Kangacha PHPで書かれた簡単なwebアプリケーションの問題. Gachaというボタンを押せば日本の戦艦の名前がランダムでリストに追加されていく. ソースコードも与えられているので読んでいく. if (isset($_POST['submit'])) { // Gacha if ($_POST['submit'] === 'Gacha') { // Yamato is ultra rare $ship[] = mt_rand(0, count($shipname)-2); $s = implode(',', $ship); $sign = hash('sha512', $salt.$s); setcookie('ship', $s); setcookie('signature', $sign); } // Clear if ($_POST['submit'] === 'Clear') { setcookie('ship', '', 0); setcookie('signature', '', 0); } header("Location: {$_SERVER['REQUEST_URI']}"); exit(); } このソースから, $_COOKIE['ship']に戦艦の番号の配列が, $_COOKIE['signature']にあらかじめ決められた$saltと戦艦番号のハッシュ値が格納される. // Check signature and read if (isset($_COOKIE['ship']) and isset($_COOKIE['signature']) and hash('sha512', $salt.$_COOKIE['ship']) === $_COOKIE['signature']) $ship = explode(',', $_COOKIE['ship']); else $ship = array(); ここで$_COOKIE['signature']のバリデーションを確認され, 不正であれば配列の中身が空になってしまう. ...

第3回CTF勉強会 ksnctfの9, 11, 12, 13が課題で, 14が演習問題である. 11が難しいらしい 9 Digest is secure! pcapファイルをダウンロードして, wiresharkでhttp通信をフィルタリングしてみると, digest認証の通信が行われている. ちなみにDigest認証とは、 Digest認証とは、Basic認証と同じくApacheで利用できるアクセス制限です。ユーザーIDとパスワードを求める点までは全く同じですが、入力されたユーザーIDとパスワードをハッシュ関数であるMD5を用いて解析されにくい状態で送信する仕組みです。しかし、Basic認証と比べて後発の機能なので、かつては一部対応していないブラウザがありました。現在ではほとんどのブラウザに対応しているため、Basic認証ではなくDigest認証が使われるケースが増えています。レンタルサーバー比較なび ここで, 認証の際に渡しているパラメータをみてみる. Digest username=“q9” realm=“secret” nonce=“bbKtsfbABAA=5dad3cce7a7dd2c3335c9b400a19d6ad02df299b” uri="/~q9/" algorithm=MD5 response=“c3077454ecf09ecef1d6c1201038cfaf” qop=auth nc=00000001 cnonce=“9691c249745d94fc” これから以下のようにresponseが作成される. A1 = ユーザ名 ":" realm ":" パスワード A2 = HTTPのメソッド ":" コンテンツのURI response = MD5( MD5(A1) ":" nonce ":" nc ":" cnonce ":" qop ":" MD5(A2) ) これをみると. パスワードがわからなくてもA1さえわかればサーバーから送られてきたnonceを元にresponseを生成できることがわかる. ここで, A1を得るためにresponseを解読する. MD5は脆弱性が存在し鍵長も短いので復号ツールで復号できてしまう. 追記 後のパケットにA1が帰ってきているので, ツールを使わなくて良い. Qiita:暗号化とハッシュ化に関する基本的な事柄まとめ Hash Toolkit: 復号ツール c627e19450db746b739f41b64097d449:bbKtsfbABAA=5dad3cce7a7dd2c3335c9b400a19d6ad02df299b:00000001:9691c249745d94fc:auth:31e101310bcd7fae974b921eb148099c この結果A1がわかった. ちなみにA1は解読できなかったのでパスワードがわからない. しかし他の全てのパラメータがわかるのでresponseを生成できる. ...

前回は, CpawCTF2の1問を解いたが難易度が高かったので, ksnctfをみんなで解くことにした. 今回の課題は2, 3, 5, 6である. write up [2] Easy Cipher EBG KVVV vf n fvzcyr yrggre fhofgvghgvba pvcure gung ercynprf n yrggre jvgu gur yrggre KVVV yrggref nsgre vg va gur nycunorg. EBG KVVV vf na rknzcyr bs gur Pnrfne pvcure, qrirybcrq va napvrag Ebzr. Synt vf SYNTFjmtkOWFNZdjkkNH. Vafreg na haqrefpber vzzrqvngryl nsgre SYNT. 見るからにシーザ暗号なので, 文字をずらすことを考える. 文字コードはUnicodeに従うとして, 空白の文字コードは32 大文字の文字コードは65~90 小文字の文字コード97~122 である. これを加味して以下のような解読するための関数をpythonでかく. # シーザー暗号の解読 def decrypt(text, rot): decrypt_text = '' for ch in text: # 文字コードに変換 code = ord(ch) if code == 32: # 空白ならそのまま出力 decrypt_text += ch continue if code <= 90: # 小文字 code += rot if code > 90: code = code - 90 + 64 else: # 大文字 code += rot if code > 122: code = code - 122 + 96 # 文字に変換 decrypt_text += chr(code) return decrypt_text text = "EBG KVVV vf n fvzcyr yrggre fhofgvghgvba pvcure gung ercynprf n yrggre jvgu gur yrggre KVVV yrggref nsgre vg va gur nycunorg. EBG KVVV vf na rknzcyr bs gur Pnrfne pvcure, qrirybcrq va napvrag Ebzr. Synt vf SYNTFjmtkOWFNZdjkkNH. Vafreg na haqrefpber vzzrqvngryl nsgre SYNT" for i in range(1, 26): if decrypt(text, i).find("FLAG") != -1: print(decrypt(text, i)) # ROT XIII is a simple letter substitution cipher that replaces a letter with the letter XIII letters after it in the alphabet; ROT XIII is an example of the Caesar cipher9 developed in ancient Rome; Flag is FLAGSwzgxBJSAMqwxxAU; Insert an underscore immediately after FLAG また, ROT13はPythonに実装されているので一瞬で解読できる. ...

背景 TAとして研究室のB4の課題を手伝う事になったが, 課題に取り組む前の環境構築につまずいてしまって課題どころじゃなくなる…みたいな状況を避ける為に, Windowsでjupyter notebookするところまでを手伝ってあげた. 内容 Pythonをインストール まず, Pythonをインストールしてもらう. いろいろな設定をするように言われるが, すべてデフォルトの設定にする. これは, あとでPythonの設定を変更するときに, どんな設定にしたかを忘れないようにするために有効である. 注意点 Pathを通すことを忘れないように. 忘れていた場合, もう一度インストーラーを起動して設定を変更できる. adminの実行権限が必要である. これは, Pythonがwindowsのシステムに関わる部分を触るためだとおもわれる. これは, Pythonのコマンドをpythonと打つだけで実行できるようにショートカットを作るイメージである. cdだったり, lsのコマンドはデフォルトで実行できるようになっているが, pythonは設定しなければいけない. git bashをインストール 次に, git bashをインストールしてもらう. 本来, windowsのコマンドプロンプトを使ってもいろいろ実行できるのだが, linuxのコマンドの方が圧倒的に使用者が多いので, Linuxコマンドをwindows上で使えるようにする. 注意点 git bashの起動と同時にPathの情報が読み込まれる. Pathの設定を変更したならば, git bashを再起動する必要がある. jupyter notebookをインストール git bash上で以下のコマンドを実行する. command not foundとなればPathが通っていない可能性が高い. pip install -U pip pip install jupyter 余談 このコマンドでPythonのいろんなパッケージをインストールできる. jupyter notebookを実行する 以下のコマンド実行する. カレントディレクトリ以下に.ipynbのファイルがあることを確認する. jupyter notebook これで, ブラウザ上で.ipynbファイルをいじることができる. まとめ pathで詰まっただけで1時間弱くらいで4人とも実行することができた.