情報処理安全確保支援士 - SE娘の剣 -

左門至峰による情報処理安全確保支援士試験に合格するためのサイトです。 過去問を引用しながら、試験に出る基礎知識を体系的かつ詳細に整理します。

公開鍵暗号

1.公開鍵暗号の必要性

情報処理安全確保支援士試験において、公開鍵暗号はPKIを含めて非常に重要です。腹の底から理解するようにしましょう。

共通鍵暗号方式のデメリットは何か?

dcf52feb

公開鍵暗号ですが、そもそも公開鍵暗号はなぜ必要なのですか?
共通鍵暗号方式では何か問題があるのでしょうか?

デメリットは例えば以下です。
① 鍵の安全な受け渡し
 インターネットで共通鍵を安全に渡すのはとても難しい。

② 鍵の数が増え、管理が大変
 たとえば、海外の友達と共通の鍵を使って暗号化通信をするとします。でも、その鍵をどうやって送ればいいのでしょうか?インターネットを使えば、誰かに盗聴される可能性があるから危険です。だからといって、郵便は面倒ですよね。
そこで、公開鍵暗号方式が登場しました。たとえば、Aさんが秘密鍵と公開鍵を作ります。秘密鍵はAさんが保有し、公開鍵はみんなに公開します。すると、誰もがAさんの公開鍵をつかって暗号化することができます。そして、その暗号を解くことができるのは、公開鍵のペアである、Aさんの秘密鍵だけです。つまり、Aさん以外に中身を見られることなく通信をすることができるのです。
次の図をもとに、解説をします。
公開鍵暗号方式の仕組み_情報セキュリティスペシャリスト試験

共通鍵方式で鍵を共有するのは大変です(図①)。そこで、暗号化する鍵をみなさんに公開します(図②)。送信者は公開鍵で暗号化します(図③)。受信者は自分の秘密鍵で復号するのです(図④)。

■公開鍵暗号方式の仕組み
公開鍵暗号方式の一つであるRSAは、大きな素数の素因数分解の困難さを使っている。素数というのは、大きな数になれば、それが素数かどうかの判断もかなり難しい。

