IoT セキュリティ: RSA 暗号化および復号化アルゴリズム

[[357279]]

WeChat パブリックアカウント: コンピューターとネットワークのセキュリティ

ID: コンピュータネットワーク

従来の暗号化方法では、暗号化と復号化に同じキーを使用し、送信者と受信者が別々に保存して、暗号化と復号化の際に使用します。このアプローチの主な問題は、キーの生成、挿入、保存、管理、配布が非常に複雑であり、特にユーザー数が増加すると、キーの需要が指数関数的に増加することです。ネットワーク通信において、大量の鍵を配布することは解決が難しい問題です。

従来の鍵暗号の鍵配布問題を解決し、デジタル署名に対するユーザーのニーズを満たすために、1976年にアメリカの学者ディフィーとヘルマンが有名な論文「暗号の新方向」を発表し、「公開鍵暗号システム」の確立を提案しました。ユーザーAが暗号化鍵ka（公開）を持ち、それが復号化鍵ka′（秘密）と異なる場合、ka′のセキュリティに影響を与えないようにkaを公開する必要があります。ユーザーBが平文mをユーザーAに秘密裏に送信したい場合、ユーザーAの公開鍵kaを確認できます。kaを使用して暗号文cを暗号化して取得する場合、ユーザーAはcを受け取った後、ユーザーAだけが知っている復号化鍵ka′を使用してcを復号化し、mを取得します。

1978 年、マサチューセッツ工科大学の研究チームのメンバーである Rivest、Shamir、Adleman (図 1 を参照) は、公開鍵暗号システムに基づく優れた暗号化アルゴリズムである RSA アルゴリズムを提案しました。 RSA アルゴリズムは、暗号化とデジタル署名の両方に使用できる、最初の比較的完全な公開鍵アルゴリズムです。 RSA アルゴリズムは、3 人の発明者 Rivest、Shamir、Adleman の頭文字にちなんで名付けられました。このアルゴリズムは、長年にわたる徹底的な暗号解読に耐えてきました。暗号解読者は RSA アルゴリズムの安全性を証明することも反証することもできませんが、これはアルゴリズムが一定の信頼性を持っていることを示しているだけです。現在、RSA アルゴリズムが最も人気のある公開鍵アルゴリズムとなっています。

[[357280]]

図1 RSA公開鍵アルゴリズムの発明者

注: 左から右へ: レヴィスター、シャミール、エデルマン、1978年に撮影された写真

1. RSAアルゴリズムの原理

RSA は最も有名で広く使用されている公開鍵アルゴリズムであり、暗号化とデジタル署名の両方に使用できます。国際標準化機構 (ISO) は、1992 年に公布された国際標準 X.509 で RSA アルゴリズムを正式に国際標準に組み込みました。 1999年、米国上院は、米国内の文書や電子メールにおけるデジタル署名は手書きの署名と同じ法的効力を持つと規定する法案を可決しました。

RSA アルゴリズムは、大きな素因数を持つ合成数に基づいて機密性の強度が高められ、因数分解が困難なブロック暗号アルゴリズムです。 RSA アルゴリズムの公開鍵と秘密鍵は、大きな素数のペア (100 ～ 200 桁以上の 10 進数) の関数です。公開鍵と暗号文から平文を復元することの難しさは、2 つの大きな素数の積を因数分解することと同等です (これは認識されている数学の問題です) が、それが NP 問題であるかどうかはまだ定かではありません。表 1 は、大きな数を因数分解することの難しさの例を示しています。

表1 大きな数を分解することが難しい例

RSA アルゴリズム システムには、公開鍵 KU={e, n} と秘密鍵 KR={d, n} が含まれます。公開鍵と秘密鍵の構成、および暗号化と復号化の式を表 2 に示します。

表2 RSAアルゴリズム

①すべてのMに対してe、d、nの値を見つけることが可能である。

②すべてのM

③ eとnが与えられた場合、dを計算することは不可能です。

（１）RSAアルゴリズムの数論的基礎

以下では、RSA アルゴリズムで使用する必要があるいくつかの用語を紹介します。

1) 素数

素数とは、1 とそれ自身以外の自然数では割り切れない、1 より大きい自然数を指します。たとえば、15=3×5 なので、15 は素数ではありません。また、別の例として、12=6×2=4×3 なので、12 も素数ではありません。 13 は 13×1 に等しいだけでなく、他の 2 つの整数の積として表すこともできないため、13 は素数です。

