累計

  • 130,028 pv

アクセスカウンター

DataEntrepreneurFellows コンピュータサイエンス 学びのアウトプット

【学びのアウトプット】コンピュータサイエンス〜RSA公開鍵暗号方式〜

2019-07-27

 

どうも、solobochiです。

 

 

今年度受講している文部科学省のデータ関連人材育成の学習プログラムでコンピュータサイエンスについて学習しましたのでまとめておきます。

 

 

 

目次

  1. コンピュータサイエンス
  2. ユークリッド互除法
  3. フェルマーの小定理
  4. 因数分解の計算量
  5. RSA公開鍵暗号
  6. 量子コンピュータ

7/27更新　Update

 



 

コンピュータサイエンス

👉コンピュータの科学、では直訳ではあるが説明としては不十分。

👉Wikiによれば、情報と計算の理論的基礎、およびそのコンピュータへの実装・応用に関する研究分野

👉正確には、情報処理・問題処理をコンピュータの計算手順に転換することにより自動化する方法を発見する研究分野
→すなわち、言い換えれば、コンピュータシステムを作るための科学

👉具体的な研究分野としては、プログラミング言語論、計算理論・計算の基礎、アルゴリズム論、人工知能、自然言語、ソフトウェア工学、etc

 

 

ユークリッドの互除法

👉２つの自然数の最大公約数を求めるアルゴリズム

└アルゴリズムとは：問題を解く手順について定式的に表現したもの。計算可能なもの(=チューリングマシンで解くことができるもの)を計算するためのもの。

👉人類最古のアルゴリズム

🔸アルゴリズムは以下の通り

ユークリッド互除法

\displaystyle  a = b \times q+ r　となるa,bについての最大公約数を求める

ⅰ)　以下の式のx , yにそれぞれa , bを代入する
\displaystyle x = y \times q + r

ⅱ)　y　≠　0まで以下1,2を繰り返す

1.  x = y \times q + r
（xをyで割った商をq、余りをrとする）◀️a = bq + r が成り立つ時、aとbの最大公約数は、bとrの最大公約数に等しいことを利用する

2. xにyを代入、yにrを代入する

ⅲ)　y　=　0となった時のｘの値が最大公約数

👉数式で簡潔に書くと、

ユークリッド互除法を数式で簡潔に表現

\displaystyle a = b \times q + rの時、

gcd (a , b)　＝　gcd (b , r)　＝　d

※gcd ：greatest common divisor（最大公約数）

 

 

 

フェルマーの小定理

👉RSA公開鍵暗号にも応用されている素数に関する定理

フェルマーの小定理

素数ｐ、ｐと互いに素である整数ａについて

\displaystyle a^{p-1} \equiv 1(\mod{p})

 

 

因数分解の計算量

👉多項式時間で解ける素因数分解アルゴリズムは見つかっていない

因数分解の計算量

・計算量とは
→計算量理論：計算の複雑さを数学的に表現する
→入力サイズの関数で表現する
└→オーダー記法：O

・オーダー記法の一覧

オーダー記法（O） 内容
O(1)　：　定数時間 データ数（N）によらず同じステップ数で実行できるアルゴリズム。
例）ハッシュ探索、ハッシュテーブルによるデータ検索、配列要素へのアクセス
O(\displaystyle \log{n})：対数時間 処理ごとに処理対象を減らすことのできるアルゴリズム。
データ数（N）が増えてもそれほど計算時間はほとんど増えない。
例）２分探索
O(n)　：　線形時間 データ数（N）の分だけ時間がかかるアルゴリズム。
例）forループ１回分、未ソート配列の探索
O(\displaystyle N \times \log{N})：準線形/線形対数時間 O（n）相当のループとO（\displaystyle \log{n}）相当のループが合わさったアルゴリズム。
例）クイックソート（基準値との比較でソート）、マージソート、ヒープソートなどの高速ソートアルゴリズム
O(\displaystyle n^2)　：　二乗時間 O（n）相当のループを二重にしたアルゴリズム。全ての組み合わせのペアを調べるようなアルゴリズム。
例）バブルソート、挿入ソートなどの単純なソートアルゴリズム、工夫しないソートアルゴリズム。
O(\displaystyle k^N)　：　指数時間 全ての組み合わせについて調べるようなアルゴリズム。パターンを列挙する必要がある問題は指数時間となる。
例）ルービックキューブの総当たりによる解法、素因数分解の試し割りによる解法
O(n!)　：　階乗時間 Nの階乗に比例する時間がかかるアルゴリズム。
例）巡回セールスマン問題

 

