セキュリティ・シリーズ - RASの過去と現在 #セーフだ。

私に言わせれば、どのアルゴリズムが最も重要ですか？

私なら「公開鍵暗号」と答えますね。

コンピュータ通信のセキュリティの基礎であるため、暗号化されたデータが破られることはありません。

本題に入るために、まず「公開鍵暗号アルゴリズム」とは何かを簡単に紹介します。

I. 歴史

1976年以前は、暗号化の方法はすべて同じパターンでした：

パーティAはメッセージを暗号化するために特定の暗号化ルールを選択します；

パーティBは同じルールで情報を解読します。

暗号化と復号化には同じルールが使われるので、これは「対称暗号化アルゴリズム」と呼ばれます。

この暗号化モデルには大きな弱点があります。A当事者はB当事者に暗号化ルールを伝えなければならず、そうしなければ復号化できないのです。鍵の保存と転送が最大の頭痛の種となります。

1976年、ウィットフィールド・ディフィーとマーティン・ヘルマンという2人のアメリカ人コンピュータ科学者が、鍵を直接転送することなく復号化を可能にする新しいアイデアを思いつきました。これは「ディフィー・ヘルマン鍵交換アルゴリズム」として知られています。このアルゴリズムは他の科学者にも影響を与えました。2つのルールの間に何らかの対応関係があれば、暗号化と復号化に異なるルールを使用することができ、鍵を直接渡す必要がないことに気づきました。この新しい暗号化方式は「非対称暗号化」と呼ばれています。

当事者Bは2つの鍵を生成。公開鍵は誰でも利用できる公開鍵で、秘密鍵は秘密鍵です。

パーティAはパーティBの公開鍵を入手し、それを使ってメッセージを暗号化します。

当事者Bは暗号化されたメッセージを受け取り、秘密鍵で復号します。

公開鍵が秘密鍵によってのみ復号化できるメッセージを暗号化する場合、秘密鍵が漏洩しない限り、通信は安全です。

1977年、リベスト、シャミア、アドルマンという3人の数学者が、非対称暗号化を可能にするアルゴリズムを考案しました。このアルゴリズムは3人の名前にちなんでRSAアルゴリズムと呼ばれています。それから現在に至るまで、RSAアルゴリズムは最も広く使われている「非対称暗号化アルゴリズム」です。コンピュータ・ネットワークがあれば、どこにでもRSAアルゴリズムがあると言っても過言ではありません。

開示されている文献によると、破られたことのあるRSA鍵の最長は768バイナリビットです。つまり、768ビットより長い鍵は破られないので、1024ビットのRSA鍵は基本的に安全であり、2048ビットの鍵は極めて安全であると考えられます。

次に本題に入り、RSAアルゴリズムの仕組みを説明します。この記事は2部構成になっており、今日はその第1部で、使用する4つの数学的概念を紹介します。ご覧の通り、RSAアルゴリズムは難しくはなく、理解するのに必要なのは数論のわずかな知識だけです。

II. 相互の質量関係

つの正の整数が1以外の共通因子を持たない場合、互いに素であるといいます。例えば、15と32は共通の因数を持たないので、互いに素です。これは、素数でない数も互いに素数の関係を形成できることを示しています。

相互の品質関係について、次のような結論を導き出すのは難しいことではありません：

1.任意の2つの素数は、例えば、13と61のような相互関係の関係を形成します。

2.素数と、素数の倍数でない別の数は、例えば3と10のように、互いに素数の関係になります。

3.97と57のように、2つの数のうち大きい方が素数であれば、2つの数は互いに素数。

4.1と任意の自然数は相互に素数、例えば1と99。

5.pを1以上の整数とすると、pとp-1は互いに素数の関係になります。

6.pが1より大きい奇数の場合、pとp-2は互いに素数の関係になります。

III. オイラーの関数

以下の質問についてご検討ください：

任意の正の整数nが与えられたとき、n以下の正の整数のうち、nと互いに素数の関係にあるものはいくつありますか。

この値を計算する方法をオイラー関数といい、φと表記します。1から8のうち、8と逆数をなすのは1、3、5、7なので、φ＝4。

φの計算は複雑ではありませんが、最後の式を得るためには、段階を追って説明する必要があります。

シナリオ1

n = 1ならば、φ = 1 。1は任意の数と相互素数関係を形成するから。

第2シナリオ

nが素数の場合、φ = n-1 。これは、素数がそれより小さいすべての数と相互に素数の関係を形成するからです。例えば、5は1、2、3、4と互いに素。

第3のシナリオ

n が素数のべき乗、すなわち n = p^k である場合、次のようになります。

例えば、φ = φ = 2^3 - 2^2 = 8 - 4 = 4。

