ホーム » スタッフ » 斉藤徹 » 講義録 (ページ 69)

「講義録」カテゴリーアーカイブ

2025年6月
日	月	火	水	木	金	土
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

2段階認証のTwitter設定例

2018年1月10日

Twitterの2段階認証の設定は、以下の通り。(2018年1月時点)

最初に、パソコンのTwitterの画面右上のプロフィールと設定より、「設定とプライバシー」を選択。

このなかのセキュリティの欄の「ログイン認証を設定」をクリック。

2段階認証で、ワンタイムパスワードが送られてくる携帯電話の番号を登録する。

電話番号を記入し「コードを送信」を選ぶとショートメッセージで6桁のワンタイムパスワードが送られてくるので、それを入力する。

携帯電話を紛失すると、ログインができなくなるので、その非常事態用に、最終手段のバックアップコードが表示される。このログイン時のパスワードで、バックアップコードを入力すればログインできる。

このバックアップコードは重要なので、必ずどこかに保存しておくこと。

リモート接続と暗号化

2018年1月10日

リモート接続と暗号化について説明

リモート接続

サーバなどの管理をしていると、インターネットの先にあるコンピュータを操作したい場合が多い。こういった場合には、リモート接続機能を用いる。

リモート接続による相手側のコンピュータを操作する場合、相手側のコンピュータにはリモート接続用のサーバプログラムを起動しておく。こういったリモート接続を利用するのは、”unix” の利用者が多いが、”unix” では、サーバのプログラムは、一般的にデーモン(daemon/守護神)と呼ばれる。

telnet と rlogin

telnet は、最も基本的なリモート接続の方法であり、TCP の 23 番ポートを使う。telnetのサーバ(telnetd)は、送られてくるタイプされた文字を unix の shell (キーボードでの命令を実行するプログラム) に渡し、shell の実行結果の文字を接続元に送り返す。

rlogin は、TCP の 513 番ポートを使うリモート接続用のソフトで、サーバで rlogind を起動しておく。unix で rlogin クライアントを使うと、リモート側で命令を実行したりファイルをコピーすることができる。

こういったリモート接続ができると、ネットワークの向こう側のコンピュータを自由に操作できる一方で、login のパスワードが破られるとコンピュータを悪用されたり情報を盗まれる可能性がある。
特に、telnet , rlogin では、通信の内容が暗号化されないため、パケット盗聴(後述)されると、サーバを悪用されてしまう。

このため、ルータや firewall では、ポート番号 23 , 513 などは、遮断するのが一般的である。

ssh

暗号化されない rlogin の通信を暗号化により安全に実行できるようにしたものが、ssh (secure shell) である。
ssh は、通常では TCP の 22 番ポートを使う。しかし、暗号化されていたとしてもパスワード破りなどの危険性があるため、ポート番号を変更したり、特定のコンピュータに対してのみ接続許可を与え、安全対策を行う。

リモートデスクトップ

Windows では、コンピュータの操作では、マウス操作が中心(GUI: Graphical User Interface)となる。これに比べ、telnet,rlogin,ssh などの方法では、キーボードによる操作が中心(CUI: Character User Interface)であり、初心者には難しい。こういう場合はリモートデスクトップ(remote desktop)が用いられる。

remote desktop では、サーバのディスプレイ画面の情報をクライアントに送り、クライアントの操作(キーボード入力やマウス操作)がサーバに送られ、サーバのコンピュータを自由に操作ができる。

暗号化

Ethernet では1本の通信線を共有したり、WiFiのような無線通信では、通信データの盗聴が簡単にできてしまう。クラッカーは、通信データの中から”login, password” といった文字を検索し、その近辺の文字を探すことでパスワードを盗み出す。

このようなことを防ぐために通信データの暗号化は重要な方法である。

暗号化アルゴリズム

