はじめに
本記事では、基本情報技術者試験の学習を通じて、特に頻出かつ理解に苦労した分野を整理し、アウトプットを兼ねてまとめています。
アルゴリズムとプログラミング
基本情報技術者試験では、以下のアルゴリズムが出題される
- 整列アルゴリズム（データを並べるためのアルゴリズム）
- 探索アルゴリズム（データを見つけ出すためのアルゴリズム）
- 再帰的アルゴリズム（処理の途中で自分自身を呼び出すアルゴリズム）
整列アルゴリズム
データを特定の順番に並べるアルゴリズム
ソートアルゴリズムとも呼ばれる
主な整列アルゴリズム
| 種類 | 解説 |
|---|---|
| バブルソート | 配列の先頭から順に隣り合ったデータを比較して、順序が間違っていたら交換することを繰り返すアルゴリズム |
| 選択ソート | 配列の先頭から順に、データを比較して最小値を選択し、選択した最小値を先頭のデータと交換することを繰り返すアルゴリズム |
| 挿入ソート | 整列済みの要素を持つ配列に対して、未整列のデータを適切な場所に挿入するアルゴリズム |
| クイックソート（頻出） | 「基準値よりも小さいグループ」と「基準値よりも大きいグループ」の2つに分け、分けたグループに対しても同じ手順を繰り返すアルゴリズム |
探索アルゴリズム
特定のデータを見つけ出すアルゴリズム
主な探索アルゴリズム
| 種類 | 解説 |
|---|---|
| 線形探索法 | 先頭のデータから順番に1つずつ照合することで目的のデータを見つける、単純な探索アルゴリズム |
| ハッシュ法（頻出） | ハッシュ表を使って目的のデータを見つける探索アルゴリズム |
| 2分探索法（頻出） | 調べる範囲を半分に切り分けながら目的のデータを見つける探索アルゴリズム |
ハッシュ法
ハッシュ関数を使って探索対象のデータをハッシュ値に変換
ハッシュ値を指定してハッシュ表（ハッシュ値を要素番号とした配列）から目的のデータを取り出す
ハッシュ法のデメリット
衝突
入力値が異なるのにハッシュ値が同じ値になってしまうことがある
2分探索法
特徴
- データをあらかじめ昇順か降順で整列させておく必要がある
- データを2つに分けながら探索する
配列の中から中央の要素を見つけて探索対象と比較することを繰り返す
再帰的アルゴリズム
処理の途中で自分自身を呼び出すことを再帰呼び出しという
再帰的アルゴリズムの用途
| 種類 | 解説 |
|---|---|
| 総和 | 与えられた数全ての合計、数式では「Σ」で表す |
| 剰余 | 割り算の余り、「mod」を用いて表す |
| 階乗 | 1からnまでの全ての整数を掛け算した数、「3の階乗」は「3!」と表す |
アルゴリズムの計算量を算出する問題
異なるアルゴリズムであっても、結果が同じになるならば、実行時間が短く、メモリの使用量が少ないアルゴリズムの方が優秀
→アルゴリズムの計算量を算出することで、最適なアルゴリズムを見つける
オーダー（計算量）
アルゴリズムを完了するために必要な計算量をオーダーという
データ数と計算量の関係を表す記法のことを「オーダー記法」という
オーダー記法
O（計算量）
例えば、データの数nが2倍、3倍になった際に計算量が2倍、3倍になる場合、「O(n)」となる
なお、オーダーは「これ以上大きくならない」という「最大の計算量」を表す
アルゴリズムのオーダー
| アルゴリズム | オーダー記法による計算量 |
|---|---|
| ハッシュ法 | O(1) |
| 2分探索法 | O(log₂n)もしくはO(log n) |
| 線形探索法 | O(n) |
| クイックソート | O(n log n) |
情報セキュリティ
基本情報技術者試験では、暗号化技術とデジタル署名が頻出
暗号化技術とは
- 平文 暗号化前の文章
- 暗号化 平文を暗号文にすること
- 復号 暗号文を平文に戻すこと
共通鍵暗号方式
暗号化と復号で共通鍵(同じ鍵)を使う暗号化方式
共通鍵暗号方式の欠点
相手に確実・安全に共通鍵を送る方法がない
公開鍵暗号方式
公開鍵と秘密鍵の2つの鍵を使う暗号化方式
- 公開鍵 いくつでも複製できる、誰でも入手できる鍵
- 秘密鍵 1つしかない、自分以外の誰にも知られてはいけない鍵
公開鍵暗号方式の仕組み
公開鍵暗号方式では、公開鍵を使って平文を暗号化し、暗号文は秘密鍵を使って復号する
重要
公開鍵暗号方式における暗号化と復号は「ペアとなった鍵」でしか行えない
公開鍵暗号方式で文章を送る場合
- 受信者がペアとなる2つの鍵(公開鍵と秘密鍵)を作る
- 公開鍵は公開して全員に渡し、秘密鍵は受信者のみが自分で保管する
- Aが公開鍵を使って文章を暗号化し、暗号文を送信
- Bが秘密鍵で復号
公開鍵暗号方式の欠点
誰でも暗号化できることによるなりすまし
→「なりすまし」を防ぐための技術が、「デジタル署名」
共通鍵方式に比べて、暗号化と復号に時間がかかる
ハイブリッド暗号方式
共通鍵暗号方式と公開鍵暗号方式を組み合わせて使う暗号化方式のこと
2つの方式を組み合わせることで、大量データを高速に暗号化(共通鍵暗号方式の長所)でき、安全に鍵を送る(公開鍵暗号方式の長所)ことができる
ハイブリッド暗号方式の仕組み
1.送信者は、共通鍵を使って文章を暗号化
2.共通鍵を公開鍵で暗号化して相手に送信
3.受信者は秘密鍵で共通鍵を復号し、共通鍵を使って暗号文を復号
デジタル署名
デジタル署名とは、公開鍵暗号方式を使って、データに電子的に署名を行うこと
デジタル署名の大原則
- 秘密鍵で暗号化した文章は、ペアとなる公開鍵でしか復号できない
公開鍵暗号方式と比べ、秘密鍵と公開鍵の位置が入れ替わっている
- 公開鍵暗号方式：「誰でも暗号化でき、特定の人のみ復号できる」
- デジタル署名：「特定の人のみ暗号化でき、誰でも復号できる」
ハッシュ関数とダイジェスト
デジタル署名を理解するためには、前提として「ハッシュ関数」と「ダイジェスト」について知っておく必要がある
ハッシュ関数
文字列を入力すると、一定の長さの値を出力する関数
- 同じ文字列を入力する限り、必ず同じ値が出力される
- 入力する文字列が少しでも異なると、出力される値は大きく異なる
ダイジェスト
ハッシュ関数によって出力される値
-
データサイズは一般的に256桁などの固定長のビット列
-
ダイジェストを元のメッセージに戻すことはできない
SHA
ハッシュ関数のアルゴリズム
現在はSHA-2が一般的
SHA-2のうち、256ビットの長さのダイジェストを出力するハッシュ関数のアルゴリズムをSHA-256という
デジタル署名の特徴
デジタル署名を利用すると、文章の作成者(文章を暗愚化した人)を特定できる
したがって、
- 「なりすまし」の検知
- 「内容の改ざん」の検知
ができる
認証局
データに付与されているデジタル署名が、署名者本人のものであることを証明する第三者機関であり、公開鍵の所有者が本人であることを証明するデータである、「デジタル証明書」を発行する
基本情報技術者試験では、認証局のことを「CA」と表記する場合もある
PKI
認証局を使って「なりすまし」を防ぐ仕組みのことを「PKI」という
PKI(公開鍵基盤)とは、公開鍵暗号方式や、デジタル署名で使用する「公開鍵」の持ち主を保証するためのインフラ(基盤)のこと
終わりに
アウトプットとしてまとめることで、学習の中で曖昧だった知識を整理でき、理解がより深まったと感じています。基本情報技術者試験は出題範囲が広く、すべてを完璧に理解するのは難しいですが、こうして一つひとつ整理し直すことで少しずつ力がついていくと思います。
今後も過去問演習や参考書を通じて知識を定着させながら、試験の合格に向けて取り組んでいきます。同じように学習している方にとっても、この記事が復習や理解のきっかけになれば嬉しく思います。