RSA暗号とは？仕組みや応用事例を初心者にもわかりやすく解説！

RSA暗号とは

RSA暗号の概要を見ていきましょう。

素因数分解が困難であることを利用したアルゴリズム

大きな数字を素因数分解するのは困難です。総当たりする以外に素因数を見つけ出す方法がないためです。したがって、コンピュータで素因数分解しようとしても、大きな数であれば膨大な時間がかかります。

この仕組みを利用した暗号がRSA暗号です。RSAは発明した３人の名前「R. L. Rivest、A. Shamir、L. Adleman」に由来します。

素因数分解の難しさを安全性の根拠にするということは、逆に言えば素因数分解されてしまうと解読されるということです。膨大な時間を掛けてコンピュータで計算すれば素因数分解されてしまいます。

しかし、それまでには情報の価値が失われているため、暗号として機能するのです。

公開鍵暗号方式の一種

公開鍵暗号方式とは、暗号鍵と復号鍵が別々の暗号方式です。データを解読するために使うのは復号鍵であって、暗号鍵ではありません。

つまり、暗号鍵は第三者に見られても問題ないということです。暗号鍵は第三者を含め誰にでも公開されて使われることから、公開鍵暗号方式と呼ばれます。

一口に公開鍵暗号方式といっても、その種類はさまざまです。たとえば、DH法は鍵を交換するためのアルゴリズムです。暗号化自体のアルゴリズムではないため、暗号化にはほかのアルゴリズムを使う必要があります。

それに対して、RSA暗号は鍵の交換だけでなく、暗号化とデジタル署名を実現するアルゴリズムです。暗号とデジタル署名を両方とも達成できるアルゴリズムとして、世界で初めて登場しました。

RSA暗号を使ったやり取りの仕組み

RSA暗号における、鍵を交換する仕組みを見ていきましょう。

１．受信者が公開鍵と秘密鍵を生成する

始めに、データを受信する側が公開鍵と秘密鍵を準備しなければなりません。以下の手順で鍵を生成します。

1. １．異なる２つの大きな素数「p」「q」を任意にとる
2. ２．n＝pqとする
3. ３．（p?１）（q?１）と互いに素な自然数eを任意にとる
4. ４．edを（p?１）（q?１）で割った余りが１となる自然数dを任意にとる

「互いに素」とは、最大公約数が１という意味です。こうして用意したnとeを公開鍵としてメッセージ送信側に渡します。p・q・dは秘密鍵であるため公開しません。では、上記の手順の具体例を見ていきましょう。

1. １．p＝７、q＝５とする
2. ２．n＝７×５＝35
3. ３．（p?１）（q?１）＝６×４＝24なため、e＝５とする
4. ４．d＝５とする。このとき、ed÷（p?１）（q?１）＝１余り１となる

２．送信者がメッセージを暗号化する

次は、メッセージの送信側が作業します。受信側から受け取った公開鍵であるnとeを使い、以下の手順でメッセージを暗号化しましょう。

1. １．送りたいメッセージを自然数xとする。ただしx＜nとする
2. ２．xをe乗し、これをnで割った余りをyとする

こうして算出されたyが暗号文です。これを受信側に送信します。では、上記の手順の具体例を見ていきましょう。

1. １．x＝12とする。これはx＜nを満たす（n＝35）
2. ２．12を５乗し、これを35で割ると余りy＝17となる

３．受信者がメッセージを復号する

最後に、受信側は送られてきた暗号文yを復号し、平文を得ます。解き方の手順は以下のとおりです。

1. １．yをd乗する
2. ２．これをnで割った余りが平文xとなる

では、上記の手順の具体例を見ていきましょう。

1. １．17を５乗する
2. ２．これを35で割った余りが平文12となる

復号するにはdが必要ですが、これは受信者しか持たない秘密鍵であるため、第三者には復号されません。

第三者がdを得るにはpとqが必要ですが、これらも秘密鍵です。p×qで算出されるnは公開されていますが、nからpとqを逆算するには素因数分解をしなければなりません。ここで膨大な手間がかかるため、現実的な時間では第三者に解読されることがないとされています。

RSA暗号の応用事例

RSA暗号による暗号化は公開鍵暗号方式であり、公開鍵で施した暗号化を、秘密鍵を持つ者のみが復号できる方法です。この仕組みは、逆の方向に使うことでデジタル署名にも応用できます。

秘密鍵を持つ側が、秘密鍵によって自身の署名を暗号化します。この署名を受け取った側が公開鍵によって署名を復号できれば、その署名が公開鍵と対になる秘密鍵で暗号化されたものだと判明するのです。

その結果、通信相手が秘密鍵を持つ正規の相手であることが証明されます。この特徴から、RSA暗号は暗号化やデジタル署名の規格として広く使われています。

RSA暗号について理解し、セキュリティの知識を深めよう！

RSA暗号とは素因数分解に時間がかかることを利用した公開鍵暗号です。以下の流れで暗号化と復号を行います。

1. １．受信者が公開鍵と秘密鍵を生成
2. ２．送信者がメッセージを暗号化
3. ３．受信者がメッセージを復号

公開鍵から秘密鍵を得るには素因数分解を行う必要があり、これが現実的な時間では不可能なことから安全性が確認されています。暗号化技術への理解を深める参考にしてください。