暗号化の最も原始的な方法が、置換式 と呼ばれる方法で、特定の文字を別な文字に変更する。rot13は、A→N,B→Oに置き換える暗号。コナン・ドイル原作のシャーロック・ホームズに出てくる踊る人形などもこれに相当する。これらの方法では、アルファベットの文字の出現頻度から元の文を想像することで解読されてしまう。

エニグマ(Enigma)は、第2次世界大戦でナチス・ドイツが用いたロータ式暗号機であり、置換式の解読方法が不可能であった。しかし、イギリスのアラン・チューリングが電気式の解読器を開発することで暗号解読が可能となった。この解読器が現在のコンピュータの原型となっている。

チューリングによる暗号解読は、映画「イミテーションゲーム」を参照。

最近では、様々な暗号化アルゴリズムが開発されており、古くは “DES, AES“といったアルゴリズムが使われていたが、コンピュータの性能の向上と共に、解読に必要な時間が短くなったことから、RSA といった新しい暗号化方式が考えられ、さらに暗号化の鍵を長くすることで解読に要する時間を長くするようになっている。

パスワード解読方法

ログインなどで使われるパスワードは、どのように破られるのだろうか？

ブルートフォース攻撃：単純に全ての文字を試す方式。文字の組み合わせ問題なので、パスワード文字列長をNとした場合、数字だけ(10^N)とか英字だけ(26^N)といった組み合わせでは、短時間に解読されてしまう。数字,大文字,小文字,記号などを交えたパスワードが理想。
英単語辞書を用いた辞書攻撃：パスワードが長い場合、文字列の全ての組み合わせを試すには長い時間が必要となる。しかし、パスワードはユーザが記憶して使うことから覚えやすい単語が使われる。このため英単語辞書の文字を組み合わせることで、解読時間を短くできる場合がある。
漏えいパスワードによる辞書攻撃：サーバへのリモート接続などができてしまった場合、パスワード情報が盗まれる場合がある。この時、別なサイトに同じパスワードを使っていると、その漏えいしたパスワードで別のサイトも接続ができてしまう。これらのことから、同じパスワードを使いまわすことは避けるべきである。
ソーシャル攻撃：パスワードには、簡単に覚えられるように自宅の電話番号、誕生日、家族の名前といったものを使う人が多い。このため、SNS で相手に友達登録をしてもうことで、こういった情報を手に入れ、パスワードを破る方法。最近の有名人の個人情報漏洩はこの手の攻撃が多い。

ソーシャル攻撃は、元クラッカーケビン・ミトニックが有名

攻撃が難しい暗号化へ

先に述べたような、login に使うパスワードなどは、ブルートフォース攻撃をうけると解読は時間の問題となる。これらの対策として毎回違う鍵(パスワード)を使えばいい。

暗号表：置換式で読み取られるのを防ぐために、置換する文字の表を沢山作っておき、別の方法でその度毎に置換表を変更する
ワンタイムパスワード：使い捨てのパスワードをあらかじめ沢山作っておき、接続の度に次のパスワードを用いる方式。あるいは、時間から特殊な計算方法で生成されるパスワード。時間と共に変化するのでその度毎に違うパスワードとなる。毎回違うパスワードを入力するため、パスワード表を常に持ち歩いたり、入力が面倒なので数字だけを使うことが多く、この方法だけでは使いにくい。

公開鍵暗号方式

以前に使われていた暗号化の方式は、暗号化の鍵と復号化の鍵に同じものを用いる共通鍵方式であった。
しかし、この鍵をどうやって相手に渡すか…が問題となっていた。(鍵を相手に渡す瞬間のデータを盗聴されると危険)

このため、最近では公開鍵暗号方式が中心となっている。この方式は「暗号化するため専用の公開鍵」と、「暗号化を復号するための秘密鍵」をペアにして用いる。公開鍵は、暗号化するため専用なので、この鍵が他の人に見られても、暗号を復号することはできない。

