sonickun.logスマートフォン用の表示で見るsonickun.log備忘録この広告は、90日以上更新していないブログに表示しています。本稿では楕円曲線暗号の安全性の根拠とされている離散対数問題について、それを高速に解く方法をまとめる。sonickun.log」という記事を書いたが、この記事で言う離散対数問題(主にElGamal暗号で利用される)は、有限体上の離散対数問題と呼ばれるのに対し、今回扱うのは楕円曲線上の離散対数問題というものである。ちなみにこれまで楕円曲線上を離散対数問題を題材としたCTF問題に巡り合ったことはほとんどない(あったら教えてください)。algorithmを紹介し、実際に実装してみる。楕円曲線の基礎知識や楕円曲線暗号のアルゴリズムの説明については省略する。厳密な定義や証明は省き、イメージとして理解することを目指す。(スカラー倍算)を計算するのは容易である。求めよ、という問題を楕円曲線上の離散対数問題と呼ぶ。巡回群の位数が巨大な素数となるような楕円曲線とベースポイントを選んだ場合、この離散対数問題を解くことは非常に困難であることが知られている。その理由の一つには、スカラー倍算の結果が離散的に変化するという性質が挙げられている。回たどることは簡単だが、始点と終点を与えられたときに、始点から何回たどって終点にたどり着いたかを求めることは困難である、ということである。楕円曲線上の離散対数問題は、楕円曲線暗号の安全性の根拠とされている。ちなみに、1024ビット鍵長のRSA暗号やElGamal暗号と同等の安全性を持つためには、楕円曲線暗号では160ビットの鍵長で十分であるといわれている。そのため、暗号化・復号や署名認証用のハードウェア規模やソフトウェアの計算速度は、楕円曲線暗号のほうが数倍も優れており、たとえばICカードなど、コンパクト化・軽量化が要求される場合には、楕円曲線暗号が活用されている。giant-stepと根本的な考え方は同じである。)として、以下の式を得る。求めるよりも少ない試行数で離散対数問題が解ける。回程度のスカラー倍算が必要になる。以上をSageMathで実装したものが以下である。