数理・情報科学概論 代数学と暗号 第一回 暗号の重要性 大阪府立大学総合科学部 数理･情報科学科 高橋哲也 暗号の目的 • 暗号の目的 情報を第三者に知られることなく伝えること （秘匿） 伝達（通信）の途中で第三者が見ても元の情 報（文章）が分からないように暗号化する。 現在ではより広く改竄防止、認証（本人確 認）にも用いられる。この認証が電子政府実 現にも不可欠 暗号の利用 • 暗号理論の使われる場面 ・コンピュータ内部のデータの保護 ・個人のプライバシーを保護する安全で確実 な通信システムの構築（携帯電話、電子メー ル） ・電子商取引に必須な電子決済システム ・電子政府における個人認証（本人確認） インターネットの普及により急速に高 まる重要性 電子政府 • 行政情報の電子的提供 • 行政への申請・届出の電子化 • 政府調達の電子化 等等 問題点 •セキュリティは大丈夫か •プライバシーの保護 電子政府の実現の中心は暗号技術！ 電子政府 http://www.atmarkit.co.jp/fsecurity/special/21gpki/gpki01.html より引用 暗号の用語 • 暗号の用語と一般的な枠組 ［用語］ 平文---元の文章（文字列） 数字（ビット列）に変換したものも平文と呼ぶ 暗号文---平文を暗号化したもの 暗号化関数---平文を暗号文に変換する仕組み（ア ルゴリズム） 数字に対しては関数として記述される。暗号化 関数には、暗号化の為の鍵が変数として必要で ある。 暗号の用語 復号化 ---暗号文を平文に戻すこと。復号 化関数は暗号化関数の逆関数である。 （暗号化して復号化すれば元に戻る） 復号化の為の鍵も必要。 平文 盗聴者 平文 暗号化 暗号文 送信者 復号化 暗号文 受信者 暗号の例 暗号の例（古典暗号） • 換字式暗号 平文に現れる文字を他の文字に置き換えて暗 号文を作る方法。 ［例］シーザー暗号 アルファベット順に３つ後ろへずらす。（z の次はa とする）鍵は３ angouhaomosiroi （平文） dqjrxkdrprvlurl（暗号文） 暗号の例２ • 転置式暗号 平文に現れる文字の順序を入れ換えて暗号文 を作る方法 ［例］横木柵暗号 o r u v y s p e t r i e t a a f c e n r i k e u s osakaprefectureunivesity (平文) oruvyspetrietaafcenrikeus(暗号文) 鍵は棚の数で４ 現代の暗号 • ネットワーク暗号 コンピュータネットワークで用いられるよう になり、暗号はその性格が大きく変化 ネットワークで使う暗号に必要な条件 ・アルゴリズムの公開 ・世界中で安全性のチェック ・暗号化に時間がかからない （コンピュータを用いて） DES • 現代の暗号の歴史 (DES と RSA) 1970年代以降、ネットワークのための新しい暗 号 DES（Data Encryption Standard) ・米国商務省標準局(NBS) が公募し、1977年に公布 ・アルゴリズムを公開し，暗号の安全性を鍵の秘 匿のみに依存。 ・鍵の長さは、56ビット DES ・アルゴリズムは換字式暗号と転置式暗 号を組み合わせて16回繰り返す。 ・計算機の性能向上により、パソコン１ 万台で１日弱で破られるようになり次 世代の標準暗号(AES)の策定が行われて 歴史的使命を終えた。 ・米国の暗号政策として、長い間、輸出 禁止であった。（現在は暗号の殆どの 輸出規制はなくなっている） RSA • RSA 暗号化するときの鍵を公開するという公開鍵 暗号の最初の実装(1977)。開発者Rivest, Shamir, Adleman の頭文字を取ってRSA暗号と 呼ばれる。 ・大きな整数（300桁ぐらい）の素因数分解が 難しいことに基づくアルゴリズム。 ・現在は、鍵の長さは512ビットか1024ビット この暗号について詳しく説明。 公開鍵暗号 • 公開鍵暗号とは暗号化の為の鍵を公開 し、復号化の為の鍵を秘密にするもの である。（それ以前は暗号化の鍵と復 号化の鍵が同じであった）この暗号方 式によって鍵を相手に送らなくても暗 号を送れるようになった。 ・公開鍵方式は、1976年に Diffie,Hellman によって提唱された。 公開鍵方式でない暗号を秘密鍵暗号と いう。 公開鍵暗号 • 公開鍵暗号の仕組み 鍵 Kで暗号化 y=f(x,K) 平文 x 暗号文 y 送信 平文 x 暗号文 y 鍵 K’で暗号化 x=g(y,K’) 暗号化と復号化の鍵が異なる! 暗号方式の比較 • 秘密鍵暗号と公開鍵暗号の比較 暗 号 復 号 ア ルゴ 化鍵 化鍵 リ ズム 秘密 非 公 鍵 開 公 開 公開 鍵 非 公 公開 開 非 公 公開 開 暗 号 化 速度 速い 遅い 上記の表のような特長があるため、本 文全体の暗号化には、秘密鍵暗号を 使い、秘密鍵の送信に公開鍵暗号を 使うのが一般的。また、公開鍵暗号は 電子署名にも使える。 認証（電子署名） • 認証（本人確認） 認証とは、電子商取引やE-mail の送信 の際に確かにその人であることを確認 する手段である。電子署名（印鑑の代 わり）もその一形態。 • 公開鍵暗号での電子署名 秘密鍵と公開鍵を入れ換えると電子署 名ができる。電子署名が自然に実現で きることが公開鍵の大きな利点 電子署名の例 ［電子署名の例］ A さんの公開鍵を K、 秘密鍵をK’ とする。 A さんが署名x（自分の名前とか本文の要約 など）を自分の秘密鍵を使って暗号化する。 y=g(x,K’) これを受け取ったBさんは、 公開されているAさんの公開鍵 K を用いて f(y,K)を計算しその結果が x と等しければ確 かにAさんだと確認できる。 公開鍵と代数学 公開鍵暗号と実現するアルゴリズムに代数学が用いられる。 集合にある種の演算が定義されているときその演算まで込め てその集合の構造を理解しようとする学問が代数学である。 （こういうと難しいが演算は足し算、かけ算などのよく知られた 演算が殆ど） 整数論、群論、有限体上の代数幾何などが使われるがここで は、整数論、群論（いずれも初歩）が使われるRSA暗号という 公開鍵暗号の説明に必要な理論を説明する。 RSAの説明は以下のPDF file にまとめてあります。 http://wwwmi.cias.osakafu-u.ac.jp/~takahasi/2002/rsa.pdf
© Copyright 2024 ExpyDoc
