家 › 電話 › RSAさん、本当にそんなに簡単ですか？ RSA 暗号パラメータの選択と考えられる結果 rsa アルゴリズムを使用した暗号化

RSAさん、本当にそんなに簡単ですか？ RSA 暗号パラメータの選択と考えられる結果 rsa アルゴリズムを使用した暗号化

パーソナルコンピュータ機器のすべてのユーザーが RSA 暗号化とは何かを知っているわけではなく、この用語を聞くと驚きます。しかし、この概念には複雑な要素は何も隠されていません。 RSA 暗号化は、コンピューター技術上で作成されたすべての電子データを安全に使用できるようにする暗号システムです。これは、特定のコードを知らなければファイルを読み取ることができないデータの復号化ではありません。 RSA 暗号化は、キーがオープンであることを意味します。

RSA 暗号化は、因数分解の原理に基づいて機能します。このような？そしてこれがファクタリングです
2 つの大きな数値データの再現。

RSA 暗号化システムを作成したのは誰ですか?

RSA 暗号化アルゴリズムは 1977 年に作成されました。その作成者は科学者の Rivest、Shamir、Adleman であり、彼らの姓の頭文字を省略して RSA という用語が構成されています。以前のアルゴリズムは、イギリスの数学者で、国の諜報機関で働いていたクリフォード・コックスによって開発されました。 1973 年に、彼は同等のシステムを作成することに成功しましたが、それは機密扱いの個人によってのみ使用され、その技術はパーソナルコンピュータ機器の一般ユーザーのレベルには配布されませんでした。

RSA暗号化はどのように機能しますか?

システムのユーザーは、最初に公開キーを作成し、公開します。公開キーは 2 つの大きな数値に基づいており、補助値のみが含まれています。最も単純な数字は秘密にされます。たとえば、電子メールを読むには、文書の公開キーを使用するだけで済みますが、キーが長い場合、情報にアクセスすることが困難になります。

現在、RSA 暗号化は、あまり信頼性の低いデータ暗号化方式として特徴付けられています。これは遅いアルゴリズムであるため、一般的なコンピュータユーザーの間ではあまり一般的ではありません。それでは、一般のコンピュータ科学者が実際には使用しないのに、なぜこのシステムが作成されたのでしょうか?

問題は、高速で大量の暗号化と復号化を行うように設計された対称暗号化キーの公開キーの暗号化された送信にその用途が見つかったことです。

最新の非対称キー暗号システムは、Diffie と Hellman の研究のおかげで登場しました。彼らは 1976 年にこのコンセプトを開発し、デジタル録音として一般に公開しました。彼らは、特定の数値を素数で割る原理に基づいて公開鍵を作成することができました。しかし、当時は因数分解の原理自体がまだ十分に研究されていなかったため、その原理は宙に浮いたままでした。

Rivest、Adim Shamir、Adleman は、これまでの成果にとどまらず、解読が容易ではない一方向関数の仕組みを徹底的に解明しました。 Rivest と Shamir は関数そのものに直接取り組み、Adleman は作成中のアルゴリズムの弱点を探しました。最終的に、彼らは RSA 非対称鍵システムの作成に成功しました。

デジタル署名と公開鍵通信

現在、多くの企業が業務活動においてこのような電子要素をデジタル署名として使用しています。いわゆるデジタル署名を含む作成された電子文書は、法的レベルで認められた公式文書です。電子デジタル署名は、データが暗号的に変更されるときに作成されます。

従来の署名に代わるこの方法により、文書を機密にし、完全性を確保し、作成者と所有者に関する情報を常に保持することが可能になります。

電子署名は、問題の RSA 暗号化と密接に関連しています。前述したように、このシステムは公開鍵の存在を前提としています。現在、権限のない人が情報にアクセスするのを防ぐために、誰もが知っている公開キーと暗号化された秘密キーの 2 つのキーが実際に使用されています。

したがって、公開キーを使用すると電子印鑑のあるドキュメントにアクセスでき、秘密キーを使用すると署名を復号して検証できます。言い換えれば、RSA 暗号化を使用すると、ドキュメントを覗き見から隠して秘密に保ちながら、適切なタイミングでドキュメントにアクセスできるようになります。

発明されたアルゴリズムの本質が何であるかを理解してみましょう?

RSA 暗号化は 4 つの段階で機能します。
鍵の生成。
キーの配布。
キーの暗号化。
キーの復号化。

RSA 暗号化の原理は、公開キーと秘密キーの作成を組み合わせたものです。これについてはもう一度考えてみましょう。オープン – 誰にでも知られており、メッセージの暗号化に使用できます。この電子データは秘密鍵を使用して復号化できます。公開キーを作成するとき、数値はランダムに選択され、サイズは同じですが、記録の期間が異なるため、因数分解はより困難になります。

同一の数値は、その単純性をテストすることで見つかります。したがって、暗号化は徐々に複雑になってきました。公開鍵は何で構成されていますか? そして、それは通常のモジュールといわゆる公開指数で構成されます。ただし、クローズドなものにはモジュールとプライベートインジケーターが含まれており、作成者以外には提供されません。

RSA 暗号化技術の弱点

よく考えられた暗号化原理にもかかわらず、簡単に破られる可能性があります。これは、キーの作成に小さな数値が使用された場合に実行でき、単純な整数を単純に選択するだけでキーを明らかにできます。

