暗号化アルゴリズムRSA (Rivest-Shamir-Adleman)の基本

RSAは、データの暗号化と復号化によく使用される、安全性の高い暗号化アルゴリズムです。このアルゴリズムは、機密データをインターネット経由で送信するための安全な手段を提供します。RSAにはいくつかの脆弱性がありますが、それでもメッセージの送信元を認証するためのデジタル署名など、さまざまな用途で利用されています。

この記事では、RSAとその仕組み、そして主な用途をご紹介します。また、RSAのセキュリティ上の脆弱性と、その脆弱性を緩和する方法についてもご説明します。

RSAとは？

RSA (Rivest-Shamir-Adleman)は、一般によく知られている公開鍵暗号方式(非対称暗号化)アルゴリズムです。秘密鍵と公開鍵のペアを使用した暗号化と復号化によって機密データを保護します。

1977年にマサチューセッツ工科大学のRon Rivest氏、Adi Shamir氏、Leonard Adleman氏によって初めて発表されたこのアルゴリズムは、彼らの苗字の頭文字を取ってRSAと名付けられました。

RSAは秘密鍵と公開鍵のペアを使用します。秘密鍵は鍵ペアの作成者以外に知られないように秘密にされますが、公開鍵は誰でも使用できます。この公開鍵と秘密鍵のいずれか一方を暗号化に、もう一方を復号化に使用できます。

この方式が受け入れられ、RSAは世界で最も広く使われている暗号化メカニズムの1つとなっています。ただし、RSAの計算は複雑であることから、アルゴリズムとしては比較的効率が悪く、大量のリソースを消費します。そのため、大容量のメッセージやファイルの暗号化には適していません。

RSAの仕組み

RSAは、大きな整数の素因数分解を利用したアルゴリズムです。まず、因数分解が困難になるように、2つの大きな素数を鍵ペアとして選択する必要があります。この2つの素数はランダムに選択され、かつ互いの差が大きい数でなければなりません。ここでは、選択された2つの素数をpおよびqとしましょう。

次に、このアルゴリズムは2つの素数の積を計算します(n = p * q)。pとqの値は秘密にしておく必要がありますが、公開鍵と秘密鍵のモジュラス値として使用されるnは公開する必要があります。

さらに、pとqを使用してカーマイケルのトーティエント関数を計算し、公開指数として使用される整数eを選択します。その後、秘密指数として使用されるdの値を計算します。

RSAでの暗号化と復号化の方法

公開鍵をペア(n, e)、秘密鍵をペア(n, d)とします。

• 暗号化：メッセージを暗号化する場合、送信者は受信者の公開鍵(n, e)を使用して、暗号文を計算します(暗号文 = m^e mod n)。mは平文のメッセージを示します。
• 復号化：RSAで暗号化されたメッセージを復号化する場合、受信者は秘密鍵(n, d)を使用して、平文メッセージを計算します(平文メッセージ = c^d mod n)。

RSAの用途とユースケース

RSAは、情報セキュリティや暗号化に関連する複数の用途で使用されています。以下に、最も一般的な用途をいくつかご紹介します。

デジタル署名

デジタル署名は、メッセージの受信者がその真正性や完全性を検証したり、否認防止を確保したりするために使われる手法です。この手法により、メッセージが送信中に改ざんされていないことが証明されます。

デジタル署名を作成する場合、送信者はまず、暗号化ハッシュ関数を使ってメッセージのハッシュ値を生成します。次に、秘密鍵を使いRSAアルゴリズムを適用して署名することで、デジタル署名を生成します。その結果、受信者が送信者の公開鍵を使って、RSAアルゴリズムをデジタル署名に適用できるようになります。

さらに、メッセージに対して生成されたハッシュ値と照合することで、その署名を検証できます。

デジタル証明書

RSAは、SSL証明書などのデジタル証明書で広く使用されています。この証明書を使用することで、Webサイトを運営している個人または組織の身元を証明できます。

デジタル証明書は、RSAを利用して証明書の発行者のデジタル署名を暗号化し、公開鍵を使って検証できるようにしたものです。デジタル証明書はドメイン名やWebサイト運営組織などの情報で構成されており、クライアントに対してWebサイトの身元を証明します。

安全な通信プロトコル

RSAは、インターネットのような安全でないネットワーク上で、二者間の通信を暗号化します。たとえば、RSAをTLS (Transport Layer Security)とともに使用することで、WebサーバーとWebブラウザ間の安全な接続を確立します。さらにRSAは、メッセージを暗号化および復号化する手段を提供してメール通信の安全性を確保します。

また、仮想プライベートネットワーク(VPN)でもRSAが使用されます。VPNではTLSを利用し、情報をやり取りする二者間のハンドシェイクがスムーズに行われるようにします。TLSハンドシェイクではRSAアルゴリズムを利用し、情報をやり取りする二者の身元を認証します。

安全な鍵交換

RSAのもう1つのユースケースとして、過去に秘密鍵を共有したことがない二者間で行う安全な鍵交換があります。この二者は、RSAアルゴリズムを使って公開鍵と秘密鍵のペアを生成します。

• 送信者は対称鍵を生成し、それを受信者の公開鍵を使って暗号化して、暗号化された鍵を受信者に送信します。
• その後、受信者は秘密鍵を使ってそれを復号化します。

