RSA：拡張ユークリッドアルゴリズムを使った秘密鍵計算

Question

私は高校生でRSAに関する論文を書いています。私はいくつかの非常に小さな素数を使っています。私はシステムがどのように動作するのか理解していますが、私の人生では、拡張ユークリッドアルゴリズムを使って秘密鍵を計算することはできません。ここで

は、私がこれまで行っているものです：

• 私は素数pを選択している= 37とq = 89と計算をN = 3293
• 私が計算した（P-1）（qは-1）= 3168
• eと3168が互いに素であるようにeを選択しました。私はこれを標準的なユークリッドアルゴリズムでチェックしています。これはうまくいきます。私のE = 25今

私はちょうどそのようなことをDを見つけるために、拡張ユークリッドアルゴリズムを使用して、ED = 1（MOD 3168）

を満足させなければならない秘密鍵dを計算する必要が+ tNの= 1デ私は-887・25 + 7・3168 = 1を得ます。私は7番を投げてd = -887にする。しかし、メッセージを解読しようとすると、これは機能しません。

私は自分の本からdが2281でなければならないことを知っていますが、それはうまくいきますが、その数字にどのように到達するのか分かりません。

誰でも手助けできますか？私は過去4時間この問題を解決しようとしましたが、どこでも答えを探しました。私は手で拡張ユークリッドアルゴリズムをやっていますが、結果は正しく計算されているはずです。事前に

おかげで、

マッズ

Answer 1

は、あなたが自分自身をキックしようとしているので、近いです。

3168-887 = 2281。

具体的には、mod xをお持ちの場合、Aは0<=a<xを満たさなければなりません。そうでない場合は、この範囲内になるまでxを必要に応じて追加または減算します。これはモジュラー算術と呼ばれます。

線形合同および数論を読みたい場合があります。これらの話題は、イギリスの学位レベルの数学（私はあなたが推測する大学と呼んでいます）ですので、ちょっと変わっていると心配しないでください。線形合同は、単に-887 mod 3168と2281 mod 3168が、同じクラスの一部であるため、実際には同じものであると言います。これは、必要な範囲で2281 mod 3168となるクラスです。 2281+3168 mod 3168もそのクラスに含まれます。

楽しくお楽しみください！

P.S. PARI/GPは、理論家が計算に使用するユーティリティー数です。一見の価値があるかもしれません。