ホーム » 2018 (ページ 17)
年別アーカイブ: 2018
ガベージコレクタと演習(ハッシュ法)
ハッシュ法について演習ができていなかったので、前半座学(ガベージコレクタ)と後半演習(ハッシュ法)
ガベージコレクタ
前回、malloc などで使用を終えたデータを free で開放する際に発生する問題について説明し、その問題の解決法として参照カウンタ法を説明した。しかし、参照カウンタ法は循環リストなどが含まれる場合、free で開放できない状態が発生する場合があることを説明した。
このため、malloc で確保したデータ領域を、free で開放する処理は、複雑なデータ構造の場合かなり処理の記述が大変になる。
そこで最近のプログラム言語では、ガベージコレクタがある。この方法では、プログラムが malloc で確保した動的データ領域は、データが不要となっても開放処理 free は行わない。
しかし、このままでは、不要となったデータ領域がメモリに溢れ、メモリ不足が発生してしまう。そこで、一定量のメモリを使い切ったら、不要なメモリ(ゴミ=ガベージ)を回収(コレクタ)する。
マーク&スイープ法
ガベージコレクタの方法には、色々あるが、マーク&スイープ法では、
- 処理を一旦停止し、
- 動的メモリの領域すべてに「未使用マーク」をつける。
- 実際に使用している変数や、その変数が指している領域には「使用中マーク」をつける。
- マーク処理が終わったら「未使用マーク」の付いているデータは誰も使っていないので回収する。
他にも、コピー法といった方法もあるが説明は割愛する。
上で述べた様に、ガベージコレクタはプログラムを一旦停止し、全動的メモリ領域を検査するという手間のかかる作業を行うため、通常は「一時的にプログラムが止まる」ことからリアルタイムに処理を行うような場合には、極めて不都合が多い。
このため、最近では参照カウンタ法の技術なども取り入れ、局所変数は参照カウンタ法の技法を中心に回収し、大域変数はガベージコレクタの技法で回収する。
CやC++言語では、ガベージコレクタは基本的には利用できず、ガベージコレクタが取り入れられた言語としては、Java が有名。Java では、ガベージコレクタが実装されているため、通常のプログラミングでは、free や delete といった処理は不要である。しかし、処理速度や突発的な一時停止を避ける場合には、適切なタイミングで変数に null を代入するといった処理を明記するなどのテクニックが重要となる。
局所変数とスタック
局所変数は、関数に入った時に作られるメモリ領域であり、関数の処理を抜けると自動的に開放されるデータ領域である。
関数の中で関数が呼び出されると、スタックには戻り番地情報を保存し、関数に移動する。最初の処理で局所変数領域が確保され、関数を終えると局所変数は開放される。
この局所変数の確保と開放は、最後に確保された領域を最初に開放されることから、スタック上に保存される。
演習(ハッシュ法)
ハッシュ法のプログラム(オープンアドレス法もしくはチェイン法)を用いて、
(1)名前と電話番号,(2)名前と住所,(3)名前と誕生日について、名前をキーとして検索するプログラムを作成せよ。
「出席番号 % 3 + 1」の番号のテーマに取り組むこと。
レポートを作成する際には、ハッシュ関数を変更してどういった変化があるか確認せよ。
ハッシュサイズは、10〜20件程度で良い。
高専ライブ:2018年1月14日(第559回)
- 学習到達度試験の話
- 風邪予防の話
- サイエンス共和国 第20回 「煮物に味がしみる話」
- 冬の定番の話
- センター試験・進路の話
担当:中島(3C,MC)、川﨑(4EI)、西島(3EI,MIX)、中村(教員)
2段階認証のGoogle設定例
Googleでの2段階認証の設定方法は、以下の通り。(2018年1月での画面)
2段階認証の設定
Google の右上の「アカウント」のを選択すると、ログインとセキュリティの設定画面となる。
パスワードの設定画面の中の、2段階認証プロセスをクリックして設定を行う。
2段階認証の設定を行うと以下のような画面となり、現在のパスワード・携帯電話の番号などを入力する。
テキストメッセージを選ぶと、携帯電話のSMS(ショートメッセージ)で6桁の数字によるワンタイムパスワードが送られてくるので、それを入力することで設定が完了する。
認証アプリの設定
Google の2段階認証には、いくつかの方法があるが、最も簡単な方法は、”Google アプリ”をスマートフォンにインストールしておく方法。
Googleアプリ
この場合、2段階認証が必要になると、”Google アプリ“から「ログインしようとしていますか?(はい/いいえ)」と表示されるので、スマホ画面で「はい」を入力すれば良い。
Google認証システム
もう一つの方法が、Google 認証システムを使う方法。この方法は、時間(分単位)で変化するワンタイムパスワードを入力する方式。
最初に、Google 認証システムを使うためのQRコードが表示されるので、Google認証システムアプリで読み取ると、ワンタイムパスワードが表示されるようになる。
2段階認証のTwitter設定例
Twitterの2段階認証の設定は、以下の通り。(2018年1月時点)
最初に、パソコンのTwitterの画面右上のプロフィールと設定より、「設定とプライバシー」を選択。
このなかのセキュリティの欄の「ログイン認証を設定」をクリック。
2段階認証で、ワンタイムパスワードが送られてくる携帯電話の番号を登録する。
電話番号を記入し「コードを送信」を選ぶとショートメッセージで6桁のワンタイムパスワードが送られてくるので、それを入力する。
携帯電話を紛失すると、ログインができなくなるので、その非常事態用に、最終手段のバックアップコードが表示される。このログイン時のパスワードで、バックアップコードを入力すればログインできる。
このバックアップコードは重要なので、必ずどこかに保存しておくこと。
リモート接続と暗号化
リモート接続と暗号化について説明
リモート接続
サーバなどの管理をしていると、インターネットの先にあるコンピュータを操作したい場合が多い。こういった場合には、リモート接続機能を用いる。
リモート接続による相手側のコンピュータを操作する場合、相手側のコンピュータには リモート接続 用のサーバプログラムを起動しておく。こういったリモート接続を利用するのは、”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とした場合、数字だけ(10N)とか英字だけ(26N)といった組み合わせでは、短時間に解読されてしまう。数字,大文字,小文字,記号などを交えたパスワードが理想。
- 英単語辞書を用いた辞書攻撃:パスワードが長い場合、文字列の全ての組み合わせを試すには長い時間が必要となる。しかし、パスワードはユーザが記憶して使うことから覚えやすい単語が使われる。このため英単語辞書の文字を組み合わせることで、解読時間を短くできる場合がある。
- 漏えいパスワードによる辞書攻撃:サーバへのリモート接続などができてしまった場合、パスワード情報が盗まれる場合がある。この時、別なサイトに同じパスワードを使っていると、その漏えいしたパスワードで別のサイトも接続ができてしまう。これらのことから、同じパスワードを使いまわすことは避けるべきである。
- ソーシャル攻撃:パスワードには、簡単に覚えられるように自宅の電話番号、誕生日、家族の名前といったものを使う人が多い。このため、SNS で相手に友達登録をしてもうことで、こういった情報を手に入れ、パスワードを破る方法。最近の有名人の個人情報漏洩はこの手の攻撃が多い。
ソーシャル攻撃は、元クラッカーケビン・ミトニックが有名
攻撃が難しい暗号化へ
先に述べたような、login に使うパスワードなどは、ブルートフォース攻撃をうけると解読は時間の問題となる。これらの対策として毎回違う鍵(パスワード)を使えばいい。
- 暗号表:置換式で読み取られるのを防ぐために、置換する文字の表を沢山作っておき、別の方法でその度毎に置換表を変更する
- ワンタイムパスワード:使い捨てのパスワードをあらかじめ沢山作っておき、接続の度に次のパスワードを用いる方式。あるいは、時間から特殊な計算方法で生成されるパスワード。時間と共に変化するのでその度毎に違うパスワードとなる。毎回違うパスワードを入力するため、パスワード表を常に持ち歩いたり、入力が面倒なので数字だけを使うことが多く、この方法だけでは使いにくい。
公開鍵暗号方式
以前に使われていた暗号化の方式は、暗号化の鍵と復号化の鍵に同じものを用いる共通鍵方式であった。
しかし、この鍵をどうやって相手に渡すか…が問題となっていた。(鍵を相手に渡す瞬間のデータを盗聴されると危険)
このため、最近では公開鍵暗号方式が中心となっている。この方式は「暗号化するため専用の公開鍵」と、「暗号化を復号するための秘密鍵」をペアにして用いる。公開鍵は、暗号化するため専用なので、この鍵が他の人に見られても、暗号を復号することはできない。
公開鍵暗号方式では、RSA などが最も有名で現在広く利用されている。
高専ライブ:2018年1月7日(第558回)
新年あけましておめでとうございます。本年も高専ライブをよろしくお願いいたします。
- 年越しの瞬間の話
- お正月の話
- サイエンス共和国 第19回 「クオーツ時計の話」
- 冬休みの話
- 今年の抱負
担当:坂田(F1,MC)、越後(2E,MIX)、木村(F3)、山野(F3)、西(教員)