気まぐれブログ(日記・技術記事・研究のことなど)

気まぐれに更新します．温かい目で見ていただければ...

BASE64の仕組み

CTF 暗号理論

今回はbase64というエンコード方式についてまとめます.

base64とは

base64とは, 64種類の印字可能な英数字(a-z, A-Z, 0-9, +, /)のみを用いて, マルチバイト文字やバイナリデータをエンコードする方式です. SMTPという電子メールを送信するときに使用されるプロトコルでは, ASCIIコードという7bitで表現される英数字しか送信することができなかったので, 画像データなどの添付データをそのまま送信することができませんでした. そのため, すべてのデータを英数字で表すMIME(Multipurpose Internet Mail Extensions)という規格が登場し、その中でbase64というデータの変換方法が定められました.

base64でエンコードした結果, データ量は約4/3倍になります. MIMEの基準では76文字ごとに改行コードが入るため、この分の2バイトを計算に入れるとデータ量は約137%となることがわかっています.

base64の仕組み

base64は以下のようにしてエンコードされます.

(1) 文字列をasciiコードに変換し, それを2進数表現する.

"ABCD" => "01000001 01000010 01000011 01000100"

(2) 6ビットずつに分割する.

"01000001 01000010 01000011 01000100" => "010000 010100 001001 000011 010001 00"

(3) 余ったビットは0でパディングする.
"010000 010100 001001 000011 010001 00" => "010000 010100 001001 000011 010001 000000"