ベリサイン社の何重にも厳格なセキュリティが施された部屋の奥の奥に金庫がある。そこには何がしまってあるか?
なんと、素数である。素数はそれほど、暗号にとって大事なのである。(出典は、DVDの「リーマン予想・天才たちの150年の闘い ~素数の魔力に囚われた人々~ (NHKエンタープライズ)」より。
リーマン予想・天才たちの150年の闘い ~素数の魔力に囚われた人々~ [DVD]リーマン予想・天才たちの150年の闘い ~素数の魔力に囚われた人々~ [DVD]
著者:ドキュメンタリー
販売元:NHKエンタープライズ
(2010-05-28)



2.公開鍵暗号方式

過去問(H23春FE午前問42)
「非常に大きな数の素因数分解が困難なことを利用した公開鍵暗号方式」は何か?






これを開発したのはMITの助教授であったロナルド・リベスト(Ronald Rivest)、アディ・シャミア(Adi Shamir)、レオナルド・エーデルマン(Lenonard Adleman)の3人の名前。3人の頭文字をとってRSAとしています。
ロナルド・リベスト(Ronald Rivest)はRC4の開発者でもある(はず)。
RSAは公開鍵暗号方式のスタンダード。RSAの問題点であった処理の複雑さを、楕円曲線暗号は改善しています。ただ、セキュリティ強度は不明です。

(1)整数の特徴

シンプルな仕組みであるが、それでも解説しようとすると数ページに及ぶため基本原理のみ説明します。 
整数を1乗2乗3乗していくと次の結果になります。今回は2と7を紹介。

暗号化文字 1乗 2乗 3乗 4乗 5乗 6乗 7乗 8乗 9乗
2 2 4 8 16 32 64 128 256 512
7 7 49 343 2401 16807 117649 823543 5764801 40353607

これを見ると、1乗、5乗、9乗の1桁目は全て同じである。
この原理は、全ての数についてあてはまる。
ということは、暗号化するときは3乗し、復号するときは1乗すればよい。
(※結果の値は、1桁目のみ)
2→(3乗)→6→(1乗)→2
7→(3乗)→1→(1乗)→7
3が秘密鍵で1が公開鍵である。これが暗号化に使う鍵と復号に使う鍵が異なる公開鍵暗号の仕組みである。
15863853

でもこんなに簡単な仕組みだったら誰でも1乗して復号できますね

そう。実際にはもっと大きな数(例えば128ビット)で行われるので大丈夫。
例えば、13×17を例にすると、同じ数字になる間隔は192です。
※これは、(13-1)×(17-1)=192で求められるようです。
なので、復号する側は、何乗すればいいかを192回試す必要があり、かなり大変です。

2桁×2桁程度でも大変そうなので、128ビットだったらとても計算できないですね。
たしか、素因数分解の難しさを利用しているって聞きましたが。

13×17という素因数分解ができれば、同じ数字になる間隔が (13-1)×(17-1)=192と割り出せてしまいます。だから、素因数分解の難しさが大前提になります。

以上、ほんの一部だけ説明しました。
詳しい内容まで踏み込む必要はありません。雰囲気を感じていただくだけでいいです。

(2)RSA暗号の計算

RSA暗号の計算については、Wikipediaなどいろいろなサイトに掲載されています。
ja.wikipedia.org

これらと同じですが、順番にやってみましょう。

(1)2つの互いに素な素数を用意
 ・2つの素数(p,q)を用意し、n = p x q とする。 今回は(p,q)=(3,5), n = 3 x 5 =15
 ・φ = (p-1) x (q-1)。 今回は φ = (3-1) x (5-1) = 8

(2)鍵を作る。
①公開鍵 →(e,n) 今回は、(3,15)
公開鍵e(eはnより小さい値にする)は、eとφが互いに素な値。 今回は e=3,7などがあるが、e=3とする。(e=7でも可)
②秘密鍵 →(d,n) 今回は、(3,15)
秘密鍵dは、d x e をφで割ると、余りが1になるような値。 今回は、d x 3を8で割ると、余りが1になる値として、d=3とした。(e=7の場合、d=7)

(3)暗号化と復号
①暗号化
平文mから暗号文cを作る。たとえば、インタネット上にて、秘密鍵(3,15)を持っているAさんに、公開鍵で暗号化してデータmを送る。復号できるのは、秘密鍵を持っているAさんだけである。
暗号文 c = mのe乗 mod n 。つまり、mのe乗をnで割った余り。 今回は平文m=7として、c = 7の3乗(= 343)÷15 = 22 余り13 ←この13が暗号文c

②復号
暗号文cから平文mを作る。
平文 m = c のd乗 mod n 。つまり、cのd乗をnで割った余り。今回は、暗号文 c = 13 として、m=13の3乗(= 2197) ÷15 =146 余り7 ←これが平文mであり、見事に復号できた。

(4)Pythonプログラムで計算します。以下は、GoogleColabで実行しました。

GoogleColabで実行
\#公開鍵と秘密鍵がわかっている状態で、暗号文を平文に復号する

!pip install pycrypto

from Crypto.Util.number import inverse, long_to_bytes

c = 13   # 暗号文
n = 15   # 公開鍵 (e,n)
e = 3
d = 3    # 秘密鍵 (d,n)

\#dを計算で求める場合は以下
\#d = inverse(e, (p-1)*(q-1)) # 2つの素数(p,q)を用意し、n = p x q

m = pow(c, d, n) # 平文
print("m=",m)

ちなみに、非常に大きな数字の素因数分解は以下で計算ができる。

http://factordb.com/index.php

もう少し大きな値でやってみましょう。
■鍵
公開鍵(e,n) = (1597,17006568238658686328981)
秘密鍵(d,n)=(2864600394244698655861,17006568238658686328981)

■送信者
平文:m = 123456
暗号文:mをe乗し、その結果をnで割った余りを計算 --> c = 6406635412033314169603

この場合、nの素因数分解(n = 172046089 × 98848909251629) ができれば解けるのですが、コンピュータを使わないと簡単ではないですよね。つまり、復号することは簡単ではありません。

■受信者
暗号文から、秘密鍵を使って元に戻してみましょう。
暗号文 cをd乗し、その結果をnで割ったあまりを計算 -->平文:m = 123456 が計算できます。

非常に大きな数字の素因数分解の場合
!pip install pycrypto

from Crypto.Util.number import inverse, long_to_bytes

\# (1)2つの互いに素な素数を用意
\# 2つの素数(p,q)を用意し、n = p x q とする。
\# 素因数分解は、このページで可能。http://factordb.com/index.php?

n = 17006568238658686328981
p = 172046089
q = 98848909251629

\# (2)公開鍵(e,n)を作る
\# 公開鍵e(eはnより小さい値)は、eとφが互いに素な値。
e = 1597 # 他にも候補は山ほどあるが、これを選んだ

\# (3)秘密鍵(d,n)を作る
\# 公開鍵eとp,qから秘密鍵を求める
d = inverse(e, (p-1)*(q-1))
print("d =",d) # d = 2864600394244698655861

\# (4)暗号化
\# 平文を公開鍵(e,n)を使って暗号化
m = 123456 # 平文(message)
c = pow(m, e, n)  # 暗号文(chipher)
print("c =",c) # c = 6406635412033314169603

\# (5)復号1 秘密鍵から
\#以下のように、暗号文cと秘密鍵(d,n)がわかっていれば計算できる
m2 = pow(c, d, n) # 平文
print("m2 =",m2) # m2 = 123456

\#(6)復号2 nの素因数分解ができれば
\#秘密鍵(d,n)がわからない場合は、(3)でやったように、公開鍵eとnを素因数分解したp,qから秘密鍵を求める。そして、(5)で復号する。

3.ハイブリッド暗号方式

情報セキュリティスペシャリスト試験を目指す女性SE


公開鍵暗号方式という優れた方式があるなら、もう共通鍵暗号方式は不要では?

下のようなイメージです。
公開鍵暗号であれば、鍵の数は少ないし、本人のみが見ることができます。
以下は、成子がイメージする公開鍵暗号による安全な暗号化通信
メールの暗号_情報セキュリティスペシャリスト試験

鍵の管理が大変な共通かぎ暗号方式のデメリットを解消する公開鍵暗号方式であるが、インターネットの世界ではとてもよく使われている。

しかし、デメリットとして共通鍵と比べて数百倍の時間がかかるといわれています。
そこで、両者の長所を組み合わせるハイブリッド方式が使われます。

具体的には以下です。
①鍵の受け渡し→公開鍵暗号方式
 暗号化通信をするための共通鍵を交換するのに、公開鍵暗号方式を使います。
 公開鍵暗号方式を使えば、鍵を安全に相手に送ることができます。
②暗号化通信→共通鍵暗号方式
 実際にデータを暗号化して通信をする部分では、共通鍵暗号方式を使います。
 その方が各段に高速だからです。

たとえば、メールを暗号化する仕組みであるS/MIMEもハイブリッド暗号方式です。

■過去問(H28秋AP午前)を解いてましょう。

過去問(H28秋AP午前)
問42 OpenPGPやS/MIMEにおいて用いられるハイブリッド暗号方式の特徴はどれか。

ア 暗号通信方式としてIPsecとTLSを選択可能にすることによって利用者の利便性を高める。
イ 公開鍵暗号方式と共通鍵暗号方式を組み合わせることによって鍵管理コストと処理性能の両立を図る。
ウ 複数の異なる共通鍵暗号方式を組み合わせることによって処理性能を高める。
エ 複数の異なる公開鍵暗号方式を組み合わせることによって安全性を高める。






ハイブリッドの特徴は、公開鍵暗号方式と共通鍵暗号方式を組み合わせることです。ウやエのように、1つの方式ではありません。
正解:イ

4.鍵管理

(1)公開鍵暗号方式と共通鍵暗号方式の違い

公開鍵暗号方式は、共通鍵暗号方式に比べ、利用する鍵の数が少なくなります。
たとえば、以下ののように、AからFの6人が相互に通信する場合を考えます。通信のペアは全部で15組ありますから、共通鍵暗号方式の場合は、15個の鍵が必要です。一方、公開鍵暗号方式の場合は、6人がそれぞれ持つ2つの鍵(公開鍵と秘密鍵)だけを使いますので、鍵の数は12個だけです。
鍵管理

この数は、通信相手が多くなると、共通鍵の場合はさらに増えます。
たとえば、100人と通信する場合、必要な鍵の数は4950個で、公開鍵暗号方式の場合は、わずか200個です。いので、鍵の受け渡しなどの鍵管理が行いやすくなります。

鍵の数の計算式は以下です。
①共通鍵暗号方式 n(n-1)/2
 全部でn人いますから,それぞれが(n-1)人と通信をします。この組み合わせの数は,n(n-1)/2です。組み合わせごとに鍵が必要ですから,全部でn(n-1)/2になります。

②公開鍵暗号方式 2n
 各人が秘密鍵と共通鍵の2つずつの鍵を持ちます。全部でn人ですから,鍵の数は合計2nになります。

(2)秘密鍵の適切な保管方法
過去問(平成18年SU午前)
問24 社内のセキュリティポリシで、利用者の事故に備えて秘密鍵を復元できること、及びセキュリティ管理者の不正防止のための仕組みを確立することが決められている。電子メールで公開鍵暗号方式を使用し、鍵の生成はセキュリティ部門が一括して行っている場合秘密鍵の適切な保管方法はどれか。

ア 一人のセキュリティ管理者が、秘密鍵を暗号化して保管する。
イ 暗号化された秘密鍵の一つ一つを分割し、複数のセキュリティ管理者が分担して保管する。
ウ セキュリティ部門には、秘密鍵を一切残さず利用者本人だけが保管する。
エ 秘密鍵の一覧表を作成して、セキュリティ部門内に限り参照できるように保管する。






鍵を安全に保つ方法の、なかなか良い問題だと思う。
よく考えれば分かりますが、ひとつひとつなぜダメなのかを考えよう。
例えば、ア。これはどうでしょう。
db2fc28c

これは、その一人が不正をする可能性がありますね。
いくらセキュリティ管理者といえど、不正の可能性は多いにあります。
正解はイ

5.【頭の整理】2つの暗号方式と3つの鍵

情報処理安全確保支援士試験において、「鍵」がつく言葉には①秘密鍵,②共通鍵,③公開鍵の3つがあります。一方,「暗号方式」は,共通鍵暗号方式と公開鍵暗号方式の2つです。この点を整理します。
共通鍵暗号方式で使用する鍵が①秘密鍵です。一方、公開鍵暗号方式で使用する鍵は①秘密鍵と③公開鍵の2つです。

方式 共通鍵暗号方式 公開鍵暗号方式
使用する鍵 秘密鍵 秘密鍵,公開鍵

 共通鍵暗号方式は,暗号化する鍵と復号する鍵が同じ(共通)だから「共通」鍵と言われますが、実際に使うのは秘密に管理すべき「秘密鍵」です。 

6.過去問

情報処理安全確保支援士試験以外のものばかりですが、理解を深めるために解いてみましょう。
(1)公開かぎ暗号方式の鍵

過去問(平成17年度NW午前問47)
公開かぎ暗号方式を用い、送受信メッセージを暗号化して盗聴されないようにしたい。送信時にメッセージの暗号化に使用するかぎはどれか。






まあ、よく考えれば分かる。
選択肢は、
①送信者の公開鍵
②送信者の秘密鍵
③受信者の公開鍵
④受信者の秘密鍵
ちなみに、今回の正解は送信先の公開かぎ(受信者の公開かぎ)

(2)公開鍵暗号方式の問題

過去問(平成18SU午前)
問23 公開鍵暗号方式の用法によって、送信者が間違いなく本人であることを受信者が確認できる鍵の組み合わせはどれか。
ア 送信者は自分の公開鍵で暗号化し、受信者は自分の秘密鍵で復号する。
イ 送信者は自分の秘密鍵で暗号化し、受信者は送信者の公開鍵で復号する。
ウ 送信者は受信者の公開鍵で暗号化し、受信者は自分の秘密鍵で復号する。
エ 送信者は受信者の秘密鍵で暗号化し、受信者は自分の公開鍵で復号する。






4d80b27a

こういう問題は、考えると頭がいたくなってきます。
きちんと考えればわかると思います。
正解はイ

(3)ディジタル署名のプロセスとハッシュ値の使用方法

過去問(平成17年度SU午前)
問24 公開かぎ暗号方式によるディジタル署名のプロセスとハッシュ値の使用方法に関する記述のうち、適切なものはどれか。

ア 受信者は、送信者の公開かぎで復号してハッシュ値を取り出し、元のメッセージをハッシュ変換して求めたハッシュ値と比較する。
イ 送信者はハッシュ値を自分の公開かぎで暗号化して、元のメッセージと共に受信者に送る。
ウ ディジタル署名の対象とする元のメッセージは、それを変換したハッシュ値から復元できる。
エ 元のメッセージ全体に対して公開かぎ暗号化を行い、ハッシュ値を用いて復号する。






正解は、以下。