実用的暗号通信ソフトウェア 「まめだくん」の開発 Shiota Laboratory 梶畑、佐伯、高岩、 辰西、本澤、森川

発表概要 暗号とは（梶畑） 公開鍵暗号方式（梶畑） 研究動機（梶畑） 動作画面、システム設計概要（森川） RSA暗号（辰西） ElGamal暗号（高岩） デジタル署名（佐伯） まとめ（本澤）

１．暗号とは

１．暗号とは 隠語文 ニイタカヤマノボレ１２０８ 知ってる人 秘匿情報の伝達 知らない人

１.暗号とは 合言葉 山！ 川！ 認証

暗号の用途 秘匿情報の伝達 認証

暗号系 暗号化 復号化 平文　　　　　　　　 暗号文 平文

鍵 暗号方式 マンションにはどの部屋にも同じ形式の鍵がついているが部屋ごとに鍵は違い、その部屋の鍵を持っていなければ、部屋に入ることはできない

２．公開鍵暗号方式 暗号化に使う鍵と復号化に使う鍵が異なっている暗号 Alice Bob 秘密鍵 公開鍵 一対の鍵と錠前を作る 相手に片方送る 秘密鍵 公開鍵 暗号文を受け取る 鍵で開ける 文章に鍵をかける

３．研究動機 ユーザフレンドリーなツールの開発 まめだくん 昨今、暗号手法は実用化に耐えうるものが研究開発されている. 暗号理論に明るくない一般のユーザが利用できるものは少ない. 　 ユーザフレンドリーなツールの開発

４．「まめだくん Ver.1.0」 特徴と利用方法

システムの特徴 ユーザが使いやすい 十分な安全性のある暗号方式 実用に耐えうる実行速度（ハイブリッド暗号） 署名を用いて送信者確認

システム構成 鍵の授受 暗号メール 送受信 鍵の授受 鍵サーバ クライアント 秘密鍵 クライアント 公開鍵 データベース 秘密鍵 (PostgreSQL) 秘密鍵

システム動作 ボブの公開鍵要求 ボブの公開鍵 アリスの公開鍵要求 アリスの公開鍵 署名の検証 暗号化 鍵サーバ 送信 復号化 平文 アリス （クライアント） 鍵サーバ 暗号化 ボブの公開鍵 暗号文 アリスの公開鍵要求 送信 ボブ （クライアント） アリスの公開鍵 復号化 署名の検証 平文

初期設定画面

操作方法 メールアドレスを入力 POP3パスワードを入力 SMTP・POP3サーバ名を入力 OKをクリック 自動で鍵を生成し、システムに登録

新規メール作成画面

操作方法 送信先メールアドレス（＝ユーザ名）を入力 件名を入力 本文を入力 送信をクリック 自動で暗号化（署名）し、送信

受信メールボックス画面

操作方法 受信をクリック → メール受信 返信をクリック → 引用返信 新規メール作成をクリック → 新規メール作成 受信をクリック　→　メール受信 返信をクリック　→　引用返信 新規メール作成をクリック　→　新規メール作成 削除をクリック　→　メール削除 設定変更をクリック　→　初期設定画面表示 利用停止をクリック　→　利用停止処理

クライアントソフトウェア ユーザが使用する部分 今回はメールクライアントソフト（メーラ） 暗号化・復号化 鍵サーバとの通信

クライアントソフトウェアの特徴 Windows®上で動作 ユーザフレンドリな画面設計 簡素な操作手順

クライアントソフトウェアの動作 ボブ公開鍵 取得 アリス公開鍵 取得 秘密鍵 署名計算 署名確認 アリス （クライアント） 暗号化 暗号文 送信 アリス公開鍵 取得 ボブ （クライアント） 秘密鍵 復号化 平文 署名 署名確認

鍵サーバ 公開鍵暗号方式では、公開鍵の管理が必要 ユーザの公開鍵の保持 他のユーザの公開鍵の配布 DSA、ElGamal等では共通鍵の保持・配布

鍵サーバの特徴 高拡張性（標準の言語とライブラリ） 高将来性（環境依存性の排除）

鍵サーバ・内部設計 C言語で開発 RDBMS(PostgreSQL)を使用 PostgreSQL標準のライブラリを使用 高い拡張性 今後開発をほかへ受け継ぐ場合でも、再開発が容易 高い拡張性

鍵サーバ・クライアント間プロトコル TCP/IP方式で実現 環境依存性を軽減 共通性が高く、今後の普及などに関して高い将来性 高い将来性

