はじめに
この記事では共通鍵暗号方式の鍵の本数の求め方のみをまとめています。
また厳密な証明ではなく、分かりやすい解説を目指して書いていますので、ご了承ください。
この記事が対象とする読者
・基本情報技術者試験のレベルで共通鍵暗号方式がざっくりと分かる方
鍵の本数の求め方
一般式を使わない場合
A,B,C,Dの4台のデバイスがあるとします。
-
Aから考えると、Bとの鍵、Cとの鍵、Dとの鍵、で3本の鍵が必要です。
-
Bから考えると、Aとの鍵は必要ないので、Cとの鍵、Dとの鍵、で2本の鍵が必要です。
-
Cから考えると、Dとの鍵の1本の鍵が必要です。
-
Dから考えると、すでにすべてのデバイスとの鍵を持っています。
1〜4を合計すると6本の鍵が必要です。
一般式を使う場合
はじめに一般式を示します。
n台のデバイスに必要な共通鍵の本数は
\frac{n\left(n - 1\right)}{2}
です。
次にこの式の求め方を示します。
一般式を使わない場合のように具体的な台数で計算してみると分かりますが、必要な鍵の本数は1から(台数 - 1)までの総和になっています。
賢い方はここでお気づきかも知れませんが、
1 + 2 + \cdots + (n - 2) + (n - 1) = \sum_{k=1}^{n-1} k
なので、あとは計算すれば終わりです。
しかし、これは現在の高校数学Bの内容ですので、別のやり方も紹介します。
このような総和を求めるときは、元の式とは項が逆の順番に並んだ式を考えます。
// 元の式
1 + 2 + ... + (n - 2) + (n - 1)
// 項が逆の順番に並んだ式
(n - 1) + (n - 2) + ... + 2 + 1
そして縦に足します。
1 + 2 + ... + (n - 2) + (n - 1)
(n - 1) + (n - 2) + ... + 2 + 1
// 縦に足す
n + n + ... + n + n
この結果は元の式と、項が逆の順番に並んだ式とを足した結果と等しいです。
ここでnの個数は(n - 1)個なので、
n + n + \cdots + n + n = n(n - 1)
です。
ただし、勝手に項が逆の順番に並んだ式を足しています。そして、元の式と項が逆の順番に並んだ式の総和は、項の順番が違うだけなので等しいです。ですので、2で割ります。すると、
\frac{n\left(n - 1\right)}{2}
となります。
さいごに
ただ暗記するのではなく、意味まで理解してもらえたならば幸いです。
- 間違いや分かりにくいところは遠慮なくコメントしてください