書記が数学やるだけ#343 オイラー関数とRSA暗号

暗号理論の初歩として，RSA暗号の仕組みについて見ていく。

問題

入試問題としては大掛かりな問題。

説明

暗号化には，主に共通鍵暗号と公開鍵暗号がある。

共通鍵暗号では，暗号化と復号で同じ鍵を使う。仕組みが単純で高速であるが，鍵の受け渡し過程で漏洩すると機密性が崩れる難点がある。

それを克服したものが公開鍵暗号である。

手順：
1.受信者は公開鍵と秘密鍵の2つを作成する。
2.公開鍵を，送信者を含める全世界に公開する
3.送信者は，公開鍵を用いて暗号化する
4.暗号文を送信する
5.受信者は，秘密鍵を用いて復号する

公開鍵暗号の代表例として，桁数が大きい合成数の素因数分解問題が困難であることを安全性の根拠としたRSA暗号がある。RSA暗号方式は、1977年に発明され、発明者であるロナルド・リベスト、アディ・シャミア、レオナルド・エーデルマンの原語表記の頭文字をつなげてこのように呼ばれる。

解答

オイラー関数について復習。

参考：

本問はRSA暗号の原理に基づいた計算問題である。このことは，もし秘密鍵であるφ(N)がわかっていれば，Nの素因数分解ができる，つまりRSA暗号が解けてしまうことを意味する。

本記事のもくじはこちら：