公開鍵暗号方式では、RSA　などが最も有名で現在広く利用されている。

WWWとhttp

2017年12月18日

前回の DNS とメールで紹介の抜けていた点を補足。内容は前回の講義録に追記。

WWWとhttp

WWWとは、ティム・バーナーズ=リーによって作られたサービスであり、元々は研究データの論文やデータの共有のために作られた。この際のWebサーバのデータのやり取りのためのプロトコルがhttp(Hyper Text Transfer Protocol)であり、ポート番号80のTCPを用いたものであり、最近では通信を暗号化したhttps(ポート番号443)も多く使われる。

httpでは、文字データの中に画像や音声といった情報に加え、他のデータへのリンクを埋め込むことができる HTML(Hyper Text Markup Language) のデータがやりとりされる。このHTML形式のデータを表示するためのソフトは、ブラウザと呼ばれる。

URL

WWWのデータの場所を示すものが、URL(Uniformed Resource Locator)であるが、最近ではインターネットが複雑化しLocator という表現が難しいため、URI(Uniformed Resource Identifier)と呼ぶようになってきた。

URLは基本的に、スキーマ://コンピュータ名/サーバ内ファイル位置といった文字で構成される。URL は、HTTP だけでなく、インターネットの情報の場所を記述するために使われており、httpやhttps以外にも使う。

http

httpのサーバ(Webサーバ)とブラウザでは、以下のような手順で処理が行われる。例えば http://www.ei.fukui-nct.ac.jp/~t-saitoh/index.html のページが表示されるまでを考えると、

ブラウザのURL欄に、目的サイトのURLを入力。
基本的には、スキーマ欄に記載されたプロトコル(http)名から、ポート番号と通信方法(http)を決める。
コンピュータ名部分(www.ei.fukui-nct.ac.jp)を DNS に問合せして、得られたIPアドレスのコンピュータに接続。
httpの最も簡単な GET メソッドでは、Webサーバに、サーバ内のファイル位置(/~t-saitoh/index.html)を伝えると、Webサーバは指定された場所のファイルを返送する。
HTML形式のデータが指定された場合、ブラウザはその HTML をどの様に表示するか判断しながら表示する。

このような予め保存されているWebページを返送する場合は静的ページと呼ばれる。サーバのデータベースなどを参照しながらページ内容を返送する場合は、動的ページと呼ばれ、CGI(Common Gateway Interface) という手法が使われたり、動的なページを表示するためのプログラム言語(例えばPHP)が使われる。

サーチエンジン

インターネットでは、大量のWebページが出現してきたため、自分の目的に応じてWebページを探す機能が必要となってきた。このような目的のWebページを検索してくれるシステムは、サーチエンジンと呼ばれる。

ディレクトリ型

最初に現れた検索システムは、ページ作者が自分のページのURLと内容となるキーワードを登録しておき、内容のカテゴリー別に、ページの紹介文章が表示されるディレクトリ型であった。(初期のYahoo)

しかし、登録するキーワード以外の文字で探そうとすると、情報を見つけることができない。

ロボット型

これらの問題を解決すべく登場したのが、Google のようなロボット型サーチエンジンである。
ロボット型の検索システムでは、クローラーとかロボットとか呼ばれるプログラムを使い、Webページの内容をダウンロードし、そこに記載された文字を使ってURLのデータベースを作成する。クローラーは、リンクが貼られていると、そのページでも同様の処理を行い、大量の情報を次々と取得していく。

直接サーバと接続

サーバの動作を知るために、メールサーバやWebサーバと直接通信をしてみよう。

この実験をするには、telnet コマンドを使う。telnet コマンドは、タイプされた文字をサーバに送り、サーバから返答された文字を画面に表示するだけの単純なコマンドである。

使い方： telnet 相手サーバ ポート番号

(例1) メールサーバに接続
$ nslookup -query=MX fukui-nct.ac.jp # 自組織メールサーバを探す
 :