(4) 以下の変換表(引用: https://ja.wikipedia.org/wiki/Base64)から, 印字可能文字に4文字ずつエンコードする.

"010000 010100 001001 000011 010001 000000" => "QUJD RA"

f:id:tomonori4565:20181110153152p:plain

(5) 余った分は=でパディング

"QUJD RA" => "QUJD RA=="

(6)完成.

"QUJD RA==" => QUJDRA==

実装

UNIXコマンドには標準でbase64のエンコードとデコードが実装されています. 

$ echo -n 'I am Hirata' | base64
SSBhbSBIaXJhdGE=
$  echo 'SSBhbSBIaXJhdGE=' | base64 -D
I am Hirata

気が向いたら, 自分でも実装してみます.

CTF ネットワーク問題の基本問題(1)

CTF

CTFの勉強をサボりすぎていたのでそろそろ勉強を再開しようと思います.

今回はネットワーク問題に焦点を絞って, 学んだことを書いていきたいと思います.

以下のCTFビギナーズで使用された練習問題を元に勉強をしていきます.
https://onedrive.live.com/?authkey=%21ANE0wqC_trouhy0&id=5EC2715BAF0C5F2B%2110056&cid=5EC2715BAF0C5F2B

www.slideshare.net

sample.pcap

まずはWiresharkでパケット情報を見てみましょう.

f:id:tomonori4565:20181019003335p:plain

以上のようになっています. HTTPやTCPのプロトコルが使われていることや, 「GET /ctf_web/login/index.php HTTP/1.1\r\n」というな記述が散見されることから, どうやら端末とwebサーバーとのやりとりが記述されているようです.

http通信について詳しくみていきましょう.

display filterのウィンドウに「http」と入力し, http通信のみを閲覧できる状態にします.

f:id:tomonori4565:20181019140534p:plain

Info. に「HTTP/1.1 200 OK」と書かれていますが, これはリクエストを正しく受理したことを表します. 私たちがいつもPCやスマホでウェブサイトを閲覧できている際の多くがこの番号を受信している状態です.

ただ注意しておきたいことがあって, ログインするときにログインに失敗してしまった時も「HTTP/1.1 200 OK」というステータスコードが返されます.

sample.pcapにおける大部分の通信での「HTTP/1.1 200 OK」は, 後者に当たります.

しかし, 違うステータスコードが返されているものも存在します.
f:id:tomonori4565:20181019141023p:plain

「HTTP/1.1 302 Found」というステータスコードは, リダイレクション処理が行われていることを指します.

CTFでネットワーク問題を解くときは, 他のものとは違う通信を重点的に分析する必要があるので, この通信を分析してみましょう.
「TCPストリーム」という機能を使用して, データを見ていきましょう. すると, この通信の流れを一覧として閲覧することができます.

f:id:tomonori4565:20181019141923p:plain

このような画面が出てくると思います. 赤文字は端末が送信したパケット, 青文字は端末が受信したパケットをさします. このストリームでは, データの送受信を4往復していることがわかりますね(赤文字と青文字のやりとりが4回実行されているため).

ここで一旦元の画面に戻ってみましょう.

f:id:tomonori4565:20181019143313p:plain

display filterのウィンドウに「tcp.stream eq 7」と入力されていることがわかります. 先ほど選択したストリームのパケットが順に並んでいますね. ここでもGETやPOSTなどのアクションと, ステータスコードのやりとりが4往復されていることが確認できます.

再度, TCPストリーム画面に戻ってみましょう. 中盤にこのような記述があるかと思います.

f:id:tomonori4565:20181019142845p:plain

「FLAG is this accout password」と書かれていますね. なので, FLAGはこのアカウントのパスワードであることがわかります.

ではパスワードはどこに存在するか. それは, ログイン時にPOSTしたパケットの中に存在します.

f:id:tomonori4565:20181019143104p:plain

画面下部に「Form item: "password" = "c2bd8772532521ef2e127c020503f09f"」とありますね. これがアカウントのパスワードなのです.


従って答えは「c2bd8772532521ef2e127c020503f09f」となります.

sample2.pcap

wiresharkでパケットを見てみましょう. 今回は, ARPプロトコルやICMPプロトコルが散見されます.

ARPプロトコルは, IPアドレスから物理層のネットワーク・アドレス（MACアドレス）を求めるために利用されるプロトコルのことで, ICMPプロトコルはTCP/IPが動作するために必要な、補助的な役割を果たすためのプロトコルです.


まず一番最初に, arpプロトコルを使ってMACアドレスを求め, その後にpingコマンドを使ってやりとりをしているようです. 途中で, TCPパケットがあるので, 前回同様「TCPストリーム」を追跡してみましょう.

f:id:tomonori4565:20181019144642p:plain

f:id:tomonori4565:20181019144713p:plain

なんと, そのままflagを発見することができました.


sample3.pcap

sample3.pcapはパケット数が9268もあって, 一つ一つを確認していくのは無理そうです. こういうときは,

  1. パケットの統計を見る
  2. 暗号化されていないプロトコルの分析
  3. 特定のポート・アドレスの通信を分析

を実行していきましょう.

パケットの統計を見る

「統計 > 対話」を選択すると, パケットの統計を一覧で確認することができます. ここで異常なデータ量の通信が行われている場合は, 作問者がわざとデータを発生させたんじゃないかと疑いましょう.

f:id:tomonori4565:20181019150232p:plain

暗号化されていないプロトコルの分析

「統計 > プロトコル階層」で, どのようなプロトコルが使用されているかを確認しましょう.

f:id:tomonori4565:20181019150415p:plain

また, 暗号化されていないパケットを重点的に分析しましょう. 具体的には, http, telnet, smtp, ftpなどが挙げられます.

まずftpパケットの分析をしてみましょう.

display filterのウィンドウに「ftp-data」と入力してみましょう(ftp-dataでデータのやりとりをチェックできます).

f:id:tomonori4565:20181019150731p:plain

データ量が大きいパケットを「TCPストリーム」で追跡しましょう.

f:id:tomonori4565:20181019150818p:plain

よってこのデータは「png」ファイルであることがわかりますね. 「save as」でデータを保存してチェックしてみましょう(Raw(無加工)形式で)保存.

すると,
f:id:tomonori4565:20181019150957p:plain
というflagをゲットすることができます.



続いて, smtpパケットを分析してみましょう.

smtpパケットの「Info」部分が「C: DATA」になっているものをチェックしていきましょう.

f:id:tomonori4565:20181019151525p:plain

f:id:tomonori4565:20181019151610p:plain

f:id:tomonori4565:20181019151613p:plain

するとメールの本文らしきものが見えましたね. 本文に書かれている通り, デコードして見るとflagをゲットすることができます.


特定のポート・アドレスの通信を分析

httpでは一般的に80番ポートが使用されているのですが, 今回は8080番ポートが使用されているところがあります. このように, 特定ポートで通信している場合は怪しいと疑いましょう.

f:id:tomonori4565:20181019152034p:plain

検証部分でflagが見えていますね.


終わりに

今回はメモ書きのように解説してしまいました...

まだまだ僕もCTF勉強中なので, 今後も頑張っていきたいと思いました.

暗号理論 [番外編] ~ ElGamal暗号 ~

暗号理論

ElGamal暗号とは

ElGamal暗号とは, 1984年にエルガマルによって提案された暗号です. ElGamal暗号は, 離散対数問題の計算困難性を安全性の担保として利用している暗号化手法になります.

事前知識

別の記事で, Diffie-Hellman鍵共有プロトコルの話をしました. Diffie-Hellman鍵共有プロトコルも, 離散対数問題の計算困難性を利用したプロトコルであるので, 一度そちらの記事を読んでいただいた方がスムーズに理解できると思います.

tomonori4565.hatenablog.com

追加で, オイラーの定理というものを紹介します. a, mは互いに素である自然数とすると, 以下が成り立ちます.


a^{\varphi(m)} \equiv 1 \ \ (mod \ \ m)

ここで, \varphiとはオイラー関数というもので, \varphi(m)は mを超えない正の整数のうちで mと互いに素であるものの個数を指します. 例えば, \varphi(8) = 4となります(8と互いに素な正の整数は1,3,5,7の4つであるため).

ElGamal暗号の仕組み

鍵生成アルゴリズム

f:id:tomonori4565:20181016163057p:plain

(1) kビットのランダムな素数 pと原始元 g \ \ (1 < g < p)を選択する.
(2) 0 \leq x \leq p-2となる整数 xをランダムに選択する.
(3) y = g^x \ mod \ pを計算する.
(4) pk = (p, g, y)を公開鍵として公開し, sk = xを秘密鍵として保管する.

暗号化アルゴリズム

f:id:tomonori4565:20181016163112p:plain

平文 m \ (0 < m < p), 公開鍵 pkを入力とします.

(1) 0 \leq r \leq p-2となる整数 rをランダムに選択する.
(2) c_1 = g^r \ mod \ p \ とc_2 = my^r \ mod \ pを計算する.
(3) c = (c_1, c_2)を暗号文として出力する.

復号化アルゴリズム

f:id:tomonori4565:20181016163122p:plain

暗号文 c, 公開鍵 pk, 秘密鍵 skを入力とします.

(1) m' = c_2c_1^{p-1-x} \ mod \ p を計算して, m'を出力する.

ElGamal暗号の正当性

ElGamal暗号において, 正当性をチェックしてみましょう.


m'
= c_2c_1^{p-1-x} \ mod \ p
= my^r \cdot g^{r(p-1-x)} \ mod \ p
= mg^{rx} \cdot g^{r(p-1-x)} \ mod \ p
= mg^{r(p-1)} \ mod \ p
= m \cdot 1^r \ mod \ p \ (\because フェルマーの小定理より)
= m \ mod \ p

したがって, m' = mとなることがわかりました.

ElGamal暗号の安全性

盗聴者には pk, cが観測可能になります．しかし， y=g^x \ mod \ p \ (y,g,pは既知)から xを求めることは，離散対数問題の計算困難性から難しいとされています．したがって，秘密鍵が漏れない限りElGamal暗号は安全であると言われています．

暗号理論 [まとめ1] ～ (2)から(8)のまとめ ～

暗号理論

これまで紹介してきた記事は1つ1つが独立している訳ではなく，それぞれ関連があります．それを1度まとめてみましょう．

共通鍵暗号方式

共通鍵暗号方式とは，暗号化と復号に同じ鍵を使用する場合のことを指します．バーナム暗号やストリーム暗号は共通鍵暗号方式と言えます．

共通鍵暗号方式のメリットは，暗号化と復号をするのにかかる時間が短いことが挙げられます．

デメリットとして，鍵配送問題が生じることが挙げられます．

公開鍵暗号方式

公開鍵暗号方式は，暗号化と復号に異なる鍵を使用する場合のことを指します．RSA暗号は公開鍵暗号方式の代表的な1つです．

公開鍵暗号方式のメリットは，鍵配送問題が解決される点が挙げられます．

デメリットとしては，メッセージデータが大きい場合には暗号化と復号に時間がかかることと，man-in-the-middle攻撃に弱いことが挙げられます．

ハイブリッド暗号システム

ハイブリッド暗号システムは，メッセージの暗号化と復号には共通鍵を使用し，共通鍵を事前に共有するために公開鍵暗号方式を使用するというシステムのことを指します．

ハイブリッド暗号システムによって，共通鍵暗号方式と公開鍵暗号方式のデメリットを，お互いのメリットで補完することが可能になります．具体的には，共通鍵暗号方式のデメリットであった鍵配送問題が公開鍵暗号方式によって解決され，公開鍵暗号方式のデメリットであった暗号化と復号に時間がかかることが，共通鍵暗号方式によって解決できるようになります．

一方向ハッシュ関数

一方向ハッシュ関数は，あるメッセージが入力されたら，固定長ビットの出力値(ハッシュ値)を得ることができる関数です．

一方向ハッシュ関数の性質として，任意のデータに対してハッシュ値を得ることができる，同じデータに対しては同じハッシュ値を得ることができる，1ビットでも違うデータに対してはまったく違うハッシュ値が出力されることなどが挙げられます．

一方向ハッシュ関数を使用することでメッセージの改竄を検出することが出来ます．

しかし，一方向ハッシュ関数は「なりすまし」を検出することが出来ません．

メッセージ認証コード

メッセージ認証コードとは, 送信者と受信者間で共通鍵を共有し, データの送信者が計算したMAC値と, データの送信者が実際に計算したMAC値を確認することによって, なりすましとデータの改ざんを防ぐ仕組みのことを言います. メッセージ認証コードを使用することで, 一方向ハッシュ関数のデメリットであった「なりすましの検出が不可能であること」が解決されます.

しかし, メッセージ認証コードだけでは, 否認を防止したり第三者に証明することができません.

デジタル署名

デジタル署名とは, 送信者が送信データに署名をし, その送信データを送信者以外の人が検証できるシステムのことを指します. デジタル署名は公開鍵暗号方式の逆適用であり, 秘密鍵を使用して署名(暗号化)をし, 公開鍵を使用して検証(復号)することができます. デジタル署名によって, このデータはAさんが送ったものであるということを第三者に証明することができるので, 否認を防止することができます.

しかし, デジタル署名だけでは, 検証するにあたって公開鍵が本当に正しい相手のものなのか確認する手段がまだ確立されていません.

証明書

この公開鍵はAさんのものであると証明するものが証明書になります. この証明書のおかげで, 公開鍵が本当に正しい相手のものなのかを確認することができます.

まとめ

いかがでしょうか. 分からないことがあったら該当記事に戻っていただくか, コメントを頂けるとありがたいです.

暗号理論 [番外編] ~ Diffie-Hellman鍵共有プロトコル ~

暗号理論


共通鍵暗号方式において, 鍵共有問題は永遠のテーマでもあります. いかに安全に鍵を共有するかを議論することはとても大事なことなのです.

今回はDiffie-Hellman鍵共有プロトコルについて説明します. Diffie-Hellman鍵共有プロトコルを使用することで, 安全に鍵を配送することが可能になります.

これからDiffie-Hellman鍵共有プロトコルの仕組みを紹介していくのですが, 理解するにあたって「剰余計算(いわゆるmodの計算)」などの基本的な知識が必要となります. modの計算ができていることと, 初等整数論を理解しておくことで, 仕組みがスムーズにわかると思います. これから軽く説明したいと思います.

事前準備(初等整数論)

剰余計算

「 x \ \ mod \ \ y」とは, xをyで割ったときの余りを指します.

(例)

  • 5 mod 2 = 1
  • 10 mod 4 = 2
フェルマーの小定理

aを任意の整数, pを素数とする. 以下の公式を「フェルマーの小定理」といいます.


a^{p-1} \equiv 1 \ \ (mod \ \ p)

フェルマーの小定理は, aに関する数学的帰納法で証明できます.

位数, 原始元

フェルマーの小定理より, 「 a^{p-1} \equiv 1 \ \ (mod \ \ p) 」が成り立ちますが, 実際には, あるk (< p-1)に対して「 a^{k} \equiv 1 \ \ (mod \ \ p) 」が成り立つ場合もあります. 「 a^{k} \equiv 1 \ \ (mod \ \ p) 」が成り立つ最小のk( 1 \leq k \leq p-1)のことを, pを法とするaの位数（order）と言い,
「 order_p(a) = k」と書きます.

一方, 「 order_p(g) = p-1」を満たすgのことを, pの原始元（原始根・生成元）と言います.

(例)

  • 「 order_5(2) = 4」
  • 「 order_5(3) = 4」
  • 「 order_5(4) = 2」

したがって, 5の原始元は2, 3である.


Diffie-Hellman鍵共有プロトコルの仕組み

以下にDiffie-Hellman鍵共有プロトコルのアルゴリズムを紹介します. いつものごとく, AliceとBobがデータのやり取りをする場合を考えていきます.

(1) ランダムに大きな素数pを生成し, pの原始元g (1 < g < p)を選択して, pとgを公開します.
(2) Aliceは整数a( 1 \leq a \leq p-2)をランダムに選択し, A = g^a \ \ mod \ \ pを計算してBobに送信します.
(3) Bobは整数b( 1 \leq b \leq p-2)をランダムに選択し, B = g^b \ \ mod \ \ pを計算してAliceに送信します.
(4) Aliceは, B^a \ \ mod \ \ pを計算して出力します.
(5) Bobは, A^b \ \ mod \ \ pを計算して出力します.
(6) B^a \ \ mod \ \ pと A^b \ \ mod \ \ pは共に「 g^{ab} \ \ mod \ \ p」であり, これが鍵となる. したがってAliceとBobは鍵を共有することができます.


以下は(1)から(5)の流れです.


f:id:tomonori4565:20181011232240p:plain



Diffie-Hellman鍵共有プロトコルの安全性

Diffie-Hellman鍵共有プロトコルを攻撃する場合を考えてみましょう.
AliceとBobのやり取りを盗聴すると, 「 p」, 「 g」, 「 A」, 「 B」を取得することができます. しかし, AliceとBobがそれぞれ選択したa, bが攻撃者に漏れない限り, g^{ab} \ \ mod \ \ pを計算することは難しいのです.

このように, 「 g^{x} \ \ mod \ \ p」から xを簡単に計算するアルゴリズムは, いまだに発見されていません. これは, 有限体の上の「離散対数問題」と呼ばれています.


つまり, Diffie-Hellman鍵共有プロトコルの安全性は, 離散対数問題の計算困難性によって保たれていることになるわけです.

Diffie-Hellman鍵共有プロトコルに対する攻撃手法

Diffie-Hellman鍵共有プロトコルに対する攻撃手法の1つとして, man-in-the-middle攻撃が挙げられます.

例えば, 攻撃者Malloryが公開情報 p, gを取得し, 自分が選択した x, yを用いて g^{x} \ \ mod \ \ pと g^{y} \ \ mod \ \ pを作成します.
AliceがBobに g^{a} \ \ mod \ \ pを送信するとき, Malloryはこっそり g^{x} \ \ mod \ \ pとすり替えます. さらに, BobがAliceに g^{b} \ \ mod \ \ pを送信するとき, Malloryはこっそり g^{y} \ \ mod \ \ pとすり替えます. すると, Aliceの手元には g^{ay} \ \ mod \ \ p, Bobの手元には g^{bx} \ \ mod \ \ pが存在することになり, Malloryの手元には g^{ay} \ \ mod \ \ pと g^{bx} \ \ mod \ \ pの両方が存在することになります. したがって, MalloryはAliceに対してはBobに, Bobに対してはAliceになりすますことが可能になるのです.

この攻撃に対しては, デジタル署名や証明書などの対策が必要になってきます. これに関しては以下の記事を参考にしてください.

tomonori4565.hatenablog.com
tomonori4565.hatenablog.com

暗号理論(8) ~ 証明書 ~

暗号理論

暗号技術入門 第3版

暗号技術入門 第3版

暗号技術のすべて

暗号技術のすべて

証明書とは

前回では, デジタル署名について紹介しました. デジタル署名によって, なりすましやデータの改ざんを検出できたり, 送信データが正しい相手のものなのかを検証できるようになりました.

しかし, 受け取った公開鍵が本当に正しい相手のものなのかを検証する手段は依然として確立されていません. それを検証するために「(公開鍵)証明書」を使用します.

証明書を使用するまでの手順

証明書は信頼できる第三者機関が作成する必要があります. この第三者機関を「Trent」と命名しましょう.

例によってAliceがBobにメッセージを送信する場合を考えていきましょう.

(1) 公開鍵の登録
Bobはまず自分の公開鍵を認証局Trentに登録する必要があります. 登録する際には, 定められた「運用規定」にしたがって本人確認をする必要があります. 例えば, メールによる本人確認, 実際にBobが認証局を訪れて対面することによる本人確認などがあります.

(2) 証明書の作成
本人確認によりBobであることが確認できたら, TrentはBobの公開鍵にデジタル署名をします. もちろん, デジタル署名をする際にはTrent自身の秘密鍵が必要なので, あらかじめ用意しておきます(同時にTrentの公開鍵も用意しておきます). 証明書には, Bobの公開鍵とTrentによるデジタル署名が存在しています.

(3) 証明書の取得
AliceはBobに対してメッセージを送りたいので, Bobの公開鍵が必要になります. その際に, AliceはTrentから証明書を取得し, Trentの公開鍵で検証をします. 検証に成功すれば, 証明書に含まれているBobの公開鍵が正しいものであるとわかります.

このようにして, AliceはBobの正しい公開鍵を入手することができます.

公開鍵基盤(PKI)

公開鍵基盤(以下, PKI)とは, 公開鍵を効果的に使うために定められた規格や仕様の総称を指します.

PKIの構成要素は主に3つあります.

(1) 利用者
ここでいう利用者とは, 公開鍵を登録しようとしている人と, 公開鍵を利用しようとしている人の両方を指します.

(2) 認証局
認証局では, 証明書の管理を行います.

(3) リポジトリ
リポジトリとは, 証明書を保存し, PKIの利用者が証明書を入手できるようにしたデータベースのことを指します.

証明書に対する攻撃

証明書に対してもいくつかの攻撃手法が考えられます.

認証局へ登録する前に公開鍵を攻撃する

認証局に登録されてしまったら攻撃は難しくなるので, 登録する前にman-in-the-middle攻撃などを仕掛けることができます.
この攻撃を防ぐためには, Bobが公開鍵を認証局に登録する際に, 認証局の公開鍵を作成してBobの公開鍵を暗号化することが有効です.

攻撃者自身が認証局になる攻撃

認証局は信頼ある第三者機関によって営まれなければならないのですが, この認証局が悪意ある第三者であることを偽ることができれば, 攻撃者自身が認証局になりえます. こうすれば悪意ある攻撃がいくらでも可能になってしまいます.
こうなることを防ぐには, 信頼できない認証局は使用しないことが大切です.

暗号理論(7) ~ デジタル署名 ~

暗号理論

暗号技術入門 第3版

暗号技術入門 第3版

暗号技術のすべて

暗号技術のすべて

デジタル署名とは

前回の記事では, メッセージ認証コードの話をしました. メッセージ認証コードを使用することで, 送信データが改ざんされていないか, あるいはなりすましされていないかということを検証することができました.
しかし, メッセージ認証コードだけでは第三者に「このデータはこの人が送信したものだ」と証明することはできません. さらに, 否認を防止することもできません.


そもそもメッセージ認証コードでは, なぜ第三者への証明や否認を防止することができないのかというと, 二者間で「同じ共有鍵を使用しているから」です.

では, どうしたら第三者に対して証明できたり, 否認を防止することができるのでしょうか.


それは, 送信者と受信者で「違う鍵を使用する」ことで可能になります.

ここからは従来のやり方に沿って, AliceとBobのやり取りを例に説明していきます. AliceがBobにデータを送信する場合を考えましょう.
Aliceさんは事前に公開鍵と秘密鍵を用意しておきます. 次にBobさんに送信したいデータを秘密鍵で「署名」します(署名は「暗号化」と置き換えてもらっても構いません). 続いて, もとのデータと「署名」したデータをBobさんに送信します.
Bobさんは, これらを受け取り, さらにAliceさんの公開鍵を取得します. Bobさんは公開鍵を用いて署名されたデータを「検証」します(検証は「復号化」と置き換えてもらっても構いません). その結果, もとのデータと検証したデータが一致すれば, そのデータはAliceさんが送信したものだと確認することができます.


ここまではメッセージ認証コードの仕組みとそんなに変わりませんね. でもここからがメッセージ認証コードとデジタル署名の大きな違いです.

では, Bobさんが受け取ったデータが本当にAliceさんのものであるかを第三者に証明するとしましょう. どうしたらいいでしょうか.



簡単なことです. Aliceさんが送信したデータを, 検証する第三者Victorが受け取り, Aliceさんの公開鍵で正しいデータかどうかを実際に検証すればいいだけなのです.

ではどうしてVictorはそのデータがAliceさんが送信したものだと証明できるのでしょうか.


それは, 「署名データはAliceさんにしか作り出せない」からです.

秘密鍵を持っている人にしか, デジタル署名を施すことができません. なので, その人の公開鍵で実際に検証が成功すれば, データの送信者を一意に特定することができます.



これまでの記事を読んで理解が深まっていらっしゃる人は, デジタル署名の仕組みについて何か気づいたかもしれません.


デジタル署名は, 「公開鍵暗号方式と逆の関係」であるということが言えます.

公開鍵暗号とデジタル署名

公開鍵暗号方式については以下の記事を復習してください.
tomonori4565.hatenablog.com

公開鍵暗号方式では, 公開鍵を暗号化に使用し, 秘密鍵を復号化に使用していました.
デジタル署名では逆の関係になります. 秘密鍵を署名(暗号化)に使用して, 公開鍵で検証(復号化)するのです.

ここで, なぜ暗号化が署名の作成に相当して, 復号化が署名の検証に相当するのかを考えてみましょう.

公開鍵暗号方式の記事でも説明したように, 公開鍵と秘密鍵は「数学的に深い関連をもつ」鍵ペアでなければいけません. よって秘密鍵で暗号化した暗号文は, その秘密鍵とペアになっている公開鍵でしか復号化することはできないのです. そして, 正しく復号ができていれば, その公開鍵と対になっている秘密鍵で暗号化されたんだということがわかりますね.


以上からもわかるように, デジタル署名は, 「公開鍵暗号方式と逆の関係」であるということが言えるのです.

デジタル署名の方法

ここからは, どのようにデジタル署名が施されるかということについて説明していきます.

主に2通りの署名方法があります.
(1) メッセージに直接署名する方法
(2) メッセージのハッシュ値に署名する方法

今回は, 主に使用されている「(2) メッセージのハッシュ値に署名する方法」について解説していきます.

メッセージのハッシュ値に署名する方法

ここでもAliceさんがBobさんにメッセージを送信する場合を考えましょう.

以下に署名の流れを示します.

(こちらのサイトに乗っている図が参考になるかもしれません. )
www.infraexpert.com


(1) まず, Aliceさんはメッセージのハッシュ値を計算します.

(2) 次にAliceさんはハッシュ値を秘密鍵で署名(暗号化)します.

(3) Aliceさんは, もとのハッシュ値と署名データをBobに送信します.

(4) Bobさんは, 受信した署名をAliceの公開鍵で検証(復号化)します.

(5) Bobさんは, 検証データとハッシュ値を比較して, 一致するかどうかを確認します. 一致すれば検証成功です.


このような流れになっています.

デジタル署名に対する攻撃

man-in-the-middle攻撃

公開鍵暗号方式では, man-in-the-middle攻撃が脅威となりましたが, デジタル署名に対しても脅威となります(公開鍵暗号方式の逆の関係なので想像はつくと思います).

man-in-the-middle攻撃を防ぐには, 公開鍵が本当に正しい相手のものなのかを確認する必要があります. 例えば, 入手した公開鍵がAliceさんのものであるか, Bobさんが確かめるとしましょう. BobさんはAliceさんに電話をかけ, 自分が持っている公開鍵が本当にAliceさんのものなのかを確かめることができます.

では電話などでチェックできない場合はどうしたらいいのでしょうか. それは, 次回の記事で紹介する「証明書」で説明します. 証明書を用いれば, 公開鍵が正しいものかどうかを証明することができます.

デジタル署名を駆使した公開鍵暗号方式に対する攻撃

RSA暗号を用いでデジタル署名を作成しようとすると, 以下のようになります.


m^d \ \ mod \ \ N

これは, 公開鍵暗号方式における復号操作となります. この仕組みを利用して, 公開鍵暗号方式を攻撃することができます.

攻撃者Malloryは, AliceとBobの通信を盗聴しています. Malloryはこのやり取りの内容を解読したいので, Bobにこんなメールを書きました.

Bobへ,
現在デジタル署名の実験をしているのですが, 添付データにあなたの署名をつけて返信してください.
添付データはランダムなので問題は発生しません.
Malloryより.

BobはMalloryのメールを読んで, 添付データを閲覧しましたが, メールの本文の通りランダムなデータに見えます.
しかし実際には, 添付データはAliceがBobの公開鍵で暗号化した暗号文なのです. 当然, Bobが署名をしてしまうと, もとのデータが復元されてしまうことになります.

このデータをうっかりMalloryに返信してしまうとさあ大変. Malloryは何も苦労せず平文をGetできてしまうのです. Bob本人に復号化をさせるという大胆な方式ですね.

これを防ぐには, まず公開鍵暗号方式で使用する鍵ペアと, デジタル署名で使用する鍵ペアを分けておく必要があります. 他にも, メッセージに直接署名するのではなく, ハッシュ値に署名をするなどの対策が考えられますが, 何と言っても一番の対策方法は, 意味不明なメッセージにはデジタル署名をしないということです.

デジタル署名では解決できない問題

デジタル署名によって, 改ざんやなりすまし, そして第三者に対して「このデータはこの人が送信した」ということを証明できたり, 否認防止が可能になったりします.
これで悪意ある第三者からの攻撃が来ても安心 ...



...とはなりません. 前にも言いましたが, 絶対安全な通信手段はまだまだ確立されていません.



本記事の途中でも言いましたが, デジタル署名において, 受け取った公開鍵というのは本当に正しい相手のものでしょうか. もしかしたら悪意ある攻撃者Malloryが勝手にすり替えた公開鍵かもしれません. 次の記事において, 「証明書」について説明しますが, これは受け取った公開鍵が本当に意図した人物のものなのかを確認することができます.