楕円曲線暗号解読におけるDynamic DNSを用いた解読成功判定

摘要

楕円曲線暗号は今日広く用いられている暗号方式である．楕円曲線暗号の効率的な解読方法としてPollard のRho 法がある．この方法では与えられた楕円曲線上の有理点を次々に生成し，これまでに生成したものと同じ有理点が発見された場合に解読に成功したと判定するため，生成する膨大な有理点を記憶するためには膨大な記憶領域を必要とする．しかし，1 台の計算機で利用可能な記憶領域には限界があるため，生成した有理点は分散して記憶する必要がある．そこで我々はDNSを一種の大規模分散データベースとして使用し，Dynamic DNS機能を用いて有理点を登録する方法を用いた．本稿ではその方法や性能について述べる．