Non-authoritative answer:
fukui-nct.ac.jp	mail exchanger = 10 smtp.ip.fukui-nct.ac.jp.
$ telnet smtp.ip.fukui-nct.ac.jp 25 # メールサーバに接続
Trying 10.10.21.55...
Connected to smtp.ip.fukui-nct.ac.jp.
Escape character is '^]'.
220 ews.ip.fukui-nct.ac.jp EGVA/SMTP Ready.
HELO ei.fukui-nct.ac.jp           # 送信開始
250 Requested mail action okay, completed.
MAIL FROM: foo@ei.fukui-nct.ac.jp # 送信元の設定
250 Requested mail action okay, completed.
RCPT TO: bar@example.jp           # 送信先の設定
250 Requested mail action okay, completed.
DATA                              # メールデータ
354 Enter mail, end with "." on a line by itself.
From: foo@ei.fukui-nct.ac.jp
Subject: test
test
.
250 Requested mail action okay, completed.
QUIT  # 送信中止

(例2) Webサーバに接続
   # http://www.ei.fukui-nct.ac.jp/~t-saitoh/ を参照
$ telnet www.ei.fukui-nct.ac.jp 80
Trying 104.215.24.241...
Connected to fnctei.ei.fukui-nct.ac.jp.
Escape character is '^]'.
GET /~t-saitoh/ http/1.1    # GET ファイル位置 プロトコル
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" id="sixapart-standard">
　：

文字をキーとするハッシュ値

2017年12月18日

前回のハッシュ法では、数値(電話番号)をキーとする検索であった。このためハッシュ関数は、数値の不規則性の部分を取り出すだけでよかった。それでは、文字をキーとしてデータを探す場合はどのようにすればよいか？

文字列をキーとするハッシュ

文字の場合は、文字コードを用いてハッシュ値を作れば良い。

int hash_func( char* s ) {
   int sum = 0 ;
   for( int i = 0 ; s[i] != '¥0' ; i++ )
      sum += s[i] ;
   return sum % HASE_SIZE ;
}

しかし、この方法では、文字の並び順が違うだけ(“ABC”,”CBA”,”BBB”)に対して、同じハッシュ値となってしまう。英文字の場合は文字数も限られ、文字コード的には末尾4bitが変化するだけであり、上位ビットは文字数に左右されることになる。この場合、同じような文字数であれば、末尾4bitの不規則性も平均化されて、近いハッシュ値になることが懸念される。

そこで、文字コード的に変化のある部分が、数値的に全体に影響を及ぼし、最終的な値が広く分布するように以下のような計算とする場合が多い。

// 積算部のみ
sum = ( sum * (小さめの素数) + s[i] ) % (大きめの素数) ;

このような考え方は、疑似乱数を生成する方式と近い部分が多い。

共有のあるデータの取扱い問題

struct List* join( struct List* p , struct List* q )
{  struct List* ans = p ;
   for( ; q != NULL ; q = q->next )
      if ( !find( ans , q->data ) )
         ans = cons( q->data , ans ) ;
   return ans ;
}
void list_del( struct List* p )
{                            // ダメなプログラムの例
   while( p != NULL ) {      // for( ; p != NULL ; p = p->next )
      struct List* d = p ;   //    free( p ) ;
      p = p->next ;
      free( d ) ;
   }    
}
void main() {
   // リストの生成
   struct List* a = cons( 1 , cons( 2 , cons( 3 , NULL ) ) ) ;
   struct List* b = cons( 2 , cons( 3 , cons( 4 , NULL ) ) ) ;
   struct List* c = join( a , b ) ;　// c = { 4, 1, 2, 3 }
                                     //          ~~~~~~~ ここは a
   // a,b,cを使った処理

   // 処理が終わったのでa,b,cを捨てる
   list_del( c ) ;
   list_del( b ) ;
   list_del( a ) ; // list_del(c)ですでに消えている
}                  // このためメモリー参照エラー発生