RSA 暗号化自体は、ランダムなコンポーネントを排除するアルゴリズムであるため、コンピュータネットワークの詐欺師が Dos 攻撃の平文と照合することで、決定論的なメカニズムを突破することが容易になります。Dos 攻撃では、実行中のテキストの長さが生成されたキーと永続的に等しいかどうかがチェックされます。

これは、まず第一に、RSA 暗号化が、望ましくない人物による攻撃から電子データを保護する上であらゆる点で安全な暗号システムではないことを説明しています。より高度なサーバーに追加された場合を除き、そのようなプロパティは取得されません。

RSA 暗号化を使用する際のセキュリティを確保する追加コンポーネント

RSA 形式の暗号化がハッキングされる可能性を防ぐために、プログラマは構造化された、いわゆるランダム化された埋め込みの形式を RSA 形式の暗号化に組み込みます。これは、電子情報が実際に暗号化される前に行われます。この点により、電子文書の内容が全員に公開されることはなく、鍵をランダムに選択するメカニズムが文書に適用されている場合、機密情報が閲覧できないことが保証されます。

RSA 暗号化は数学的な数値を因数に分解しますが、そのメカニズムはまだ完成していません。したがって、現時点では、攻撃者にはデータ暗号化を破る方法を選択する機会と多くの抜け穴がまだあります。そして彼らは、素因数を復元するメカニズムを通じてこれを正確に行うことに成功しました。

詐欺師は公開キーに含まれる秘密インジケータを計算し、標準的な方法を使用してドキュメントを復号します。したがって、本当に企業に損害を与えようとする人々の行動範囲は非常に広いものになります。 RSA 暗号化セキュリティの問題は、公に語る人はほとんどいませんが、依然として関連性があり未解決であるとだけ言っておきましょう。

自動化された電子データ暗号化プロセス

セキュリティ評価は低いにもかかわらず、問題の RSA 暗号化は多くの業界で適用可能です。電子文書が大量に流通する場合には特に歓迎されます。 RSA 暗号化は、平均的な責任レベルでドキュメントを保護するために使用されているとだけ言っておきましょう。

Yafu ソフトウェアを使用すると、電子データを自動的に暗号化できます。このプログラムを使用すると、ファクタリングの信頼性のルールを遵守しながら、非対称キーを作成するためのデータをすばやく見つけることができます。 SIQS、ECM、SNFSなどのプロセッサと互換性があります。コマンドラインから起動します。このコマンドを一行で入力すると、キー作成のためのデータの検索時間を数分の1に短縮できます。

パーソナルコンピュータ機器の平均的なユーザーは、このソフトウェアに対応できません。そのインストールと構成には特定の知識が必要であり、これは多くの場合、IT プログラマーや専門家によって行われます。

RSA 暗号化には深刻な脆弱性があり、公開キーと秘密キーの作成にディスク上で数千ビットに及ぶ大量のキーが使用されているにもかかわらずです。

ベンジャミンムーディは 2009 年に、公開鍵と秘密鍵をクラッキングするプロセスが可能であることを証明しました。これには 2 年以上かかる可能性がありますが、世界中のコンピューターシステムの多くがハッキングされる危険にさらされているという事実は変わりません。

たとえば、この専門家は、主要なスクリプトをふるい分けるのに特別なもの、つまり一般ユーザーのコンピュータと GGNFS ソフトウェアを必要としませんでした。数千ビットの暗号化キーを使用しても、情報が機密情報として現場に流出し、他のユーザーがアクセスできなくなることを防ぐことはできません。

もちろん、RSA 暗号化を破るには時間がかかります。多くのハッカーは、良い結果を達成するために何年も費やします。これらは多くの場合、高収入の見込み客であり、適切なキーを探し続ける意欲を刺激します。ほとんどの場合、長いキーのハッキングは、より簡単な方法を求めて放棄されます。しかし、これは、誰もより単純化されたキークラッキングメカニズムを作成しようとしていないことを意味するものではありません。

詐欺師による侵入攻撃に対する主な防御策は、2,000 ビットを超える大きくて長い鍵を作成することです。長さが 100 ビットから 500 ビットの範囲のキーがハッキングされたケースがすでに知られています。したがって、耳を鋭く保つ必要があります。短い鍵を解読するためのメカニズムが存在する場合、電子データ暗号化の最長の組み合わせを解読するための悪意のある者側のどこかでの作業が本格化している可能性があります。

結論

上記に基づくと、RSA 暗号化は、長く情報量の多いキーが作成される限り、電子データの機密性を維持する安全な方法です。

これらを手動で選択するのは難しいため、自動化されたソフトウェア製品 Yafu が使用されます。 IT スペシャリストによってインストールおよび設定されます。自分で行うと、コンピュータのオペレーティングシステムに損傷を与える可能性があります。
このソフトウェアは、最新世代のマルチコアコンピュータプロセッサと連携して動作するように設計されています。

不正攻撃の主なターゲットは大規模な産業企業や金融企業であるため、RSA 暗号化がなければ電子文書管理は機能しません。文書の電子署名も暗号化の対象となり、他の情報データと同様のセキュリティ基準が適用されます。キーが大きいほどドキュメントのハッキングが難しくなるという原則は、公共利用を意図していないすべてのデータに適用されるべきです。