2) 互いに素な数

唯一の公約数が 1 である 2 つの自然数は互いに素な数と呼ばれます。 2 つの自然数が互いに素であるかどうかを判定する方法は主に 8 つあります (これらに限定されません)。

① 2つの素数は互いに素でなければなりません。たとえば、2と7、13と19などです。

② 素数が他の合成数を割り切れない場合、その2つの数は互いに素である。例えば、3と10、5と26など。

③ 1は素数でも合成数でもありません。1と9908のように、どの自然数とも互いに素です。

④ 2つの隣接する自然数は互いに素である。たとえば、15と16。

⑤ 隣接する2つの奇数は互いに素である。たとえば、49と51。

⑥ 97と88のように、2つの大きな数は互いに素である。

⑦ 小数が素数の場合、その小数の倍数でない大きな数を持つ2つの数は互いに素な数です。たとえば、7と16です。

⑧ 両方の数は合成数（2つの数の差が比較的大きい）であり、小さい数のすべての素因数は大きい数の約数ではありません。2つの数は互いに素です。たとえば、357 と 715 の場合、357=3×7×17 となり、3、7、17 は 715 の約数ではないため、これら 2 つの数は互いに素です。

3) モジュロ演算

モジュロ演算は整数演算です。整数 m があり、モジュロ演算は n を法として実行されます。つまり、mmod n です。 m を n で割り、余りのみを結果として取ることをモジュラー演算と呼びます。たとえば、10 mod 3 = 1、26 mod 6 = 2、28 mod 2 = 0 などです。

モジュロ演算には次の特性があります。

① 合同: a mod n = b mod n の場合、正の整数 a と b は合同です。

②対称性：a=b mod nならば、b=amod nとなる。

③推移性: a=b mod n、b=cmod nならば、a=cmod nとなる。

4) オイラー関数

任意の正の整数 n に対して、n 以下の正の整数のうち n と互いに素であるものがいくつあるかを計算する方法はオイラー関数と呼ばれ、φ(n) と表記されます。例えば、φ(8)=4 です。1～8 の中で 8 と互いに素な数は 1、3、5、7 の 4 つだからです。

φ(n)の計算方法は複雑ではないので、以下でさまざまなケースで説明します。

最初のケース: n=1 の場合、 φ(1)=1 です。これは、1 と任意の数 (それ自体を含む) が互いに素な関係を形成できるためです。

2 番目のケース: n が素数の場合、素数とそれより小さいすべての数は互いに素な関係を形成できるため、φ(n)=n-1 となります。

3番目のケース: nが素数の累乗、例えばn=pk、pが素数、k≥1の場合、

φ(pk)=pk-pk-1

例えば、φ(8)=φ(23)=23-22=4です。これは、数が n と互いに素となるのは、その数が素数 p を含まない場合のみであるためです。素数 p を含む数は合計 pk-1 個あり、1×p、2×p、…、pk-1×p です。

4 番目のケース: n を 2 つの互いに素な整数の積に分解できる場合 (たとえば、n=p1×p2)、φ(n)=φ(p1p2)=φ(p1)φ(p2) となり、つまり、積のオイラー関数は各因数のオイラー関数の積に等しくなります。例えば、φ(56)=φ(7×8)=φ(7)×φ(8)=6×4=24です。

5番目のケース: 1より大きい任意の整数が、次のような一連の素数の積として表せる場合、

、 それから

。

5) オイラーの定理

2つの正の整数aとnが互いに素である場合、nのオイラー関数φ(n)は次を満たします。

aφ(n)≡1(nを法として)

つまり、a を φ(n) から 1 を引いた乗数は n で割り切れます。例えば、3と7は互いに素なので、φ(7)=6、(36-1)/7=104となります。

正の整数 a と素数 p が互いに素である場合、φ(p)=p-1 なので、オイラー関数は次のように表すことができます。

ap−1≡1(pを法として)

これは有名なフェルマーの定理です。

6) フェルマーの小定理

m が素数で、a が m の倍数でない場合は、am-1 mod m=1 となります。あるいは、m が素数の場合、ammod m=a となります。たとえば、46 mod 7 = 4096 mod 7 = 1、47 mod 7 = 16384 mod 7 = 4 です。

系: a と n が互いに素である場合、aφ(n)mod n=1 です。

（２）素数の生成と検証

