個別教師Campブログ

こんにちは、個別教師Campライターの内海です。
いつも個別教師Campブログをお読みいただきありがとうございます。

今回は私が大学生の時に学んだ

RSA暗号についてブログを書いていこうと思います。

RSA暗号とは？

素因数分解が困難であることを利用した公開鍵暗号アルゴリズムの1つです。
1977年にロナウド・リベスト氏、アディ・シャミア氏、レオナルド・エイドルマン氏が

共同研究で開発し、3人の頭文字をとってRSA暗号と名付けられました。

公開鍵暗号とは？

公開鍵　と　秘密鍵　という、対になる2種類の鍵を用いる暗号方式・暗号技術のことを指します。
公開鍵暗号とよく比較されるのが共通鍵暗号です。
共通鍵暗号の場合は、同じ共通鍵で暗号化したり、復号化したりします。

公開鍵暗号のメリット・デメリット

データの安全性の高さが1番のメリットです。
また、管理がしやすいという点(公開鍵を1つしか公開しなくて良い)もメリットだと言えます。

一方でデメリットは暗号化や復号化の処理時間が長くなるという点です。
共通鍵暗号と比べ、鍵のデータの長さを長く確保する必要があり、その分暗号化や復号化の処理に時間を要してしまいます。

RSA暗号の仕組み

1.受信者が公開鍵と秘密鍵を作成する

初めに、受信者が公開鍵と秘密鍵の準備をする必要があります。
以下の手順で、鍵を作成します。

①異なる2つの大きな素数p,qを生成し、n=pqとする。
②(p-1)(q-1)と互いに素な自然数eを任意にとる。
③edを(p-1)(q-1)で割った余りが1となる自然数dを任意にとる。
※互いに素とは最大公約数が1という意味です。

用意したe,dを公開鍵としてメッセージ送信側に渡します。
一方でp,d,nは秘密鍵のため、公開しません。

2.送信者がメッセージを暗号化する

次に、送信側が受信側から受け取った公開鍵であるn,eを使って、以下のようにメッセージを暗号化します。
④送りたいメッセージを自然数xとします。ただし、x<n。
⑤xをe乗し、これでnで割った余りをyとします。

以上の手順で算出されたyが暗号文です。これを受信側に送信をします。

3.受信側がメッセージを復号化する
最後に、受信側が送られてきた暗号文yを復号し、以下のように平文を得ます。
⑥yをd乗する。
⑦これをnで割った余りが平文xとなる。

復号するにはdが必要ですが、これは秘密鍵であるため、公開されません。
また、dを得るためにp,qが必要ですが、これらも秘密鍵です。
nは公開されていますが、nからpqを逆算するには素因数分解をしなければならないため、

膨大な時間が掛かってしまいます。そのため、現実的に第三者が解読するのは難しいとされています。

では、実際のRSA暗号の計算例を見て、理解を深めましょう！
①p=5,q=7とします。n=35です。
②(p-1)(q-1)=4×6=24になるため、e=5とします。
③d=5としたとき、ed÷(p-1)(q-1)=25÷24=1···1
④x＝5とします。これはx<nを満たします。
⑤5を5乗し、これを35で割ると、余りは10となります。
⑥10を5乗します。
⑦これを35で割った余りが平文5となります。

RSA暗号の応用事例

・通信の暗号化

RSA暗号は通信の暗号化に活用されており、活用されている通信プロトコルはSSL(Secure Socket Layer)です。
SSLの特徴として、

①Webサーバーとブラウザ間の通信プロトコルを暗号化する、

②ファイル転送時のFTP技術にも採用されているの2つが挙げられます。

また、サーバーからの情報は秘密鍵で暗号化されていますので、ブラウザの公開鍵で復号化した後、参照が可能です。

・デジタル署名

RSA暗号はデジタル署名にも活用されています。
デジタル署名とは、電子文書ファイルを暗号化・復号化して本人性があることや改ざんされたものではないことを証明するものです。
デジタル署名の例として、電子印鑑やタブレット端末へのサインインなどが挙げられます。

【数学・情報】RSA暗号について知ろう！　◎まとめ

今回、RSA暗号についてブログを書きました。いかがだったでしょうか。
実は数学と暗号は深い関係にあったのです。
他にも暗号の種類はありますので、ぜひ調べてみてください。

初めての方へ