RSA 暗号化は、最初の実用的な公開キー暗号化システムの 1 つであり、安全なデータ送信に広く使用されています。同様のサービスとの主な違いは、暗号化キーが公開されており、秘密に保たれる復号化キーとは異なることです。 RSA テクノロジーは、2 つの大きな素数を因数分解する実際の難しさ (因数分解問題) に基づいています。

創作の歴史

RSA という名前は、1977 年にこれらを初めて公に説明した科学者であるリベスト、シャミール、アドルマンの姓の頭文字から構成されています。英国諜報機関で働いていた英国の数学者クリフォード・コックスは、1973 年に初めて同等のシステムを開発しましたが、機密解除されたのは 1997 年になってからでした。

RSA ユーザーは、2 つの大きな素数と補助値に基づいて公開キーを作成し、公開します。秘密にしなければなりません。誰でも公開鍵を使用してメッセージを暗号化できますが、公開鍵が十分に大きい場合、素数の知識を持つ人だけがメッセージを復号化できます。 RSA 暗号化の解読は大きな問題であることが知られています。現在、このメカニズムの安全性についてオープンな議論が行われています。

RSA は比較的遅いアルゴリズムであるため、直接ユーザーにはあまり使用されていません。この方法の最も一般的な使用法は、対称暗号化キーの暗号化された共有キーを送信することです。これにより、大量の暗号化および復号化操作をより高速に実行できます。

暗号システムが現代的な形になったのはいつですか?

非対称鍵暗号システムのアイデアは、1976 年にこの概念を発表したディフィーとヘルマンによるもので、デジタル署名を導入し、数理論を適用しようとしました。彼らの定式化では、素数を法とするある数値の指数から作成された共有秘密鍵が使用されます。ただし、当時は因数分解の原理が十分に理解されていなかったため、この機能の実装には問題が残されました。

MIT の Rivest、Adi Shamir、Adleman は、デコードが難しい一方向関数を作成するために 1 年にわたって何度か試みました。 Rivest と Shamir は (コンピューター科学者として) 多くの潜在的な関数を提案し、Adleman は (数学者として) アルゴリズムの弱点を調査しました。彼らは多くのアプローチをとり、最終的に 1977 年 4 月に現在 RSA として知られる最終システムを開発しました。

デジタル署名と公開鍵

電子デジタル署名 (EDS) は、電子ドキュメントに不可欠な部分です。これは、データ内の特定の暗号化変更によって形成されます。この属性を使用すると、ドキュメントの完全性や機密性をチェックしたり、その所有者が誰であるかを判断したりすることができます。基本的に、これは通常の標準署名の代替です。

この暗号システム (RSA 暗号化) は、対称キーとは異なる公開キーを提供します。その動作原理は、秘密 (暗号化) 鍵と公開鍵という 2 つの異なる鍵が使用されることです。 1 つ目は、電子署名を生成し、その後テキストを復号化できるようにするために使用されます。 2 つ目は、実際の暗号化とデジタル署名の検証です。

署名を使用すると、RSA 暗号化をより深く理解できるようになります。その例としては、通常の「覗き見を遮断された」機密文書が挙げられます。

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

RSA アルゴリズムは、キーの生成、キーの配布、暗号化、復号化の 4 つの段階で構成されます。すでに述べたように、RSA 暗号化には公開キーと秘密キーが含まれます。 Open は誰もが知ることができ、メッセージの暗号化に使用されます。その本質は、公開キーを使用して暗号化されたメッセージは、秘密キーを使用した一定期間内でのみ復号化できるということです。

安全を期すために、整数はランダムに選択され、サイズは同じである必要がありますが、因数分解をより困難にするために長さは数桁異なります。同一の数値は素数性のテストを使用して効果的に見つけることができるため、情報の暗号化は必然的により複雑になるはずです。

公開キーは、モジュラスと公開指数で構成されます。プライベートは、秘密にしておく必要があるモジュールとプライベートインジケーターで構成されます。

RSA ファイル暗号化と弱点

ただし、単純な RSA を突破するメカニズムは多数あります。低いレートと小さな数値で暗号化する場合、整数の上に暗号文のルートが見つかると、暗号は簡単に破られる可能性があります。

RSA 暗号化は決定論的なアルゴリズムであるため (つまり、ランダムなコンポーネントがありません)、攻撃者は公開鍵でもっともらしい平文を暗号化し、それらが暗号文と等しいかどうかを確認することで、暗号システムに対して選択した平文攻撃を成功させることができます。攻撃者が対応するテキストを平文で知っていたとしても、2 つの暗号を互いに区別できない場合、その暗号システムは意味的に安全であると言われます。上で説明したように、RSA は他のサービスで補完しない限り、意味的に安全ではありません。

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

上記の問題を回避するために、RSA の実際の実装では通常、暗号化の前に何らかの形式の構造化されたランダム化されたパディングが組み込まれます。これにより、コンテンツが安全でない平文の範囲内に収まらず、メッセージが偶然に侵害されることがなくなります。

RSA 暗号システムのセキュリティと情報の暗号化は、大きな数の素因数分解の問題と RSA 問題自体の 2 つの数学的問題に基づいています。 RSA における暗号文とデジタル署名の完全な開示は、これらの問題の両方を同時に解決できないという前提に基づいて、受け入れられないと考えられています。