鍵サーバの動作 公開鍵要求 署名要求 認証用乱数列生成 鍵サーバ 署名送信 署名確認 確認 メッセージ 要求 ユーザ名 ユーザ公開鍵取得 公開鍵 データベース 署名要求 認証用乱数列生成 署名送信 署名確認 確認 メッセージ 要求 ユーザ名 ユーザ公開鍵取得 公開鍵

まめだくん 安全・高速な暗号方式 ユーザフレンドリ 高い拡張性 容易に導入が可能な有用ツール

5.RSA暗号 素因数分解の困難性を利用した暗号

暗号化の方式 暗号化 復号化 暗号文 平文 平文 復号化鍵 暗号化鍵

法演算 合同式 a ≡ b ( mod n ) a と b は n を法として合同 ⇔ a と b は n で割った余りが等しい

暗号化 復号化 ↓ ↓ y d mod n = x 暗号文 y = x e mod n 平文 x を得る 例 n = 221, 復号化鍵 n , d ,暗号文 y 　　　　　↓ y d mod n = x 平文 x を得る 例　n = 221, d = 167, 　 y = 138より 138 mod 221 = 213 x = 213 を得る 暗号化鍵 n ,e , 平文 x 　　　　　↓ 暗号文 y = x e mod n 例　n = 221, e = 23, 　 x = 213 のとき y = 213 mod 221 = 138 23 167

鍵の生成 p, q ： 異なる大きな素数 を生成 → n = pq、m = ( p – 1 )( q – 1 ) を計算 e：mと互いに素な自然数を生成 →　整数 d ( ed ≡ 1 mod m を満たす ) を計算 ( n , e ) ： 暗号化鍵 ( 公開鍵 ) ( n , d ) ：復号化鍵 ( d は秘密鍵 ) 例 p=13,q=17→n=221,m=192, さらに　e=23→d=167

使っている演算 ( ユークリッド ) y = x e mod n （ 反復二乗法 ） 最大公約数 ed ≡１ mod m 最大公約数　 ed ≡１ mod m 素数の生成　（ 素数判定 ） ( ユークリッド )

反復二乗法 y ≡ x e mod n を高速に計算する方法 例．2 の場合 通常:2×2×2×2×2×2×2×2 ⇒7回の演算 例．2　　の場合 通常:2×2×2×2×2×2×2×2 ⇒7回の演算 反復二乗法: ((2 ) ) 　　⇒3回の演算 　　 2　　の場合　　　　　　 通常：　2×2×2×･･･×2　⇒1023回の演算 反復二乗法：((((2 ) ) )･･･) ⇒10回の演算 8 2 2 2 1024 2 2 2 2

ユークリッドのアルゴリズム 入力：整数 a,b ⇒出力：整数 c, x ,y aとbの最大公約数 gcd ( a,b ) = c c = ax + by を満たす x, y 　高速に計算 例 1．a = 5 , b = 3 の場合 1 = 5x + 3y x = 2 , y = ‐3 例 2． e = a = 23 , m = b = 192 の場合 　1 = 23x + 192 y x = 167 , y = ‐20

素数の生成 乱数 k を生成 確率的素数判定 （高速） no k ← k + 2 yes 素数 p = k

素因数分解の困難さ 効率的な素因数分解法は発明されていない 512ビットの鍵では解読される可能性がある → 429ビットの鍵は解読済み 　→　429ビットの鍵は解読済み n が10ビット増えると、最低でも計算に2倍の時間が必要 1024ビットになると512ビットのときのおよそ 　 250 倍(1千兆倍以上)の時間が必要

素因数分解の困難さ （過去の懸賞問題） 129桁のnで設計された暗号文を解読する問題 17年後、1600台のコンピュータを8ヶ月間使った 結果nを素因数分解し、解読に成功

素因数分解の困難さ （新しい懸賞問題） 576ビット長の鍵　　　　　10,000ドル 2048ビット長の鍵　　　　 200,000ドル

ＲＳＡのまとめ 秘密鍵 ( n , d ) を持っていると… → x = y d mod n の計算が容易 　→　素因数分解 ( p , q を求める ) が 必要となり困難

６．ElGamal暗号 　１９８２年にElGamalによって提示 　離散対数問題に基づく初めての公開鍵暗号

有限巡回群 但し　a n = 1 G：a によって生成される有限巡回群 a：G の生成元

例．p＝7を法としたとき、a＝3のべき乗を計算することにより、有限巡回群であることを示す。 １ ５ ３ ４ ２ ６

離散対数問題 例． p= 20000003 を法としてa=2,b=3とすると 3 = 2x mod 20000003 x =10502638 a：pを法とする生成元 b：b≠0 整数 x を求める。 例． p= 20000003 を法としてa=2,b=3とすると 3 = 2x mod 20000003 x =10502638 暗号に使われる離散対数問題では、a と b がわかっていても，x を求めることは不可能に近い。

