書店員向け情報 HELP
基礎から学ぶ整数論
RSA暗号入門
- 初版年月日
- 2020年10月14日
- 書店発売日
- 2020年9月25日
- 登録日
- 2020年8月12日
- 最終更新日
- 2020年10月1日
紹介
【書籍の紹介】
本書では,RSA 暗号の原理の理解を目標とし,RSA 暗号を求めるのに必要となる,さまざまな基礎的な整数論の定理,演算手法を学びます。
1 章では,暗号の基礎知識とRSA 暗号の導入,数と式について学びます。読者の皆さんは,ここではRSA暗号の仕組みや特徴を学び,「なぜそのようなことが可能なのか」という疑問をもつことが大切で,理解できない部分があっても,まったく問題ありません。
2 章では,4 章の一次不定方程式,5 章の合同式を解くのに重要なキーワードとなる最小公倍数と最大公約数について学びます。
3 章では,最大公約数を効率的に求めることのできるユークリッドの互除法について学びます。このアルゴリズムは,4 章で学ぶ一次不定方程式の解法アルゴリズム4.1(拡張ユークリッドの互除法アルゴリズム)につながります。
4 章では,7 章のRSA 暗号を理解するのに必要となる一次不定方程式の解法を学びます。この方程式は,3 章3.3 節で学んだユークリッドの互除法アルゴリズムから導出される「拡張ユークリッドの互除法アルゴリズム」で求めることができます。
5 章では,合同の基本的な演算から合同式の解法について学びます。合同の考え方は,7 章のRSA 暗号において,暗号文を生成したり解読するのに必要となります。
6 章では,RSA 暗号を理解するうえで必要となる,素数にまつわるさまざまな定理や関数について学びます。
最後の7章では,6 章までに学んだ整数論の知識を基に,公開鍵暗号の一つのRSA暗号の原理を理解します。ユーザは,秘密鍵(secret key)SK から公開鍵(public key)PK を作成し,PK を自分の鍵として公開し,SK を自分だけが知っている値として秘密にしておきます。これらの鍵を求めるのに,巨大な素数や素因数分解などに関する知識が必要となりますが,6章までを習得していれば,1章では疑問だらけだったRSA暗号が,スラスラと計算でき原理も理解できるようになるはずです。
【読者へのメッセージ】
みなさんのなかに,今までに整数論を学ぼうとして挫折した人はいませんか?あまりにも難しい定理が急に出てきて「あぁ,もうだめだ・・・」などと感じたことがありませんか?筆者たちもその一人かもしれません。そんな筆者たちの経験をもとに,この内容から書いてあれば数学を専門としない読者にもわかるかもしれないと,構想(妄想か?) を立て書いたつもりです。本書の中には難しい証明もあるかもしれません。でも,そんなものは読み飛ばしても,全体の理解には問題はありませんので安心してください。この本を小説のように(?!) 読むことにより,「整数論って何だろう,RSA暗号ってどんな方式なんだろう」を理解できることを願っています。
目次
1.整数の基礎的知識-RSA暗号の導入-
1.1 RSA暗号の導入
1.2 暗号の歴史
1.3 共通鍵暗号
1.3.1 共通鍵暗号とは
1.3.2 共通鍵暗号の弱点とその対策
1.4 公開鍵暗号
1.4.1 公開鍵暗号とは
1.4.2 原理
1.4.3 RSA暗号
1.5 数と式
1.5.1 自然数
1.5.2 整数
1.5.3 倍数と約数
章末問題
2.最小公倍数と最大公約数-整数の組に共通性を探す-
2.1 最小公倍数
2.2 最大公約数
2.3 最小公倍数,最大公約数に関するおもな定理
章末問題
3.ユークリッドの互除法-最大公約数を効率的に求める-
3.1 ユークリッドの互除法とは
3.2 ユークリッドの互除法の原理
3.3 ユークリッドの互除法アルゴリズム
3.4 三つ以上の整数a1,a2,a3,…,anの最大公約数
3.5 一次不定方程式の導入
章末問題
4.一次不定方程式-RSA暗号の理解の手助け-
4.1 一次不定方程式とは
4.2 (2元)一次不定方程式
4.2.1 一次不定方程式の解法手順
4.2.2 解の存在
4.2.3 1組の解の解法
4.2.4 すべての解に関する定理
4.3 拡張ユークリッドの互除法アルゴリズム
章末問題
5.合同式-RSA暗号の暗号鍵の計算に必要-
5.1 合同とは
5.2 剰余類と剰余系
5.3 合同式に関する基本演算
5.4 合同式の除法
5.5 一次合同式の解法
5.5.1 一次合同式
5.5.2 一次不定方程式と一次合同式の関係
5.5.3 一次合同式の解
5.5.4 一般的な解法の手順
5.5.5 (a,n)=1のときの解法(一次合同式の別解法)
章末問題
6.素数-RSA暗号を根底から支える数-
RSA暗号の手順のまとめ
6.1 素数とは
6.1.1 素数の定義
6.1.2 素因数分解の難しさ
6.1.3 素数の分布
コーヒーブレイク n次代数方程式の解と係数の関係は基本対称式によって表される
コーヒーブレイク オイラー(Euler)の積と素数の数は無限大
6.2 オイラーの関数
6.2.1 オイラーの関数とは
6.2.2 RSA暗号に必要となるオイラーの関数の諸定理
6.2.3 オイラーの定理を用いた一次合同式の解の公式
6.3 RSA暗号に必要となるフェルマーの諸定理
6.3.1 フェルマーの小定理
6.3.2 平方因子とフェルマーの定理
6.3.3 素数判定法
章末問題
7.RSA暗号-さぁRSA暗号に挑戦-
7.1 RSA暗号の基本的な処理手順
7.1.1 RSA暗号の基本的な処理手順
7.1.2 RSA暗号の実践
7.2 RSA暗号の原理
7.3 最小公倍数を用いるRSA暗号
7.4 指数が大きいときの効率的な計算方法
7.4.1 繰り返し2乗法
7.4.2 Excelでの効率的な計算方法
章末問題
引用・参考文献
章末問題解答
索引
上記内容は本書刊行時のものです。