ただし、素因数を回復する機能のおかげで、攻撃者は公開キーから秘密の指数を計算し、標準的な手順を使用してテキストを復号化できます。現在、古典的なコンピューターで大きな数を因数分解する既存の方法は見つかっていませんが、その方法が存在しないことは証明されていません。

オートメーション

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

現代におけるハッキングの試み

2009 年、Benjamin Moody は、RSA-512 ビットキーを使用し、一般的なソフトウェア (GGNFS) と平均的なデスクトップコンピューター (1900 MHz のデュアルコア Athlon64) のみを使用して、73 日間暗号文の復号化に取り組みました。この経験からわかるように、「選別」プロセスには 5 GB 弱のディスクと約 2.5 GB の RAM が必要でした。

2010 年の時点で、最大の因数分解された RSA 数値は 768 ビット長 (10 進数 232 桁、つまり RSA-768) でした。その展開は、数百のコンピュータ上で同時に 2 年間続きました。

実際には、RSA キーはさらに長くなり、通常は 1024 ～ 4096 ビットになります。一部の専門家は、1024 ビットの鍵は近い将来に安全でなくなる可能性があり、あるいは、十分な資金を持った攻撃者によってすでに解読されている可能性さえあると考えています。しかし、近い将来に 4096 ビットの鍵も公開される可能性があることに異論を唱える人はほとんどいないでしょう。

展望

したがって、数値が十分に大きければ、RSA は安全であると一般に想定されます。基底数が 300 ビット以下であれば、既に無償で公開されているソフトウェアを使用して、パソコン上で暗号文と電子署名を数時間以内に分解することができます。 512 ビットキーは、1999 年には数百台のコンピュータを使用して解読可能であることが証明されていました。最近では、公的に入手可能なハードウェアを使用して、これが数週間以内に可能になります。したがって、将来的には、RSA 暗号化が簡単に破られ、システムが絶望的に時代遅れになる可能性が十分にあります。

公式には、2003 年に 1024 ビット鍵の安全性が疑問視されました。現在、少なくとも 2048 ビット長にすることが推奨されています。

カットの下には、「不適切な」RSA 暗号パラメータを選択した例が示されています。

「RSA モジュール (番号) の選択には注意が必要であることを強調しておく必要があります。 n) 各ネットワーク通信者に対応します。この点に関しては、次のことが言える。読者は、3 つの量のいずれかを知っていることを独立して検証できます。 p, qまたは φ(n)、RSA 秘密キーを簡単に見つけることができます...」。

この文に付け加えてみましょう。以下に示すマニュアルの例のように、RSA 暗号モジュールの選択が失敗した場合は、秘密キーが存在しなくてもテキストを復号化できます。指定された 3 つの量のいずれも知らずに。

これを行うには、暗号モジュールによって指定された暗号文があれば十分です。 n、公開鍵 e暗号化して、わずか 3 ステップのキーレス読み取り攻撃を実行します。 4 番目の攻撃ステップの後、ソーステキストが前のステップで取得され、読み取ることができることが確立されます。それがいかに簡単かを示してみましょう。

まずは、同マニュアルの313～315ページにある例そのものをあげてみましょう。

例

暗号化短い最初のテキストメッセージ: RSA.
受信者は特性を備えた暗号を設定します n=pq=527、どこ p=17, q=31そして φ(n)=(р –1)(q – 1)=480。公開鍵として eと互いに素である数値が選択されます。 φ(n), e=7。拡張ユークリッドアルゴリズムを使用して、この数値の整数が見つかります。 あなたそして v、関係を満たす e・u+φ(n)・v=1:

480=7∙68+4,
7=4∙1+3,
4=3∙1+1,
1=4–3∙1=4–(7–4∙1)∙1=4∙2–7∙1=(480–7∙68)∙2–7∙1=480∙2–7∙137,
v=2、u=–137.

なぜなら –137≡343(mod480)、それ d=343.

検査： 7∙343=2401≡1(mod480).

テキストメッセージは、間隔に含まれる一連の数字として表示されます。。このための手紙 R, Sそしてあは 5 ビットの 2 進数としてエンコードされます。英語のアルファベットのこれらの文字のシリアル番号は、バイナリ表現で使用されます。

R=18 10 =(10010) 2, S=19 10 =(10011) 2,
A=1 10 =(00001) 2.

それから RSA=(100101001100001) 2。テキストを制限された長さのブロックに分割すると、2 つのブロックからなるプレゼンテーションが作成されます。 RSA=(100101001)、(100001)=(M 1 =297、M 2 =33).

ソーステキストのブロックは順番に暗号化されます M 1 =297, M 2 =33:
y 1 =E k (M 1)=M 1 e ≡297 7 (mod527)=474.

ここでは、次の事実を利用しました。

297 7 =((297 2) 3)297≡(mod527)=(200 3 (mod527)297)(mod527)=474,
y 2 =E k (M 2)=M 2 e ≡33 7 (mod527)=407.

暗号文は、元の暗号文と同様に、2 つのブロックの形式で取得されます。 y 1 =474; y 2 =407.

デコード一連の動作のようです D k (y i)=(y i) d =(y i) 343 (mod 527), i=1.2.

べき乗の計算 d最初に指数を数値の累乗の合計として表すことによって実行する方が便利です。 2 、つまり: 343=256+64+16+4+2+1 .

この指数表現を使用する d=343、我々が得る：