参照カウンタ法

上記の問題の簡単な解決方法は、参照カウンタ法である。

参照カウンタ法は、データを指すポインタ数を一緒に保存し、

データ生成時は、refc = 1
共有が発生する度に、refc++

データを消す場合は、

refc–
refc が 0 の時は、本当に消す

struct List {
   int          refc ; // 参照カウンタ
   int          data ; // データ
   struct List* next ; // 次のポインタ
} ;

void list_del( strcut List* p ) {  // 再帰で全廃棄
   if ( p->refc <= 0 ) {           // 参照カウンタを減らし
      list_del( p->next ) ;        // 0ならば本当に消す
      free( p ) ;
   }
}

ただし、参照カウンタ法は、循環リストではカウンタが0にならないので、取扱いが苦手。

DNSとメール

2017年12月13日

DNSとドメイン名

インターネットでの通信では、IPプロトコルでコンピュータを指定するが、IPアドレスは無機質で覚えるのが大変であり、これをサポートするのが、IPアドレスの電話帳でもある DNS(Domain Name Service) である。

コンピュータでサービスに使うコンピュータには、ドメイン名を割り振る。ドメイン名は、www.ei.fukui-nct.ac.jp といったピリオド区切りの名前であり、以下のような意味を持つ。

www.	ei.	fukui-nct.	ac.	jp
ホスト名	サブドメイン	組織ドメイン	組織種別	国ドメイン

ただしアメリカでは、国ドメインを一般的に使わない。また最近では、世界的な企業では国ドメインが意味をなさないので、アメリカ以外でも .com や .net といった、トップレベルドメインが使われる。様々なサービスを展開している企業では、組織種別が意味をなさないため、toyota.jp といったものも増えてきた。

以下に、主要な組織ドメイン・国ドメインをあげる。

このドメイン名から、IPアドレスを調べる DNS は、ポート番号53,UDP を使ったサービスで、一般的な機器はその組織用の DNS サーバに接続して名前からIPアドレスを知ることができる。各組織の DNSサーバは、上位サーバが設けられ調べられない IP アドレスは、さらに上位のサーバに問合せが行われる。

nslookup の使い方

DNSの問合せには、nslookup というコマンドを用いる。

$ nslookup www.u-fukui.ac.jp     # 福井大学のWebサーバの問合せ
Server:		192.168.xx.xx
Address:	192.168.xx.xx#53

Non-authoritative answer:        # この例では、複数のコンピュータの
Name:	www.u-fukui.ac.jp        # IPアドレスが求まっている。
Address: 220.110.205.26          # 負荷分散を目的とした
Name:	www.u-fukui.ac.jp        # ラウンドロビン DNS のため
Address: 202.19.136.96
:

DNSの問合せには、ドメイン名からIPアドレスを求める「正引き」とは反対に、IPアドレスからドメイン名を求める「逆引き」もある。この機能を使って、アクセスしてきたコンピュータの逆引きを行うことで、どういった組織からのアクセスかを調べることができ、危険な組織からであればアクセスを拒否するようにサーバを設定したりする。

$ nslookup 192.156.146.100       # 福井高専のWebサーバの問合せ
 :
Non-authoritative answer:
100.146.156.192.in-addr.arpa	name = sv1.ip.fukui-nct.ac.jp.
 :

DNSと階層構造

前回説明したDNSでは、1つのDNSサーバに処理が集中しないようにするために、階層型構成となっている。

組織に属するパソコンは、その組織用のDNSサーバに接続する。DNSサーバは自身の組織のDNS情報を提供するとともに、他の組織の DNS の問合せ結果をある程度保存し(キャッシュ)、同じ問合せがあった場合は保存した情報を返す。保存されていない場合は、上位DNSサーバに問合せを行う。最上位サーバにまで届いた問合せは、各ドメイン名を管理しているDNSサーバに問合せを行う。

