個別通信プロトコルとその脆弱性(第3回)/通信の符号化と暗号化

## はじめに

* プログラミング初学者向けに
* 通信の符号化、符号化の一種としての暗号化を学び
* 公開鍵暗号方式の理論と実態を小さな数で計算し
* RSA暗号方式を使用するSSHの実践的な利用方法を学ぶ

### まとめと前回予告

これまで学んできたDNSやメール送受信は、多くの場合、情報が平文のまま流れていました。

次回は、通信内容を守るための**暗号化**技術に焦点を当てます。題材は「SSH」

遠くのコンピュータに安全にログインする仕組みを体験しながら、「通信を盗み見られないようにするとはどういうことか」を深く学びます。

第3回は、符号化と符号化の延長として暗号化を学びます。どうやって秘密の通信が成立するのでしょうか？

---

## 3-1. 秘密の通信の比喩

> コンピュータ同士が会話をしているとき、その内容が誰にでも聞こえてしまうとしたらどうでしょうか？ たとえば、廊下で大声で話しているようなものです。盗み聞きされても仕方ありません。
> 
> 
> では、他の人にはわからない「秘密の言葉」で会話していたら？ それが「符号化」と「暗号化」の世界です。
> 
> 今回は、「伝えたいことを守る」ための仕組みを、実習を通じて理解していきます。

---
## 3-2. 符号化と暗号化の基本

| 項目 | 内容 |
| --- | --- |
| **What** | 符号化（エンコード）とは、情報を決まったルールで別の形に変えること。暗号化（エンクリプション）とは、第三者に読めないように情報を保護すること。 |
| **Why** | データを他のシステムで扱いやすくする（符号化）、あるいは盗まれても読めないようにする（暗号化）ために必要。 |
| **How** | 符号化は誰でも元に戻せるが、暗号化は「鍵」がないと復号できない。用途と目的が異なる点に注意。 |

### 符号化の例：モールス信号表（アルファベット）

モールス信号は、アルファベットや数字を「・（短点）」と「－（長点）」の組み合わせで表す符号です。これはまさに「情報を別の形に変換する」＝符号化の一種です。

| 文字 | モールス信号 | 文字 | モールス信号 | 文字 | モールス信号 |
| --- | --- | --- | --- | --- | --- |
| A | ・－ | B | －・・・ | C | －・－・ |
| D | －・・ | E | ・ | F | ・・－・ |
| G | －－・ | H | ・・・・ | I | ・・ |
| J | ・－－－ | K | －・－ | L | ・－・・ |
| M | －－ | N | －・ | O | －－－ |
| P | ・－－・ | Q | －－・－ | R | ・－・ |
| S | ・・・ | T | － | U | ・・－ |
| V | ・・・－ | W | ・－－ | X | －・・－ |
| Y | －・－－ | Z | －－・・ |  |  |

モールス信号を発呼する器械: 電鍵; [出典:Wikipedia:電鍵](https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A1%E3%82%A4%E3%83%AB:J38TelegraphKey.jpg) 
> ![電鍵](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/192607/419dd12b-328d-4c42-93b6-4cafbb74fc7e.png)


