基礎から学ぶ整数論 - RSA暗号入門 -

基礎から学ぶ整数論 - RSA暗号入門 -

中学レベルの知識をもとに整数論の基礎を理解しながら,RSA暗号の考え方を学ぼう!

ジャンル
発行年月日
2020/10/08
判型
A5
ページ数
192ページ
ISBN
978-4-339-06120-8
基礎から学ぶ整数論 - RSA暗号入門 -
在庫あり

定価

2,750(本体2,500円+税)

カートに入れる

購入案内

  • 内容紹介
  • まえがき
  • 目次
  • 著者紹介

【書籍の紹介】
本書では,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),十(10),百(10^2),千(10^3),万(10^4),億(10^8),兆(10^12),···の漢数字が用いられています。知られている最大数は,恒河沙(10^52),阿僧祇(10^56),那由他(10^60),不可思議(10^64),無量大数(10^68)のほか諸説ありますが,無量大数です。この数(かず)という概念形成の過程で,数(すう)という抽象概念へと発展していたと考えられます。では,位取りには欠かせない0は,いつから使われるようになったのでしょうか。ゼロ「0」はインドで使われだしたというのが有力な説です。この0の発見により数学が爆発的に進歩したともいわれています。そして,0が,整数論の体系化に大きく寄与した記号と考えられます。

整数論の中で,その不思議さ・難しさ・神秘さがゆえに私たちを魅了し続けている数(かず)に6章で学ぶ素数があります。素数は,すでに古代ギリシャの数学者ユークリッドにより,無限個の存在が証明されています。さらに,素数を効率的に見つける方法は,古代ギリシャの数学者エラトステネスが考案したとされる「エラトステネスの篩」です。そして,素数の出現には規則性がないとされているため,いまだにエラトステネスの篩を上回る素数を見つける方法はないとされています。この素数が,現代の高度情報化社会の情報通信の安全性を根底から支える暗号に用いられています。インターネット上の情報は,暗号化することで安全に通信相手に送ることができるようになります。さまざまな暗号技術が考案されていますが,実用化されている暗号技術の中に,大きな二つの異なる素数を用いるRSA暗号があります。残念ながら,RSA暗号は未来永劫に安全な暗号技術とはいえません。いままさに新しい暗号技術の研究が進んでいます。しかし,安心してください,まだRSA暗号は安全とされています。

本書は,中学生レベルの整数の知識を基に整数論の基礎を理解しながら,RSA暗号の基礎となる考え方を学ぼうとする読者を想定してまとめてあります。数学科ではない学生は,整数の話題に興味はあるが難しいと感じている人も多いと思います。そのような人は,暗号に興味があるけれど,なにから始めてどのように学んだらよいかわからないと思います。学生ではなくても,RSA暗号を学びたいのになにから始めたらよいかわからない人も多くいると思います。RSA暗号を学ぶのにいきなり,合同式や素数に関する難しい定理な素数に関する難解な演算からスタートするのは避けたいものです。

本書でRSA暗号を学び始めるために最低限必要な数学の知識は,中学生までに学んだ整数の四則演算だけです。はじめに,1章においてRSA暗号の概要を学び,目的を明確にします。ここでは,RSA暗号の仕組みや特徴を学び,「なぜそのようなことが可能なのか」という疑問をもつことが大切です。読者の皆さんは,1章を終えた時点で,RSA暗号について理解できない部分があっても,まったく問題ありません。つぎに,2章から6章では,RSA暗号の理解に必要な整数論の各項目を学びます。ここでは,中学高校レベルの知識から始まり,徐々に新しい定理や知識を身に付けていきます。各項目とRSA暗号との関係は,目次の⋆の数で表してありますので,参考にしてください。RSA暗号の計算をできるようになるためには⋆⋆まで,RSA暗号の原理を理解したい場合は⋆⋆⋆までの知識が必要となります。最後の7章では,再びRSA暗号に戻り原理の理解と実践を目指します。6章までを修得していれば,1章では疑問だらけだったRSA暗号が,7章ではスラスラと計算でき原理も理解できるようになるはずです。

