6

これは私が学校を通してやっている課題のためです。秘密鍵の生成に問題があります。私の主な問題は、方程式同士の関係を理解することです。すべてをセットアップするには、次のものが必要です。

p = 61
q = 53
n = p * q (which equals 3233)

ここから n ( phi(n)) の totient が得られ、これは 3120 に等しいので、素数 e を選択できます。ここで、1 < e < 3120

e = 17

十分に簡単です。

私の課題では、 が認識されていますがd = 2753、この値を任意に生成できるようにする必要があります。

今、ここが私が困っているところです。私は理解するためにウィキペディアを熟読してきましたが、どこかで何かが接続されていません。私たちの私的指数であるの剰余乗法逆数を見つける必要があることはわかっています。e (mod phi(n))d

ウィキペディアを読むと、拡張ユークリッド アルゴリズムを使用するために必要な mmi を見つけるように指示されます。次のようにPythonでアルゴリズムを実装しました：

def egcd(a, b):
    x, lastX = 0, 1
    y, lastY = 1, 0
    while (b != 0):
        q = a // b
        a, b = b, a % b
        x, lastX = lastX - q * x, x
        y, lastY = lastY - q * y, y
    return (lastX, lastY)

これは私が迷っているところです。私の理解では、式ax + bx = gcd(a, b) = 1は同じe*x + phi(n)*y = gcd(e, phi(n)) = 1です。を呼び出して、x と yegcd(e, phi(n))を取得します。[-367, 2]

ここから先は正直、どこに行けばいいのかわかりません。この同様の質問を読んだことがありますが、いくつかの置換が行われていることがわかりますが、それらの数が得た答えや最初に使用した値にどのように関連するのかわかりません。誰かがここから何をする必要があるかを実用的に説明できますか? (実用的に言うと、実際のコードがないことを意味します。疑似コードは問題ありませんが、実際のコードを取得した場合、割り当てられた盗作なしでは学ぶことができません。これは大きな問題です)。

いつものように、どんな助けも本当に感謝しています。みんな、ありがとう！

(そして、はい、私はこれらを見てきました: RSA: 拡張ユークリッド アルゴリズムを使用した秘密鍵の計算とRSA暗号化では、p、q、e、および c を指定して d を見つけるにはどうすればよいですか? )

4

2 に答える 2

7

あなたが持っている拡張ユークリッド アルゴリズムの実装は、秘密鍵に対して負の数を生成しているため、完全ではありません。代わりに次のコードを使用してください。

https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm

あなたの例では、秘密鍵 d は 2753 です。

p=61
q=53
n = 3233
phi(n)=3120
e=17
d=modinv(17,3120)=2753

やってみて：

message m m=65


encryption: m^e mod n = c    (65**17) % 3120 =  65
decryption: c^d mod n = m      (65**2753) % 3120 =   65

そのすべてがここで説明されています：

http://southernpacificreview.com/2014/01/06/rsa-key-generation-example/

于 2014-01-06T01:03:40.333 に答える