因数分解の計算量（続き）

・整数Nを素因数分解するもっとも素朴な方法である、試し割り
→１から順に割っていき、\displaystyle \sqrt{N}まで割る
→\displaystyle \sqrt{N}の総当たりなので、指数時間アルゴリズム

・コンピュータ内部では０、１の２進数で整数・状態を表現しているので、１ビットで１０進数の１、２を表現する。
（※余談→ノイマン型：０か１、量子：０と１の重ね合わせを表現）
同様に、２ビットで、１〜４、３ビットで１〜８、、、、ｐビットであれば、\displaystyle \Large 2^{p}まで表現できる

Nを表現するために必要なビット数計算

整数Nを表現するために必要なビット数は、\displaystyle \log_2{N}ビット（※）
※\displaystyle 2^p > N　のとき

\displaystyle \log_{10}{2^p} > \log_{10}{N}

⇒　\displaystyle p \times \log_{10}{2} > \log_{10}{N}

⇒　\displaystyle p > \frac{\log_{10}{N}}{\log_{10}{2}}

∴　\displaystyle p > \log_{2}{N}

整数Nを素因数分解するアルゴリズムの計算量

\displaystyle N = 2^{\log_{2}{N}}

⇒　\displaystyle \sqrt{N} = 2^{\log_{2}{\frac{N}{2}}}より、

整数Nを試し割りで\displaystyle \sqrt{N}まで全て試していく方法の計算量は、\log_{2}{\frac{N}{2}}の指数時間アルゴリズムとなる

 



 

RSA公開鍵暗号

👉RSA公開鍵暗号の安全性は素因数分解の難しさ、計算量の大きさに依存している

RSA公開鍵暗号方式

・RSA公開鍵暗号とは
→素数p,qの積n（\displaystyle n = p \times q）とある整数eを公開鍵として公開しておき、暗号文を公開鍵で暗号化
※平文に対して、e乗してmod nを求める
→暗号文を平文にする際には、秘密鍵dを使って、暗号文をd乗してmod nを求めて平文にする
→p、ｑがわかっていれば簡単だが、p、ｑが分からない場合は、公開されているnからp,qを探さなければならない。この時素因数分解の計算量が膨大であることがRSA公開鍵暗号方式の安全性を保っている。

 

 

dav

 

量子コンピュータ

👉RSA公開鍵暗号方式は電子署名やメール、SSLサーバ認証（https）を用いたECなど今やありとあらゆる場面で利用されているが、量子コンピュータにより素因数分解の計算量が低コスト化すればRSA公開鍵暗号をはじめとする様々なセキュリティが破られることになる

Shorのアルゴリズム

・Shorのアルゴリズム
→Shorのアルゴリズムを用いると、素因数分解を効率的に解くことができる
→2n個の量子ビットがあれば、2^nの因数分解を効率的に解くことができる

 

 

 

 

以上

 

 

 

 

 

  • この記事を書いた人
  • 最新記事
solobochi

solobochi

（名前）：solobochi

（説明）
独身アラサー男子
国内大手IT企業中堅社員。
プログラミングやセミナーのアウトプットがしたいと思いブログを開設。
プロジェクトマネジメント関連の資格やディープラーニング、機械学習系の資格取得ノウハウについても発信。


（Like）
・最適化することが好き
・PDCAを回すのが好き


（当サイト）
日々思うことを徒然と発信
└（例）
・学びのアウトプット
・投資・資産運用
・プログラミング
・資格試験の対策
・セミナーのレビュー
・書評
etc...


詳しくは自己紹介記事にて。
自己紹介①
自己紹介②
自己紹介③
自己紹介④

-DataEntrepreneurFellows, コンピュータサイエンス, 学びのアウトプット
-, , , ,

Copyright© そろボチ , 2022 All Rights Reserved Powered by AFFINGER5.