暗号方式 ≪状況設定≫ 〈共通鍵〉 〈秘密鍵〉 〈公開鍵〉 例． 〈共通鍵〉〈秘密鍵〉 〈公開鍵〉

例． ≪暗号化≫ 平文 暗号文 アリス ボブ メッセージm=10 乱数k=8 (mod (p-1)) 共通鍵（ g，p ） 公開鍵（ y ） 平文　　　　　　　　　　　 暗号文 　　乱数k (mod (p-1)) 例． アリス　　　　　　　　　　　　　　　　ボブ メッセージm=10 乱数k=8

例． ≪復号化≫ 暗号文 復号文 復号文m＝平文m アリス ボブ 復号文m＝10は、メッセージm となる。 共通鍵（ p ） 秘密鍵（　　s　　） 暗号文　　　　　　　　　　　 復号文 復号文m＝平文m 例． アリス　　　　　　　　　　　　　　 ボブ 復号文m＝10は、メッセージm となる。

ElGamal暗号の安全性 離散対数問題の難しさ 鍵サイズ 512ﾋﾞｯﾄ 300年 768ﾋﾞｯﾄ 200万年 1024ﾋﾞｯﾄ 30億年 解読するとしたら、 1秒に108回演算を行う能力を有するマシンを使用 鍵サイズ 512ﾋﾞｯﾄ 　 300年 768ﾋﾞｯﾄ 　　 　200万年 1024ﾋﾞｯﾄ 　　 　30億年

７．デジタル署名 公開鍵暗号技術の応用の１つとして重要なディジタル署名を話したいと思います。 2019/1/15

本物はどっち？ 明日の３時に公園で待っててください。 アリスより 明日の３時に駅で待っててください。 アリスより ある日、ボブの元へアリスから２通の手紙が届きました。 手紙1 手紙２ 明日の３時に公園で待っててください。 　　　　　　　　　　　　　　　　アリスより ボブ「おっアリスから手紙だ、なんだろう楽しみだなぁ」 明日の３時に駅で待っててください。 　　　　　　　　　　　　　　　　アリスより 2019/1/15

ボブ、どうする？ これではどっちの手紙が本当のアリス から来たかわかりません。 こんなとき、手紙に署名がついていればなぁ… ボブ「これじゃあ、どっちの手紙がアリスから来たのかわからないなぁ」 2019/1/15

もし、署名がついてたら Alice ＊☆←＃▼・⊆△▽※← 明日の３時に公園で待っててください。 アリスより 明日の３時に駅まで迎えに来てください Alice ボブ「本当にアリスからの手紙だな」 ＊☆←＃▼・⊆△▽※← 2019/1/15

物理的署名 本人であることを確認できるものがデジタル文書（e-mailなど）にもほしい デジタル（0と1だけ）で本人を確認するには？ 通帳と印鑑 クレジットカードとサイン いずれも本人にしかできない（持ってない）もの 本人であることを確認できるものがデジタル文書（e-mailなど）にもほしい デジタル（0と1だけ）で本人を確認するには？

公開鍵暗号方式で署名 公開鍵暗号では、暗号文は誰にでも作れる 送られてきた暗号文が本当にその人から来たかを確認したい 公開鍵暗号で実現可能

毎回同じ署名で大丈夫？ 文書毎に違う署名を付けなければならない もし、毎回同じ署名を使っていると 攻撃者に署名の部分を見つけられる その部分をコピーされる 文書毎に違う署名を付けなければならない 自分の署名が偽造されると大変困るわけです。 自分のクレジットカードが他人に勝手に使われると困るのと同じことなのです 2019/1/15

デジタル署名に要求されること 安全性（偽造不可） 正しいデジタル署名をつけられるのは、自分 だけ 検証が容易（誰にでも署名を確認できる） 　正しいデジタル署名をつけられるのは、自分　だけ 検証が容易（誰にでも署名を確認できる） 　　署名を確認することは易しい 相手に本当に自分であることが容易に確かめられる仕組みが求められます。

署名に必要なものとその用途 デジタル署名にも公開鍵と秘密鍵が必要 暗号化・復号化 デジタル署名 公開鍵 暗号化を行う （受信者の鍵） 署名を検証する （送信者の鍵） 秘密鍵 復号化を行う 署名を生成する 暗号通信用の鍵と署名用の鍵を同じにしてはいけないのです