左の枝が短点、右の枝が長点: モールス符号木; 出典: [roombaの日記/モールス符号の地図](https://roomba.hatenablog.com/entry/2015/07/29/150803)

> ![モールス符号木](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/192607/8d7cfdb4-4e2d-4f00-8844-1436eafdccbc.png)


このように、モールス符号化では文字を一定のルールで別の記号列に変換しています。誰でもそのルールを知っていれば復元可能です。これが**符号化（エンコード）** の本質です。

- 長短長さがある可変長の符号の場合は、長さnの符号は2^{n+1} -2 の文字を表せます
- 各文字の出現数が多いものに短い符号を、少ないものに長い符号を割り当てると、同じ情報を少ない符号で表すことができる。これを情報の**圧縮**といいます
- 短点・長点ではなく、旗の位置を符号とする信号は手旗信号です
    - 符号単体の情報量が多ければ(モールス信号は2通り、手旗信号は21通り)、符号長はその分短くできます
    
> 引用: [海上自衛隊/手旗でメッセージ](https://www.mod.go.jp/msdf/special/flag/)
>![手旗信号](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/192607/2b6afb5e-c79a-475b-a43d-17c89b7651ee.png)

    
- また、信号は誤って伝えられることもあり、**誤り訂正符号**を付加して伝送情報を冗長化することもあります
- 暗号化も符号化の一種

---

## 3-3. 実習：符号化と暗号化を体験する

### 実習1：Base64での符号化

- 文字列「hello」をBase64でエンコードすると → `aGVsbG8=` になる

```bash
$ echo 'hello' | base64 - 
aGVsbG8-
```

- 逆に復号（デコード）して元の言葉に戻ることを確認

```bash
$ echo 'hello' | base64 - | base64 -d -
hello
```

### 実習2：簡単な暗号で体験（シーザー暗号）

- アルファベットを3文字ずらして[暗号化](https://dencode.com/ja/cipher/caesar)（A→D, B→E, C→F...）
- 暗号鍵＝「何文字ずらしたか」がわからないと読めないことを体験

---

## 3-4. 暗号化と復号化: 公開鍵と秘密鍵の仕組み

### 比喩：箱と鍵の物語

> 誰でも開けられる「郵便受け」に手紙を入れることはできるが、取り出せるのは鍵を持っている本人だけ。 これが公開鍵（誰でも使える）と秘密鍵（本人だけが持つ）の関係です。
> 
> 
> 送り手は受け取り手の「公開鍵」で箱を閉じ、本人だけが持つ「秘密鍵」でしか開けられない。
> 

### 暗号化と復号化の基本式

公開鍵暗号の中でもRSA暗号方式の数学的正当性を理解するために、まず暗号化と復号化の基本構造を確認します。

暗号化：

$$
c = m^e \bmod n
$$

復号化：

$$
m = c^d \bmod n = (m^e)^d \bmod n = m^{ed} \bmod n
$$

ここで重要なのは、**復号結果が $m$ に戻るためには $ m^{ed} \bmod n = m$  を満たす$e,d$のペアが必要**ということです。

つまり、$m$をある回数$ed$分べき乗して$n$で割ると$m$に戻るということです。本当にそんな$e,d$のペアが存在するのでしょうか？

### フェルマの小定理

RSA暗号方式を理解するために、まずフェルマの小定理を紹介します。

**フェルマの小定理：**

素数 $p$ と、$p$ と互いに素な整数 $a$ に対して、

$$
a^{p-1} \bmod p = 1
$$

この式は「$a$ を $p−1$ 回かけると $1$ になる（$\bmod p$ の世界で）」という意味です。

$a$の$p$乗なら次の通りです。

$$
a^p \bmod p = a \bmod p
$$

つまり、$p$が素数であれば、$a$ の $p$ 乗は $a$ に戻るのです。

これは、暗号化された内容を復号化すると元に戻るという RSA暗号方式の復号化に似ています。

$a=3, p = 7$のとき：

```math
\begin{array}{cl}
3^6 \bmod 7 &= 729 \bmod 7= 700 + 28 + 1 \bmod 7 =1  \\
3^7 \bmod 7 & = 3
\end{array}
```

次の表は、素数 $p = 7$ のとき、$a$ を $1〜6$ まで変化させて $a^6 \bmod 7$ の値を求めたものです。 すべての $a$ について $a^6 \bmod 7 = 1$  が成立することがわかります。$a$を$7$で割った余りは必ず$0～6$になります。必ずです。$a$は$p$で割って余りが$0$の時は$a$と$p$が素であるという条件を満たさないのでこの表には現れません。

| $a$ | $a^6$ | $a^6 \bmod 7$ |
| --- | --- | --- |
| 1 | 1 | 1 |
| 2 | 64 | 1 |
| 3 | 729 | 1 |
| 4 | 4096 | 1 |
| 5 | 15625 | 1 |
| 6 | 46656 | 1 |

これがフェルマの小定理の実例です。 「素数 $p$ に対して、$a$ を $p−1$ 回かけると $1$ になる（$\bmod p$ の世界で）」という性質が、確かに成り立っていることが確認できます。

さて、ここで、$p$が素数であるという条件がなくなった場合にはどうなるのでしょうか？つまり、**$p$が素数でない場合として、ある素数と別の素数$q$の積$n$になっていると考えてみましょう**。これは、

$$
a^x \bmod n (=pq) = 1が成り立つxが存在するか？
$$

と考えることです。実はこの条件は、$a$ を$m$と書くと、RSA暗号方式の復号化に直結する話です。

この$x$はよく考えると存在することがわかります。フェルマの小定理は素数$p$に対して$p－1$回べき乗すると1になるのでした。この$n＝pq$の場合は、素数$p$に対して$p－1$回べき乗すると$1$になる場合と、$q$に対して$q－1$回べき乗すると$1$になる場合の、両方の組み合わせの回数分べき乗すると$1$になります。つまり、

$$
a^{(p-1)(q-1)} \bmod n = 1 
$$

です。これをオイラーの定理といいます。

---

### オイラーの定理

RSA暗号方式では、復号化で元に戻すために重要なのが、**オイラーの定理** です：

$$
n と互いに素な整数 m に対して、 m^{(p-1)(q-1)} \bmod n (=pq) = 1
$$

もし $ed = k (p-1)(q-1) + 1$（ある整数 $k$）ならば、

```math
\begin{array}{cl}
m^{ed} \bmod n & = m^{k(p-1)(q-1)+1} \bmod n= m(m^{k(p-1)(q-1)}) \bmod n \\
 & = m(m^{(p-1)(q-1)})^k \bmod n = m 1^k =  m 
\end{array}
```

となり、**復号化すると m に戻る** ことが「オイラーの定理に基づいて」成立します。

公開鍵暗号のRSA暗号方式は、数学的にペアとなる「鍵」$(e, n)$と$(d, n)$を使うことで、安全な通信を実現しています。

---

### RSA暗号方式の例

1. 素数を選ぶ：$p = 5, q = 11$
2. $n = p × q = 55$
3. $\phi(n) = (p-1)(q-1) = 4 × 10 = 40$
4. $e$ を選ぶ（$\phi(n)$と互いに素なもの）：$e = 3$
5. $d$ を求める：$e d \bmod 40 = 1$ → $d = 27（3×27 \bmod 40 = 81 \bmod 40 = 1）$

→ 公開鍵：($e = 3, n = 55$)、秘密鍵：($d = 27, n = 55$)

暗号化と復号：

- 暗号化：

$$
c = 12^3 \bmod 55 = 1728 \bmod 55 = 23
$$

- 復号化：
$$
m = 23^{27} \bmod 55 = 12
$$

→ **暗号化して復号化すると元に戻る**ことが確認できます。

---

### 安全性の根拠

- オイラー関数 $\phi(n)$ は、$n$ と互いに素な数の「個数」を表す
- $\phi(n)$ の計算は、$n$ が素数や素数の積である場合は簡単にできる
- しかし、$n$ が巨大な合成数である場合、$\phi(n)$ を求めるには $n$ の素因数分解が必要になる

> つまり、$n$ から $p, q$ を求めることが困難であるという性質が、RSA暗号の安全性の基礎
 
- 公開鍵$(e, n)$は誰でも知ってよい
- 秘密鍵$(d)$は、$\phi(n)$ を知っていないと計算できない
- $\phi(n)$ を知るには $n$ の素因数分解が必要

これが「ペアでないと開かない」「ペアかどうかは数学的に決まっている」理由です。

また、公開鍵暗号は「電子署名」にも応用されます：

- 秘密鍵で暗号化（署名）したデータは、対応する公開鍵で検証できる
- 本人しか秘密鍵を持っていないため、デジタル署名として成立する

### n = pq の素因数分解が重要なのはわかった、しかし、e, d はどうやって設定すればいいのか？

いま、$n = pq$ の時、$ed = k(p-1)(q-1) + 1$ の関係が成り立つから、暗号化されたメッセージが復号できるといいました。ここで、改めて $d = x , k = -y , φ(n) =(p-1)(q-1) = f$ と置き換えると、

$$
ex = -yf + 1
$$

さらに移行すると：

$$
ex + fy = 1
$$

これは、$x$ と $y$ に関する **一次不定方程式** です。

この方程式は、$e$ と $\phi(n) = f$ が **互いに素** であるなら、**必ず整数解 $(x, y)$ を持ちます**。このときの $x$ が、RSAにおける秘密鍵 $d$ になります。

一次不定方程式 $ex + fy = 1$ の解は、最大公約数を求める手続きによって求めることができます。最大公約数は、二つの数のうち、大きな数を小さい数で割って余りを求め、あらたな余りが1になるまで繰り返せばいいのでした。

$e = 3, f = 40$ の時、$f = 39 + 1 = 3*13 + 1$

ということは、元の式を変形すると、$3x + 40y = 3x + (3*13 + 1)y = 3(x + 13y) + y = 1$

ここで、$x + 13y = i,  3i + y = 1$ なら、$y＝－3i+1$

さらに、$x + 13(-3i+1)=i$ となるので、$x = 13(3i -1 ) +i = 40i - 13$

つまり、$x$と$y$は変数$i$で表せる。$x＝40i-13, y = -3i + 1$ となる。この式で$i$が$1$の時、$x$は$27$である。

いま、最初に $d = x$ と変数を置きなおしたから、この $x = 27$ は、$d = 27$ と同じです。

---

**一連の計算まとめ：**

$e = 3, φ(n) = 40$ のとき：

1. $3x + 40y = 1$ を解く
2. $φ(n) = 40 = 3 × 13 + 1 → 3(x + 13y) + y = 1$
3. $i = x + 13y$ とおくと：
    - $3i + y = 1 → y = -3i + 1$
    - $x = i - 13y = 40i - 13$
4. よって：
    - $x = 40i - 13$
    - $y = -3i + 1$
5. $i = 1$ のとき：
    - $x = 27, y = -2$
    - 最小の正の整数解 $x = 27$ が得られる

→ これが秘密鍵 $d = 27$ になるというわけです。

---

## 3-5. SSH：公開鍵暗号の実践的活用

> 公開鍵と秘密鍵の理論がわかったところで、実際にこの仕組みを使って安全な通信を行うしくみとして「SSH（Secure Shell）」を紹介します。
> 

| 項目 | 内容 |
|:-:|-|
| What | SSH は、ネットワーク越しに別のコンピュータに安全に接続するための仕組みです。特に、ログイン（リモートシェル）やファイル転送などでよく使われます。 |
| Why | 従来の Telnet のような接続では、パスワードが暗号化されずに送られ、盗聴のリスクがありました。SSH では、通信を暗号化することで、安全な接続を実現します。ここで、公開鍵暗号が威力を発揮します。<br>• 通信開始時に、クライアントはサーバの公開鍵を使ってセッション鍵を暗号化して送り、サーバだけがそれを復号できる<br>• その後の通信は、セッション鍵による共通鍵暗号（対称暗号）で高速に暗号化 |
| How | SSH 接続の一般的な手順は以下のとおりです：<br>1. クライアントがサーバに接続を開始（`ssh ユーザ名@サーバIP`）<br>2. サーバが自分の公開鍵を提示 <br>3. クライアントがその鍵を使ってセッション鍵を暗号化して送信<br>4. サーバが秘密鍵で復号し、安全な通信チャネルが完成 <br> これにより、盗聴されても復号は不可能になります。 |

### 実習：SSHを観察してみよう

- Linux 端末で次のコマンドを実行して、鍵ペアを作成。-bのオプションは鍵の強度です。無指定は2048ビットで生成されますが、4096ビットを指定してみます

```sh
$ ssh-keygen -t rsa -b 4096
Generating public/private rsa key pair.
Enter file in which to save the key (/root/.ssh/id_rsa): 
Enter passphrase (empty for no passphrase): 
Enter same passphrase again: 
Your identification has been saved in /root/.ssh/id_rsa.
Your public key has been saved in /root/.ssh/id_rsa.pub.
The key fingerprint is:
SHA256:xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx pi@localhost
The key's randomart image is:
+---[RSA 4096]----+
|      . o +o+=E  |
|   . . + . o+.o  |
|  . o.. + .. .   |
|   ..+.* + o     |
|   .o.% S =      |
|    oO * o .     |
|   .o.B .        |
|    +O..         |
|   .+=+          |
+----[SHA256]-----+
```

- 公開鍵（`id_rsa.pub`）をサーバ側に配置し、秘密鍵（`id_rsa`）は自分だけが持つ
    - **パスワードが要求される**: 本来は、物理媒体やWebサーバ経由などを介して配置する必要がある

```sh
$ slogin -l pi@192.168.0.10
pi@192.168.0.10's password: 
# パスワードが要求されるCtrl+cで中断

# ファイルを送る
$ scp .ssh/id_rsa.pub pi@192.168.0.10:/tmp
pi@192.168.0.10's password: 
id_rsa.pub

$ slogin -l pi@192.168.0.10
pi@192.168.0.10's password: (入力する)
$ cat /tmp/id_rsa.pub >> .ssh/authorized_keys
# 公開鍵を追記する
```

- 実際に ssh 接続してみて、パスワード不要でログインできることを確認

```shell-session
$ exit

$ slogin -l pi@192.168.0.100
(パスワードを要求されなくなる)
```

### 応用：ファイル転送でSSHを使ってみよう

SSH は、ただログインするだけでなく、**安全なファイル転送**にも使えます。以下のコマンドで、ファイルを圧縮しながら転送してみましょう。

#### 方法1：SSHと tar を組み合わせる

- `local_folder` を gzip 圧縮しながら送信し、サーバ側で展開します

```shell
$ mkdir local_folder
$ touch local_folder/scp_test
$ tar czf - local_folder | ssh pi@locahost 'tar xzf - -C /tmp/remote/path1'

$ ls -al /tmp/remote/path1/
```

- 安全かつ高速に複数ファイルを一括転送できます

#### 方法2：rsync を使った安全な同期転送

```sh
$ rsync -avz -e ssh local_folder/ pi@localhost:/tmp/remote/path2/
```

- `a`：アーカイブモード（再帰的・属性保持）
- `v`：進行状況を表示
- `z`：圧縮転送
- `e ssh`：SSH 経由で転送

rsync は**変更されたファイルのみを転送する**ので、何度も転送する際に効率的です。

---

## 3-6. まとめ

### 秘密を守る技術とその活用

- 符号化は「読みやすさ」のため、暗号化は「見えなくする」ための技術
- 暗号の世界では「鍵」がとても重要。誰が持っているかで読める人が決まる
- 公開鍵と秘密鍵の仕組みによって、本人確認や盗み見防止が実現される
- SSHはtelnetの安全版。暗号と認証の両方を備えている

## おわりに

* 本稿では、通信プロトコルを説明する文脈で、符号化の一種として暗号化を説明する導入にした
* 中学生でもわかるよう、比喩の後、説明し、具体例とコンピュータ上での操作を念頭に構成した
    * 今回は、具体的な計算でRSA暗号方式を示した
* 発展的にはいくつか考えられるが、90分の時間制約上割愛した
    * 代表的なハフマン符号の符号化計算
        * 連続的な信号を離散化する符号化: デジタル通信
    * RSA暗号方式は絶えず掛け算をしているので、足し算を使う離散対数問題として他暗号方式
    * 通信路そのものの暗号化として、VPNとしてのL2TP/IPSec
* 電気通信での、電圧の高低、オームの法則による電圧の減少・雑音という要素の体感があるとよい
    * 通信の符号化・冗長化がよくイメージできる
* なお、生パスワードは保存しなくても認証がなされる点は、別稿で触れる予定のためここでは省いた
    * 暗号化されたパスワードがどこにどのように保存されているかは、アカウント管理で説明の予定