グループ報告書
Future University Hakodate 2011 System Information Science Practice Group Report
プロジェクト名
暗号解読の可視化Project Name
Visualization of Code-Breakingグループ名
RSA・楕円曲線暗号グループGroup Name
RSA Code・Elliptic Curve Cryptograrhy Group
プロジェクト番号/Project No. 13-B
プロジェクトリーダ
/Project Leader
1009087 大久保貴裕 Takahiro Okuboグループリーダ
/Group Leader
1009064 伊藤拓海 Takumi Itoグループメンバ
/Group Member
1009064 伊藤拓海 Takumi Ito 1009067 亀井謙斗 Hanako Hakodate 1009076 永井善孝 Yoshitaka Nagai 1009145 及川真那実 Manami Oikawa指導教員
白勢政明 小西修Advisor
Masaaki Shirase Osamu Konishi
提出日
2012年1月18日Date of Submission
本プロジェクトでは暗号の解読を可視化し暗号に興味のない人にも楽しんでもらえるような装 置を実装する。前半は誕生日パラドックスグループ、RSA暗号グループ、楕円曲線暗号グルー プ、実装グループの4つのグループに分かれて暗号について学習した。後半ではRSA暗号グ ループと楕円曲線グループを合わせ学習した。 RSA暗号は桁の大きい数の素因数分解の難しさより安全性が確保されている暗号であり、広 く一般的に使われている。また楕円曲線暗号は比較的新しい暗号でRSA暗号よりも計算時間 が短く処理も早いがRSA暗号と同等の処理ができる。広く一般的に使われており、一般の人 がイメージする共通鍵暗号の解読には頻度分析のような考え方が必要となる。これに対して公 開鍵暗号であるRSA暗号や楕円曲線暗号は誕生日パラドックスの考え方を利用して解読する ことができる。そのため誕生日パラドックスは暗号の世界ではとても重要である。本プロジェ クトではこのようなことをわかりやすく可視化するためのアプリケーションを実装したい。 キーワード キーワード 公開鍵暗号，誕生日パラドックス，RSA暗号，楕円曲線暗号 （文責:伊藤拓海）
This project implements a device for person who are not interested in cryptography to enjoy by visualization of break. Then, we divide into four groups, Birthday paradox, RSA cryptography, Elliptic Curve Cryptography, Implementation and learn it about a code the first term. The RSA cryptograph group and the Elliptic Curve Cryptography were united and learned the second term.
RSA cryptography is generally used widely because safety is secured by the hardness prime factoring of big numerical. Elliptic Curve Cryptography is a relatively new cryp-tography. Elliptic Curve Cryptography can handle the processing that is equal to RSA cryptography in short time. Attacker of Symmetric key cryptography which many per-sons images needs thought such as the Frequency analysis. On the other hand, public key cryptosystems such as RSA and elliptic curve cryptographies can decipher by using a way of thinking of Birthday paradox. Therefore the birthday paradox is very impor-tant in the fild of the cryptography. We want to implement plain visualization of the decryption by this project.
Keyword Public key cryptosystem, Birthday Paradox, RSA cryptography, Elliptic Curve Cryptography
目次
第1章 背景 1 1.1 現状における問題点 . . . 1 1.2 課題の概要 . . . 1 第2章 到達目標 2 2.1 本プロジェクトにおける目的 . . . 2 2.2 具体的な手順・課題設定 . . . 2 第3章 課題解決のプロセスの概要 4 3.1 前期. . . 4 3.2 後期. . . 4 第4章 暗号とは 5 4.1 平文. . . 5 4.2 暗号化 . . . 5 4.3 復号. . . 5 4.4 アルゴリズム . . . 5 4.5 鍵 . . . 5 4.6 公開鍵 . . . 5 4.7 秘密鍵 . . . 6 4.8 公開鍵暗号 . . . 6 4.9 共通鍵暗号 . . . 7 4.10 DES暗号 . . . 7 4.11 デジタル署名 . . . 7 4.12 ユーザ認証 . . . 8 4.13 情報の保護 . . . 9 4.14 暗号の安全性 . . . 10 第5章 RSA暗号とは 11 5.1 特徴. . . 11 5.2 秘密鍵と公開鍵. . . 11 5.3 暗号化と復号 . . . 11 5.4 安全性 . . . 12 5.5 ρ法. . . 12 5.6 RSA暗号の例 . . . 13 第6章 暗号に必要な4つの条件 15 6.1 機密性 . . . 15 6.2 完全性 . . . 156.4 否認防止 . . . 15 第7章 暗号化と復号 16 7.1 RSA暗号の実装例 . . . 16 7.2 ユークリッドの互除法 . . . 16 7.3 拡張されたユークリッド互除法 . . . 17 7.4 暗号化 . . . 17 7.5 復号. . . 18 7.6 ρ法による解読. . . 19 第8章 楕円曲線暗号 21 8.1 楕円曲線とは . . . 21 8.2 楕円曲線上での演算 . . . 21 8.3 加算. . . 21 8.4 ２倍算 . . . 22 8.5 スカラー倍算 . . . 22 8.6 楕円曲線上の離散対数問題 . . . 23 8.7 楕円曲線暗号とは . . . 23 8.8 特徴. . . 23 8.9 楕円エルガマル暗号 . . . 24 8.10 成果. . . 26 第9章 課題解決のプロセスの詳細 28 9.1 全体のプロセス. . . 28 9.2 各人の課題の概要とプロジェクト内における位置づけ . . . 28 9.3 担当課題と他の課題の連携内容 . . . 35 9.3.1 伊藤拓海 . . . 35 9.3.2 亀井謙斗 . . . 35 9.3.3 永井善孝 . . . 35 9.3.4 及川真那実. . . 35 第10章 発表会評価 36 10.1 中間発表 . . . 36 10.1.1 発表技術について . . . 36 10.1.2 発表内容について . . . 36 10.1.3 中間発表の評価まとめ . . . 37 10.2 最終発表 . . . 38 10.2.1 発表技術について . . . 38 10.2.2 発表内容について . . . 39 10.2.3 最終発表の評価まとめ . . . 40 第11章 結果 42 11.1 成果. . . 42
第12章 今後の展望 44
第13章 相互評価 45
付録A 新規習得技術 50
付録B 活用した講義 51
第
1
章 背景
情報化社会の現代においてインターネットというのは身近な存在になっている。携帯電話やパソ コンから誰でも気軽にアクセスができるようになった。インターネットがつながっている場所なら ばどこでも世界中の人とコミュニケーションが取れたり、どのようなことが起こっているかなどの 情報を得ることができる。しかしこれは第三者が簡単に他人の情報を得ることができたり他人にな りすましたりすることができるようになってしまったといえる。インターネットを利用する上でこ のようなことを防ぐためにもセキュリティ技術は欠かすことができないものである。 セキュリティ技術の中でも暗号技術というのは広く使用されているものである。暗号化は第三者 に通信内容を見られても読めないように変換する表記法で特殊な知識がない限りは見ることができ ない。通信のみでなく保管する文章などにも使用できる。 しかしインターネット利用に置いて重要で身近なものでも一般には認識が薄いところがある。パ スワードを覚えやすい簡単な文字列にしたり、他人に分かってしまうようなものにしてしまうなど 意識の低さが見られるところがある。 （文責:伊藤拓海）1.1
現状における問題点
非常に重要で身近に使われている暗号だが一般にはあまり関心が持たれていない。暗号と聞くと 難しく堅苦しいなどのイメージを持っている人が多いかもしれない。さらにインターネットを使う 上でもパスワードを自分で設定することがあっても暗号に直接触れる機会は少ない。 （文責:伊藤拓海）1.2
課題の概要
暗号というものは誰もが直接目に見えて使うものではない。そこで私たちは暗号の解読を目に見 える形で行いさらに楽しんでもらえるような形で行うことで暗号というもののマイナスのイメージ を消し、もっと身近に感じてもらおうとした。 （文責:伊藤拓海）第
2
章 到達目標
2.1
本プロジェクトにおける目的
今、世界中でインターネットが普及している。このように世界がつながっている中で安全にイン ターネットを利用できている理由として挙げられるのが「さまざまな暗号の利用」である。私たち のプロジェクトの目標としては、多くの人に暗号に興味を持ってもらうために、さまざまな暗号 （RSA暗号や楕円曲線暗号など）を目に見えるように可視化しようというものである。このような 可視化をしようと思った理由は、多くの人が暗号に対して「複雑なイメージがある」や「大変そう」 といった学ぶことに対してのマイナスの考えが多いだろうということで、暗号をより身近に感じて もらおうと考えたからである。これにより、現在私たちが生きている中で暗号が広く使われている ことを感じ取ることができ、暗号の大切さ・重要さを再認識できるだろう。これらのことを学びな がら暗号の基礎を知り、可視化するための方法などについて考えていく。 （文責:伊藤拓海）2.2
具体的な手順・課題設定
本プロジェクト全体の目的は、上で挙げた通り暗号の可視化である。前期には暗号を学ぶために 誕生日パラドックス班・RSA暗号班・楕円曲線暗号班の3つのグループとアプリ作成の準備のた めの実装班の計4つのグループで行い、後期にはさらに深く学習するためRSA暗号班・楕円曲線 暗号班を合わせたRSA・楕円曲線暗号班と頻度分析を学習するための頻度分析班、アプリを作成 するための実装班の計3つのグループにして行なった。 誕生日パラドックス班の前期の目標は、誕生日パラドックスの基礎を学び、スライドを使って他の 人に説明できることとした。また、換字式暗号のプログラム作成や頻度分析についても理解しよう というのを目標とした。RSA暗号班の前期の目標は、まずはRSA暗号の基本的な構造を学ぶということである。RSA
暗号の考え方や使用例などを学び、数学的な考えや誕生日パラドックスとの関連性などについても 理解することを目標とした。また、RSA暗号の複雑さを理解するためにRSA暗号の解読プログラ ムの作成も目標として掲げた。 楕円曲線暗号班の前期の目標は、まず楕円曲線暗号の基本構造を理解することとした。その後、 楕円曲線暗号の実装プログラムを組むことを目標とし、解読のプログラム作成のためのρ法を学 び、解読プログラムの作成をしようと考えた。 実装班の前期の目標は、暗号解読の可視化をするためにアプリケーション開発に関しての知識を 増やしたり、アプリケーション開発環境の整理などとした。また、中間発表の際のポスターをイラ ストレーター使い製作することを目標とした RSA・楕円曲線暗号班の後期の目標は前期で学んだことを生かし二つの暗号の共通点や相違点 などを話し合いもっと二つの暗号についての理解することを目標とした。 頻度分析班の後期の目標は、頻度分析の基本的な構造を学ぶということである。さらに頻度分析 の中では暗号の歴史について調べることも目標とした。
実装班の後期の目標は学習班の作成したプログラムをアプリとしてiPadで実行できることを目 標とした。
第
3
章 課題解決のプロセスの概要
本プロジェクトの目的は可視化ということなのでその方法について考えた。大きな考えとしては iPadを使った可視化である。本プロジェクトのプロセスとして、RSA暗号班・楕円曲線暗号班は まずはPARI/GPという高速計算機の使い方を学んだ。また、暗号というものには共通鍵暗号と 公開鍵暗号があるので、その2種類についての概要を学んだ。後期には新たに2つの班をあわせて 目標を立て行なった。ここからプロセスについて前期と後期に分けてまとめる。 （文責:伊藤拓海）3.1
前期
RSA暗号班の課題に対するプロセスは、RSA暗号の基本的な構造の理解や数学的な考えの理 解をし、素因数分解の重要性などを学んだ。他にも誕生日パラドックスとの関連性を学び、それを 実装する段階で理解した。また、PARI/GPという高速計算機を用いてRSA暗号の解読プログラ ムの作成も行った。 楕円曲線暗号班のプロセスとしては、まず数学的な楕円曲線について学び、その後楕円曲線暗号 の基本的な構造の理解を行った。解読のために必要なρ法という解読方法を学んだ。また、楕円曲 線暗号のプログラム作成や解読プログラムの作成なども行った。 （文責:伊藤拓海）3.2
後期
後期のプロセスは、まず前期に行なったことを復習し互いの活動内容やPARI/GPで行なっ た作業を確認しあった。そして二つの暗号の共通点や相違点などを話し合い暗号についての理解を 深めあった。さらに暗号に欠かせないρ法を中心に学び、プログラムを作成した。 （文責:伊藤拓海）第
4
章 暗号とは
暗号とは当事者以外には意味がわからないように、当事者間でのみ理解できるように取り決め た、特殊な記号や文字、またはその手順の方式のことである。 （文責:亀井謙斗）4.1
平文
暗号化するときに送信者が送りたい元の文章のことである。 （文責:亀井謙斗）4.2
暗号化
平文を暗号文に変換する作業のことである。暗号化が複雑になればなるほど復号に時間がかかっ たり、暗号化プログラムも大きなものになる。 （文責:亀井謙斗）4.3
復号
受信者が暗号文を元の文章(平文)に戻すことである。 （文責:亀井謙斗）4.4
アルゴリズム
暗号化や復号を行うための手順である。 （文責:亀井謙斗）4.5
鍵
暗号化に用いるパラメーターのことである。 （文責:亀井謙斗）4.6
公開鍵
公開鍵暗号でデータの暗号化に用いる鍵で、あらかじめ他の人に公開している鍵である。（文責:亀井謙斗）
4.7
秘密鍵
公開鍵暗号で使用される一対の鍵の組のうち、一般的に誰にも公開されない鍵である。 （文責:亀井謙斗）4.8
公開鍵暗号
公開鍵暗号とは、公開鍵と秘密鍵の対になる2つの鍵を使ってデータの暗号化と復号を行う暗号 方式である。公開鍵暗号では、暗号文を作り出す鍵と暗号文を元に戻す鍵が異なる。暗号通信をし たい人は、まず独自に対になる2つの鍵を作成する。1つは平文を暗号化して暗号文を作り出す鍵 で公開鍵と呼ばれ、通信相手に知らせる鍵としてインターネット上でもやりとりできる。だれでも この公開鍵で暗号文を作成でき、鍵を公開している人に送ることができる。暗号文の受け手は、公 開鍵と対になっている、本人だけが分かるように厳重に管理された秘密鍵で復号する。そのため、 暗号化されたメッセージが途中で第三者に見られることになっても中身を解読されることはない。 公開鍵暗号は公開鍵の共有が容易なことや、相手の数に関係なく公開鍵は１つのみでいい等、鍵の 管理が容易で安全性が高い。 公開鍵暗号は共通鍵暗号よりも処理が複雑であり、より多くの計算資源や時間を必要とする。この ため、暗号通信に利用する場合は、実際の通信内容の暗号化には即興で鍵を生成した共通鍵暗号を 使い、その鍵を送信者と受信者の間で安全に交換するために公開鍵暗号を使うといった使い方をす ることが多い。また、公開鍵暗号は非対称な鍵を用いる特徴から、デジタル文書の正当性を保証す るデジタル署名にも応用されている 。 公開鍵暗号方式を用いれば、送信者が通信の事実を後で否認したり、他人が偽造することを不可能 にするデータ転送が可能になる。公開鍵暗号の欠点としては、暗号化通信中の計算負荷と通信負荷 がともに大きいことである。計算負荷を比較すると、公開鍵暗号は通常、共通鍵暗号よりも2桁か ら3桁以上、速度で劣る。公開鍵暗号の速度を制限する要因は、べき剰余演算である。RSA暗号 では送信者側で1回＋受信者側で1回＝合計2回、ElGamal暗号では送信者側で2回＋受信者側 で1回＝合計3回行わなければならない。通信負荷を比較すると、DESでは64bitの平文が同じ く64bitの暗号文に変換されて送られるので、通信オーバヘッドは発生しない。初期ベクトルが必 要なモードで利用したとしても、通信オーバヘッドでは64bitである。それに対して、1024bitの 素数を用いたElGamal暗号では1024bitの平文が倍の2024bitの暗号文に変換されて送られる。 すなわち、1024bitもの通信オーバヘッドが加わることになる。RSA暗号ではオーバヘッドは発生 しないが、平文も暗号文もRSA合成数サイズ単位で処理されるので、サイズの小さなデータのや り取りに用いればパッティングのオーバヘッドは大きいことになる。また、任意長の平分を扱う場 合は大きな通信オーバヘッドが必要となる。鍵のビット長や平文（元のデータ）長を長くとる必要 があるため、暗号化と復号が複雑化し、処理時間を要することなどがある。 公開鍵暗号を使用するための具体的な暗号方式がいくつか存在している。最も有名なのは、巨大な 整数の素因数分解の困難さを利用したRSA暗号で、現在最もよく使われている暗号方式で様々な 分野で利用されている。他には、離散対数問題の解の困難さを利用したElGamal,暗号楕円曲線上 の離散対数問題を利用した楕円曲線暗号などがある。（文責:亀井謙斗）
4.9
共通鍵暗号
共通鍵暗号とは、暗号化するときと復号するときに同じ鍵を利用する暗号方式である。また，そ れぞれの鍵を秘密に管理する必要があるため，秘密鍵暗号方式と呼ばれる場合もある。共通鍵暗号 の代表的な例としてはDESがある。 共通鍵暗号の長所は，処理が比較的高速であるという点である。共通鍵暗号のアルゴリズムは色々 あるので，共通鍵暗号のアルゴリズム間で比較すると差はある。しかし、公開鍵暗号と比べれば総 じて高速であるといえる。このため，大量デー タの暗号化に向いている。短所となるのは，鍵の配 送・管理に気を使わなければならないという点です。共通鍵暗号の仕組みを利用するには，受信者 があらかじめ鍵を入手しておく必要がある。したがって、大勢で相互に共通鍵暗号を利用してデー タをやり取りするときは鍵の数が増えてしまうので管理が大変になる。 また、安全性のために、鍵は暗号額的にランダムに生成されるべきである。要するに、統計学的に ランダムではなく、予測不可能性も満たさなければならない。しかし、本質的に一意決定的な動作 指向で設計されているデジタル計算機は、そのような乱数生成は苦手である。 さらに、鍵に関してはいくつかの留意する必要がある。それは、鍵の長さが長いほど処理速度が遅 くなる、鍵の長さが不十分であれば、所望の安全性は得られない、同じ鍵を使えば使うほど、攻撃 が容易になる、使用する共通鍵暗号方式に独特のある既存の攻撃に弱く、破られやすいことがわ かっている鍵がある場合には、それを秘密鍵として採用しないなどといったことである。 （文責:亀井謙斗）4.10
DES
暗号
DESは、データを64ビット長のブロックに分割し、各ブロックを56ビット長の鍵で暗号化す る共通暗号鍵アルゴリズム。トリプルDESは、DESを3重に繰り返すことで、暗号強度を高めて いる。DESは仕様が公開されている。 UNIXシステムにおけるログイン時のパスワードによるユーザー認証でDESが使われているのは 有名である。UNIXのパスワードはDESの鍵として機能しており、ある固定したデータを、ユー ザーが打ち込んだパスワードを鍵として暗号化する。その出力された暗号文を、/etc/passwdに記 録されたユーザーの暗号文データと一致するかどうかをチェックすることによって、ユーザー認証 を行っている。UNIXのパスワードが8文字までしか有効ではないのは、DESの鍵が 56ビット であることと関連している。トリプルDESが採用されていれば、16文字あるいは24文字まで有 効である。 （文責:亀井謙斗）4.11
デジタル署名
デジタル署名はインターネットを通じてやり取りされるデータの正当性を保証するために用いら れる電子書名を公開鍵暗号の技術を用いて、暗号化された署名情報のことである。また、デジタル署名を行うための技術および一連の手順のことである。公開鍵暗号を応用したもので、文書の送信 者を証明し、かつその文書が改竄されていないことを保証する。送信者は、メッセージの原文から 一定の計算手順で割り出した短いデータを文書に添付して送信する。受信者は受け取った署名デー タを一定の手順でこれを検証することにより、文書に署名を行ったのが送信者本人であることや、 文書が通信途上で改ざんされていないことなどを確認することができる。 デジタル署名は電子署名を実現するための方式の一つであり、電子署名とは紙に署名する行為を電 子的に代替する技術の一般的な総称のことを指す。 デジタル署名の安全性を保つためには、偽造できない、偽造されないといった、次の３つの偽造不 可能性が必要である。１つ目は、一般的偽造不可能性である。これは、署名を偽造できないメッ セージが存在することである。２つ目は、選択的偽造不可能性である。これは、ある特定のメッ セージには署名を偽造できるが、それ以外のメッセージには書名を偽造できないことである。３つ 目は、存在的偽造不可能性である。これは、いかなるメッセージに対しても署名を偽造できないこ とである。 ここでは、デジタル署名に対する３つの攻撃の種類を説明する。１つ目は、受動攻撃である。これ は、公開鍵だけを使って署名の偽造を試みる攻撃である。２つ目は、一般選択的文書攻撃である。 これは、攻撃者があらかじめ選択しておいたメッセージに対して正規ユーザに署名をさせ、その結 果を参考にして別のメッセージに対する署名の偽造を試みる攻撃である。３つ目は、適応的選択文 書攻撃である。これは、攻撃者が選択したメッセージに対して正規ユーザに署名をさせ、その結果 を見て攻撃者が次のメッセージを選択し、それに対して正規ユーザに署名の偽造を試みる攻撃であ る。一般選択文書攻撃と適当的選択文書攻撃は、いくつかの選択メッセージ、署名対を入手できる かという個数でさらにランク付けすることもできる。但し、実際のネットワークアプリケーション で具体的に何個の選択メッセージ、署名対を入手できるかは推測困難なことである。 （文責:亀井謙斗）
4.12
ユーザ認証
ユーザ認証とは情報にアクセスしようとするユーザが何らかの形で身元保証されているユーザで あることを確認することをいう。相手が人である場合はこれを個人認証と呼び、パスワードのよう な記憶による方法、ICカードなどの持ち物による方法、指紋、虹彩パターンなどバイオメトリッ クスによる方法がある。 記憶、持ち物、バイオメトリックスのいずれもユーザの持つ固有情報または固有の能力に基づいて ユーザを確認していることになる。持ち物の場合も、持ち物の持つ情報または能力により確認して いるわけである。持ち物の場合、それがコピーされて悪用されることを防ぐためには、その持ち物 に耐タンパー性を持たせるか、あるいはその持ち物に対し固有で改竄の難しい情報を利用しなけれ ばならない。このような情報としての例としては、磁気記録において記憶されたパルスの感覚の微 妙な揺らぎ、磁気繊維を漉き込んでできる磁気のランダムなパターンがある。 最もよく用いられる個人認証はパスワードによるものであるが、簡単なだけに、管理が杜撰である と攻撃を受けやすく、盗まれてしまうことが多い。自分の名前やタレントの名前などをパスワード として用いるのは論外であるが、辞書に載っているような言葉であれば、パスワード攻撃用のプロ グラムで推定されてしまう恐れがある。 最近では推定しやすいパスワードは管理者が警告を発するなどして改善が図られているが、弱いパスワードが不正侵入を誘う最大の入り口であることは変わりないのである。そのために、パスワー ドの作り方、管理のしかたに対する啓蒙が必要である。しかし、誰でも使うインターネットなどの システムにおいては、パスワードの管理を徹底するのは難しいと考えれれている。 また、インターネットでパスワードをそのまま相手に渡したり、流すのは非常に危険なことであ る。それはネットワークを流れるパスワードを採集するようなプログラムも存在するからである。 もしパスワードの交換を行う際にはパスワードを暗号化して行うか、または毎回パスワードが変わ る、ワンタイムパスワード方式を用いるのが好ましい。 人以外の認証も、その対象が持つ固有情報または固有能力を利用することは変わりのないことであ る。このような場合は、不正アクセスがありえる環境では、暗号的な認証が基本となる。これは、 その対象がある秘密の暗号鍵を用い得る事を確かめることにより行われる認証である。例として は、与えられた乱数をこの秘密の鍵で暗号化できるかどうかを確認するのである。正しく暗号化さ れていることが確かめられれば、この対象は秘密の暗号鍵を使える立場にあることが確認できて、 それによってある資格を持つことが認証できるのである。 このようにして認証される側がある固有情報を持つことを確認したとしても、認証する側が認証 される側をよく知らなければ、認証される側を信用することができないのである。そのため、この ような場合は、認証する側の信頼する人は機関が認証される側が必要な資格をもつことを証明す る必要がある。これは、認証される側の固有情報と資格との結びつきを、機関の署名などにより保 障した証明書を提示することにより行われる。言い換えれば、認証する側が信頼している人または 機関に認証される側を紹介してもらうようなものである。それにより、信頼の移管が行われるので ある。 （文責:亀井謙斗）
4.13
情報の保護
情報の保護とは、対象となる情報への定められた形のアクセスを、定められた情報を持つものに だけ許して、それ以外のアクセスを排除することをいう。本来許されないアクセスを不正アクセス と呼ばれている。この不正悪性の代表的な例として、盗聴、改竄、偽造などがある。情報保護には 2通りの方法が存在する。1つは防止であり、もう1つは検知による抑止である。 防止は、施設、設備などの物理的安全性に基づく方法、ソフトウェアによる方法があり、それぞれ 重要であるが、特に重要となるのは暗号的な手法である。これは暗号化することにより仮に情報を 見られたとしても、情報は漏洩しないようにする方法である。 検知による抑止は、不正アクセスが生じたときに、それを検知し警告を発したり、その情報を無効 にして被害を防いだり、不正アクセスの証跡に基づいて何らかの制裁を加えるなどの手段により不 正アクセスの意欲を削ぎ、抑止することをいうのである。このためには不正アクセスを検知するこ とが必須であり、さらには不正アクセス者の検知、不正アクセスの証跡の保持も重要である。 （文責:亀井謙斗）4.14
暗号の安全性
暗号を守秘に用いる場合、解読ができるだけ難しくなるように暗号を設計しなければならない。 このとき、解読者の入手可能な情報が何であるかによって、暗号に対する攻撃を暗号文攻撃、既知 平文攻撃、選択平文攻撃の3つに分けることができるのである。 暗号文攻撃は、解読者が暗号文のみを入手可能と想定したときの攻撃である。但し、暗号文は大量 に入手できると考える。既知平文攻撃は、平文と暗号文の対が入手可能な場合の攻撃である。これ は暗号文のみによる攻撃より厳しい攻撃であるが、このような状況は実際にしばしば生じることが るので、暗号を設計する場合は、少なくとも既知平文攻撃を想定すべきことである。さらに、通常 は選択平文攻撃に耐えるように設計するとより強力な暗号になる。選択平文攻撃は、解読者が任意 に選んだ平分に対する暗号文が得られるという状況であり、最も厳しい攻撃である。 暗号の安全性には、情報理論的安全性と計算量的安全性がある。しかし、情報論理的に安全な暗号 は、膨大な秘密鍵を要するため、実用的ではない。商用や世間一般的に使われている暗号は、ほと んどが計算量的に安全な暗号である。 計算量的に安全であるとは、原理的には解読でても、膨大な計算量を要し、実際には解読不可能で ある場合をいう。商用暗号のほとんどは計算量的な安全性を目指して設計されている。たとえば、 DESは、既知平文攻撃の場合、入手した平文と暗号文の対に対して、すべての鍵を確かめるとい う総当り攻撃を行えば原理的には鍵が求まり、解読可能となる。しかし、鍵の総数は２の５６乗で あり、１０００万分の１秒で１つの鍵を調べたとしても、すべての鍵を調べるには２００年以上か かる計算となり安全であると考える。 （文責:亀井謙斗）第
5
章
RSA
暗号とは
Ronald Rivest氏、Adi Shamir氏、Leonard Adleman氏の3人が1978年に開発した公開鍵暗 号の一つで、現在インターネットなどで最も使用されている暗号方式である。RSA暗号を解読す るには、巨大な整数を素因数分解する必要があり、効率の良い鍵の発見方法はまだ見つかってい ない。 （文責:亀井謙斗）
5.1
特徴
RSA暗号は暗号化も復号化も行える公開鍵暗号の一つであり，鍵の長さは可変長である。RSA 暗号の作成し使用する際には，安全性の強化のためには鍵の長さを非常に長くする必要があり，効 率を良くするのためには鍵の長さが短い鍵を作成する必要がある。RSA暗号の平文の長さ（暗号 化されるデータのサイズ）もまた可変長である。平文の長さは，鍵の長さよりも小さい必要があ る。暗号文の長さは鍵の長さと同じにする必要がある。 （文責:亀井謙斗）5.2
秘密鍵と公開鍵
RSA暗号では平文を暗号化する前に公開鍵と秘密鍵を作成する必要がある。それを以下で説明 する。 1．２つの大きな異なる素数p，qを選択する。 2．n = p＊qとφ(n)＝(p−1)(q−1)を計算する。このnを係数と呼ばれている。 3.gcd（ｅ,φ(ｎ)）＝1の関係をもつ乱数e(公開指数)を選択する。gcdとは２つの引数の最大公 約数を意味している。この公開指数eと係数nが公開鍵（e,n）となる。 4．１＝de mod φ(n)となるd（秘密指数）を計算する。この秘密指数dと係数nが秘密鍵（d,n） となる。 5．公開鍵（e,n）を公開する。p,q,dは誰にも知られないようにしておく。 （文責:亀井謙斗）5.3
暗号化と復号
送信者が送りたいメッセージを元の意味の通る文章のことを平文という。また。平文を鍵を使用 して一見しただけでは意味の通らない文章に変換したものの事を暗号文という。そして暗号化と は、鍵を使用して暗号のアルゴリズムに従い、平文を暗号文に変換することをである。これに対し て復号とは、暗号化の反対の操作を行って、元の文章を(平文)に戻す操作のことである。以下で は暗号化と復号のときに実際に行われる操作についてを説明する。平文をＭ，暗号文をＣとすると，Ｍ＜ｎであれば，次の関係式が必ず成り立つ。 (1. C = Memod n (2. M = Cdmod n RSA暗号の原理は，これらの関係式が必ず成り立つという数学的特性を利用している。 1は暗号 化の操作を示していて、２は復号の操作を示している。 （文責:亀井謙斗）
5.4
安全性
RSA暗号の安全性は，大きな数を素因数分解するのが難しいというプロセスであり，それはい くら暗号文Ｃ，係数ｎおよび公開指数ｅの値を知っていたとしても， 秘密指数ｄの値を知らなけ れば暗号文Ｃから平文Ｍを得ることは計算量的に殆ど不可能であることを示している。つまり、攻 撃者が暗号文を復号することが計算量的に困難であるという期待に基づいている。 また，RSA暗号はこれまで多くの人々の間で使われてきたが， 誰もその素早い解読方法を見つけ られていないということによって信頼性を得ているわけである。もし素因数分解を簡単に行うこと ができれば，RSA暗号を解読することは可能である。 公開鍵（ｅ,ｎ）を知っていて，さらにもし ｎを因数分解してｐとｑを知ることができるのであれば， 秘密指数ｄはそれらから簡単に求めら れる。 しかし，ｎを素因数分解することだけがRSA暗号を解読する唯一の方法かどうかは分かっ ていないというのが現状である。 （文責:亀井謙斗）5.5
ρ法
ρ法とはポラードにより1975年にいくつかの合成数の素因数を速く見つける方法として考えら れたものである。Ρ法はnを合成数、dをnの未知の真約数、f(X)を既約(因数分解できない)多 項式を使用する。実用上、X2+ 1のようなものを使う。整数X0から始めて、次の漸化式により 数列を生成する。 Xi = f (Xi− 1) mod n 例としてX0 = 2, f (X) = X2+ 1,およびn=1133とすると、数列は次のようになる。 X0 = 2, X1 = 5, X2 = 26, X3 = 677...また、Y i = Xi mod dとおく。d=11とするとYiの 列は次のようになる。 Y 0 = 2, Y 1 = 5, Y 2 = 4, Y 3 = 6...となる。Xi = f (Xi− 1) mod nであるからYiはdを法 としてf (Y i− 1)に合同である。dを法とする同値数は有限個しかない(すなわち、d個)から、い ずれ、あるiとjについて、Y i = Y j が成り立つ。しかし、ひとたびこれが成り立つと以後循環 し、任意の正のtについて、Y i + t = Y j + tが成り立つ。 YiがYjに等しければ、Xi = Xj( mod d)であり、dはXi− Xjを割り切る。XiとXjが同じで ない場合がほとんどであり、そうであればgcd(n, Xi− Xj)はnの真の約数となる。循環の長さ をcとすると、いったん尻尾を離れたら、cがj-iを割り切るような任意のiとjが使える。 （文責:亀井謙斗）図5.1 ρ法
5.6
RSA
暗号の例
RSA暗号の例を実際に使われているものよりも小さい数で以下では表す。 pとqの素数を、 p = 7, q = 13 として， n = p∗ q = 72 とする。また， e = 5 とします。ここで，φ(n) = (p− 1) ∗ (q − 1) = 220と eとの最大公約数は 1となる。そこで， ed≡1(modφ(ｎ)) となるn未満の正整数dを計算する。実際に求めてみると， d = 29 となる。 そこで，eと n の組(e, n) = (5, 72)を公開し，n 未満の非負整数xに対して， ｘe(mod n) によって暗号化する。例えば，x = 33を暗号化する。 ｘe(mod n) = 335(mod 72) = 6 6が暗号文である。これを受け取った側は，これを d 乗してもとの文を求める。実際，これを計 算すると， 6d(mod n) = 33 が得られ，復号されたことが分かる。 d の計算には，φ(n) = 72が必要であった。しかし，φ(n)の計算にはnの素因数分解が必要で す。以上のことから個々では小さな数値で計算を行っているが実際には非常に大きな数で計算を行うことになるのでnの素因数分解には非常に時間がかかり、pとqを知らない場合，φ(n)の計算 は難しくなる。
第
6
章 暗号に必要な
4
つの条件
6.1
機密性
機密性とは、アクセスを認可された者だけが情報にアクセスできることを確実にすることであ る。その様にする事で、第三者が見ることができなくなるので情報を漏えいや不正アクセスから保 護することができる。 （文責:亀井謙斗）6.2
完全性
完全性とは、情報及び処理方法が、正確であること及び完全であることを保護することである。 その様にする事で、情報の改ざんや間違いから保護するできる。 （文責:亀井謙斗）6.3
認証
認証とは、正当性を検証する作業である。ユーザ名とパスワードの組み合わせを使って、コン ピュータを利用しようとしている人にその権利があるかどうかや、その人が名乗っている本人かど うかなどを確認することである。利用者を識別してユーザごとに異なるサービスを提供するために 利用したりもする。認証の際に用いられる情報(ユーザ名やパスワードなど)が他人に発覚すると 不正利用が行われてしまう恐れがある。そのため、金銭移動を伴うサービスなど、特に認証データ の機密性が要求される場合には、認証データを暗号化するなど、漏洩防止に細心の注意が払われて いる。成りすまし防止のための本人確認を行う認証については、認証サービスを行う企業から入手 したデジタル署名が用いられている。 （文責:亀井謙斗）6.4
否認防止
否認防止とは、インターネットなどで利用者が事後になってその利用事実を否定することができ ないように証拠を残すことである。デジタル証明を利用した商取引などが挙げられる。デジタル署 名は、本人確認を行うための技術であり、これを利用することで、防止することが可能である。普 段から利用する顧客にデジタル証明を発行し、顧客はそのデジタル証明を利用して、商取引を行え ば、事後にその取引を否認できなくなる。 （文責:亀井謙斗）第
7
章 暗号化と復号
7.1
RSA
暗号の実装例
RSA暗号の実装例として、RSA暗号を使った文章を変換させるプログラムをC言語を用い て作成した。今回はASCII文字コード表を用いてアルファベット、数字及び記号を数値化して扱 うプログラムを作成した。RSA暗号を実装するにあたって、２つの異なる素数p,q、その２つを掛 け合わせたN、暗号化するための整数e、復号するための整数dを用意する。eの条件としては、 (p−1)∗ (q−1)未満であり、さらに互いに素である必要がある。dは(p−1)∗ (q−1)を法とし たeの逆数とする。このdは拡張されたユークリッドの互除法を使って求めることが可能である。 またRSA暗号はNを法として暗号化が行われる。 （文責:永井 善孝）7.2
ユークリッドの互除法
暗号化されたものを復号するために必要な方法であるユークリッドの互除法について記す。 ユークリッドの互除法は、２つの自然数または整式の最大公約数を求める手法の一つである。２ つの自然数（または整式）a, b (a≧ b)について、aの bによる剰余をr とすると、a とbとの 最大公約数は bと r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数がa とb との最大公約数となる。 例 1071と 1029の最大公約数を求める。 1071を 1029で割った余りは 42 1029を 42 で割った余りは21 42 を 21で割った余りは よって、最大公約数は21である。 アルゴリズム 1. 入力を m, n (m ≧n) とする。 2. n = 0なら、 mを出力してアルゴリズムを終了する。 3. mを nで割った余りを新たに n とし、更に 元のnを新たにmとし 2. に戻る。 （文責:永井 善孝）7.3
拡張されたユークリッド互除法
整数 m, n の最大公約数をgcd(m,n)と表すときに、拡張されたユークリッドの互除法を用い て am + bn = gcd(m, n) の解となる整数a, b の組を見つけることができる。上の1071と1029の場合の例を以下に記す。 1071 = 1∗ 1029 + 42 1029 = 24∗ 42 + 21 42 = 2∗ 21 であるから、 21 = 1029− 24 ∗ 42 = 1029− 24 ∗ (1071 − 1 ∗ 1029) =−24∗ 1071 + 25 ∗ 1029 となる。 特に、m, nが互いに素（最大公約数が1）である場合、am + bn = cは任意の整数 cに対して整 数解 (a, b)をもつことが分かる。これを利用してeの逆元であるdの値を導いていく。 （文責:永井 善孝）7.4
暗号化
暗号化の流れをp=7、q=13、e=5、変換したい文章（平文）をAprilとして以下に示す。 まず平文を数値化する P r e s s 80 114 101 115 115 ASCIIコード表の文字と対応させるために値から33を引き、e乗（mod N)する 47 81 68 82 82 73 9 87 10 10 この値に33を加えて文字として表示すると暗号化できるj * x + + このような流れで暗号化が行われる。 （文責:永井 善孝）
7.5
復号
(p−1)*(q−1)、eの値から復号するためのdの値を拡張されたユークリッド互除法によっ て求める。 (p−1)∗ (q−1) = 6∗ 12 = 72、e = 5より 72 = 5∗ 14 + 2 5 = 2∗ 2 + 1 1 = 5− 2 ∗ 2 = 5− (72 − 5 ∗ 14) ∗ 2 = 5∗ 29 − 72 ∗ 2 よって、d = 29となる 暗号化された文章を数値化し、33を引く j * x + + 73 9 87 10 10 この値をd乗する 47 81 68 82 82 この値に33を加えて文字として表示すると復号できる 80 114 101 115 115 P r e s s このような流れで復号が行われる。 （文責:永井 善孝）7.6
ρ法による解読
前節とは違って２つの異なる素数p、qがわからない場合の解読のためのプログラムも作成し た。暗号化された文章を解読するためには公開鍵であるN、eからp、qを求め、そこから更にd の値を求める必要がある。つまり公開鍵であるNを素因数分解しなければいけない。ここではρ 法による素因数分解、暗号化された文章の解読の流れを具体例を通して記す。 公開鍵N=91、e=7、暗号化された文章がMe[6vCとする 素因数分解すべき整数をN、擬似乱数発生関数をf (x) = x2 + 1 mod N とする 初期値x = 2、y = 2、d = 1とする x = f (x) = 5 y = f (f (y)) = f (5) = 26 d = gcd(|x − y|, N) = gcd(21, 91) = 7 素因数p = 7を求めることができた。次に擬似乱数発生関数の定数部分を変えてもうひとつの 素因数qを求める。 f (x) = x2 + 10 mod N とする x = f (x) = 14 y = f (f (y)) = f (14) = 24 d = gcd(|x − y|, N) = gcd(10, 91) = 1 dの値が1なので繰り返す x = f (x) = 24y = f (f (y)) = f (40) = 63 d = gcd(|x − y|, N) = gcd(39, 91) = 13 素因数q = 13を求めることができた。 次に求めたp、qと公開鍵であるeの値を使って復号するための秘密鍵であるdを拡張された ユークリッド互除法によって求める。 (p−1)∗ (q−1) = 6∗ 12 = 72、e = 7より 72 = 7∗ 10 + 2 7 = 2∗ 3 + 1 1 = 7− 2 ∗ 3 = 7− (72 − 7 ∗ 10) ∗ 3 = 7∗ 31 − 72 ∗ 3 よって秘密鍵d = 31が求められた。 暗号化された文章を数値化し、33を引く M e [ 6 v C 44 68 58 21 85 34 この値をd乗して、33を加えて文字として表示する 119 101 105 103 104 116 w e i g h t このように暗号化された文章をρ法を使って解読することができる。 （文責:永井 善孝）
第
8
章 楕円曲線暗号
この章では、楕円曲線、楕円曲線暗号について記す。 （文責:永井 善孝）8.1
楕円曲線とは
楕円曲線とは、以下の式で定まる３次曲線である。 y2= x3+ ax + b ここで、4a3+ 27b2≠0である必要がある。 楕円曲線は上記の式を満たす有限個の点の集合であり、無限遠点も楕円曲線上の点として考え る。また、楕円曲線上には整数点は有限個しか存在しない。 （文責:永井 善孝）8.2
楕円曲線上での演算
楕円曲線上での演算は、一般的な方法と異なるので、その方法について以下に記す。 （文責:永井 善孝）8.3
加算
楕円曲線の有理点の集合は加法群となる、つまり有理点同士の加算、減算を計算することが可 能である。このときの加算の計算ルールはとても特徴的になっている。単純に点同士のx座標、y 座標を足しあわすわけではない。計算方法を以下に記す。 楕円曲線E : y2= x3+ ax + b 上の２点P、Qの和R = P + Qを以下のように定める。 1.２点P、Qを通る直線Lを引く 2.楕円曲線Eと直線Lの３つ目の交点をR’とする 3.R’のx軸に関する対称点をRとする 途中で得られたR’をRの逆元と呼び、R’ = −Rとかくことが多い。このようにして得られた 点Rが P + Qとなる。 次に楕円曲線上での加算を数式で以下に表す。楕円曲線E : y2= x3+ ax + b上の２点P(x1,y1)、Q(x2,y2)の和R(x3,y3)を以下のように定 める。
P ≠Qの場合 x3 =λ2− x1 − x2 y3 =λ(x1− x3) − y1 λ= (y2− y1)/(x2 − x1) P ＝Qの場合 x3 =λ2− 2x1 y3 =λ(x1− x3) − y1 λ= (3x12+ a)/2y1 このように数式で表される。 （文責:永井 善孝）
8.4
２倍算
加算のように２倍算の場合でも単純に点のx座標、y座標を２倍にするのではない。 楕円曲線E : y2= x3+ ax + b 上の点Pの２倍算S = 2Pを以下のように定める。 1.点Pにおける接線を引く 2.楕円曲線Eと接線との交点をS’とする 3.S’のx軸に関する対称点をSとする このようにして得られた点Sが点Pの２倍算である2Pとなる。 （文責:永井 善孝）8.5
スカラー倍算
楕円曲線上の点Pを選び（この点をベースポイントと呼ぶ）、適当な整数dに対し、ベースポ イントPをd倍した点 d * P = P + ・・・+ P を求める計算をスカラー倍算と呼ばれる。 実際にスカラー倍算を計算するには、加算を繰り返して適用していく。 スカラー倍算d * Pを計算する場合、加算をd ? 1回適用すれば計算することができる。例とし て、 8 * P = P + P + P + P + P + P + P + Pは加算を７回適用することによって計算可能である。しかし、 8 * P = 2 * (2 * (2 * P)) と表せることを利用すれば３回の加算で計算可能である。このように加算と２倍算を組み合わせる ことによって効率的にスカラー倍算を計算することができる。 （文責:永井 善孝）
8.6
楕円曲線上の離散対数問題
普段我々が用いている整数の集合 Z の要素を p で割った余りの集合Z mod pについて考え る。この場合の有理点の数mは必ず以下のような範囲 (√p - 1)2 ≦ m≦(√p + 1)2 に収まるため、有限個の点から成り立つ群であることがわかる。これにより有限体と同様に離散対 数問題を定義することができる。 楕円曲線上の有理点P、Qに対して iP = Q を満たすような整数解iを求める問題を楕円曲線上の離散対数問題という。 （文責:永井 善孝）8.7
楕円曲線暗号とは
楕円曲線暗号とは、楕円曲線上の離散対数問題を安全性の根拠とする暗号である。楕円曲線暗 号では、上で説明した楕円曲線の式y2 = x3+ ax + b を使用する。四則演算の考え方も楕円曲線 での方法を適用する必要がある。 楕円曲線上の点Pとそれをs倍（s回繰り返し加算を行う）した点Q、Q = sPのQとPを公 開鍵とし、sを秘密鍵とされる。楕円曲線上の点における計算は複雑であるという楕円曲線上の離 散対数問題によって、P、Qからsを求めることは困難なため、このsを秘密鍵として利用できる。 つまり暗号化は公開鍵P、Qを使用して行い、復号は秘密鍵sを使用する。 （文責:永井 善孝）8.8
特徴
楕円曲線暗号の特徴やメリットを、公開鍵暗号のデファクトスタンダードであるRSA暗号と 比較しつつ以下に記す。RSA暗号に比べ短い鍵長で同等の安全性が確保できる。（RSA暗号で１０２４ビット長の暗号 化鍵を使用した場合と、楕円曲線暗号で１６０ビット長の暗号化鍵を使用した場合、同程度の安全 性を保つ） 高速処理が可能であり、ハードウェアを実装した場合も、より小規模で実現可能である。 楕円曲線暗号においての安全性は鍵の長さだけではなく、曲線パラメタの選択に大きく左右され る。 このようにRSA暗号と比べて、同レベルの安全性をより短い鍵で実現でき、処理速度も速いこ とをメリットとして、ポストRSA暗号として注目されている。 図8.1 楕円曲線暗号 （文責:永井 善孝）
8.9
楕円エルガマル暗号
楕円曲線暗号には様々なアルゴリスムがある。ここではそのひとつである楕円エルガマル暗号 の構成、数値を使った例を紹介する。 楕円エルガマル暗号の構成方法は以下のとおりである。 秘密鍵k 公開鍵P, Q = kP , 楕円曲線y2= x3+ ax + b平文(楕円曲線上の点) X 適当な乱数rを選び、A = rP とB = X + rQを計算する。このAとBのペア(A,B)が暗号文 となる 平文(楕円曲線上の点) 秘密鍵kを用いて B− kA を計算する。この式は B− kA = (X + rQ) − k(rP ) = X + rkP − krP = X であるので復号される。 数値例 公開鍵 P, Q = kP , 楕円曲線y2= x3+ x + b 秘密鍵をk = 13とする 公開鍵をP = (1, 1)とすると曲線上の点は P = (1, 1), 2P = (2, 16), 3P = (13, 9), 4P = (16, 8), 5P = (11, 7) 6P = (18, 4), 7P = (7, 8), 8P = (15, 8), 9P = (8, 5), 10P = (8, 14) 11P = (15, 11), 12P = (7, 11), 13P = (18, 15), 14P = (11, 12), 15P = (16, 11) 16P = (13, 10), 17P = (2, 3), 18P = (1, 18), 19P = (0, 0)←無限遠点 この曲線の法は19である Q = kP = 13P = 13(1, 1) = (18, 15)となる 暗号化 平文をX = (15, 11)とする 乱数r = 3として暗号文を作成する A = rP = 3(1, 1) = (13, 9) B = X + 3∗ Q = (15, 11) + 3(18, 15) = (15, 11) + 3∗ 13P = (15, 11) + (13, 10) = (9, 2) 暗号文= ((13, 9), (9, 2)) 復号 秘密鍵k = 13を用いて (9, 2)− 13(13, 9) = (9, 2)− (13, 10) = (−4,−8) = (19− 4, 19 − 8) = (15, 11)
= X となるため復号できた。 （文責:永井 善孝）
8.10
成果
楕円曲線暗号の解読プログラムを作成した。 今回のプログラムの言語はPARI/GPを用い た。この言語を使うことで、解読の際、重要である素因数分解の計算を効率よく行なうことが可能 になった。 今回の楕円曲線暗号の解読プログラムは、暗号文を作成し、その暗号文を解読するようなプログ ラムを作成した。解読のプログラムでは 「s」 が秘密鍵、「p」、「q」 を公開鍵としている。このと き、「q = sp」 という関係があり、この「p」、「q」 から秘密鍵を 「s」 を求める。 楕円曲線暗号の解読の流れを以下のプログラムの一部とともに説明する。 ・暗号化する 公開鍵となる 「p」、「q」を決定する。このとき 「p」 は 100億の次の素数を用いている。 p = 1000000000; p = nextprime(p); q = p + 1− ellap(e, p); このとき、楕円曲線上の点Pの座標 (x, y)は 以下の式で求められる。 x = M od(1, p); y = M od(2, p); 秘密鍵 「s」 は以下の式で求める。 s = 1 + random(q− 1); 「m」 を暗号化する。このとき、「p」から数字をランダムに選びその数字を 「m」とする。 m = random(p); ある数「m」 を暗号化するため１以下の乱数を使い、ランダムに選び、「m」 を暗号化した 暗号 文「C1」を作る。 r = 1 + random(q− 1); C1 = ellpow(e, P, r);・復号する 楕円曲線の式より、係数「a」、「b」、「a1」、「b1」 の値を、楕円曲線上の座標の点「A1」と公 開鍵 「q」 用いることで値を決定する。 A1 = f (a1, b1, R1); a = A[1]b=A[2]a1 = A1[1]b1=A1[2] さらにこの 「a」、「b」、「a1」、「b1」 を用いて、秘密鍵 「s」 と思われる 「s1」 を求める。 if (gcd(b− b1, l) == 1, s1 = M od((a1− a)/(b − b1), l); s1 = lif t(s1); ここで出てきた 「s1」と 暗号化の際に決めた秘密鍵 「s」 と同じ数値であればこの「s1」は秘 密鍵 「s」 であるといえる。この秘密鍵 「s」 を使い 暗号文を復号することで、暗号化した「m」 を求めることができる。 以上より、楕円曲線暗号の暗号化、復号のプログラムを数値の段階という限定されたものであ るが作成することができた。 （文責:及川真那実）
第
9
章 課題解決のプロセスの詳細
9.1
全体のプロセス
4月 暗号についての基礎知識をつける学習を行なった。 どのようにプロジェクト学習を行なっていくか話し合った。 5月 暗号解読のプログラムを作成するためPARI/GPの学習を行なった。 グループ分けを話し合い、今後の進め方について話し合った。 6月 グループに別れRSA暗号、楕円曲線暗号の暗号解読のプログラムを作成した。 7月 引き続きRSA暗号、楕円曲線暗号の暗号解読のプログラムを作成した。 中間発表に向け、スライド作成、ポスター作成、発表練習を行なった。 8月 中間発表の反省から、今度について話し合いを行なった。 9月 今度の進め方を話し合った。 新しいエディタのインストールを行なった。 10月 成果物についてどうしていくのか話し合いを行なった。 RSA暗号、楕円曲線暗号において重要となるρ法を学習した。 RSA暗号をアプリケーションにするためのプログラムを作成した。 11月 最終発表の担当分けを行なった。 最終発表に向けてスライド、ポスター作成に取り組んだ。 最終発表に向けて発表練習を行なった。 12月 最終発表に向けてスライド、ポスター作成に取り組んだ。 最終発表に向けて発表練習を行なった。 最終発表の反省を行なった。 1月 個人報告書、最終報告書の作成を行なった。 （文責:伊藤拓海）9.2
各人の課題の概要とプロジェクト内における位置づけ
伊藤拓海の担当課題は以下の通りである。4月 どのようにプロジェクト学習を行なっていくか話し合った。 暗号についての基礎知識をつける学習を行なった。 PARI/GPという言語の高速計算機を学んだ。 PARI/GPの背景を学習した。。 PARI/GPの基礎を学び、簡単な四則演算のプログラムを作成した。 5月 誕生日パラドックス班、RSA暗号班、楕円曲線暗号班、実装班にわかれた。 誕生日パラドックス、RSA暗号、楕円曲線暗号について学習した。 素因数分解、素数について学習した。 割った数の余りを表す Modについて学習した。 PARI/GPの基礎を学び、簡単な四則演算のプログラムを作成した。 PARI/GPで関数のプログラムを作成した。 6月 RSA暗号についての学習、関連プログラム作成した。 PARI/GPでRSAに関する簡単なプログラムを作成した。 中でもModを使用したものを中心に作成した。 素因数分解についての学習もした。 7月 中間発表に向けての準備。 スライド・ポスターの作成。 発表者を担当した。 8月 中間発表の反省から、今度について話し合いを行なった。 わかりにくいという意見が多かったのでさらに深い学習が必要だと考えた。 9月 前期までの復習。 新しいエディタのインストール。 グループを新しくしてRSA・楕円曲線暗号グループに所属した。 解読法を中心に学習していくことにした。 10月 成果物について考えた。 ρ法について学習。 ρ法に関する学習では解読に欠かせないものなんでしっかりと理解を深めるようにした。解 読のプログラムの作成。 11月 ポスター作成。 最終発表に向けた、発表練習。 ポスター作成ではメンバーの作成したものをまとめた。 発表者を担当した。 12月 最終発表に向けた、発表練習。 発表においては中間発表で出ていた反省点をしっかりと確認して行なった。 前期より多くの練習時間をとった。
個人報告書、グループ報告書作成。 1月 個人報告書、グループ報告書作成。 （文責:伊藤拓海） 亀井謙斗の担当課題は以下の通りである。 4月 どのようにプロジェクト学習を行なっていくか話し合った。 暗号についての基礎知識をつける学習を行なった。 PARI/GPという言語の高速計算機を学んだ。 PARI/GPの背景を学習した。。 PARI/GPの基礎を学び、簡単な四則演算のプログラムを作成した。 5月 誕生日パラドックス班、RSA暗号班、楕円曲線暗号班、実装班にわかれた。 誕生日パラドックス、RSA暗号、楕円曲線暗号について学習した。 素因数分解、素数について学習した。 割った数の余りを表す Modについて学習した。 PARI/GPの基礎を学び、簡単な四則演算のプログラムを作成した。 PARI/GPで関数のプログラムを作成した。 6月 実際にRSA暗号のプログラムの作成をした。 プログラムを作成するにあたり、公開鍵、秘密鍵の生成方法や擬似乱数発生関数の作り方を 学んだ。 PARI/GPで最初は簡単なModの計算から行い、徐々に複雑な計算を行った。 7月 中間発表の準備。 中間発表では、主に発表で使うスライド、ポスター作りに携わった。 プレゼンテーションの流れや内容を理解しつつ発表の練習や準備をおこなった。 発表練習から聞いている人に発表内容を理解してもらえるように大きな声ではきはきと話す ことを心がけた。 実際の発表ではスムーズに行うことができた。 発表のときに質問に対してはあらかじめ予想を立てたりしていたので、あたふたせずに答え ることができた。 予想外の質問に対してはうまく答えることができない場面もあった。 スライドとポスターはできる限り文字を少なくして図や表を加えることで、見栄えのよいも のを作成した。 8月 今後の話し合いを行った。 中間発表で失敗した事を最終発表でもしないように対策を練った。 9月 新しいエディタのインストール。 後期の活動内容を把握し、スケジュール管理を行った。 RSA暗号の復号するときの過程で、素因数分解を素早く行うために、非常に重要なρ法の
ことを知った。 ρ法のことが書かれている本を読み、ρ法について学習した。 10月 ρ法について学習。 ρ法を説明するための方法を考えた。 ρ法を発表のときに理解してもらうための方法として、図やグラフで表すとわかりやすいと いうことが話し合われた。 11月 最終発表の担当分け。 最終発表の担当は、ポスター作成とスライド作りであった。 ポスター作りでは、ρ法に関する事をまとめて、ポスターを見ただけで、ρ法がどのような ものかわかるようなものを作成した。 スライドではρ法に関する事と、RSA暗号に関することを説明する文章を考えた。 ポスターとスライド作りは、中間発表と同様に文字をできる限り少なくして、図やグラフを 加えることで見栄えのよいものを作成した。 12月 最終発表に、向けた練習。 最終発表会では発表を担当した。 発表の時には他のプロジェクトの声で発表の声が聞こえないということがないように、大き な声で発表をすることを心がけた。 発表を聞く人の中には高校生もいたので、できるだけ専門用語を使わないようにして、簡単 な言葉で発表するように心がけ、発表を理解してもらえるように努力した。質問に対して も、中間発表のときと同様にあらかじめ予想を立てていたので、スムーズに答えることがで きた。 個人報告書の作成。 グループ報告書の作成。 1月 個人報告書の作成。 グループ報告書の作成。 （文責:亀井謙斗） 永井善孝の担当課題は以下の通りである。 4月 どのようにプロジェクト学習を行なっていくか話し合った。 暗号についての基礎知識をつける学習を行なった。 PARI/GPという言語の高速計算機を学んだ。 PARI/GPの背景を学習した。。 PARI/GPの基礎を学び、簡単な四則演算のプログラムを作成した。 5月 誕生日パラドックス班、RSA暗号班、楕円曲線暗号班、実装班にわかれた。 誕生日パラドックス、RSA暗号、楕円曲線暗号について学習した。 素因数分解、素数について学習した。 割った数の余りを表す Modについて学習した。
PARI/GPの基礎を学び、簡単な四則演算のプログラムを作成した。 PARI/GPで関数のプログラムを作成した。 6月 楕円曲線の性質を理解した上で、楕円曲線上での点の計算法や簡単な楕円曲線のプログラム 作成を行った。 プログラムを自分たちのパソコン上で動作させることで楕円曲線ではどういった計算が行わ れているのかといったことをより実感することができた。 これらの楕円曲線についてのプログラムや学んできた知識を基に楕円曲線暗号についての勉 強を始めた。 暗号化や復号についてを先生から学び、数値を使った楕円曲線暗号の簡単なプログラム作成 を行った。 暗号化されたものをρ法という素因数分解法を用いて解読していくということを学んだ。 このρ法を使った楕円曲線暗号の暗号化から解読までのプログラム作成を行った。 7月 前期にやってきたことをグループ内でまとめ、中間発表で話す内容について話し合った。 発表者として楕円曲線及び楕円曲線暗号についての発表、質疑応答を担当した。 個人報告書、及びグループ報告書の作成を行った。 8月 夏季休業という長い時間を使ってプログラム作成に使用しているC言語などの復習を行っ た。 後期へ向けて今まで学んできた暗号についての情報をまとめ、今後どのようなことをしてい けばよいかを考えた。 9月 後期のプロジェクト学習が始まり、また新たにグループ分けを行った。 後期では、RSA暗号、楕円曲線暗号グループ、頻度分析グループ、実装グループの３つに 分け、RSA暗号、楕円曲線暗号グループに所属した。 RSA暗号と楕円曲線暗号の解読において重要となるρ法の更なる理解を目指して活動を始 めた。 10月 自分のパソコン上で動く簡単なRSA暗号を使用したプログラムを作成した。 暗号化や復号、解読の流れがよくわかるようなプログラムにするために最初はJavaを使用 したが、なかなかうまく動作させることが出来ないという結果になったしまった。 この結果を得てJavaではなくC言語を用いて作成し始めた。アルファベット、記号及び数 字のみだが、これらを何か別な文字に変換させるRSA暗号を使ったプログラムを作成する ことが出来た。 暗号化から復号までの過程を文字を数値に置き換えて変換させていくというプログラムを作 成した。 11月 暗号化と復号ができるプログラムは作成できたので、これらを使って今度は解読ができる プログラム作成を始めた。 解読にはρ法という素因数分解法を利用して行っていく。