まず、素数を決定するための簡単なアルゴリズムを紹介しましょう。 C プログラミングでは、素数を決定するアルゴリズムは次のようになります。正の整数 n が与えられた場合、n を 2 から sqrt(n) までのすべての整数で割ります。n が割り切れる場合、n は素数ではありません。割り切れない場合は、n は素数です。このアルゴリズムの時間計算量は O(sqrt(n)) であり、アルゴリズムの記述は単純で、実装も難しくありません。ただし、このアルゴリズムでは桁数が大きい素数を判定することはできません。

現在、RSA アルゴリズムに適した素数を生成する最も実用的な方法は、確率検定法です。この方法の考え方は、大きな奇数をランダムに生成し、それが条件を満たすかどうかをテストすることです。条件を満たしている場合、その大きな奇数は素数である可能性があり、そうでない場合は合成数です。

素数は無限に存在するため、整数が素数であるかどうかを判断することは常に難しい問題です。ウィルソンの定理は、その判断方法の 1 つです。

ウィルソンの定理: 正の整数 n>1 の場合、(n-1)! ≡ -1(mod n) の場合にのみ、n は素数です。

ウィルソンの定理は素数に対して同等の命題を与えますが、階乗が急速に増加するため (たとえば、13! は 60 億を超えます)、その実用的な価値は高くありません。そこで、確率検定法を提案する。

ミラー・ラビン素数検定は典型的な確率検定法です。単一のミラー・ラビン法の正解確率は 3/4 より大きいことが証明されており、これを複数回繰り返すことでこの確率を高めることができます。ミラー・ラビン法には一定の誤りの確率がありますが、実践では、20 回繰り返すと 107 以内の素数は誤って判定されないことがわかっています。

2. RSA暗号化および復号化アルゴリズムのプロセス

（１）RSA暗号化アルゴリズムのプロセス

RSA 暗号化アルゴリズムのプロセスは次のとおりです。

① ランダムに２つの大きな素数 p と q を取ります（秘密にしておきます）。

② 公開係数n = p × q（公開）を計算する。

③秘密のオイラー関数φ(n)=(p-1)×(q-1)を計算し（秘密にしておいてください）、pとqを破棄し、誰にも知らせないでください。

④ gcd(e,φ(n))=1となる整数eをランダムに選択する（公開e暗号鍵）。

⑤ de≡1(mod φ(n))を満たすようにdを計算する（復号鍵dは秘密にしておく）

⑥ 平文Xをrのe乗で法として暗号化演算を完了し、暗号文Yを生成します（XとYの値は0からn-1の範囲です）。つまり、Y=Xemod nです。

⑦ 復号：暗号文Yをnのd乗で割って、X=Ydmod nを得る。

RSA 暗号化（復号化）アルゴリズムの実装プロセスでは、主な計算量はモジュールの逆元とモジュラー指数の計算です。通常、モジュールの逆元の計算には拡張ユークリッドアルゴリズムが使用されます。

（２）RSA復号アルゴリズムのプロセス

指数が大きいため、RSA 復号化プロセスには時間がかかりますが、中国剰余定理 (CRT) を使用することで復号化アルゴリズムの効率を向上させることができます。 CRT は、RSA 復号化アルゴリズム (M=Cdmod pq を使用) に対して 2 つの復号化方程式を生成します。つまり、M1=Mmod p=(Cmod p)d mod (p-1)mod p、M2=Mmod q=(Cmod q)d mod (q-1)mod q です。

方程式 M=M1mod p と M=M2mod q を解くと、一意の解があることがわかります。

3. RSAアルゴリズムの応用

(1)デジタル署名のためのRSA

① 署名: 任意のメッセージm∈Mに対して、ユーザーは自分の秘密鍵を使用して次のように署名します: S≡md(mod n)、その後、署名されたメッセージ(m, S)を取得できます。

②署名を検証する：ユーザの公開鍵（e, n）を用いてm≡Se(mod n)が成立するかどうかを検証する。

（２）RSA暗号化アルゴリズムの例

RSA の動作原理は簡単な例を通して理解できます。計算を簡単にするために、次の例では小さな素数 p、q、e のみが選択されています。ユーザー A が RSA を介してプレーンテキストの「キー」を暗号化し、ユーザー B に渡す必要があると仮定します。プロセスは次のとおりです。

1) 公開鍵と秘密鍵(e,n)と(d,n)を設計する