パソコンがインターネットに接続できない場合は、DNS のトラブルが原因の場合もある。こういった場合には、Google が、IPアドレス 8.8.8.8 でDNSサーバを公開している。これを使って DNS のトラブルを調べることも多い。
$ nslookup www.u-fukui.ac.jp 8.8.8.8
最近のマルウェアによる攻撃手法の１つに、DNS ポイズニングという手法がある。
マルウェアに感染した際に、パソコンの DNS の設定を攻撃者用の DNS に変更することで、偽物のコンピュータに接続させる手法。

メール

電子メールは、非常に迅速にメッセージを相手に届けることができ、そのメッセージを蓄積・加工・編集・転送できる。また、音声や画像といった情報も、複雑な文字情報に置き換えることで、転送できるようになっている。

メールは、foo@example.co.jp といったような、ユーザ名とドメイン名から構成される。

foo	@	example.co.jp
ユーザ名		ドメイン名

メールは、直接相手のコンピュータにメールが届くわけではない。メールは、相手のメールサーバまでメールを届ける SMTP プロトコルと、メールサーバから自分のメールを取り出す POP や IMAP というプロトコルによって行われる。

例えば、A さん(aaa@foo.co.jp) から、Bさん(bbb@bar.co.jp)にメールを出す場合には、送信処理で…

Aさんは、メールソフトでメールを出す。この時、メールは、Aさんの利用しているメールサーバ(A-server)に SMTP で送る。
A-server は、メールの To: の部分のドメイン名部分より送付先のメールサーバを見つける。^[MX]
送付先のドメイン名から、IPアドレスを調べ、メールは SMTP で相手のメールサーバ(B-server)に送られる。
B-server は、メールのユーザ名部分をみて、各ユーザ毎にメール内容を保存する。

この後、Bさんは、自分宛のメールを受信するには…

Bさんは、メールソフトでメールを受信しようとすると、メールサーバ(B-server)に、POP または IMAP で接続する。
接続時には、ユーザ名とパスワードで本人を確認する。
POP であれば、新着メールをパソコン側にダウンロードし、一般的にメールはサーバから削除される。
IMAP であれば、ユーザが読みたいメールをパソコンに転送し表示する。メールは削除を行わない限り、サーバに残る。

このプロトコルの流れで、注目すべき点は、SMTP でメールを送る際に、ユーザ確認が行われないことである。このため、メールでは現在でも迷惑メール(spam)を無くすことが困難となっている。

最近では、メールを自分のメールサーバに送る前に、POP/IMAP でサーバに接続して認証を受けてからでないとメールを出せないようにするなどの対応を取っているが、自組織からは、認証無しで SMTP でメールを出せる場合も多い。

[MX]メールアドレスのドメイン名では、ホスト名部分やサブドメインは省略されることも多い。送信先のメールサーバを見つける場合には、DNS の MX レコードを参照する。
$ nslookup -query=MX fukui-nct.ac.jp 8.8.8.8
 :
Non-authoritative answer:
fukui-nct.ac.jp	mail exchanger = 10 pomme.ip.fukui-nct.ac.jp.
fukui-nct.ac.jp	mail exchanger = 20 peche.ip.fukui-nct.ac.
[spam]迷惑メールの対策として、以下のような対策が行われている。
組織外からメールを受信した時は、”To:”の送り先が組織内の人である確認をする。(オープンリレー対策)

ファイアウォールで、メールサーバ以外の機器からSMTP(ポート番号25)の接続を禁止する。(OP25B)
SPF,DKIM といった送信ドメインの認証を行う。
$ nslookup -query=TXT xxx.fukui-nct.ac.jp 8.8.8.8
 :
Non-authoritative answer:
xxx.fukui-nct.ac.jp	text = "v=spf1 +ip4:xxx.xxx.xxx.xxx +a ~all"

