楕円暗号

ウィキペディア

楕円曲線暗号

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/03/17 23:54 UTC 版)

楕円曲線暗号（だえんきょくせんあんごう、Elliptic Curve Cryptography、ECC）とは、楕円曲線上の離散対数問題 (EC-DLP) の困難性を安全性の根拠とする暗号。1985年頃にビクター・S・ミラー（英語版）とニール・コブリッツ（英語版）が各々発明した。

具体的な暗号方式の名前ではなく、楕円曲線を利用した暗号方式の総称である。DSAを楕円曲線上で定義した楕円曲線DSA (ECDSA)、ディフィー・ヘルマン鍵共有（DH鍵共有）を楕円化した楕円曲線ディフィー・ヘルマン鍵共有 (ECDH) などがある。公開鍵暗号が多い。

EC-DLPを解く準指数関数時間アルゴリズムがまだ見つかっていないため、それが見つかるまでの間は、RSA暗号などと比べて、同レベルの安全性をより短い鍵で実現でき、処理速度も速いことをメリットとして、ポストRSA暗号として注目されている。ただしP=NPが成立した場合、EC-DLPを多項式時間で解くアルゴリズムが存在するということになり、ECCの安全性は崩壊する（公開鍵暗号自体が崩壊）。また、送信者が暗号化時に適当な乱数（公開鍵とは違うモノ）を使うので鍵が同じでも平文と暗号文の関係が1対1でない点にも注意（ElGamal暗号でも同様）。

一部の楕円曲線には、DLPを解く多項式時間アルゴリズムが見つかっているため、注意が必要である。

歴史

暗号理論に楕円曲線を利用しようというアイディアは、1985年にニール・コブリッツ^[1] と ビクター・S・ミラー^[2] によって独立に提案された。楕円曲線暗号は、2004～2005年ごろから広く使用されるようになっている。

理論

楕円曲線の例： secp256k1(後述)で規定されている ${\displaystyle \mathbb {R} ^{2}}$

離散的楕円曲線の例： 有限体 F₆₁ 上の楕円曲線 y² = x³ − x

${\displaystyle \mathbb {Z} _{p}}$