トピックス

CRYPTREC ER-0001-2017

768ビット素数位数の有限体上の離散対数問題の状況と
DSA, DHの今後のパラメータ選択について

平成29年8月30日
CRYPTREC 暗号技術評価委員会

　有限体上の離散対数問題^[1]は、現在、CRYPTREC暗号リストの電子政府推奨暗号リスト^[2]に掲載されているDSA及びDHや、インターネットで使われているセキュア通信プロトコルTLS^[3]における鍵共有方式など、多くの暗号技術の安全性の根拠として利用されています。
CRYPTRECでは、以前より、(素数位数の)有限体上の離散対数問題における安全なパラメータサイズは、RSA合成数の素因数分解問題における安全なパラメータサイズと同等であると判断しています^[4]。
今般、位数が768ビット長の素数である有限体(以下、768ビットの素体という)における離散対数の計算結果を示した論文^[5]が、国際暗号学会(International Association for Cryptologic Research(IACR))が主催する国際会議 EUROCRYPT 2017^[6]で発表されました。この論文では、768ビットの素体上の離散対数の計算に要する計算コストが、2.2 GHz Xeon E5-2660プロセッサ換算で、約5300コア・年に相当するものと見積もられています。
768ビットのRSA合成数の素因数分解に要する計算コストは、CRYPTO2010で発表された論文^[7]では、約1700コア・年と見積もられているので、これらの計算コストの違いはたかだか数倍程度となります。これは上記の判断の妥当性の根拠の一つとみなせます。
このため、暗号技術評価委員会では、RSA1024に係る移行指針^{[2, 8]}と同様に、今後ともDSAやDHを利用する場合には、鍵長において、2048ビット以上の素数位数の有限体を用いることを推奨します。
暗号技術評価委員会では、今後も引続き状況の監視・調査を行い、CRYPTREC Webサイトなどを通じてお知らせしてまいります。ご意見・コメントなどの問い合わせがございましたら、下記までお願いいたします。

CRYPTREC事務局
E-mail:

1. 有限体の元であるgとyがy = g^x を満たすときxを求める問題を有限体上の離散対数問題といいます。現在までのところ、大きな位数(元の総数)である有限体上の離散対数を計算することは、一般的に難しいこととされています。
2. 電子政府における調達のために参照すべき暗号のリスト(CRYPTREC暗号リスト),
   https://www.cryptrec.go.jp/list.html
3. T. Dierks et al., “The Transport Layer Security (TLS) Protocol Version 1.2”, RFC5246,
   https://tools.ietf.org/html/rfc5246
4. CRYPTREC Report 2006,
   https://www.cryptrec.go.jp/report/cryptrec-rp-2000-2006.pdf
5. T. Kleinjung et al., “Computation of a 768-bit prime field discrete logarithm”,
   https://eprint.iacr.org/2017/067
6. https://eurocrypt2017.di.ens.fr/
7. T. Kleinjung et al., “Factorization of a 768-bit RSA modulus”,
   https://eprint.iacr.org/2010/006
8. 「政府機関の情報システムにおいて使用されている暗号アルゴリズムSHA-1及びRSA1024に係る移行指針」(平成20年4月22日 情報セキュリティ政策会議決定, 平成24年10月26日改定 情報セキュリティ対策推進会議決定),
   https://www.nisc.go.jp/pdf/policy/general/angou_ikoushishin.pdf
9. 暗号技術検討会2015年度報告書,
   https://www.cryptrec.go.jp/report/cryptrec-rp-1000-2015.pdf