メールヘッダの読み方

メールには迷惑メールや、マルウェアが仕込まれたものも多い。しかしながら、偽装したメールなども多く、メールを正しく分析できる知識が必要となる。この一つとして、メールヘッダを理解することが重要となる。
メールヘッダには、その宛先(To:)や発信者(From:)や発信日時(Date:)以外にも、様々な情報が記載されている。メールヘッダを読むには、メールソフトで「表示 – メッセージのソース」を選ぶと以下のようなものが表示される。

From: メールの送信者
To: メールの宛先            漢字が含まれると
Subject: メールのタイトル    =?iso-xxxx?...?= といったMIME形式
Date: メール送信日時
Received: どのコンピュータからどのコンピュータに送られたか
   From:のコンピュータ名と中継されたコンピュータが無関係だと怪しい
Received-SPF:    SPF(送信ドメイン認証)
DKIM-Signature:  DKIM(送信ドメイン認証)

一方で、だます目的の迷惑メールでは、タイトルなどにお金やアダルトに関するキーワードであったり、有害サイトへのリンクが含まれることが多い。このため、メールソフトやメールサーバで、キーワードやURLの類似性を見て自動的に迷惑メール判定を行うことも多い。

ハッシュ法

2017年12月12日

2分木なども終わって、検索処理のさらなる高速化として、ハッシュ法を説明する。

オープンアドレス法

電話番号が記録されているのかどうかを探す処理を考えると、最も単純な方法は、電話番号を配列の添字にする方法となる。

int array[ 1000000 ] ; // 局番2桁+4桁
void entry( int tel ) {
   array[ tel ] = tel ;
}
int search( int tel ) {
   if ( array[ tel ] == 0 ) // O(1) のアルゴリズム
      return 0 ;
   else
      return 1 ;
}

しかしこの方法では、0778621111 といった番号も考えると、巨大なメモリを必要として、非現実的となる。この際の解決法がハッシュ法で、データ件数が少なければ、例えば電話番号の末尾2桁がおなじデータの発生する確率は低い。もし、電話番号末尾2桁が同じでも、その番号の次の場所に保存するなどすればよい。

#define SIZE 100     // ハッシュ表のサイズ
int hash[ SIZE ] ;   // ハッシュ表
int hash_func( int phone ) {   // hash_func:ハッシュ関数
   return phone % SIZE ;
}
void entry( int phone ) {
int idx = hash_func( phone ) ; // idx:ハッシュ値
   while( hash[ idx ] != 0 )   // データ件数100で無限ループだけど...
      idx = (idx + 1) % SIZE ;
   hash[ idx ] = phone ;
}
int search( int phone ) {
   int idx = hash_func( phone ) ;
   while( hash[ idx ] != 0 ) {
      if ( hash[ idx ] == phone )
         return 1 ;
      idx = (idx + 1) % SIZE ;
   }
   return 0 ;
}

チェイン法

オープンアドレス法では、次の空き場所を探して保存するが、表サイズよりもデータ件数を多く保存することはできない。

表が埋まって、同じハッシュ値のデータがでてきたら、同じハッシュ値どうしをリスト構造で保存する方法はチェイン法と呼ばれる。

struct List *hash[ SIZE ] ; // ポインタはNULLで全て初期化
void entry( int phone ) {
   int idx = hash_func( phone ) ;
   hash[ idx ] = cons( phone , hash[ idx ] ) ;
}
int search( int phone ) {
   int idx = hash_func( phone ) ;
   struct List* p ;
   for( p = hash[ idx ] ;
        p != NULL ;
        p = p->next )
   {
      if ( p->data == phone )
         return 1 ;
   }
   return 0 ;
}

情報構造論はテスト返却

2017年11月30日

情報構造論は、来週不在となるので、授業時間を振り替えてテスト返却を行った。

データベースのテスト返却

2017年11月30日

