DSAで鍵長が二ついる理由 p を素数として、mod p の整数乗法群 G を考える。任意の g, y ∈ G が与えられて、y ≡ g ^ x mod p となる整数 x を求めるのは離散対数問題(DLP)だが、署名アルゴリズムのDSAにおける公開鍵と秘密鍵の関係は、ほとんどこの (y, g, p) と x の関係だと言える。つまり、DLPが現実的には解けないというのがDSAの安全性が破られない根拠になっている。 さて、今ほとんどと言ったのは、DSAの公開鍵における g は確かに g ∈ G なのだが、任意の g ∈ G というわけではなく、g として位数が最大の位数である p - 1 より…