Zenn
😎

Day 26: 暗号化の仕組みと数学的基盤 - 暗号化の知識

2024/11/23に公開
暗号化
tech

※現在数式の記法(LaTeX記法)が問題で、うまく数式が表示できてない状況です。ZennはKaTeX記法というやつなんですね。https://zenn.dev/zenn/articles/markdown-guide#数式

はじめに

暗号化の世界には、共通鍵暗号化（Symmetric Encryption） と公開鍵暗号化（Asymmetric Encryption） という2つの主要な方式があります。前回これらの暗号化に入門するために概要的に学びましたが、今回はその仕組みを支える数学的基盤に焦点を当て少し理解を深めます。

ここでは暗号化の基礎をより深く理解するために、次の内容を解説していきます：

  • 共通鍵暗号化とAESの数学的基盤
  • 公開鍵暗号化とRSAの数学的基盤

共通鍵暗号化の仕組みとAESの数学的基盤

共通鍵暗号化は、送信者と受信者が同じ鍵を使ってデータを暗号化・復号化する方式です。この方法は処理が高速で、大量のデータを効率よく扱うため、動画配信やオンラインショッピングなど幅広い分野で使われています。中でも代表的なアルゴリズムがAES（Advanced Encryption Standard） です。

AESの安全性は、数学を基盤にした複雑な変換プロセスによって支えられています。以下の3つがその主要な要素です。

1. 置換表（S-Box）による変換

AESの最初のステップでは、S-Box（Substitution Box） を用いてデータを複雑な形に変換します。

S-Boxの役割

  • データの置換:
    データの各部分を、新しい値に置き換えます（例：「AをXに、BをYに」）。これにより、元のデータ構造が見えにくくなります。
  • 非線形性の導入:
    S-Boxは有限体（Galois Field） 上の逆元計算を利用し、非線形な変換を実現します。この非線形性により、データの変換結果がランダム性を帯び、攻撃者が統計的な方法で解読するのが非常に困難になります。
  • セキュリティ向上:
    S-Boxによって暗号文がさらに複雑化され、解読が難しくなります。特に、攻撃者が平文と暗号文の関係を推測する手段が限られるため、統計的な解析や推測を防ぎセキュリティが大幅に向上します。

数学的基盤：有限体（Galois Field）

S-Boxの背後には、有限体（Galois Field） と呼ばれる数学的な仕組みがあります。有限体は、限られた範囲内で計算が行われる特別な空間で、AESでは0～255の整数を扱う( GF(2^8) )が使用されています。

  • 有限体の特徴:
    有限体は、限られた範囲の数字内で四則演算を行う特別な数学的空間です。計算結果が一定の範囲を超えると「巻き戻る」特性を持ちます。これは、時計の針が12時を超えると0時に戻るような仕組みです。

  • 逆元計算の応用:
    S-Boxでは有限体内の逆元計算が使われます。この計算により、元のデータを非線形な形で変換します。

イメージ: S-Boxは「データをシャッフルするルール」と考えるとわかりやすいと思います。シャッフルにより、データ構造が隠され、解読が極めて困難になります。

2. シフトと混合

次に、データの構造を大きく変えるために**Shift Rows（行のシフト）とMix Columns（列の混合）**が行われます。これらは、データ全体のパターンを大きく崩す役割を果たします。

Shift Rows（行のシフト）

各行のバイトを左方向にずらします。行ごとにシフト量が異なり、データの順序が変わります。

  • 例:
    行1: [A, B, C, D] → [A, B, C, D]（シフトなし）
    行2: [E, F, G, H] → [F, G, H, E]（1バイトシフト）
    行3: [I, J, K, L] → [K, L, I, J]（2バイトシフト）
    行4: [M, N, O, P] → [P, M, N, O]（3バイトシフト）

  • 目的: データの位置をずらして、関連性を難読化します。

Mix Columns（列の混合）

有限体上の行列演算を使用して、各列内のデータを混ぜ合わせます。この操作により、データ全体のランダム性がさらに向上します。

  • 目的: 列の各データが他のデータに影響を与えることで、暗号文全体のランダム性をさらに高めます。

イメージ: Shift Rowsは「データを散らす」、Mix Columnsは「データを混ぜ合わせる」と考えると良いと思います。

3. ラウンドキーの生成

AESでは、暗号化処理を複数の「ラウンド（ステップ）」に分けて行います。この際、各ラウンドごとに使用される鍵（ラウンドキー）が異なります。

ラウンドキーとは？

  • 主鍵（Master Key）から生成されるサブ鍵です。各ラウンドで異なるラウンドキーを使用することで、暗号化の安全性をさらに向上させます。
生成の仕組み
  • S-Boxを利用した非線形変換: 主鍵の一部をS-Boxに通して変換します。
  • XOR演算: ラウンドごとに異なる定数（Rcon）を加え、鍵にランダム性を導入します。
  • ビット操作: 主鍵を分割して加工することで、新しいラウンドキーを生成します。

イメージ: ラウンドキーの生成は、元となる1つの鍵を複数の工場で加工し、それぞれがラウンドで使用する異なる鍵を作る仕組みと考えると良いと思います。

公開鍵暗号化の仕組みとRSAの数学的基盤

公開鍵暗号化は、送信者と受信者が異なる鍵を使用する方式です。この仕組みは、鍵を事前に安全に共有する必要がないため、通信の安全性を大幅に向上させました。その代表的なアルゴリズムである**RSA（Rivest-Shamir-Adleman）は、素因数分解問題の困難さとモジュラ演算（剰余計算）**という数学的基盤に基づいています。

1. 素因数分解の困難さ（素因数分解問題）