署名をつけるには？ デジタル署名は署名者の秘密鍵（本人だけが知る秘密の情報）と文書から計算される 文書 署名 秘密鍵 署名は自分以外に付けれないものでなければなりません。そこで、署名を付けるには 自分の秘密鍵を用いるわけです。 秘密鍵

本当にアリスか？ 受信者ボブはアリスが送信したであろう暗号文を復号する 署名の部分を取り出し、これを検証する ボブの復号鍵 アリスの公開鍵 　　　　ボブの復号鍵　　アリスの公開鍵 ボブはアリスから受け取った暗号文を復号して、署名を検証します。 この文書を読むことのできる（復号できる）のは、ボブだけであり、しかも署名の検証は アリスの公開鍵を用いるので、簡単なのです。 暗号文 文書 検証 署名

本当にそれだけ？ ハッシュ関数が必要 実は、署名をつけるには鍵だけでは危険（存在的偽造による攻撃が可能） それは、存在的偽造と呼ばれる攻撃法から身を守るため

ハッシュ関数って何？ ハッシュ関数とはもともと辞書の構築などに用いられていた関数であり、メッセージダイジェスト関数ともいう ハッシュテーブル 一方向性関数の性質を説明します 文書のハッシュ値を求めることはやさしいのですが、 ハッシュ値から文書を割り出すことは非常に困難なのです ハッシュ関数 文書１ 文書2 文書3

暗号ハッシュ関数に求められること 効率性 一方向性（ハッシュ値から文書を求めることはできない） 安全性（衝突困難性） 文書をかいざんから守る 　（かいざんとは文書を不正に書きかえること） 　（衝突とは、文書が異なるがハッシュ値が同じである文書のこと） ハッシュ関数を暗号通信を行うごとに適用するので、計算に時間がかかっていては 使い物になりません。かといって、効率的にしようと手を抜いて衝突（文書は違うけれども ハッシュ値が同じになってしまうような文書のこと）すると成りすまされてしまいます

代表的なハッシュ関数 MD4（現在使われていない） MD5（POPで認証に使われている） SHA-1（デジタル署名の標準） ことが非常に多いのです。 どのくらい効率的かというと、1Mでおよそ4秒程度です。 SHA-1は160ビットのハッシュ値を出力

ハッシュを適用した署名生成法 文書 ハッシュ値 署名 署名を文書に添付し、全体を暗号化して送信 ハッシュ関数 アリスの秘密鍵 文書自体を入力にするのではなく、文書のハッシュ値を入力することで署名を生成します。 ハッシュ関数の衝突が見出せない限りこの方式の安全性は高いのです（文書を入力にするよりも）。 署名を文書に添付し、全体を暗号化して送信

ハッシュを適用した署名検証法 暗号文 ボブの復号化鍵 署名付文書 署名 文書 ハッシュ値 検証 アリスの公開鍵 ボブはアリスから受け取った暗号文を自分の暗号秘密鍵で復号化し、 署名付文書を得ます。この署名付文書から署名と文書の部分に分け、 まず文書からハッシュ値を計算します。このハッシュ値とアリスの署名公開鍵 を使って、署名を検証します アリスの公開鍵 検証

デジタル署名のまとめ デジタル署名はいわゆる本人認証を実現する技術である。 「まめだくん」では、鍵の更新およびユーザ削除の際に、本人認証を行い、公開鍵をかいざんから守っている。

８．まとめ

達成点 通常のメール操作で使用 ハイブリッド暗号を使っているので高速 RSA,ElGamal暗号を使った暗号通信 安全性を高めるために鍵の更新が可能

ハイブリッド暗号の概要 公開鍵暗号、古典暗号のデメリットを 補うようにして誕生 公開鍵暗号と古典暗号を組み合わせて 使用 情報だけでなく鍵も暗号化

古典暗号 暗号化と復号化に同じ鍵を使う暗号 日本語版シーザ暗号 むやづ こい まめだ くん まめだ くん あ → う い → え う → お +2 -2 あ　→　う い　→　え う　→　お 鍵を２と決める

比較（公開鍵暗号のメリット） 公開鍵暗号 鍵管理が容易 鍵を公開 古典暗号 鍵管理が困難 暗号通信以前に鍵を 取り決め、鍵を秘密

比較（古典暗号のメリット） 公開鍵暗号 長い文書の暗号化・ 復号化は低速 古典暗号 長い文書の暗号化・ 復号化が高速

ハイブリッド暗号の動き 復号化 暗号化 平文 暗号文 平文 した鍵 暗号化 古典暗号 古典暗号 公開鍵暗号 公開鍵暗号

今後の課題 TDESからAESへの移行 鍵サーバの耐久性 一般ユーザの評価 メーラーとしての機能の充実