整数論とRSA暗号を学ぶためには,さまざまな定理を理解しなければなりません。重要あるいは必要な定理には,詳細な証明を載せるように心がけました。そして,それらの定理の使い方を学ぶために例題を用意してあります。例題には,わかりやすい解答過程を載せるようにしました。また,各章の章末には章全体の理解確認の問題を用意してあります。各章末問題の解答は,なるべく詳細に計算過程を載せるように心がけました。さらに,基本的な計算過程のほかに理解を補う別解法がある場合には,その過程も載せるようにしています。

本書の例題や章末問題などは,数式処理言語であるMathematicaを用いて計算することができます。興味のある人は,Mathematicaにも挑戦してみてください。

なお,本書は工学院大学情報学部の1年生共通科目として設置している情報数学および演習3の教科書としてまとめたものです。「情報数学および演習3」は講義と演習の2限連続×全7週のクォーター科目であり,本書は全14コマで扱う内容となっています。情報学部情報デザイン学科の設立のとき,基礎科目に整数論や暗号に関する授業がありませんでした。そこで,2009年に整数論の講義を開始し,2013年にはRSA暗号を追加しました。そして,2016年から情報学部全体の1年生基礎科目として,整数論の基礎とRSA暗号を学ぶ情報数学3が開始されました。これに伴い,TeXのjarticle形式からjbook形式に授業資料の充実を目指して再構築を開始しました。2019年には,充実化が終了したので出版準備に取り掛かりました。本書の校正にご協力をいただいた本学の非常勤講師の渡辺桂子先生には,わかりにくいところなどいろいろご意見をいただいたことに感謝いたします。

最後に,出版を快諾していただくとともにさまざまなコメントをいただいたコロナ社の皆さまに感謝いたします。

追記:2019年末ごろより,人知れず人への感染力を獲得してしまった「新型コロナウイルス(SARS coronavirus 2(SARS-CoV-2))」が中国の武漢市を中心に出現しました。この新型コロナウイルス感染症(coronavirus disease(COVID-19))の患者数が,世界中で爆発的に増加しつつあります。日本でもその増加の脅威が迫りつつあります。1日も早いこの感染症の終息を願い執筆を終了しました。そして,出版時には終息していることを願うばかりです。

2020年4月13日     長嶋祐二 福田一帆

★発行前情報のため若干変更されることがございます。ご了承下さい。★

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暗号を根底から支える数―
6.1 素数とは
 6.1.1 素数の定義
 6.1.2 素因数分解の難しさ
 6.1.3 素数の分布
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での効率的な計算方法
章末問題

章末問題解答
引用・参考文献

長嶋 祐二

長嶋 祐二(ナガシマ ユウジ)


「会議・プレゼンテーションのバリアフリー―“だれでも参加”を目指す実践マニュアル ―」(電子情報通信学会 編・発行,情報保障ワーキンググループ 編)の編著者。

※illustration by Takayuki

福田 一帆(フクダ カズホ)

【営業担当者より】

中学,高校,大学で数学を学んでいる時に,「何の意味があるの?」と思った方々はたくさんいらっしゃると思います。しかし,情報系や工学系における数学は何かの技術を支える大きな役割を果たしています。本書は,暗号技術を学ぶ前に読んでおきたい整数論の教科書であり,さらにはもっと高度な技術,新しい技術を学んでみたいという思いが強くなる暗号技術の導入書です。現在,情報を暗号化してネット上で安全に通信を行うことができる実用的な技術としてRSA暗号があります。本書はこのRSA暗号を題材とし,「中学で勉強した素数って,実は役に立つんだ」という新たな発見など,興味が途絶えることなく学習できる1冊です。


【章末問題の詳細な解答・解説が自習にも最適】

テスト前に単位が取れるか心配になることありますよね?本書は章末問題の解答に約40頁を費やし,丁寧な解説が掲載されていますので,なぜ間違ったのか,どこで間違ったのかがよくわかり,習熟度を高めるための自習にも最適です。