1

アセンブリを使用して PIC16 マイクロコントローラに RSA を実装しようとしています!
足し算、引き算、掛け算、べき乗剰余 (すべて符号なし) を実行できる数学ライブラリを作成しました。

しかし今、私は満たす "d" を見つける最後のステップで立ち往生しています:
d*e = 1 (mod phi(n))
少し複雑で符号付き操作が必要な拡張 Euclid アルゴリズムの実装を避けたいです。

オイラーの定理http://en.wikipedia.org/wiki/Modular_multiplicative_inverse#Using_Euler.27s_theorem
で計算してみ ましたが、 p と q が安全な素数でない限り、複雑なプロセスである phi(phi(n) を見つける必要があります。

私が残した唯一のオプションは、kを変更しながらd =（KN + 1）/ eをループして（KN + 1）mod e = 0にすることです。
したがって、私の質問は次のとおりです。この最後の式は、dを計算するための唯一の他のオプションですか?
（そうでない場合）他のオプションは何ですか？
K の極限は？

4

1 に答える 1

1

バイナリ拡張ユークリッド アルゴリズムを実装できます。このアルゴリズムは、Handbook of Applied Cryptography - Chapter 14.4.3 にあります。多倍精度の加算、減算、およびシフトのみが必要です。注: 14.64 では、アルゴリズムを最適化して乗法逆数を取得する方法について説明しています(d)(この場合)。

(e)のように、ハミング重みが小さい比較的小さな素数を選択するのが一般的(65537)です。以来gcd(65537, phi(n)) = 1、乗法逆数は常に存在します。

于 2014-03-29T00:42:44.867 に答える