p=3、q=11とすると、n=p×q=3×11=33、f(n)=(p-1)(q-1)=2×10=20となります。e=3（3と20は互いに素）とすると、e×d≡1 mod f(n)、つまり3×d≡1 mod 20となります。 d の値は試行錯誤によって決定できます。計算結果を表3に示す。

表3 d値の計算結果

試算すると、d=7のとき、合同方程式e×d≡1 mod f(n)が成立することがわかります。したがって、d=7 に設定して、公開鍵と秘密鍵のペアを設計できます。暗号化キー (公開鍵) は KU=(e,n)=(3,33)、復号化キー (秘密鍵) は KR=(d,n)=(7,33) です。

2) 英語のデジタル化

プレーンテキスト情報はデジタル化され、それぞれ 2 つの数字のブロックにグループ化されます。プレーンテキストの英語文字コード表は、表4に示すように、数値がアルファベット順に並べられているものとします。

表4 プレーンテキスト英語文字エンコード表

グループ化されたキーのプレーンテキスト情報は、11、05、25 です。

3) 平文暗号化

ユーザ暗号化キー（３、３３）は、デジタル化された平文パケット情報を暗号文に暗号化する。 C≡Me(mod n)から次の式が得られます。

C1=(M1)d(modn)=113(mod33)=11

C2=(M2)d(modn)=053(mod33)=26

C3=(M3)d(modn)=253(mod33)=16

したがって、対応する暗号文情報は 11、26、16 です。

4) 暗号文の復号

ユーザー B が暗号文を受け取った後、それを復号化したい場合は、M≡Cd(mod n) を計算するだけです。つまり、次のようになります。

M1=(C1)d(modn)=117(mod33)=11

M2=(C2)d(modn)=317(mod33)=05

M3=(C3)d(modn)=167(mod33)=25

ユーザー B が取得した平文情報は、11、05、25 です。上記のエンコード表に従って英語に変換し、復元された元のテキスト「キー」を取得します。

もちろん、実際のアプリケーションはこれよりもはるかに複雑です。 RSA アルゴリズムの公開鍵と秘密鍵の長さ (モジュラス長) は、セキュリティを確保するために 1024 ビット、または 2048 ビットに達する必要があるため、p、q、e の選択、公開鍵と秘密鍵の生成、暗号化と復号化のモジュラー指数の計算には、すべて完了するためにコンピューターの高速計算能力を必要とする特定の計算手順があります。

4. RSA暗号化および復号化アルゴリズムのセキュリティ

RSA 暗号化アプリケーションでは、公開鍵 KU は公開されています。つまり、e と n の値は第三者の盗聴者によって取得される可能性があります。 RSA 暗号を解読する鍵は、e と n (n は pq に等しい) の既知の値から d の値を見つけ、それによって暗号文を解読するための秘密鍵を取得することです。上記の式、d≡e-1(mod((p-1)(q-1))) または de≡1(mod((p-1)(q-1))) から、パスワードクラッキングの本質的な問題は、値 pq から (p-1) と (q-1) を見つけることであることがわかります。つまり、pとqの値がわかればdの値もわかり、秘密鍵も取得できるのです。

p と q が大きな素数である場合、その積 pq から因数 p と q を分解することは、認識されている数学の問題です。たとえば、pq が 1024 ビットほどの大きさの場合、誰も計算ツールを使用してそれを因数分解するタスクを完了することができませんでした。そのため、RSA は 40 年以上にわたって提案され、さまざまな攻撃のテストに耐え、徐々に人々に受け入れられ、現在では最も優れた公開鍵方式の 1 つであると一般的に考えられています。

しかし、RSA の安全性は大きな数の因数分解に依存しているものの、RSA の解読の難しさが大きな数の因数分解の難しさと同等であるという理論的な証明はありません。つまり、RSA の最大の欠陥は、その機密性性能を理論的に把握できないことです。

さらに、RSA の欠点は次のとおりです。

① 鍵生成が非常に面倒であり、素数生成技術によって制限されるため、ワンタイムワンキーを実現することは困難である。

② パケット長が大きすぎる。セキュリティを確保するには、n は少なくとも 600 ビットである必要があります。計算コストが高く、速度が遅く、対称暗号化アルゴリズムよりも数桁遅くなります。さらに、大数分解技術の発展に伴い、この長さは依然として増加しており、データ形式の標準化に役立ちません。

したがって、RSA は少量のデータの暗号化にのみ使用でき、大量のデータの暗号化には依然として対称暗号化アルゴリズムを使用する必要があります。