474 2 ≡174(mod527)、
474 4≡237(mod527)、
474 8≡307(mod527)、
474 16 ≡443(mod527)、
474 32 ≡205(mod527)、
474 64 ≡392(mod527)、
474 128 ≡307(mod527)、
474 256 ≡443(mod527)、
そして最後に 474 343 (mod527)=(443∙392∙443∙237∙174∙474) (mod527)=297.

値も同様に計算されます 407 343 (mod527)=33.

復号化されたメッセージのリテラル表現に切り替えると、次のようになります。 RSA.

例を見た後、マニュアルでは RSA システムの堅牢性について説明しています。 RSA 暗号モジュール (番号) の選択には注意が必要であることが強調されています。 n) 各ネットワーク通信者に対応します。暗号化システムの選択された特性の要件を無視することは許されないことが示されています。残念ながら、これらの要件のうち、与えられた例で示されている違反は示されていません。

RSA暗号に対する攻撃

RSA 暗号に対する攻撃の例を見てみましょう。 A.P. の教科書「暗号の基礎」の 313 ～ 315 ページに記載されている例のデータを使用してみましょう。アルフェロフ、A.Yu。ズボフ、A.S. クズミン、A.V. チェレムシュキン、モスクワ。「ヘリオスARV」、2001年。

この例で選択されたシステムパラメータの失敗 (許容できないこと) は、ソーステキストのキーレス読み取りに対する攻撃を実行する計算によって簡単に示されます。このような攻撃の本質は次のとおりです。 RSA暗号の公開鍵が指定されています( e=7, n=527) と暗号文。この例では、暗号文は 2 つのブロックで表されます
y=(y 1 =474、y 2 =407).

各暗号化ブロックは個別に攻撃されます。最初に攻撃します。 y 1 =474復号化した後、別のブロックを攻撃します y 2 =407.

次に、暗号化を繰り返し、攻撃アルゴリズムの 2 つの連続するステップの結果を保存し、公開キーを使用することによって、一連の数値が形成されます。 はい、私, y 1 =y利用可能な暗号文。

暗号文攻撃アルゴリズムでは、次のステップ番号が決定されます。 j、そのために y i e j (mod n)=(y i e j–1 (mod n)) e (mod n)=y i, i>1。最後の関係から、累乗すると次のことがわかります。 e価値観 (y i e j–1 (mod n))初期暗号文が取得される y i = y 1.

しかし、これは、このステップで平文が暗号化されたことを意味します。画面上の計算機を使用した直接計算 (計算できるものはほとんどありません) によって、その値がわかります。 j、暗号化サイクルは値で終了します。 y1、そこからサイクルが始まりました。

最初のブロックへの攻撃 y 1 =474暗号文。
ステップ1: 474 7 (mod527)=382;
ステップ2: 382 7 (mod527)=423;
ステップ3: 423 7 (mod527)=297;
ステップ4: このステップでは、すでに見つかったソーステキストが暗号化されますが、攻撃者はソーステキストを知らないため、暗号化する必要があります。攻撃が完了した兆候は、最初の暗号文値 ( 474 ) と 4 番目の暗号化ステップの結果。これはまさに偶然の一致です。

297 7 (mod527)=474暗号文の最初の (最初の) ブロックを受信しました。最初のブロックへの攻撃は成功しました y 1 =474。ステップ 3 の前の結果は平文と同じです M 1 =297.

n=527 r=297モジュロ n=527。このように書かれています y i =у 1 =297。パワー残基の形成
(((297 7 (mod527)) 7 (mod527)) 7 (mod527)) 7 =297.

2ブロック目の攻撃 y 2 =407暗号文。
ステップ1: 407 7 (mod527)=16;
ステップ2: 16 7 (mod527)=101;
ステップ3: 101 7 (mod527)=33;
ステップ4: 33 7 (mod527)=407.

再び、3 番目のステップで、ソーステキストのブロックが取得されました ( M 2 =33) しかし、攻撃者はこれを知らず、次の (4 番目のステップ) を実行します。その結果は ( 407 ) は最初の暗号文と一致します y 2 =407.

本質的にモジュロ剰余の環内にある n=527短い控除処理サイクルが実装されました r=33モジュロ n=527。このように書かれています y i =y 2 =33.
パワー残基の形成 ((33 7 (mod527)) 7 (mod527)) 7 (mod527)=33.

攻撃結果（ソーステキスト） M 1 =297, M 2 =33) は、指定された暗号文を 3 回暗号化することによって取得されます。暗号文攻撃者にとってこれ以上の成功を想像するのは困難です。

モジュールとその他の暗号パラメータの選択についての説明を続けると、暗号モジュール ( n=527) 一部のソーステキストはまったく暗号化できません。この場合、公開キーの値の選択は大きな役割を果たしません。モジュラスを使用して選択した暗号で暗号化することが一般的に不可能なソーステキスト値があります n=527.

指定されたものはいずれも、数字で表されるソーステキストを暗号化できません
187 , 341 , 154 そして 373 .

例（一部のソーステキストの値を暗号化できない）

ソーステキストを 4 つのブロックで表すとします。 y=(y 1 =154、y 2 =187、y 3 =341、y 4 =373)。出展者 e暗号の公開キーは、オイラー関数と互いに素な任意の数にすることができます。 φ(n)=φ(527)=480。ただし、検討中のケースでは、公開鍵 e任意に設定できます。確かに、しましょう e=2、4、7、9、17、111それから：

