RSA暗号化。 RSAアルゴリズムの記述と実装

RSA暗号化は最初のものの1つです安全なデータ伝送のために広く使用されている実用的な公開鍵暗号システム。同様のサービスとの主な違いは、暗号化キーが公開されており、秘密にされている復号化キーとは異なる点です。 RSA技術では、この非対称性は、2つの大きな素数（因数分解問題）の再現を因数分解する実際的な複雑さに基づいています。

創造の歴史

名前RSAは、姓の頭文字で構成されています。Rivest、Shamir and Adleman - 1977年に最初にこのような暗号アルゴリズムを公表した科学者。英国の秘密サービスのために働いた英国の数学者、クリフォード・コックスは、1973年に初めて同等のシステムを開発したが、1997年までに機密解除されなかった。

ユーザーRSAが作成して公開する補助価値とともに2つの大きな素数に基づく公開鍵。素数は秘密にする必要があります。誰でも公開鍵を使ってメッセージを暗号化できますが、十分な大きさであれば、素数を知っている人だけがメッセージを解読できます。 RSA暗号化の開示は、主な問題として知られています。今日、このメカニズムがどれほど信頼できるかについてのオープンな議論があります。

RSAは比較的遅いアルゴリズムです。そのため、ユーザーデータを直接暗号化するためにあまり広く使われていません。多くの場合、この方法は、共有キーを暗号化形式で対称暗号化キーに送信するために使用され、大量の暗号化および復号化操作をはるかに高速で実行できます。

現代の暗号システムはいつ登場しましたか？

非対称鍵暗号システムの考え方1976年にこの概念を発表し、デジタル署名を提示し、数論を適用しようとしているDiffieとHellmanに起因しています。それらの定式化は、素数を法とする特定の数の累乗から作成された共有秘密鍵を使用する。しかし、ファクタリングの原則はその時点では十分に研究されていないため、この関数の実装の問題が残されていました。

マサチューセッツ州のリベスト、アディシャミール、アドレーマンInstitute of Technologyは、解読が困難な単方向関数を作成するために、年内にいくつかの試みを行った。 RivestとShamir（コンピュータ科学者として）は多くの潜在的な機能を提案し、Adleman（数学者として）はアルゴリズムの「弱点」を探した。彼らは多くのアプローチを使い、結局1977年4月に今日RSAとして知られているシステムを開発しました。

EDSと公開鍵

電子デジタル署名、すなわちEDSは、これは電子形式の文書の不可欠な部分です。それはある暗号データ変更で形成される。この属性を使用することで、文書の完全性とその機密性をチェックし、誰が所有しているかを確認することができます。実際、それは普通の標準的な署名の代わりです。

この暗号システム（RSA暗号化）は、公開鍵は対称とは異なります。その機能の原則は、プライベート（暗号化）とオープンの2つの異なるキーを使用することです。最初のものは、EDSを生成し、続いてテキストを解読するために使用されます。 2つ目は、EDSを適切に暗号化して検証することです。

署名を使用すると、RSA暗号化をよりよく理解することができます。その例は、他の人の目には見えない秘密の「秘密」として引用することができます。

アルゴリズムの本質は何ですか？

RSAアルゴリズムは4つのステップで構成されています。鍵の生成、配布、暗号化、復号化が含まれます。既に示されているように、RSA暗号化は、公開鍵および秘密鍵を含む。オープンは誰にでも分かり、メッセージを暗号化するために使用されます。その本質は、公開鍵で暗号化されたメッセージは、秘密鍵を使用して特定の時間間隔でのみ復号化できることです。

セキュリティ上の理由から、整数は無作為に選択され、同じ大きさであるが、同時に、因数分解をより困難にするために、長さが数桁異なる。同じ番号は、そのシンプルさのためにテストを使用して効果的に見つけることができるため、情報の暗号化は必然的に複雑にする必要があります。

公開鍵は、モジュールと公的な出展者で構成されています。閉鎖はモジュールと秘密のインジケータで構成され、秘密にしておく必要があります。

RSAファイルの暗号化と弱点