これは、ある数がnと互いに素であることができるのは、素数pを含まない場合に限られるからです。そして、素数pを含む数は全部でp^個あります。つまり、1×p、2×p、3×p、...、p^×pです。これらを取り除くと、残るのはnと互いに素な数です。

上記の式は次のような形でも書けます：

上の2番目のケースは、k = 1の特別なケースであることがわかります。

第4のシナリオ

nが2つの互いに素な整数の積に分解できる場合。

n = p1 × p2

原則

= =

つまり、積のオイラー関数は個々の因子のオイラー関数の積に等しい。例えば、φ＝φ×φ＝4×6＝24。

この記事の証明は「日本の残差定理」を使うべきですが、ここでは拡大せず、考え方だけを簡単に説明します：aとp1が互いに素であり、bとp2が互いに素であり、cとp1p2が互いに素である場合、cと数の組は一対一対応です。aの取り得る値はφ、bの取り得る値はφですから、数の組はφφ通り、cの取り得る値はφ通りですから、φはφφに等しい。

第5のシナリオ

なぜなら、1より大きい正の整数は、素数系列の積として書くことができるからです。

第4条の結論に基づくと、以下のようになります。

そして、第3条の結論に基づいて、次のようになります。

と同じです。

これがオイラー関数の一般的な計算式です。例えば、1323のオイラー関数は以下のように計算されます：

IV.オイラーの定理

オイラーの関数の有用性は、オイラーの定理にあります。オイラーの定理」とは

二つの正整数a、nが互いに素であるとき、nのオイラー関数φは次式が成り立つようにします：

つまり、aのφ乗をnで割った余りは1、あるいはaのφ乗から1を引いたものはnで割り切れるということです。aのφ乗は1に等しく、7のφ乗は6に等しい。例えば、3と7は互いに素であり、7のオイラー関数φは6に等しいので、3から1を引いた6乗は7で割り切れます。

オイラーの定理の証明はもっと複雑なので、ここでは省略します。結論だけ覚えておいてください。

オイラーの定理は、ある種の操作を大幅に簡略化することができます。例えば、7と10は互いに素であり、オイラーの定理によれば

φは4に等しいことが知られているので、7の4乗の桁は1でなければならないことが直ちに導かれます。

したがって、7のべき乗の1桁は暗算で求めることができます。

オイラーの定理には特殊なケースがあります。

正の整数aが素数pと互いに素であるとすると、素数pのφはp-1に等しいので、オイラーの定理は次のように書けます。

これは有名なフェルマーの小定理です。オイラーの定理の特殊な場合です。

オイラーの定理はRSAアルゴリズムの核心です。この定理を理解することは、RSAを理解することにつながります。

V. モーダル対要素

最後にもう一つ、コンセプトが残っています：

2つの正の整数aとnが互いに素である場合、ab-1がnで割り切れるか、abをnで割った余りが1になるような整数bを見つけることができなければなりません。

この場合、bはaの「モジュロ逆要素」と呼ばれます。

例えば、3と11が互いに素ならば、-1は11で割り切れるので、3のモジュロ逆数は4です。明らかに、モジュロ逆元は1つ以上あり、4プラスマイナス11の整数倍が3のモジュロ逆元{... ,-18,-7,4,15,26,...,-18,-7,4,15,26,...}すなわち、bがaのモジュロ逆行列であれば、b+knはすべてaのモジュロ逆行列です。

オイラーの定理は、モジュロ逆要素が必ず存在することを証明するのに使えます。

aのφ-1乗はaのモジュロ逆要素であることがわかります。

さて、使用する必要がある数学的なツールは、すべてintroduced.RSAアルゴリズムは、数学的な知識を含む、上記のとおりです、この知識を使用すると、RSAアルゴリズムを読んで理解することができます。

VI.鍵生成のステップ

RSAアルゴリズムを例題を通して理解しましょう。アリスがボブと暗号化して通信したいとします。

最初のステップでは、2つの不等な素数pとqをランダムに選びます。

アリスが選んだのは61歳と53歳。

第2ステップでは、pとqの積nを計算します。

アリスは61と53を掛けました。

n = 61 x 53 = 3233

3233は2進数で110010100001と書き、12ビットなので鍵は12ビットです。実際には、RSA鍵は通常1024ビットで、重要な場面では2048ビットになります。

第3ステップでは、nのオイラー関数φを計算します。

式によると

ed ≡ 1 )

アリスは、φは60×52、つまり3120に等しいと計算します。

第4ステップでは、1＜e＜φかつeとφが互いに素であることを条件に、ランダムな整数eを選択します。

アリスはそれから1から3120の間で無作為に17を選びました。

第5ステップでは、φに対するeのモジュラー逆要素dを計算します。

モジュロ逆要素」とは、edをφで割った余りが1になるような整数dのこと。

