自己的沙场:全同态加密研究分享 http://blog.sciencenet.cn/u/chzg99 不要对我说生命中无聊的事,不要对我说失败是命运的事。

博文

黎曼猜想是否会对密码学的安全产生影响 精选

已有 7530 次阅读 2018-9-23 10:34 |个人分类:信息安全|系统分类:科研笔记

  

最近由于黎曼猜想可能会被证明,网上充满了讨论,甚至波及到了区块链。有新闻说如果黎曼猜想被证实的话,将危及公钥密码学的安全。由于互联网上使用的都是公钥密码,所以互联网也都不安全了。

 

更具体的猜测是,由于黎曼猜想和素数有关,所以RSA密码体质将会被攻破。

          

以上猜测搞得人心惶惶,皆因大家的好奇心,说来也是好事。一个数学界的新闻能让大家如此关注。我也查了国外一些网站的说法。

 

 

由于我是搞密码学的,又涉足区块链界,所以有些群友不断在问我。为此我以我的理解及所查的资料,对以上说法进行正本清源。

 

1.       首先我说结论。

 

第一,黎曼猜想早在1859年就提出,而我们用的公钥密码是在70年代末提出的。所以,如果黎曼猜想会对破解RSA加密算法有什么帮助的话,一定会早有论文提出。然而,至今为止也没有看到有相关论文显示黎曼猜想会对破解RSA有什么直接效果。

 

第二,区块链上用的密码算法只有两个:哈希函数和数字签名。哈希函数和素数没有关系,所以和黎曼猜想没有关系。数字签名使用的是椭圆曲线上的方案,所以与大整数分解没有关系,从而和黎曼猜想也没有关系。

 

所以,黎曼猜想对公钥密码没有直接的任何威胁。对区块链的安全也没有任何影响。

 

为了让大家更好地理解上述结论,我们先来解释一下什么是黎曼猜想。

 

2.       什么是黎曼猜想

                                          

要说清黎曼猜想,首先得说素数。素数在自然数中是一种特别的数,它只能被1和自己整除。说白了,素数没有因子,就像一个人没有后代(比喻略显不恰当)。素数的这种孤零零的特性,使得它是整个自然数的“基石”。因为它不能再被分解了,所以只能去构造其他数。

 

因此有个结论,每个自然数都可以唯一地分解成有限个素数的乘积。而且素数的个数是无限的。

 

素数如此特别,数学家们试图搞清楚如何判断一个数是素数。给你一个小的数,例如7,你很容易判断它是素数。但是当给你一个很大的数字时,判断一个数是否为素数,是需要方法的。由此产生了素数判定的算法。

 

为了更好地理解素数,数学家们在 19 世纪便不再尝试预测素数的精确位置,转而将素数的现象视为一个整体。这种分析的方法就是黎曼所擅长的,他著名的猜想也由此得出。

 

为了理解素数是如何分布的,高斯给出了一个素数计数函数 π(x) ,它能够给出某个数之前的素数的数量(即有多少个素数)。

 

随后,高斯(和勒让德独立地)提出了素数定理当x增长到无穷大时,素数计数函数 π(x) 会近似于 x/ln(x) 函数。这意味着前x个整数中连续素数之间的平均间隙约为 ln(x)。换句话说可以用x/ln(x)近似π(x)。

 

然后又出现了对数积分函数 Li(x),数学家发现 Li(x)能够比x/ln(x)更好的近似π(x)。说明 Li(x) 能够更好的刻画素数的个数。

 

然而,素数定理所预测的分布规律与实际仍然有所偏差,而且时大时小。这一切引起了黎曼的注意。

 

 

1859年,年仅33岁的黎曼发表了论文《论小于已知数的素数个数》。在该文章中,黎曼定义了一个函数:黎曼 zeta 函数。在论文中黎曼给出了一个推测:黎曼 zeta 函数的所有非平凡零点可能都全部位于实部等于1/2的直线上。

 

具体内容各位可以忽略。那么黎曼 zeta 函数的非平凡零点有什么用呢?

 

黎曼用 Li(x)以及zeta 函数的非平凡零点,给出了自己的素数定理,即更准确地估计数字 x 以内有多少个素数。

 

这一精确的刻画素数个数的定理,让黎曼大放光彩。上述公式中的第二项,x ρ ρ就是黎曼 zeta 函数非平凡零点。

 

这就是黎曼 zeta 函数非平凡零点的意所在!

 

 

到此为止,我们说了黎曼猜想是什么?

 

简而言之,就是给出了数字 x 以内更精确的素数个数的公式。

 

 

 

3.       RSA基于的困难问题

 

RSA所基于的困难问题是“大整数分解困难问题”。即给你一个大的整数,对其分解为素数之积是困难的。这是RSA加密算法的安全性基础。

 

目前对大整数分解用的方法主要是数域筛法,但是这些方法都不能有效的分解大整数。

 

黎曼猜想是宏观上对素数的分布有个判断,它不能直接求素数,也不能对一个整数进行素数分解。目前根据文献,黎曼猜想对于生成素数,例如RSA中的密钥生成算法,是有帮助的。但是对于整数分解算法并没有直接的提升。所以不会对RSA加密体质有任何影响。

 

大家一定要区分素数检测整数分解是两回事。很多人都认为是一回事,这是产生错误的根源。

 

对于黎曼猜想的证明,大家更多的认为可能会对数域的结构有个更好的认知。从某些方面,可能会对密码学有所启示。

 

 

文章首发在微信公众号:btc201800

weixin.qq.com/r/GC8UDDj (二维码自动识别)

 

 

 

 

 

 




http://blog.sciencenet.cn/blog-411071-1136505.html

上一篇:最清晰的比特币白皮书解析-激励

10 赵克勤 文克玲 陈新 武夷山 黄永义 王林平 魏武 刘浔江 康建 李红雨

该博文允许注册用户评论 请点击登录 评论 (6 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备14006957 )

GMT+8, 2018-10-17 20:09

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部