しかし、多くのハッキングメカニズムがあります。シンプルなRSA。数字と数字の小さい数字で暗号化する場合、整数より上の暗号文のルートを選択すると、簡単に暗号を明らかにすることができます。

RSA暗号化は（すなわち、ランダム成分を持たない）決定論的アルゴリズムによって、攻撃者は、公開鍵の下にある可能性のあるオープンテキストを暗号化し、それらが暗号文と等しいかどうかをチェックすることによって、暗号システムに対して選択された公開テキスト攻撃を首尾よく開始することができる。攻撃者が拡張された形式の対応するテキストを知っていても、2つの暗号を互いに区別できない場合には、暗号システムは意味的に安全です。上述のように、他のサービスを補完することなくRSAは意味的に安全ではない。

追加の暗号化アルゴリズムとセキュリティアルゴリズム

上記の問題を回避するために、RSAの実際の実装は、通常、暗号化の前に構造化されたランダム化された埋め込みの形式に組み込まれています。これにより、コンテンツが安全でない平文の範囲内に収まらず、メッセージをランダムに選択して公開することができなくなります。

RSA暗号システムのセキュリティと暗号化この情報は2つの数学的問題、すなわち多数の因数分解問題と実際のRSA問題に基づいています。 RSAにおける暗号文と電子署名の完全な開示は、これらの問題の両方を集約して解決することができないと仮定して容認できないと考えられる。

しかし、回復の可能性のために攻撃者は、公開鍵から秘密インデックスを計算し、標準手順を使用してテキストを復号化することができます。今日では、古典的なコンピュータで大きな数を因数分解するための既存の方法は見つかっていませんが、存在しないことは証明されていません。

オートメーション

ヤフーと呼ばれるツールは、このプロセスを最適化するために使用されます。 YAFUの自動化は、インテリジェントで適応性のある方法論で因子分解アルゴリズムを組み合わせた最新の機能であり、任意の入力数に対する因子を見つける時間を最小限に抑えます。アルゴリズムのほとんどの実装はマルチスレッドであり、Yafuはマルチコアまたはマルチコアプロセッサ（SNFS、SIQS、ECMを含む）を最大限に活用することができます。まず第一に、管理されたコマンドラインツールです。通常のコンピュータでYafuを使用して暗号化係数を検索する時間は、103.1746秒に短縮できます。ツールは320ビット以上の容量のバイナリファイルを処理します。これは非常に複雑なソフトウェアであり、インストールと構成にはある程度の技術スキルが必要です。したがって、RSA-C暗号化は脆弱である可能性があります。

現代のハッキング試み

2009年、ベンジャミン・ムーディーRSA-512鍵は、よく知られているソフトウェア（GGNFS）と平均的なデスクトップコンピュータ（1900 MHzのデュアルコアAthlon64）だけを使用して暗号文を73日間解読しました。この経験からわかるように、「ふるい分け」プロセスでは、5ギガバイト未満のディスクと約2.5ギガバイトのRAMが必要です。

2010年時点で、最大の分解RSA数は768ビット（RSA-768 232桁）でした。その開示は数百台のコンピュータで同時に2年間続いた。

実際には、RSAキーは長時間にわたり、通常は1024〜4096ビットです。一部の専門家は、近い将来に1024ビットの鍵が信頼できなくなる可能性があると考えているか、かなり裕福に資金を提供されている攻撃者によって鍵が割れている可能性もあります。しかし、近い将来に4096ビットの鍵が公開される可能性があると主張する者はほとんどいない。

見通し

したがって、一般に、RSA数字が十分大きい場合は安全です。メイン番号が300ビット以下であれば、パブリックドメインで既に利用可能なソフトウェアを使用して、パーソナルコンピュータ上で暗号文とEDSを数時間以内に分解することができます。証明されているように、512ビットの長さのキーは、すでに数百台のコンピュータを使用して1999年に開設されている可能性があります。現在、これは公開されているハードウェアを使用して数週間で可能です。したがって、将来的には、指のRSA暗号化が容易に明らかになり、システムが絶望的に時代遅れになる可能性があります。

正式には2003年に、1024ビット鍵のセキュリティが疑問視されました。現在、少なくとも2048ビットの長さを持つことが推奨されています。