Comments
Description
Transcript
課題1 公開鍵の詳細 1. 暗号化
課題 1 公開鍵の詳細 1. 暗号化 暗号化とは、インターネットなどのネットワークを通じて文書や画像などのデジタルデータをやり取りする際に、 途中通信で第三者に盗み見られたり改ざんされたりされないように決まった規則に従ってデータを変換すること。 文章を暗号化するには、文字コードを用いて数値化する必要がある。暗号化、復号には暗号表にあたる「鍵」を 使うが、対になる二つの鍵を使う公開鍵暗号と、どちらにも同じ鍵を用いる共通鍵暗号がある。 ・文字コードの種類 （１）ASCII ASCII とは、アルファベットや数字、記号などを収録した文字コードの一つ。最も基本的な文字コードとして世 界的に普及している。7 ビットの整数（0∼127）で表現され、ラテンアルファベット（ローマ字）、数字、記号、 空白文字、制御文字など 128 文字を収録している。ASCII は ISO 標準 7 ビット文字コード ISO/IEC 646 の元と なり、後に 8 ビット文字コードである ISO/IEC 8859 が主流となって以降、世界中で使用されている様々な文字 の符号化方式の多くは、ASCII で使用されていない 128 番以降の部分に、その他の文字を割り当てたものである。 表 ASCII 文字コード表 コード 備考 制御文字 00-1F 空白 20 図形文字 21-7E 7F 制御文字 (DEL) 改行コードの違い 改行コード 代表的な環境 LF(0x0a) UNIX CR(0x0d) MacOS CRLF(0x0d0a) Windows （２）UTF-8 UTF-8 とは、Unicode の 16 ビット文字セットを、8 ビットのバイト列に変換するための技術仕様のことである。 UTF-8 は 8 ビットの可変長マルチバイトで文字を表現している。UTF-8 方式を用いて文字列を変換すると、Unicode の最初の 128 文字を変換した結果が ASCII コードと全く同じくなる。そのため、旧来の処理システムとも親和性 が高く保つことができる。このとき UTF-8 は、英数は 1 バイトで表現し、日本語は 3 バイトで表現する。そのた め、UTF-16 と比べるとデータのサイズが大きくなってしまうという面もあり、UTF-8 と UTF-16 に関しては状 況によって使い分ける必要がある。 表 UTF-8 文字コード表 コード カテゴリ 1 バイト文字 00-7x 8x,9x,Ax,Bx 備考 UT-ASCII に同じ 多バイト文字の 2 バイト目以降 Cx,Dx 2 バイト文字の開始バイト Ex 3 バイト文字の開始バイト Fx 4 バイト以上の文字の開始バイト 漢字はおおむねこれで開始 F0-F7 は 4 バイト、F8-FB は 5 バイト FC-FD は 6 バイト ・UTF-8 と UTF-8N の違い UTF-8 BOM 付き UTF-8N BON なし 1 テキストエディタの対応状況 アプリケーション UTF-8 UTF-8N メモ帳 読み○ 書き○ 読み× 書き× eclipse 読み○ 書き○ 読み× 書き× 秀丸エディタ 読み○ 書き△ 読み× 書き○ BOM（Byte Order Mark） BOM とは、Unicode の UTF-16 など 16 ビット幅のエンコーディング方式において、エンディアンを指定するた めにファイルの先頭に記入される 16 ビットの値。 UTF-16 などではビット列の並びとしてビッグエンディアンとリトルエンディアンの両方を許容しているため、誤っ たエンディアンで文書を読み込むと判読できなくなってしまう。このため、ファイルの先頭の BOM を読んで、文 書がどちらのエンディアンで作成されたかを判別してから本文を読み込む。 BOM は 16 進数で「FEFF」という 16 ビットの値で、誤ったエンディアンで読み込むと、これが「FFFE」とな る。BOM が「FFFE」となった場合には逆のエンディアンを使って読み込めば正しく読み込むことができる。 BOM はエンディアンの判別だけでなく、文書が Unicode で記述されているかどうかを判別するために用いられる こともある。このため、エンディアンが関係ない UTF-8 などの文書でも先頭に BOM がついている場合がある。 （３）Shift-JIS Shift JIS コードとは、日本語文字コードの一つ。Microsoft 社によって策定された。文字の 1 バイト目を見るだけ で漢字か 1 バイト文字（いわゆる半角英数字）か分かる、等幅フォントで表示した場合に画面上の桁数とバイト数 が一致するなどの特長から、同社の MS-DOS や Windows、Apple 社の Mac OS など、パソコンの標準文字コー ドとして広く普及した。 表 Shift-JIS 文字コード表 コード カテゴリ 備考 0x00-ox1f,0x7f 1 バイト文字 制御コード 0x20-0x7e 1 バイト文字 ASCII 文字 0x829f-0x82f1 2 バイト文字 全角ひらがな 0x8340-0x8396 2 バイト文字 全角カタカナ 0x8940-0x9ffc 2 バイト文字 全角漢字 （４）JIS JIS とは、日本工業規格（JIS X 0208）で規定されている日本語の文字コードである。Windows をはじめ、日本 語の文字コードとして最も一般的に用いられている文字コードの一つとなっている。 表 Shift-JIS 文字コード表 コード カテゴリ 備考 0x00-0x1f,0x7f 1 バイト文字 制御コード 0x20-0x7e 1 バイト文字 ASCII 文字 0x21-0x5f 1 バイト文字 JIS7(7 ビット JIS) の半角カタカナ 0xa1-0xdf 1 バイト文字 JIS8(8 ビット JIS) の半角カタカナ 0x2421-0x2473 2 バイト文字 全角ひらがな 0x2521-0x2576 2 バイト文字 全角カタカナ 0x3021-0x7c6e 2 バイト文字 全角漢字 （５）EUC-JP EUC-JP とは、文字コード体系の EUC（Extended Unix Code）の各国定義部分に日本語文字集合の割り当てを 定義したものである。UNIX で日本語を扱うために使用されている。EUC は 1985 年に「UNIX システム日本語機 2 能提案書」の中で定義された日本語用 UNIX 内部コード体系に基づいて、 世界各国で使用可能なように拡張した コード体系である。日本語 EUC は 4 種類の文字セットで構成される。ASCII 文字は 1 バイトで、JIS X 0208-1990 （新 JIS）は 2 バイト。JIS X 0201（1 バイトカタカナ）は 1 バイト目に 16 進数 8E の制御コードとし、続く 1 バ イトに割り振り 2 バイトで定義する。16 進数 8F の制御コードに続く 2 バイトに JIS X 0212-1990（補助漢字）を 割り振っている。 表 EUC-JP 文字コード表 コード カテゴリ 備考 0x00-0x1f,0x7f 1 バイト文字 制御コード 0xa4a1-0x7e 1 バイト文字 ASCII 文字 0xa4a1-0xa4f3 2 バイト文字 全角ひらがな 0xa5a1-0xa5f6 2 バイト文字 全角カタカナ 0xb0a1-0xfcee 2 バイト文字 全角漢字 0x8ea1-0x8edf 2 バイト文字 半角カタカナ （６）Base64 データを 64 種類の印字可能な英数字のみを用いて、それ以外の文字を扱うことの出来ない通信環境にてマルチ バイト文字やバイナリデータを扱うためのエンコード方式である。かつての電子メールを送るためのプロトコル SMTP では、ASCII といわれる 7byte で表現される英数字しか送ることができず、メールを使って画像や音声な どのデータをやりとりしたいと思った時に、英数字しか対応していなかったので、送受信することができなかっ た。Base64 は MIME によって規定されていて、7 ビットのデータしか扱うことの出来ない電子メールにて広く利 用されている。そこで、すべてのデータを英数字で表す MIME(Multipurpose Internet Mail Extensions) という 規格が登場し、その中で base64 というデータの変換方法が定められた。これによって、受信側と送信側が MIME に則ってエンコード・デコードをすることで、メールを通して画像や音声などの送受信が可能になった。具体的 には、A∼Z, a∼z, 0∼9 までの 62 文字と、記号 2 つ (+, /)、さらにパディング（余った部分を詰める）のための 記号として = が用いられる。 表 Base64 文字コード表 コード 備考 0-25 大文字アルファベット（A∼Z) 26-51 小文字アルファベット（ａ∼ｚ） 53-61 数字（0∼9） 62 + 63 / 〈変換手順〉 1. 元データを 6 ビットずつに分割。（6 ビットに満たない分は 0 を追加して 6 ビットにする） 2. 各 6 ビットの値を変換表を使って 4 文字ずつ変換。（4 文字に満たない分は = 記号を追加して 4 文字にする） 例 1) ”code ”を 16 進、2 進にコード変換せよ (16 進)63 6f 64 65 (2 進)0110 0011 0110 1111 0110 0100 0110 0101 例 2) ”あいうえお ”を base64 でコード変換せよ 文字列：”あいうえお ” （UTF-8 の場合） 16 進表示：e38182、e38184、e38186、e38188、e3818a 2 進表示：1110 0011 1000 0001 1000 0010、1110 0011 1000 0001 1000 0100、1110 0011 1000 0001 1000 0110、 3 1110 0011 1000 0001 1000 1000、1110 0011 1000 0001 1000 1010 6 ビットずつに分割 111000 111000 000110 000010 111000 111000 000110 000100 111000 111000 000110 000110 111000 111000 000110 001000 111000 111000 000110 001010 変換表により、４文字ずつ変換 ”44 ＧＣ ”、”44 ＧＥ ”、”44 ＧＧ ”、”44 ＧＩ ”、”44 ＧＫ ” Base64 文字列 ”44 ＧＣ 44 ＧＥ 44 ＧＧ 44 ＧＩ 44 ＧＫ ” (Shift-JIS の場合) 16 進表示：82a0、82a2、82a4、82a6、82a8 2 進表示：1000 0010 1010 0000、1000 0010 1010 0010、1000 0010 1010 0100、1000 0010 1010 0110、1000 0010 1010 1000 6 ビットずつに分割 100000 101010 000010 000010 101000 101000 001010 100100 100000 101010 011010 000010 101010 00 2 ビット余るので、4 ビット分 0 を追加して６ビットにする 100000 101010 000010 000010 101000 101000 001010 100100 100000 101010 011010 000010 101010 000000 変換表により、4 文字ずつ変換 ”gqCC ”、”ooKk ”、”gqaC ”、”qA ” 2 文字文余るので、２文字分＝記号を追加して 4 文字にする ”gqCC ”、”ooKk ”、”gqaC ”、”qA== ” Base64 文字列 ”gqCCooKkgqaCqA== ” (EUC-JP の場合) 16 進表示：a4a2、a4a4、a4a6、a4a8、a4aa 2 進表示：1010 0100 1010 0010、1010 0100 1010 0100、1010 0100 1010 1000、1010 0100 1010 1010 6 ビットずつに分割 101001 001010 001010 100100 101001 001010 010010 101000 101001 001010 1010 4 ビット余るので、2 ビット分 0 を追加して 6 ビットにする 101001 001010 001010 100100 101001 001010 010010 101000 101001 001010 101000 変換表により 4 文字ずつ変換 ”pKKk ”、”pKSo ”、”pKo ” 3 文字文余るので、1 文字分＝記号を追加して 4 文字にする ”pKKk ”、”pKSo ”、”pKo= ” Base64 文字列 ”pKKkpKSopKo= ” 例 3）”44 ＧＣ 44 ＧＥ 44 ＧＧ 44 ＧＩ 44 ＧＫ ”を Base64(UTF-8) でエンコードせよ Base64 文字列 ”44 ＧＣ 44 ＧＥ 44 ＧＧ 44 ＧＩ 44 ＧＫ ” 4 4 文字ずつに分割 ”44 ＧＣ ”、”44 ＧＥ ”、”44 ＧＧ ”、”44 ＧＩ ”、”44 ＧＫ ” 変換表により変換 111000 111000 000110 000010 111000 111000 000110 000100 111000 111000 000110 000110 111000 111000 000110 001000 111000 111000 000110 001010 4 ビットずつに分割 1110 0011 1000 0001 1000 0010、1110 0011 1000 0001 1000 0100、1110 0011 1000 0001 1000 0110、1110 0011 1000 0001 1000 1000、1110 0011 1000 0001 1000 1010 16 進表示に直す e38182、e38184、e38186、e38188、e3818a UTF-8 変換表により変換 ”あいうえお ” 2. 復号 復号とは、暗号化やデータ圧縮などがされたデータから、元のデータを復元すること。暗号の場合には、暗号化 に用いた秘密の情報（暗号鍵）を用いて元のデータを得ることを意味し、これを用いずに元の情報を復元するこ とは「解読」という。「復号化」と表記する例も見られるが、（「暗号」が暗号文の意味を持ち、変換作業のことを 「暗号化」というのに対し）暗号文から元のデータに戻す作業自体を復号という（復号というデータは存在しない） ことから、復号化という表記は誤りであるとみなされることが多い。 3. 共通鍵暗号 共通鍵暗号とは暗号化と復号に同一の鍵を使う暗号方式である。暗号文の受信者と送信者で同じ鍵を共有する必 要があり、暗号文を送受信する前にあらかじめ安全な経路を使って秘密の鍵を共有する必要がある。公開鍵暗号が 発明される前までは、暗号といえば共通鍵暗号のことであった。 利点：共通鍵暗号は公開鍵暗号よりも処理時間が早い。 欠点：暗号化と復号に同じ鍵を使用するため、第三者に鍵を知られてしまうとデータを復号されてしまう。また、 通信接続先ごとに鍵を作成しなくてはならない。 4. 公開鍵暗号 公開鍵暗号とは暗号化に使う鍵と復号に使う鍵が分離されており、暗号化に使った鍵で復号を行うことができず、 片方からもう一方を割り出すことも容易にはできないようになっている。鍵の持ち主は復号に使う鍵のみを他人 に知られないように管理し、暗号化に使う鍵は公開する。このため、暗号化に使う鍵は公開鍵、復号に使う鍵は 秘密鍵と呼ばれる。 利点：暗号化されたメッセージは受信者の持つ秘密鍵でしか復号できないため、途中で第三者に傍受されても中 身を解読されることはない。また、暗号に使う公開鍵は第三者に知られても解読されないため、鍵の安全な輸送 が必要なく、安全性も高い。 欠点：公開鍵暗号は共通鍵暗号よりも処理が複雑になりがちであり、より多くの計算資源や時間を必要とする。 4.1. 4.1.1. 公開鍵の種類 DH 法（Diffiel-Hellman) DH 法（Diffie-Hellman 鍵交換）とは、公開鍵暗号方式が考案される以前の 1976 年に、Whitfield Diffie 氏と Martin E. Hellman 氏によって考案された、安全でない通信経路を使って秘密鍵を安全に送受信するための鍵交換方式。 公開鍵を交換する暗号方式としては世界で始めて登場した方式とされ、IETF によって RFC 2539 として規格化さ 5 れている。 Diffie-Hellman 鍵交換方式では、離散対数問題を利用した計算によって生成された値を公開情報として相手に送 る。計算には乱数を用いるが、その乱数は秘密鍵として非公開のまま保持しておく。公開情報を受け取った相手 は、同様に自分の方で公開情報と秘密情報をランダムに生成した上で、自分が掲載によって得た公開情報を返す。 お互いの秘密情報は交換することなく、計算の元となった値を共有することが可能になる。離散対数問題の解析的 な解法が見つかっていないことを安全性の根拠としている。 〈ネットワーク公開情報〉 ネットワーク全体で共通に使用する情報として、ランダムに生成された素数 p と Zp*の原始元 g が公開されてい ると仮定する。 〈鍵生成アルゴリズム〉 ・送信者は 0 ≦ a ≦ p-2 となる a をランダムに選び、yA = g a (mod p) を計算する。[補講]Zp=0,…,p-1（要素が p 個）、Zp*=1,…,p-1（要素が p-1 個）である。つまり、0 ≦ a ≦ p-2 は、0 からカウントするので p-1 個で一致し ている。次に、yA を公開鍵として公開し、a を秘密鍵として秘密に保持する。 ・受信者は 0 ≦ b ≦ p-2 となる b をランダムに選び、yB = g b (mod p) を計算する。 次に、yB を公開鍵として公開し、b を秘密鍵として秘密に保持する。 〈鍵共有アルゴリズム〉 ・送信者は自分の秘密鍵 a と受信者の公開鍵 yB を入力として、次を計算する。 KA = (yB )a (mod p) ・受信者は自分の秘密鍵 b と送信者の公開鍵 yA を入力として、次を計算する。 KB = (yA )b (mod p) ここで、K = g ab (mod p) とおくと、K = KA = KB となる。 よって送信者と受信者は秘密鍵 K を秘密に共有できる。 4.1.2. RSA 法 (Rivest-Shamir-Adleman) 代表的な公開鍵暗号系のひとつである。一方向性関数の性質を利用することで暗号化を可能としている。暗号化 だけでなく署名などにも応用ができる。 〈歴史〉RSA 暗号は 1977 年に R.L.Rivest、A.Shamir、L.Adleman によって考案された。RSA 暗号の名称は、ア ルゴリズムの開発者の頭文字（R.L.Rivest、A.Shamir、L.Adleman）が由来である。 〈鍵生成〉次のアルゴリズムを実行する。 1：2 つの大きな素数 p,q を生成し、N=pq を計算する。 2：GCD((p-1)(q-1),e)=1 となる e をランダムに選ぶ。 3：拡張ユークリッドの互除法により、 ed ≡ 1 mod (p − 1)(q − 1) となる d を求める。 4：pk=(N,e) を公開鍵として公開し、d を秘密鍵として保持する。 〈暗号化〉公開鍵 (N,e) と平文 m(∈ ZZ) を入力として、次のように暗号文 c を計算する。 c = me mod N 6 〈復号〉秘密鍵 d と暗号文 c を入力として次のように計算し、平文 m に復号する。 ce mod N 本当にこれが m になっているかどうか確かめれば、公開鍵暗号系の仕様がいえたことになる。 [証明] ed ≡ 1 (mod (p-1)(q-1)) (p-1)(q-1)|ed-1 p-1|ed-1 ∴ed ≡ 1 (mod p-1) 一方、 cd ≡ (me )d ≡ med ≡ m mod p （∵定理「p が素数で、x が x ≡ 1 (mod p-1) をみたすとき、任意の整数 a に対して 「ax ≡ a (mod p)」が成り立つ） ∴cd -m ≡ 0 (mod p) 同様に、cd 互いに素なので、cd -m は p と q 両方で割り切れる。 cd -m ≡ 0 (mod pq) ∴cd ≡ m (mod N) 例） ・ユーザーＡが鍵を生成する 1:素数 p=5,q=11 とする。N=55 となる 2:e=3 とする (p-1)(q-1)=40 なので、e と互いに素である 3:ユークリッド互除法で d を求める d = −13 ≡ 40 − 13 = 27 mod 40 4:e=33,N=55 を公開鍵として公開し、d=27 を秘密鍵として保持 ・ユーザー B がユーザー A に m=7 を暗号化して送る B は公開鍵 e=3,N=55 を取得 暗号文 C = 73 mod 55 = 343 mod 55 = 13 ・ユーザー A による暗号文 13 の復号操作 ユーザー A は秘密の復号鍵 d=27 を知っている 1327 mod 55 を計算する 132 ≡ 4、134 ≡ 16、138 ≡ 36、1316 ≡ 31 1327 ≡ 31 × 36 × 4 × 13 ＝ 58032 ≡ 7 mod 55 復号結果は 7 4.1.3. 楕円曲線暗号 楕円曲線上の演算規則を利用した新しい公開鍵暗号技術で、次世代公開鍵暗号として注目されています。RSA 暗 号と比較して短い鍵長で同レベルの暗号強度を提供すると言われています。 〈楕円曲線上の離散対数問題〉離散対数問題 (Discrete Logarithm Problem: DLP) は，以下のように定義される。 7 (G, ・) を有限群，α, β ∈ G とする．β = α x なる x が存在するとき，整数 x を求めよ。 この x を離散対数という。有限群 (G, ・) に対しては，以下の性質が要求される．1. 群演算 ・ が簡明に記述で きる．2. 群位数 G の計算が容易である．3. G 上の離散対数問題が計算量的に困難である． Diffie-Hellman の公開鍵暗号システムは，有限体の乗法群 F*q を用いていた． 近年の離散対数問題についてのア ルゴリズムの研究の進展と計算機の能力の向上に伴い，乗法群 F*q を用いた場合の安全性を保持するために必要 な q のサイズが大きくなってきている．現在では，q のサイズは最低でも 1024 ビット以上必要と言われている． 実用上の観点から，安全性を保持しつつサイズの小さい位数の群により Diffie-Hellman 方式などを実現すること が望まれる．それに対応するのが楕円曲線暗号系である． 1986 年に V.Miller と N.Koblitz は，有限体上で定義される楕円曲線のヤコビアン群に含まれる有限巡回群が，上 記の一方向性の性質を足していることを見出し，楕円曲線に基づく暗号化システムを提唱した． 一般に，体 K 上 定義される楕円曲線の場合，その K-有理点はある加法のもとで有限群をなすことが知られている． また，2 つの 有理点 P，Q の加法演算によって得られる有理点 R の各座標は，P，Q の各座標の簡単な有理式によって表され る． すなわち，以下に示すように有限体上の離散対数問題を楕円曲線上で定義したものである． ∼楕円曲線上の離散対数問題∼ Y = x G の Y から x を求める問題 (Y，G は有限体 Fq 上の楕円曲線上の点，x G は G をスカラー倍 (x 倍) す る演算) である．Y が公開鍵，x が秘密鍵 (G は公開システムパラメータ) に対応する． ∼楕円曲線離散対数楕円曲線∼ E 上の点 G が素数の位数 r を持つとする (ここで，r2 は楕円曲線の位数 E(Fq) を割り切らない)． このとき，あ る m に対して P = m G が満足されるのは，r P = O の時に限られる． 係数 m は P の基点 G に関する楕円曲 線離散対数と呼ばれる． 楕円曲線離散対数は，法 r の整数である． 楕円曲線の群については，前述の 3 つの要件のうち 1. の群演算の簡明さについては，楕円曲線上の加法は問題な くこれを満たし，3. の安全性についても一部の曲線を除けば優秀である． F*q と比較すると 1：1024 ビットの q に対する F*q 上の離散対数問題 (DLP) 2：約 160 ビットの位数 r に対する楕円曲線上の離散対数問題 (ECDLP) がほぼ同等の安全性を持つと言われている．従って，効率面と安全性のバランスとから見ると楕円曲線の方が有 利であると言える． 但し，ECDLP が実用的時間では解けないような曲線を選択する必要がある． 〈楕円曲線暗号〉楕円曲線 E 上の基点 (ベースポイント) G が位数 r を持つとする． このとき，鍵ペアを以下の ように定義する． 1：秘密鍵 s は，法 r に基づく整数 2：公開鍵 W は，W = s G で定義される楕円曲線 E 上の点 公開鍵から対応する秘密鍵を求めるには，楕円曲線離散対数を計算することが必要である．このため，このタイ プの公開鍵暗号の安全性は，楕円曲線離散対数問題の困難性に依存する． 参考文献 [1] SecurityAkademeia〈http://akademeia.info/index.php?FrontPage〉 [2] IT 用語辞典 e-Words〈http://e-words.jp/〉 [3] シニアエンジニアの庵〈http://sehermitage.web.fc2.com/cmath/ec-calc.html〉 [4] マスター IT〈http://www.atmarkit.co.jp/ait/articles/1504/27/news032.html〉 [5] base64ってなんぞ？？理解のために実装してみた¡http://qiita.com/PlanetMeron/items/2905e2d0aa7fe46a36d4¿ 8