後期中間試験が終わり、あわてて採点していたデータベースの返却。
来週が不在となるので、課題を出すなら、12/1 17:00 までとアナウンス。

データベースの設計

返却を終え、残り時間は後半の説明。

データベース設計には、概念設計、論理設計、物理設計に分けられる。
概念設計では、データベースによって管理の対象とするものを現実の世界から抽出して設計を行う。一般的にはER図などを描きながら設計を行う。論理設計では、どのようなデータモデルで作成するのかを設計。通常であれば、リレーショナルモデルで概念設計に沿って設計を行う。物理設計では、データベースの効率を考えながら設計を行い、インデックスをどう作成するかなどを設計する。

ER図とは、データの対象で具体的な物や人といった実体(Entity)と、その実体の間の関連(Relation)であらわされるものを、図にして表現したもの。ER図では、実体を長方形、関連をひし形、属性を楕円であらわす。属性のなかでキーとなるものには、下線をつけて表す。ER図の表現には、色々な方式があるが、Peter Chen記法で説明を行う。

このような、プログラム開発での考えを表すための図には、UML(Uniformed Modeling Language)というものもある。ER図は、データ構造を表現するための構造図と、処理を表現する振る舞い図がある。

Peter Chen記法(ER図)

2017年11月22日

データベースのテスト問題を考えるべくWeb閲覧中。授業後半で説明するER図の書き方には様々なものがある。後半の授業用にメモ。

Peter Chen記法：実体を長方形、関連をひし形、属性を角丸長方形で描く最もシンプルな書き方。授業では、この方式で説明している。
IDEF1X(Integration Definition)記法：アメリカ標準技術研究所(NIST)が規格化。
IE(Information Engineering)記法：データベース設計に特化した、ER図表現法

図は、参照元サイトからの引用

家族のGoogleアカウントへの攻撃

2017年11月18日

うちの奥さんに、Google さんから、「あなたのアカウントに台湾からアクセスがありました」といったメールが届く。海外に遊びに行ってるわけでもなく、まずはメール自体が「フィッシングメール」かどうか確かめる。この文面からすると、アカウントにアクセスがあったけど、国外でのアクセスは異常なのでブロックしたという雰囲気。つまり、パスワードが漏れている可能性が高い。

使い回しパスワードは危険

パスワードの使用状況を聞いてみたら、gmail のメールアドレスで、複数の Web サービスを利用していて、そのパスワードが全部同じ。これからすると、使っている Web サービスのどこかで認証情報が盗まれ、そのアカウントで別の Web サービスに侵入が行われたと考えるべき。典型的な、共通パスワード利用者への辞書攻撃。

お金系は2段階認証が必須

ということで、早々に (1)Googleのパスワード変更と2段階認証設定、(2)Google IDと同じパスワードを使っている他のWeb サービスのパスワード変更を行った。特に金融系とか通販でクレジットカードを入力しているものは、特に。ただ、よく使っていたクレジットカードはサービス停止で切り替えたようで、多少は安心。(3)最後に Apple ID, Amazon, Facebook といったものも、2段階認証をONにする。

「講義録」カテゴリーアーカイブ

リンク集

検索・リンク

リモート接続

telnet と rlogin

ssh

リモートデスクトップ

暗号化

暗号化アルゴリズム

パスワード解読方法

攻撃が難しい暗号化へ

公開鍵暗号方式

WWWとhttp

URL

http

サーチエンジン

ディレクトリ型

ロボット型

直接サーバと接続

文字列をキーとするハッシュ

共有のあるデータの取扱い問題

参照カウンタ法

DNSとドメイン名

nslookup の使い方

DNSと階層構造

メール

メールヘッダの読み方

オープンアドレス法

チェイン法

データベースの設計

使い回しパスワードは危険

お金系は2段階認証が必須

投稿ナビゲーション

システム

最新の投稿(電子情報)

アーカイブ

カテゴリー

メタ情報