NIST、RSAや楕円曲線暗号を2030年より後は非推奨と確定

RSAの鍵を3072ビットに延ばしても、2030年より後は2048ビットと同じ「非推奨」になる。アメリカ国立標準技術研究所（NIST）は2026年10月27日、報告書「耐量子暗号の標準への移行」（NIST IR 8547）の確定版を公開した。RSA、楕円曲線を使う署名のECDSAとEdDSA、鍵共有のディフィー・ヘルマンなど、量子計算機に破られうる公開鍵暗号を、2030年より後は「非推奨」、2035年より後はNISTの標準と指針の下で「使用不可」とする。著者は、NISTで耐量子暗号の標準化を率いるダスティン・ムーディ氏ら5人である。

2024年11月の草案では、2030年より後に非推奨とするのは112ビットの強さのもの（RSAなら2048ビットの鍵）だけだった。128ビット以上（RSAなら3072ビット以上）は、2035年までそのまま使える扱いだった。確定版はこの区別をなくした。非推奨は、危険を承知のうえでなら使ってよいという段階である。ムーディ氏はNISTの発表で、「ある方式がある日を境に連邦政府のシステムで使えなくなるのか、使えるが自己責任になるのか。それを知っておくことが、組織の計画に役立つ」と話している。

鍵を長くしても逃げ切れない理由

RSAの安全は、大きな数$N=pq$を素因数分解する難しさにかかっている。古典計算機が相手なら、鍵を長くすれば解読の手間は急に増える。NISTの鍵管理の指針SP 800-57では、RSAの鍵を2048ビットから3072ビットにすると、強さは112ビットから128ビットに上がる。解読の手間で言えば$2^{16}$倍、約6万5000倍である。ところが報告書は、RSAも楕円曲線も「暗号の解読に使える規模の量子計算機があれば、ショアのアルゴリズムで破られる」と書く。

ショアのアルゴリズムは、$N$と互いに素な数$a$を何乗すると初めて$N$で割って1余るか、という周期$r$を量子計算機で求め、そこから因数を取り出す。

$r$が偶数で$a^{r/2}\not\equiv -1(\mathrm{mod}N)$なら、$\gcd (a^{r/2}-1,N)$は1でも$N$でもない約数、つまり$p$か$q$になる。周期を求める手間は、掛け算を筆算のやり方で数えても、鍵の桁数の3乗ほどでしか増えない。桁数を1.5倍にしても$1.5^3\approx 3.4$倍で、古典計算機の6万5000倍とは桁が違う（当サイトの見積もり）。強さで分けて猶予を長くしても、稼げる時間はわずかだろう。

報告書によると、以前の指針SP 800-57は、112ビットの公開鍵暗号を2031年1月1日に使用不可とする見通しを示していた。確定版はこれに代えてすべてを2030年より後に非推奨とし、理由を「この期間に耐量子暗号へ移る必要があるため」とだけ書く。解読に使える量子計算機が今はまだ無いことも認めている。

今の通信が、のちに読まれる

まだ無い計算機のために、なぜ今から移るのか。報告書は「モスカの定理」を引いて説明する。データを秘密にしておく年数を$X$、移行を終えるまでの年数を$Y$、解読に使える量子計算機ができるまでの年数を$Z$とすると、

のとき、移行が間に合わない。いま暗号化して送ったデータを集めておき、量子計算機ができてから解く「今集めて、のちに解く」攻撃を防げないからだ。たとえば10年守りたいデータを、移行に10年かかるシステムで扱っていれば、量子計算機が20年以内にできた時点で秘密は守れない。報告書は、これまでの暗号の移行には10年以上かかり、今回はもっと複雑なので少なくとも同じくらいかかるとみている。

署名は、のちに解かれても過去の通信が読まれるわけではないので、この攻撃の対象にならない。それでも報告書は、署名の移行も急ぐべきだとする。関わる相手が多く、移行に長い時間がかかるからだ。

移る先のML-KEMと数論変換

移る先は、鍵共有がFIPS 203のML-KEM、署名がFIPS 204のML-DSAとFIPS 205のSLH-DSAで、3つとも2024年8月に標準になった。NISTはML-KEMの代替としてHQCも選び、その標準を作っている。ML-KEMの中心となる計算は、係数を3329で割った余りで扱う多項式の掛け算で、高速フーリエ変換と同じ形の数論変換で速くする。その仕組みは、$17^{128}\equiv -1(\mathrm{mod}3329)$を手がかりに掛け算の速さの限界の記事で書いた。

連邦政府の期限は2030年末

2035年は連邦政府全体の移行の目標で、もっと早い期限もある。大統領令14412と行政管理予算局の覚書M-26-15は、連邦政府の特に重要なシステムに、鍵共有は2030年12月31日までに、署名は2031年12月31日までに耐量子暗号へ移るよう求めている。報告書は、これまでの移行に10〜20年かかってきたことを挙げ、この期限には余裕がほとんど無いと指摘する。2030〜2035年の非推奨の期間は、危険の小さいシステムや、古い機器の制約があるシステムのための猶予で、この早い期限は変えない。従来の暗号と耐量子暗号を組み合わせるハイブリッド方式も認めている。NISTは今後、細かい日程を指針SP 800-131Aの改訂で決める。