8

私の理解では、最近の多くの公開鍵暗号化アルゴリズムは、鍵を構成するために大きな素数に依存しており、2つの素数の積を因数分解するのが難しいため、暗号化が破られにくくなっています。また、このような大きな数値を因数分解することが非常に難しい理由の1つは、使用される数値のサイズが非常に大きいため、32ビットと64ビットの非常に小さいCPUが一致しないため、CPUが数値を効率的に操作できないことを意味することも理解しています。 1024、2048、さらには4096ビット数の場合。これらの数値を処理するには、特殊なBig Integer数学ライブラリを使用する必要があります。また、CPUは一度に小さなチャンク(32ビットや64ビットなど)しか保持(および処理)できないため、これらのライブラリは本質的に低速です。

それで...

8ビットから16ビット、32ビットから64ビットのCPUにスケーリングしたのと同じように、2048ビットレジスタと巨大な算術回路を備えた高度に特殊化されたカスタムチップを構築できないのはなぜですか。このチップは、従来のCPUのほとんどの回路を必要とせず、結局のところ、仮想メモリ、マルチスレッド、I/Oなどを処理する必要はありません。保存された命令をサポートする汎用プロセッサである必要はありません。膨大な数に対して必要な算術計算を実行するための最低限のことです。

ICの設計についてはよくわかりませんが、論理ゲートのしくみ、半加算器、全加算器の作成方法、および多数の加算器をリンクしてマルチビット演算を行う方法について学んだことを覚えています。スケールアップするだけです。多くの。

さて、上記が機能しないという非常に正当な理由(または17)があることはかなり確信しています(そうでなければ、私よりも賢い多くの人々の1人がすでにそれを行っているため)が、その理由を知りたいと思っていますそれは動作しません。

(注:質問が理にかなっているかどうかはまだわかりませんので、この質問にはいくつかのやり直しが必要な場合があります)

4

6 に答える 6

3

これは、このスピードアップがO(n)でのみ行われるためですが、数値の因数分解の複雑さは、(ビット数に関して)O(2 ^ n)のようなものです。したがって、このユーバープロセッサを作成し、数値を1000倍速く因数分解した場合、数値を10ビット大きくするだけで、最初からやり直すことができます。

于 2009-07-30T12:39:14.600 に答える
3

@cubeが言ったこと、そして巨大な算術論理演算装置が論理信号が安定するのにより多くの時間がかかるという事実、そしてデジタル設計に他の複雑さを含める。デジタルロジックの設計には、ソフトウェアで当然のことと思われるものが含まれています。つまり、組み合わせロジックを介した信号は、伝播して安定するまでにわずかですがゼロ以外の時間がかかります。32x32マルチプライヤは慎重に設計する必要があります。1024x1024乗算器は、チップ内で大量の物理リソースを消費するだけでなく、32x32乗算器よりも低速になります(ただし、1024x1024乗算を実行するために必要なすべての部分積を計算する32x32乗算器よりも高速です)。さらに、ボトルネックとなるのは乗数だけではありません。メモリ経路があります。君'

ほぼ確実に、一連の「従来の」32ビットまたは64ビットシステムを並行して動作させる方が良いでしょう。ハードウェア設計の複雑さを伴わずにスピードアップを得ることができます。

編集:誰かがACMにアクセスできる場合(私はアクセスできません)、おそらくこのペーパーを見て、それが何を言っているかを確認してください。

于 2009-07-30T14:20:06.730 に答える
2

上に示したように、主な問題は、数値を因数分解するために通過しなければならない可能性の数です。そうは言っても、この種のことを行うための専用コンピュータは存在します。

この種の暗号化の本当の進歩は、素因数分解アルゴリズムの改善です。現在、最も速く知られている一般的なアルゴリズムは、一般的な数体ふるいです。

歴史的に、10年ごとに2倍の数を因数分解できるようです。その一部はより高速なハードウェアであり、その一部は単に数学と因数分解の実行方法をよりよく理解することです。

于 2009-07-30T13:16:52.793 に答える
2

あなたが説明したものとまったく同じアプローチの実現可能性についてコメントすることはできませんが、人々はFPGAを使用して非常に頻繁に同様のことを行います。

于 2009-07-30T16:34:30.953 に答える
2

Shamir&Tromerは、一種のグリッドコンピューティングを使用して、同様のアプローチを提案しています。 加算器とTWIRLを比較した回路図

この記事では、ふるい分けステップのカスタムハードウェア実装の新しい設計について説明します。これにより、[TWINKLEと比較したふるい分けのコスト]が約1,000万ドルに削減されます。TWIRLと呼ばれる新しいデバイスは、TWINKLEデバイスの拡張と見なすことができます。ただし、TWINKLEとは異なり、オプトエレクトロニクスコンポーネントがないため、シリコンウェーハ上で標準のVLSI技術を使用して製造できます。基本的な考え方は、入力の単一のコピーを使用して、多くのサブ問題を並行して解決することです。入力ストレージがコストを支配するため、並列化のオーバーヘッドを低く抑えると、結果として得られるスピードアップは基本的に無料で得られます。実際、主な課題は、入力のコンパクトなストレージを可能にしながら、この並列処理を効率的に実現することにあります。これに対処するには、無数の考慮事項が含まれます。

于 2016-05-03T17:59:27.710 に答える
0

超量子コンピューターを構築して、その上でショアのアルゴリズムを実行してみませんか?

「...十分な数の量子ビットを備えた量子コンピューターを構築する場合、Shorのアルゴリズムを使用して、広く使用されているRSAスキームなどの公開鍵暗号方式を破ることができます。RSAは、多数を因数分解するという仮定に基づいています。計算上実​​行不可能。知られている限り、この仮定は古典的な(非量子)コンピューターに有効です。多項式時間を因数分解できる古典的なアルゴリズムは知られていません。ただし、Shorのアルゴリズムは、因数分解が量子コンピューターで効率的であることを示しています。十分に大きな量子コンピューターはRSAを破ることができます...」-Wikipedia

于 2012-09-25T08:14:05.183 に答える