これで、送信側と受信側の両方が同じ対称鍵を所有し、それを使用することで安全な通信を確立できます。

RSAアルゴリズムのセキュリティ上の脆弱性

RSAアルゴリズムは、推奨事項に準拠している限り、解読するのが困難です。それでもこの数年間で複数の脆弱性が見つかっています。具体的には、以下のような脆弱性です。

サイドチャネル攻撃

サイドチャネル攻撃は、ソフトウェアやそのコードを直接標的にするのではなく、コンピューターシステムがデータを処理する際に生じる情報(プログラムの実行時間、消費電力、電磁放射線など)を脆弱性として狙います。

たとえば攻撃者は、暗号化操作の実行中にコンピューターによって放出される電磁放射線から情報を取り出すことができます。

RSAの暗号化に対して最もよく使用されるサイドチャネル攻撃は、電力解析攻撃とタイミング攻撃の2つです。

• 電力解析攻撃では、RSAでの計算負荷の高い処理によって生じる電力消費の変動を解析します。
• タイミング攻撃では、デバイスがRSA暗号化を実行するのにかかる時間を測定します。

攻撃者は、この解析データや測定データからRSA暗号化で使用される秘密鍵を抽出します。そのため、サイドチャネル攻撃を防止するための適切な対策を講じておく必要があります。

短すぎる鍵長

RSAアルゴリズムの安全性は、鍵生成プロセスで、素因数分解が困難である大きな素数を使用しているかどうかに大きく依存します。2つの大きな素数の積の素因数分解は、鍵長が長いほど困難になります。

コンピューターの処理能力を高められる場合は、それに合わせて鍵長も長くするべきです。コンピューターの能力が高ければ、大きな数を比較的簡単かつ短時間で因数分解できます。言い換えると、鍵長が短ければ鍵を簡単に解読できる可能性が高まります。

かつて推奨されていた1024ビットのRSA鍵は解読される可能性が高いため、もはや有効ではありません。そのため、RSAを使用する場合は最低でも2048ビットの鍵長を使用することをお勧めします。

素数の弱点

素数の弱点は、ランダム性と近似性に分類できます。

素数のランダム性：RSAアルゴリズムでは、鍵生成プロセスでランダムな素数を生成する必要があり、生成された素数を乗算することで公開鍵と秘密鍵を生成します。

たとえば、組織が使用している乱数ジェネレーターやアルゴリズムの性能が低く、簡単に予測したり因数分解したりできる乱数が生成されているとします。その場合、攻撃者は素数の生成に使用されたパターンを推測し、鍵を簡単に因数分解することができます。

素数の近似性：RSAで使用される2つの素数の値が互いに近すぎたり、どちらかの値が小さすぎたりする場合も、RSA鍵の安全性が損なわれる可能性があります。このような状況では、攻撃者がRSAモジュラスの因数を簡単に特定し、暗号を解読して秘密鍵にアクセスできるようになります。

鍵の紛失または盗難

鍵の紛失、盗難、または漏えいが発生すると、攻撃者がその鍵に直接アクセスし、暗号化されたメッセージを対応する公開鍵で復号化できるようになります。このような脆弱性を回避するには、鍵を適切に管理することが必要です。

フォールト攻撃

フォールト攻撃とは、暗号化アプリケーションの実装に使用されるハードウェアまたはソフトウェアに対して、意図的にフォールト(障害)を組み込む攻撃です。たとえば、攻撃者がレーザーやビット反転を使用して暗号化機能に障害を発生させると、値を予測できる弱い鍵が生成されます。

適切な対策を講じなければ、RSAの実装がフォールト攻撃に対して脆弱になる可能性があります。

RSAの脆弱性の回避

RSAの脆弱性を緩和するために実施できる対策がいくつかあります。

• 強力な素数ジェネレーターを使用して、素数を予測不可能で攻撃者に簡単に推測されない値にします。
• 小さな素数や互いに近すぎる素数など、弱い素数を使用しないようにします。
• RSA鍵の長さを、2048ビット以上にします。
• 改ざん防止ハードウェアを使用するなど、フォールト攻撃を防ぐために必要な対策を講じます。
• 鍵のローテーションを定期的に実施したり、用途ごとに異なる鍵を使用したりするといった方法を取り入れて、RSA鍵を適切に管理および保護します。
• 脆弱性やアップデートの情報を定期的に確認し、RSAアルゴリズムを最新の状態に保ちます。

RSAのまとめ

1977年に初めて発表されたRSAは、今では広く使用されている暗号化アルゴリズムです。公開鍵と秘密鍵のペアを使用して、データを暗号化および復号化します。RSAは複数の用途に使用できますが、計算が複雑であるため、大容量のメッセージやファイルの暗号化には不向きです。現在は、安全な認証、通信、Webアクセス、およびメールメッセージや鍵の交換に必要なデジタル署名と証明書の作成に使用されています。

RSAには、サイドチャネル攻撃、短すぎる鍵長、素数の弱点、フォールト攻撃、鍵の盗難や紛失によるリスクなど、いくつかの脆弱性があります。そのため、暗号化アプリケーションにRSAを使用する際は、この記事で説明した推奨事項を考慮することが重要です。

このブログはこちらの英語ブログの翻訳です。