p$を追加のパラメータとして秘密鍵に加えてある場合がある。q$の2つの素数でないといけないわけではない。RSAが通常のRSAと異なる点は、どのように$\phi(n)$を計算するかと復号処理だろう。前者についてはEulerのTotient関数について見てもらうとして、今回は復号部分について注目したい。いっても複雑なことはしない。先の系より剰余類を小さな剰余類の直積と見ることによってRSA-CRTの要領で平文を計算し、中国人剰余定理によって平文を復元するだけだ。Attackとは、任意の合成数位数の巡回群での離散対数問題を効率よく解くアルゴリズムである。アルゴリズムは以下のように与えられる。$\gamma$が判明しているとする。\gamma^{\phi(n)/p_i}$を考える。$\Gamma_i$は位数$p_i$を持つことに注意する。p_i$なる$x_i$を求める。Giant-Step法等適当なアルゴリズムで良い。p_i$が成り立っている。このため、中国人剰余定理を用いて$x$を求めることが出来る。今回は乗法巡回群として話を進めたが、これは任意の巡回群に適用可能である。有限体や楕円曲線の群でも適用できる。秘密鍵からの素因数分解RSAにはいくつもの攻撃手法が存在する。月別アーカイブはてなブログをはじめよう!elliptic-shihoさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。