公钥密码安全基础困难问题研究

谷大武

上海交通大学电子信息与电气工程学院

教授

顾海华

上海交通大学电子信息与电气工程学院

博士后

1　概要描述

1.1　公钥密码安全基础困难问题

目前，大部分公钥密码的安全性是基于数论中的计算困难问题。RSA密码、椭圆曲线密码（ECC）是最为广泛应用的公钥密码。

RSA密码的安全基础是大整数分解问题：给定整数N，且已知它是两个素数的乘积，求这两个素数。ECC密码的安全基础是椭圆曲线离散对数问题（ECDLP）： 给定椭圆曲线上的两个点P和Q，求整数k，使得Q = kP。

1.2　公钥密码安全基础困难问题的重要性（见图1）

公钥密码已经在国防、金融、通信、电力等行业广泛应用。密码是信息安全的核心，如果底层的困难问题被求解，上层的信息安全就不复存在。为了使我国的信息安全自主可控，切实把握RSA、ECC等密码的安全性，及时、准确地掌握大整数分解、离散对数问题的研究进展就显得格外重要。

图1　安全基础困难问题的重要性

2　应用前景

为了鼓励深入研究整数分解问题和ECDLP问题，RSA公司和Certicom公司分别向全球发布了RSA悬赏列表和ECC悬赏列表。2004年，ECC悬赏列表中109比特的ECDLP被求解，当时共有2 600人通过互联网参与了计算，共耗时17个月；2010年，RSA悬赏列表中768比特的RSA数被分解，分解过程中使用了几百台计算机，共计3 404个核，花了大约2.5年完成，换算成一台计算机大约2 000年。这两张列表中更大规模的困难问题，到目前为止还没有被求解出来。

2015年，我国“天河二号”超级计算机，以每秒3.39亿亿次的浮点运算速度，成为全球最快的超级计算机。“天河二号”有16 000个节点，每节点配备两颗Xeon E5系列12核心的中央处理器、三个Xeon Phi 57核心的协处理器，计算核心总数达312万。

随着新材料的不断涌现，电子元器件的性能越来越高，超级计算机的运算速度也越来越快。所以，目前看似安全的计算困难问题也可能将被求解。预计1 024比特的RSA数将在未来5到10年内被分解；预计将在未来15到20年内将求解256比特ECDLP。

图2　超级计算机性能发展时间表^[1]

【注释】

[1]http://www.top500.org/statistics/perfdevel/.