ed ≡ 1 )

この式は次の式と等価です。

ed - 1 = k

従って、モーダル逆要素dを求めることは、本質的に以下の二次方程式を解くことになります。

ex + = 1

e = 17、φ = 3120であることが知られています。

17x + 3120y = 1

この方程式は「拡張ユークリッド・アルゴリズム」を使って解くことができますが、ここでは省略します。要約すると、アリスは整数解の集合を＝、すなわちd＝2753として計算しました。

これですべての計算が終わりました。

第6段階では、nとeが公開鍵としてカプセル化され、nとdが秘密鍵としてカプセル化されます。

アリスの場合、n = 3233, e = 17, d = 2753なので、公開鍵は、秘密鍵は。

実際には、公開鍵データも秘密鍵データもASN.1形式で表現されます例題）。

VII.RSAアルゴリズムの信頼性

上記のキー生成ステップを思い出すと、合計6つの数字が表示されます：

p q n φ e d

この6つの数字のうち、公開鍵が使われるのは2つで、残りの4つは公開されません。その中で最も重要なのはdで、nとdが秘密鍵を形成し、dが漏れると秘密鍵が漏れたのと同じことになるからです。

では、nとeがわかっている状態でdを導くことは可能なのでしょうか？

ed≡1 ）。eとφがわかって初めてdが計算できるのです。

φ=.φはpとqが既知の場合にのみ計算可能。

n＝pq。pとqはnを因数分解することでしか計算できません。

結論：nが因数分解できれば、dが計算できることになり、秘密鍵は破られることになります。

しかし、大きな整数の因数分解は非常に難しい作業です。現在のところ、潔を乱暴に破る以外に有効な方法は見つかっていません。ウィキペディアにはこうあります：

"非常に大きな整数の因数分解の難しさが、RSAアルゴリズムの信頼性を決定します。言い換えれば、非常に大きな整数の因数分解が難しいほど、RSAアルゴリズムの信頼性は高くなります。

もし誰かが高速因数分解のアルゴリズムを見つけたとしたら、RSAの信頼性は極めて低くなるでしょう。しかし、そのようなアルゴリズムが見つかる可能性は非常に低いのです。2008年まで、RSAアルゴリズムを攻撃する確実な方法は世界に存在しませんでした。

RSAで暗号化されたメッセージは、鍵の長さが十分である限り、事実上解読不可能です」。

例えば、3233を因数分解することはできますが、次の整数を因数分解することはできません。

12301866845301177551304949 58384962720772853569595334 79219732245215172640050726 36575187452021997864693899 5647494277406384592519255732630345373154826850791702 61221429134616704292143116 02221240479274737794080665 153419597459856902143413

これは2つの素数の積に等しい：

33478071698956898786044169 84821269081770479498371376 85689124313889828837938780 02287614711652531743087737 814467999489 ×36746043666799590428244633 79962795263227915816434308 76426760322838157396665112 79233373417143396810270092 897736308917

実際、これはおそらく人間が分解した最大の整数です。これより大きな因数分解は報告されていないため、現在解読されている最長のRSA鍵は768ビットです。

## 暗号化と復号化

公開鍵と鍵があれば、暗号化と復号化ができます。

暗号化は公開鍵で行う必要があります。

ボブが暗号化されたメッセージ m をアリスに送りたい場合、アリスの公開鍵で m を暗号化しなければなりません。ここで、m は整数で n より小さくなければならないことに注意してください。

いわゆる「暗号化」とは、次の式でcを計算することです：

アリスの公開鍵は , で、ボブのmは65と仮定すると、以下の式が成り立ちます：

ですから、cは2790に等しく、ボブは2790をアリスに送ります。

復号化には秘密鍵が必要です。

アリスはボブから2790を受け取った後、自分の秘密鍵を使って解読しました。以下の式が成り立つことが証明できます：

つまり、cのd乗をnで割った余りがmであり、cが2790であり、秘密鍵がmであるとすると、アリスは次のように計算します。

したがって、アリスはボブの暗号化前の原文が65であることを知っています。

この時点で、「暗号化-復号化」の全プロセスが完了します。

また、すでに述べたように、dを知るためにはnを分解しなければなりませんが、これは非常に困難です。したがって、RSAアルゴリズムは安全な通信を保証します。

公開鍵はnより小さい整数mしか暗号化できないので、nより大きい整数を暗号化したい場合はどうすればいいのでしょうか？一つは、長いメッセージをいくつかの短いメッセージに分割し、それぞれのセグメントを別々に暗号化する方法です。もう一つは、「対称暗号化アルゴリズム」を選択し、このアルゴリズムの鍵でメッセージを暗号化し、DES鍵をRSA公開鍵で暗号化する方法です。