154 2 (mod527)=1;
154 4 (mod527)=1;
154 7 (mod527)=154;
154 9 (mod527)=154;
154 17 (mod527)=154;
154 111 (mod527)=154;
187 2 (mod527)=187;
187 4 (mod527)=187;
187 7 (mod527)=187;
187 9 (mod527)=187;
187 17 (mod527)=187;
187 111 (mod527)=187;
341 2 (mod527)=341;
341 4 (mod527)=1;
341 7 (mod527)=341;
341 9 (mod527)=341;
341 17 (mod527)=341;
341 111 (mod527)=341;
373 2 (mod527)=1;
373 4 (mod527)=373;
373 7 (mod527)=373;
373 9 (mod527)=373;
373 17 (mod527)=373;
373 111 (mod527)=373.

考察した例から簡単な結論が得られます。実際、暗号化プロセスのパラメータの選択には非常に慎重に取り組む必要があり、そのようなパラメータの徹底的な予備分析を実行する必要があります。これを行う方法は別の問題であり、この作業の範囲内では考慮されません。

ついに、RSA 暗号システムの説明を開始する時期が来ました。それがどのように機能するかを説明することに加えて、その安全性について詳しく議論する必要があります。言い換えれば、RSA 暗号システムで暗号化されたメッセージを解読するのはなぜそれほど難しいのでしょうか?

§12.1。始まりと終わりについて

シングルユーザー RSA 暗号化システムを実装するには、2 つの異なる素数 p と q を選択し、その積を計算する必要があります。素数 p と q は秘密に保たれますが、数値は公開キーの一部になります。 § 12.5 では、キー素数を選択する方法と、この選択がシステムの信頼性にどのように関係するかについて詳しく説明します。

メッセージ (整数と見なすことができます) は、それを何らかのモジュロに累乗することによって暗号化されます。したがって、まず、メッセージのテキストをモジュロクラスのリストとして表現する方法を見つける必要があります。これは、実際にはまだ実現していません。暗号化プロセスですが、暗号化できるようにメッセージを準備するだけです。

わかりやすくするために、メッセージテキストには大文字で書かれた単語のみが含まれていると仮定します。したがって、メッセージは最終的には文字とスペースの連続になります。最初のステップは、メッセージの各文字を次の表から選択した数字に置き換えることです。

(スキャンを参照)

単語間のスペースは数字 99 に置き換えられます。この手順を実行すると、メッセージが長い場合には非常に大きな数字が得られます。ただし、これは私たちが目指している最終的な数値ではなく、単なるモジュロクラスのセットです。そして今、メッセージの数値表現をいくつかの部分に分割する必要があります。それぞれの部分は、通常、以下の自然数と呼ばれます。メッセージブロック。

たとえば、モットー「KNOW YOURSELF」を数値で表すと次のようになります。

単純なものを選択すれば積が得られるので、上で書き出したメッセージの数値表現は 23,393 個より小さいブロックに分割する必要がありますが、その分割の 1 つを提示しましょう。

もちろん、ブロックの選択は明確ではありませんが、完全に任意というわけでもありません。たとえば、段階での曖昧さを避けるため

復号化では、ゼロで始まるブロックを強調表示しないでください。

RSA 暗号化システムで暗号化されたメッセージを復号すると、一連のブロックが取得されます。次に、それらが結合されて、メッセージの数値表現が生成されます。そして、上の表に従って数字を文字に置き換えた後にのみ、元のメッセージを読むことが可能になります。

表内の各文字は 2 桁の番号でコード化されていることに注意してください。これは混乱を避けるために行われます。文字に 1 から順に番号を付けたとします。 A は 1、B は 2 などに対応します。この場合、ブロック 12 が 1 組の文字を表しているのか、それとも 1 つの文字 (アルファベットの 12 番目の文字) だけを表しているのかを確実に言うことはできません。もちろん、メッセージの数値表現には、文字と数字の間の 1 対 1 対応を使用できます。たとえば、メッセージのデジタル形式への変換がコンピュータによって自動的に実行される -encoding などです。

§12.2。暗号化と復号化

§ 12.1 の方法を使用して暗号化用に準備されたメッセージは、それぞれがより小さい数のブロックのシーケンスで構成されます。次に、各ブロックがどのように暗号化されるかを説明します。これを行うには、素数と自然数の積に等しい数値、可逆法が必要です。条件を満たす数値

既知の p と q から数値を簡単に計算できることを思い出してください。本当に、

このペアは、ここで説明する RSA 暗号システムの公開キー、またはエンコーディングキーと呼ばれます。メッセージブロック、つまり不等式を満たす整数を使用します。に対応する暗号化メッセージのブロックを表す記号を使用します。これは次の規則に従って計算されます。

各メッセージブロックは個別に暗号化されることに注意してください。したがって、暗号化されたメッセージは実際には個別の暗号化されたブロックで構成されます。さらに、メッセージを復号化できなくなるため、これらのブロックを 1 つの大きな数に結合することはできません。その理由はすぐに分かります。

