黎曼猜想是否会对密码学的安全产生影响区块链

王林柯 2018-09-24 10:12
分享到:
导读

由于黎曼猜想和素数有关,也不能对一个整数进行素数分解,黎曼猜想是宏观上对素数的分布有个判断。

最近由于黎曼猜想可能被证明,网上充满了讨论,甚至波及到了区块链。有新闻说如果黎曼猜想被证实的话,将危及公钥密码学的安全。所以今天谈谈我对这件事的看法。

由于互联网上使用的都是公钥密码,所以互联网也都不安全了。更具体的猜测是,由于黎曼猜想和素数有关,所以RSA密码体质将会被攻破。 

1.jpg

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

2.jpg

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

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以内更精确的素数个数的公式。

3. RSA基于的困难问题

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

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

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

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

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

素数 黎曼 猜想 密码 函数
分享到:

1.TMT观察网遵循行业规范,任何转载的稿件都会明确标注作者和来源;
2.TMT观察网的原创文章,请转载时务必注明文章作者和"来源:TMT观察网",不尊重原创的行为TMT观察网或将追究责任;
3.作者投稿可能会经TMT观察网编辑修改或补充。