RSAの安全性は、大きな整数を素因数分解することが困難である点に依存しています。

  • 基本原理:
    • 2つの大きな素数 ( p ) と ( q ) を掛け合わせて得られる ( n = p \times q ) を計算するのは簡単ですが、この ( n ) を元に ( p ) と ( q ) を求めるのは非常に難しいです。
  • 例:
    • 小さい場合: ( 15 = 3 \times 5 )（簡単）
    • 大きい場合: 数百桁の ( n ) を分解するには、スーパーコンピュータでも数千年かかることがあります。

2. モジュラ演算

モジュラ演算とは、数を割った余りを求める計算方法です。RSAでは、このモジュラ演算が鍵生成と暗号化・復号化に使用されます。

  • 暗号化:
    ( C = M^e \mod n )（公開鍵を使用）
  • 復号化:
    ( M = C^d \mod n )（秘密鍵を使用）

RSAでは、鍵生成や暗号化・復号化にモジュラ演算が使われます。モジュラ演算とは、数を割った余りを求める計算方法です。モジュラ演算は有限体の概念に関連しており、特定の範囲内で計算が完結します。

  • 基本的な例:

    • ( 7 \mod 3 = 1 )（7を3で割ると余りが1）
    • ( 10 \mod 4 = 2 )（10を4で割ると余りが2）

  • RSAでの応用:

    • 暗号化: ( C = M^e \mod n )（公開鍵を使う）
    • 復号化: ( M = C^d \mod n )（秘密鍵を使う）
      • ( M ): 平文、( C ): 暗号文、( e, d ): 公開鍵と秘密鍵の値、( n = p \times q )

鍵の生成

RSAの鍵生成には、次のステップが含まれます：

  1. 2つの大きな素数 ( p ) と ( q ) を選ぶ。
  2. ( n = p \times q ) を計算。
  3. オイラーのトーシェント関数 ( \phi(n) = (p-1)(q-1) ) を求める。
  4. 公開鍵 ( e ) を選び、秘密鍵 ( d ) を次の条件で計算：
    [
    e \cdot d \mod \phi(n) = 1
    ]

公開鍵暗号化の課題

RSAは素因数分解問題に依存していますが、量子コンピュータの登場によってこの基盤が揺らぐ可能性があります。量子コンピュータの発展によって、この問題を効率的に解くアルゴリズムが実現する可能性があるからです。暗号化の安全性が脅かされないよう、量子耐性暗号（Post-Quantum Cryptography） の研究が進められています。

小テスト

Q1: AESの暗号化プロセスで、データの構造を複雑化するために行われる操作は次のうちどれですか？

a) 素因数分解
b) シフトと混合（Shift Rows, Mix Columns）
c) オイラーのトーシェント関数の計算
d) 公開鍵と秘密鍵の交換

Q2: RSA暗号の安全性は何に依存していますか？

a) データの高速な暗号化
b) 素因数分解の困難さ
c) モジュラ演算の速さ
d) 鍵の長さの一致

Q3: AESで使用されるS-Boxの数学的基盤は何ですか？

a) 素因数分解
b) 有限体（Galois Field）
c) 公開鍵と秘密鍵の交換
d) モジュラ演算

Q4: RSA暗号で使用されるモジュラ演算とは何ですか？

a) 2つの数値を足す計算
b) 数を割った余りを求める計算
c) 特定の多項式を使用した置換
d) 平文を直接暗号文に変換する計算

Q5: 公開鍵暗号化が共通鍵暗号化に比べて優れている点は何ですか？

a) 処理が高速である
b) 鍵の安全な共有が可能である
c) データの複雑化が不要である
d) 大量データの暗号化に適している

Q6: AESのラウンドキーはどのように生成されますか？

a) 素因数分解を用いて生成される
b) 主鍵を加工してラウンドごとに異なる鍵を生成する
c) 公開鍵と秘密鍵を合成して生成する
d) モジュラ演算のみで生成される

解答

  1. b) シフトと混合（Shift Rows, Mix Columns）

    • AESでは、Shift RowsとMix Columnsの操作でデータの構造を大きく変化させ、解読を困難にします。

  2. b) 素因数分解の困難さ

    • RSA暗号の安全性は、非常に大きな数を素因数分解するのが困難であることに依存しています。

  3. b) 有限体（Galois Field）

    • S-Boxは有限体の逆元計算を利用して構築されており、AESの暗号化プロセスを支えています。

  4. b) 数を割った余りを求める計算

    • RSAでのモジュラ演算は、鍵生成や暗号化・復号化の基盤となる計算です。

  5. b) 鍵の安全な共有が可能である

    • 公開鍵暗号化では、鍵を事前に共有する必要がなく、より安全な通信が可能です。

  6. b) 主鍵を加工してラウンドごとに異なる鍵を生成する

    • AESのラウンドキーは、主鍵を基にS-BoxやXOR演算を用いて生成されます。

まとめ

今回の投稿では、前回の内容を振り返りつつ、暗号アルゴリズムの数学的な基盤について詳しく解説しました。暗号化は量子コンピュータの登場など、新しい技術の進化に対応し続ける必要がある分野です。

これらのアルゴリズムは、専門家たちが研究を重ねて作り上げたもなため「難しい」と感じるのは当然な範囲だと思います。そもそも、専門家でもない人が難しいと感じないのはセキュリティ的に良くないでしょう。それでも、深く理解したい場合は、数学、統計学、暗号学といった基礎を少しずつ学んでいく必要がありますが、その範囲は個人的にもよくわからないだらけな為、後に機会があれば投稿しようと思います。

次回の投稿では、暗号化とは異なる「ハッシュ」について掘り下げていきます。

Discussion