私は高校生でRSAに関する論文を書いていますが、素数が非常に小さい例を示しています。システムがどのように機能するかは理解していますが、拡張ユークリッドアルゴリズムを使用して秘密鍵を計算することはできません。
これが私がこれまでにしたことです：
- 素数p=37とq=89を選び、N=3293を計算しました
- （p-1）（q-1）=3168を計算しました
- eと3168が互いに素になるように、数eを選択しました。私はこれを標準のユークリッドアルゴリズムでチェックしていますが、これは非常にうまく機能します。私のe=25
ここで、秘密鍵dを計算する必要があります。これは、ed = 1（mod 3168）を満たす必要があります。
拡張ユークリッドアルゴリズムを使用して、de + tN=1となるdを見つけます。-887•25+7•3168=1になります。私は7を捨てて、d=-887を取得します。ただし、メッセージを復号化しようとすると、これは機能しません。
私の本から、dは2281である必要があり、それは機能することがわかっていますが、どのようにしてその数に到達するのかわかりません。
誰か助けてもらえますか？私は過去4時間この問題を解決しようとしましたが、どこでも答えを探してきました。私は拡張ユークリッドアルゴリズムを手作業で行っていますが、結果が機能するので、私の計算は正しいはずです。
前もって感謝します、
マッド