9

このコードは RSA キーの正しい値を与えてくれますか (他の機能が正しいと仮定して)? 特定のブロックが適切に復号化されていないため、プログラムを適切に復号化するのに問題があります

これはPythonにあります：

import random
def keygen(bits):
    p = q = 3
    while p == q:
        p = random.randint(2**(bits/2-2),2**(bits/2))
        q = random.randint(2**(bits/2-2),2**(bits/2))
        p += not(p&1)                             # changes the values from 
        q += not(q&1)                             # even to odd

        while MillerRabin(p) == False:            # checks for primality
            p -= 2
        while MillerRabin(q) == False:
            q -= 2
    n = p * q   
    tot = (p-1) * (q-1)
    e = tot
    while gcd(tot,e) != 1:
        e = random.randint(3,tot-1)
    d = getd(tot,e)                       # gets the multiplicative inverse
    while d<0:                            # i can probably replace this with mod
        d = d + tot
    return e,d,n

生成されたキーの 1 つのセット:

e = 3daf16a37799d3b2c951c9baab30ad2d

D = 16873c0dd2825b2e8e6c2c68da3a5e25

n = dc2a732d64b83816a99448a2c2077ced

4

2 に答える 2

16

数学的には、n、e、およびdは RSA ルールを尊重しているように見えます (つまり、nを割るすべての素数rについて、r 2はnを割らず、dはr-1を法とするeの逆数です)。ただし、RSA はそれ以上のものです。また、メッセージ (一連のバイト) をnを法とする整数に変換する方法とその逆の方法を管理する、いくつかのパディング規則も義務付けています。標準のパディング ( PKCS#1を参照) は、少なくとも 11 バイトがメッセージに追加されることを意味し、結果は依然としてnではない必要があります。. したがって、表示されているような 128 ビットのモジュラスでは、暗号化の最大入力メッセージ長は 5 バイトになります。

また、いくつかの RSA 実装は、セキュリティにとって小さすぎる RSA キーの使用を拒否します。128 ビットのモジュラスは数秒で因数分解できます (因数分解 Java アプレットについては、このページを参照してください。ECM と 2 次ふるいを使用して、あなたのような比較的小さな数を因数分解します)。因数分解の現在の記録は 768 ビットです。短期的なセキュリティには、少なくとも 1024 ビットのモジュラス長が推奨されます。典型的な RSA 実装は 512 ビット キーの使用を受け入れますが、多くはそれより短いものを拒否します。

別の考えられる問題は、pとqの相対的な順序にあります。PKCS#1 に示されている方程式は、p > qを前提としています (そうでない場合は、CRT 部分で実行する追加の減算があります)。p < qの場合、実装によっては間違っている可能性があります (Windows での Microsoft の RSA 標準実装で発生しました)。pとqを比較し、必要に応じて交換します。

まだ実用的なレベルでは、普及している RSA 実装の中には、公開指数eが 32 ビット整数内に収まらないような RSA キーを拒否するものがあります (これには、特に Internet Explorer が HTTPS Web に接続するために Windows で使用される RSA 実装が含まれます)。つまり、私が「広く普及した」と書いているのは、その意味です)。RSA セキュリティはeの選択による影響を受けないようです。そのため、公開鍵を使用する部分 (つまり、復号化ではなく暗号化、または署名検証ではなく) を高速化する小さなeを選択するのが通例です。署名生成)。e = 3はあなたができる最善のことですが、伝統的な理由 (主張された弱点に関する歴史的な誤解を含む) により、e=65537がよく使われます。eがp-1およびq-1に対して互いに素である必要があります。実際の実装では、最初にeを選択してから、 pとqが追加のルールに一致しない限り、世代内でループします。

セキュリティの観点から:

  • いくつかの素数が他よりも頻繁に選択されるという点で、生成プロセスは均一ではありません。特に、p+2も素数であるような素数pは、ほとんど選択されません。適切なモジュラス サイズがあれば、これは問題にはならないはずですが (特別な種類のバイアスが研究され、大きな問題ではないことが判明しました)、それでも広報活動は良くありません。

  • pとqの両方が世代範囲の下限に近い場合、 nは目標サイズより少し小さいかもしれません。これを回避する簡単な方法は、範囲をpとqの両方で[sqrt(2)*2 b-1 , 2 b ]に制限することです。

  • randomあなたが使用しているモジュールのセキュリティを保証することはできません. 暗号的に安全な乱数ジェネレーターは、簡単なことではありません。

  • 一般的に言えば、さまざまなサイド チャネル (タイミング、キャッシュ メモリの使用状況など) を通じて機密情報を漏らさずに RSA を適切に実装することは、簡単な作業ではありません。実際のセットアップでセキュリティが必要な場合は、実際に既存のパッケージを使用する必要があります。Python にはOpenSSLとインターフェースする方法があると思います。

于 2010-05-10T11:45:48.513 に答える
5

これは、実際のセキュリティを必要とするものではなく、楽しみと学習のために行っていると思います。

気になった点をいくつか挙げます（順不同）。

  1. n の長さが になるとは限りませんbits。と同じくらい短いかもしれませんbits - 4。

  2. random暗号的に安全な乱数ジェネレーターではありません。

  3. 公開指数 を 65537 に選択するのが一般的です (そして安全です) e。これは素数であるため、coprime-check を除数チェックに置き換えることができます。

  4. e設定による検索は少し奇妙ですe = tot(coprime-check は必ず失敗します)。

それ以外の場合は問題ありません。キーも問題なく使えるようです。正しく復号化されていないブロックの例はありますか? より小さいデータのみを暗号化できることに注意してくださいn。したがって、128 ビットのキー (例のように) を使用すると、すべての 128 ビットの数値を暗号化することはできません。

于 2010-05-10T08:25:03.010 に答える