最初の段落で検討し始めた例に戻りましょう。次のように修正しました。ここで数値を選択する必要があります。この数値は互いに素でなければならないことを思い出してください。23088 を割らない最小の素数は 5 に等しいです。§ 12.1 のメッセージの最初のブロックをエンコードするには、次のように設定します。シンボリック計算プログラム (忍耐力がある場合は電卓) を使用すると、必要な控除は 22,752 であることがわかります。したがって、暗号化されたメッセージは次の一連のブロックで表されます。 :

暗号化されたメッセージのブロックがどのようにデコードされるかを見てみましょう。復号化を開始するには、モジュロの逆元を知る必要があります。最後の要素は自然数であり、で表します。このペアは、秘密または RSA 暗号化システムの復号化キーと呼ばれます。 a が暗号化されたメッセージのブロックである場合、それに対応する復号化

操作の結果は次のようになります。

例に戻る前に、いくつかのコメントが必要です。まず、実際に秘密鍵が拡張ユークリッドアルゴリズムを使用して決定されることを知っていれば、計算は非常に簡単です。第二に、ブロックが元のメッセージである場合、同等であることを期待する権利があります。言い換えれば、暗号化されたメッセージのブロックを復号するとき、元のメッセージの対応するブロックを見つけたいと考えます。これが当てはまるという事実は、上記のアルゴリズムから直接得られるものではありませんが、次の段落ですべてを詳しく説明します。

最後に、序章と本書全体で議論したように、RSA 暗号システムを解読するには、メッセージを復号化する方法を知る必要があるため、因数分解する必要があります。ただし、システムの仕組みを詳細に説明すると、次のことが明らかです。後者の記述は完全に正確ではありません。暗号を読み取るには、要素自体に加えて、要素の逆剰余を知っていればよいため、システムをハッキングするには、既知の要素を使って計算するだけで十分です。この計算は数値の因数分解と同等であることがわかります。 § 12.4 で説明するように。

説明中の例では、拡張ユークリッドアルゴリズムを数値と 5 に適用して決定します。

(スキャンを参照)

したがって、5 モジュロの逆数は -9235 となり、

-9235 のモジュロに相当する最小の自然数したがって、暗号化されたメッセージのブロックをデコードするには、23,393 を法とする 13,853 乗する必要があります。この例では、最初のエンコードされたブロックは 22,752 です。数値 22 の減算の計算75213853 modulo 23,393 を計算すると、次の結果が得られます。このような小さな数値であっても、RSA 暗号システムを動作させるための要件は、ほとんどのポケット電卓の機能を超えていることに注意してください。

§12.3。なぜ効果があるのでしょうか?

前に述べたように、暗号化されたメッセージの各ブロックを復号した結果、元のメッセージの対応するブロックが復元された場合にのみ、上記の手順で暗号システムが機能します。公開鍵と秘密鍵を持つ RSA システムを扱っていると仮定しましょう。§ 12.2 の表記法を使用して、不等式を満たす任意の整数に対して恒等式が成立することを示す必要があります。

実際、それを証明するだけで十分です

実際、6 と非負の整数はどちらも小さいため、それらが等しい場合にのみ絶対値で比較できます。これは特に、メッセージの数値表現を小さなブロックに分割する理由を説明しています。

エンコードされたメッセージは個別に書き留める必要があります。そうしないと、推論が機能しません。

暗号化と復号化のレシピから、次のことがわかります。

これらの要素は係数が互いに逆であるため、次のような自然な k が存在します。また、条件によって数値は大きくなります。したがって、式 (3.1) の積の代わりに次の値が得られます。

ここでオイラーの定理を使ってみましょう。したがって、次のようになります。

そして、もし小さな間違いが紛れ込んでいなかったら、我々は完全に証明を手に入れていただろう。

私たちの推論をもう一度注意深く検討すると、オイラーの定理の条件を考慮していないことがわかります。実際、定理を適用する前に、数値が互いに素であることを確認する必要があり、これは、暗号化用のメッセージを準備するときに監視する必要があるようです。メッセージの数値表現をブロックに分割するときは、結果として得られるすべてのブロックが互いに素であることを確認する必要がありますが、幸いなことに、実際には比較はどのブロックに対しても行われるため、これは必要ありません。そして、誤りは証明したい結果にあるのではなく、証明自体にのみ存在します。正しいアプローチは、第 7 章のコルケルトの定理の証明で使用される推論に基づいています。

異なる素数があることを思い出してください。数値の剰余を定義しましょう

両方の素数の計算は似ていますが、この場合についてのみ詳しく説明します。

ある整数の場合、

ここでフェルマーの定理を適用したいと思いますが、分割しない場合にのみこれを行う権利があります。この要件が満たされるようにしましょう。それならわかります

フェルマーの定理をオイラーの定理に置き換えても、発生した問題は解決されませんでした。比較は一部のブロックに対してのみ有効であり、すべてのブロックに対しては有効ではありません。ただし、推論が機能しないブロックは、さらにで除算する必要があります。分割する場合は、両方とも 6 とモジュラスが 0 に匹敵するため、互いに匹敵します。したがって、証明された比較はこの場合にも有効です。したがって、比較はどの整数に対しても当てはまりますが、そうではないことに注意してください。確かに、数値は合成であるため、不等式は比較を意味しません。オイラーの定理を適用するときにも同様の推論を使用できたはずです。

したがって, 比較も同様に証明できることが証明されました. つまり, byとButの除算は両方とも異なる素数であるため, したがって, § 3.6の補題は, 任意の整数に対して得られるので, Aを除算することを保証します, つまり,段落の冒頭で述べたように、その両方の部分がよりも小さい非負の整数であるため、これは等しいことを証明するのに十分です。要約すると、次のように言えます。

