cryptography - モジュラー算術

Question

私は暗号化とモジュラー演算に不慣れです。だから、それはばかげた質問だと確信していますが、私はそれを助けることはできません。

     pow（a、q）= 1（mod p）からaを計算するにはどうすればよいですか？ ここで、pとqは既知です。「1（mod p）」の部分がありません。1になりますね。もしそうなら、「mod p」とは何ですか？ これは      pow（a、-q）（mod p）= 1と同じですか？

Answer 1

（mod p）の部分は、右側ではなく等号を指します。これは、モジュロp、pow（a、q）、および1が等しいことを示します。たとえば、「モジュロ10、246126、および7868726は等しい」（および、両方とも6モジュロ10に等しい）：2つの数値xとyは、pで除算したときの余りが同じである場合、または同等に、pを法として等しい。 pはxyを除算します。

プログラミングの観点から来ているように見えるので、別の言い方をすれば、pow（a、q）％p = 1です。ここで、「％」は、いくつかの言語で実装されている「剰余」演算子です（p> 1と仮定）。 ）。

ウィキペディアのモジュラー算術に関する記事、または基本的な数論の本（または、モジュラー算術を導入する可能性が高いため、暗号化の本）を読む必要があります。

あなたの他の質問に答えるために：一般的にそのような（私の知る限り）を見つけるための一般的な公式はありません。pが素数であると仮定し、フェルマーの小定理を使用してqをp-1を法として減らすと仮定し、qがp-1を除算する（またはそのようなaが存在しない）と仮定すると、pの原始根をとることによってそのようなaを生成できます。累乗（p-1）/q。[そして、より一般的には、pが素数でない場合、φ（p）を法としてqを減らすことができ、φ（p）を除算し、原始根（たとえばr）mod pを知っていると仮定すると、rを次の累乗にすることができます。 φ（p）/ q、ここでφはトーティエント関数です-これはオイラーの定理から来ています。]

Answer 2

これが公開鍵暗号化の基礎であるため、まったくばかげたことではありません。これに関する優れた議論はhttp://home.scarlet.be/~ping1339/congr.htm#The-equation-a%3Csup%3Exで見つけることができます。

PKIは、大きくて互いに素pなものを選択することで機能します。1つ（たとえば）が秘密鍵になり、もう1つ（）が公開鍵になります。攻撃者が（暗号化されたメッセージ）と（公開鍵）を推測すると、暗号化は「破られ」ます。qpqpaqq

だから、あなたの質問に答えるために：

aq= 1 modp

これaqは、で割ったときに1の余りを残す数であることを意味しpます。商の整数部分は気にしないので、次のように書くことができます。

aq/ p= n+ 1 /p

の任意の整数値n。方程式の両辺にを掛けると、次のようになりpます。

aq= np+ 1

私たちのために解決するa：

a=（np+1）^{1 /q}

最後のステップはn、の元の値を生成するの値を見つけることです a。試行錯誤以外にこれを行う方法はわかりません。これは、暗号化を破る「ブルートフォース」の試みに相当します。