前の段落のアルゴリズムは実用的な暗号システムにつながります。次に、それが信頼できるものであることを確認する必要があります。

§12.4。なぜシステムは信頼できるのでしょうか?

RSA は、さまざまな素数とモジュロ反転可能な自然数の積で構成される公開キーを使用した暗号化システムであることを思い出してください。わかっているのがペアだけである場合、RSA を解読するために何ができるかを注意深く見てみましょう

RSA で暗号化されたブロックを復号するには、モジュロ k の逆関数を知る必要があります。問題は、事実上、これを行う唯一の既知の方法が、拡張ユークリッドアルゴリズムを適用することに基づいていることです。ただし、§ 9.4 の公式を使用して計算するには、元のステートメントを裏付けるものを知る必要があります: RSA を破るには因数分解が必要です。また、分解の困難さは根本的なものであるため、RSA システムは安全です。

もちろん、いつか誰かが数値の因数に関する情報なしで計算するアルゴリズムを発見すると仮定することもできます。たとえば、誰かが数値を直接求める効果的な方法を思いついたとしたら何が起こるでしょうか。偽装された拡張方法より正確に言えば、

が既知であれば、実際に簡単に計算できます。

したがって、必要な素約数の合計がわかります。さらに遠く、

したがって、その違いもわかります。さて、単純な一次方程式系を解くことで、因数分解を簡単に見つけることができます。

これは、計算アルゴリズムが実際に数値を因数に分解することを意味するため、これは非常に簡単です。しかし、落ち着くにはまだ早いです。さらに空想を進めて、誰かが But So によって直接決定するアルゴリズムを発明したと仮定することもできます。それがわかっていれば、その倍数である数もわかっています。そのような情報も分解には十分であることがわかります。このような分解につながる確率的アルゴリズムは V で見つけることができます。演習 7 では、Rabin 暗号システムが解読される可能性があるという仮定の下で、同様の (ただしより単純な) 分解アルゴリズムを示します。からの確率アルゴリズムのアイデアが得られます。

ハッキングの可能性としては、モジュロ剰余によってブロックを直接復元するという最後の可能性が残っていますが、それが十分に大きければ、すべての可能な検索候補を体系的に検索することが唯一の方法です。これより良いものをまだ誰も思いついていません。 RSA 暗号システムの解読が因数分解に等しいと考えられる理由を説明する主な議論をリストしましたが、この主張の厳密な証明はまだありません。

§12.5。シンプルなものを選ぶ

前の説明から、RSA 暗号システムのセキュリティには正しい素数を選択することが重要であることがわかりますが、当然のことながら、素数が小さければ、システムは簡単にハッキングされます。実際、p と q が巨大であっても、その差が小さい場合でも、それらの積はフェルマーのアルゴリズムを使用して簡単に因数分解できます (§ 3.4 を参照)。

これは無駄話ではありません。 1995 年、アメリカの大学の 2 人の学生が RSA の公開バージョンを解読しました。これは、システムの素因数の選択が適切でなかったために可能になりました。

一方、RSA は長い間使用されており、素因数を慎重に選択すれば、システムは実際に非常に信頼できることがわかります。したがって、RSA 暗号化プログラマは、素数を適切に選択するための効果的な方法を必要としています。

整数が約 1 桁である公開キーを使用して RSA 暗号システムを作成するとします。まず、間に文字数が含まれる素数を選択しましょう。現在、個人使用に推奨されている鍵のサイズは 768 ビットです。長さは約 231 桁にする必要があります。このような数値を作成するには、たとえば 104 桁と 127 桁の 2 つの単純な数値が必要です。この方法で選択された素数は互いにかなり離れていることに注意してください。この状況でフェルマーのアルゴリズムを使用して分解することは非現実的です。さらに、数値を素因数に因数分解する際には、小さな因数だけでなく大きな因数も含まれていることを確認する必要があります。実際、そうでない場合、数値はいくつかのよく知られた分解アルゴリズムの格好の餌食になります (参照)。ここで、リストされた条件を満たす素数を見つける方法を考えてみましょう。

まず、素数の分布に関する単純な結果が 1 つ必要です。 xを超えない素数の数を表すものを思い出してみましょう。素数定理を考慮すると、大きな x の場合、数値は自然対数にほぼ等しいことがわかります。

に基づきます (§ 4.5 を参照)。これを非常に大きな正の数としましょう。間にある素数の個数を推定し、その差を推定したいのですが、素数定理と対数の性質により、その差はほぼ次のようになります。

それが非常に小さいと仮定すると、値が 0 に等しいと仮定して、差の妥当な推定値を得ることができます。したがって、間に囲まれた素数の数はほぼ等しいことになります。当然のことながら、x が大きいほど、推定値はより正確になります。このような推定値の詳細については、([D. 10]) を参照してください。

整数 x の近傍にある素数を選択する必要があるとします。明確にするために、 x は次数であると仮定し、 x からまでの区間で素数を探します。この区間に素数がいくつあるかを事前に知っておくと便利です。素数の数を推定するには、得られた結果を使用できます。この例では、値は非常に小さいオーダーです。したがって、上で書いた式を使用すると、次のような結論が得られます。