安企神电脑监控软件 在线试用
扫码咨询客服
安企神电脑监控软件、局域网监控软件
首页
功能介绍
产品简介
下载中心
帮助中心
客户列表
关于安企神

秀尔算法“青出于蓝而胜于蓝”

更新时间:2022-10-28 15:46:58


本文简介:此前我们一直介绍了很多RSA算法、DES算法和MD5算法,但是如今又有后起之秀了,它就是秀尔算法。RSA加密曾被视为最可靠的加密算法,直到秀尔算法出现,打破了RSA的不灭神话。RSA加密 VS 秀尔算法作为RSA加密技术的终结者——“太多运算,无法读取”的秀尔算法(Shor’s algorithm)不是通过暴力破解的方式找到最终密码的,而是利用量子计算的并行性,可以快速分解出公约数,从而打破了RS

秀尔算法“青出于蓝而胜于蓝”

此前我们一直介绍了很多RSA算法、DES算法和MD5算法,但是如今又有后起之秀了,它就是秀尔算法。

RSA加密曾被视为最可靠的加密算法,直到秀尔算法出现,打破了RSA的不灭神话。

wKioL1XUQeHSmokYAAHH1qUp4IY131

RSA加密 VS 秀尔算法

作为RSA加密技术的终结者——“太多运算,无法读取”的秀尔算法(Shor’s algorithm)不是通过暴力破解的方式找到最终密码的,而是利用量子计算的并行性,可以快速分解出公约数,从而打破了RSA算法的基础(即假设我们不能很有效的分解一个已知的整数)。同时,秀尔算法展示了因数分解这问题在量子计算机上可以很有效率的解决,所以一个足够大的量子计算机可以破解RSA。

RSA加密“曾经”之所以强大,是因为它对极大整数做因数分解的难度决定了RSA算法的可靠性。将两个质数相乘是件很容易的事情,但要找到一个庞大数字的质因子却非常困难。这便是大量现代科技的依靠之处,RSA加密就是凭借其简洁性迅速风靡。

然而,有一种技术可以让RSA加密无用武之地。秀尔算法可以破解RSA,但是怎样才能让它真正见效呢?

我们这里并非建议你同时尝试所有可能的质因子。

而是使用(相对)简洁的语句:

如果我们快速找到下面这个周期函数的周期,

f(x) = m^x (mod N)

我们便可以破解RSA加密。

秀尔五步走

那么,秀尔算法究竟是怎样工作的呢?在秀尔五步法中,只有一步需要是需要用到量子计算机的,其他的步骤则都可以采用传统方法解决。

第一步:

使用传统最大公约数分解(gcd)算法,也就是辗转相除法。N是你需要尝试的因子,m则是一个小于N的随机正整数。

如果gcd(m,N)=1,则继续。一旦你使用gcd找到一个因子,你便能获得一个非凡因子,然后结束。

第二步:

找到周期 P

m mod N, m^2 mod N, m^3 mod N

这是使用量子计算的一步。

第三步:

如果周期P是奇数,回到第一步,选择另一个随机整数。如果不是,继续下一步。

第四步:

检验

秀尔算法:破解RSA加密的“不灭神话”

如果成立,则继续第五步;反之,回到第一步。

第五步:

秀尔算法:破解RSA加密的“不灭神话”

解得一个非凡素因数N的值,然后你便能破解RSA加密了。

第二步是怎样实现的?

然而,量子计算机是如何找到函数周期的?这又为什么如此重要?

我们来看一下周期 P :

m mod N, m^2 mod N, m^3 mod N

(由于这是一个指数函数,我们可以将一个复杂的质数转换成双曲正弦、余弦然后得到周期)

这个发现周期的过程需要依赖量子计算机同时计算许多状态的能力,也就是状态的“叠加”,因此我们能找到方程的周期。

我们需要这么做:

1、应用Hadamard gate来创建一个量子叠加态

2、量子转换使方程生效

3、执行量子傅立叶变换

与传统情况类似,在这些转化之后,一个测量值将会产生一个近似方程周期的值(你可以获得“波峰”,就像傅立叶变换中的,而准确性会更高一点)。使用量子傅立叶变换,我们能够解决排序和因数问题,这二者相同。量子傅立叶变换可以让一台量子计算机进行相位估计(酉算子特征值的近似值)。

当你完成量子部分(第二步)的时候,你可以检查一下周期的有效性,然后使用另一个传统的最大公约数算法得到密钥的质因素。

有趣的是,由于这项技术并不是在于找到所有潜在质因数,而是找到潜在周期,你就不必尝试很多随机数直到找到一个成功的质因数N。如果P是奇数,那你不得不回到第一步,这里

秀尔算法:破解RSA加密的“不灭神话”

K是一个不同于N的质因素。因此,即使你加倍密钥长度(N),寻找质因数也不会出现放缓的情况。RSA是不安全的,同样加倍密钥长度也不能帮你抵御量子计算的汹涌来袭,而保障安全。

“破解RSA-2048(2048-bit)的密钥可能需要耗费传统电脑10亿年的时间,而量子计算机只需要100秒就可以完成。”

——Dr. Krysta Svore, 微软研究院

量子傅立叶变换被用于建立量子线路,使得秀尔算法的物理实现成了量子计算机最为轻松的任务之一。

量子傅立叶变换:青出于蓝

秀尔算法的核心是发现顺序,这样便可以减少阿贝尔的隐子群问题,使用量子傅立叶变换便可以解决。——NIST 量子世界

量子傅立叶变换是许多量子算法的关键所在。它并不加速寻找传统傅立叶转变,但是能够在一个量子振幅内执行一个傅立叶变换。在一台量子计算机上可以指数增长般快速处理量子傅立叶变换。虽然超过了直接映射经典傅立叶变换的范畴,量子计算机也可以做其他的事。例如,解决隐子群问题(也就是解决离散对数问题),或是计数问题(解决了这个问题就可以解决现代密码学中很多其他形式的密码)。更重要的是,量子傅立叶变换可以应用到机器学习、化学、材料科学或者模拟量子系统。

秀尔算法中只有一个步骤是需要在量子计算机上完成的,其他的都可以在普通的超级计算机上完成。量子计算机运行完子程序后就会将结果返回给超级计算机让它继续完成计算过程。量子计算机可能永远不会是单独存在的,而是一直和超级计算机配合执行任务,经过这样的配合它们就可以破解RSA密钥。

因为篇幅有限,很多数学细节和证明过程就不再赘述了,如果你对这些数学解释感兴趣,如果你具备线性代数、群论、高等数学的知识,你可以看看这些:

Quantum Computer Science

Quantum Information and Quantum Computation

NIST Quantum Zoo  — 一个所有量子算法的列表

立即下载试用

人工智能不是网络安全的“救世主”

AI技术开发人员更是对“AI能够增强网络安全防御能力”这一愿景持乐观态度。他们认为,人为错误是不可避免的,而AI技术可以利用大数据和机器学习持续性观察和监控威胁发展趋势,从而优化提升某些防御行为。

在有关新一代网络安全技术的讨论中,AI无疑是一个高频出现的词汇,总是被反复提及。当前的网络攻击形势愈发严峻,安全人员对于利用AI技术保护数字资产表现出了极大热情。而AI技术开发人员更是对“AI能够增强网络安全防御能力”这一愿景持乐观态度。他们认为,人为错误是不可避免的,而AI技术可以利用大数据和机器学习持续性观察和监控威胁发展趋势,从而优化提升某些防御行为。


但事物总是具有双面性,随着对AI技术应用效果的观察,很多用户和安全专家发现,目前的AI技术还并不能成为网络安全领域的“救世主”,至少并非像很多安全厂商宣传的那样。人们往往只关注AI的好处,却有意或无意地忽略了它的应用缺陷。这种对AI看法的偏见引起了一些研究人员的担忧,他们认为,尚不成熟的AI技术应用,正在为网络攻击者制造新的漏洞。


研究人员发现,AI技术在网络安全方面的应用弊端主要包括以下几点:


1、过度依赖大数据


掌握充分的数据是AI技术应用的基础,如果不考虑数据质量和充分性,AI的准确性就会无法保证。如果组织希望利用AI技术检测网络威胁、预测攻击并做出相应的反应,就必须通过机器学习算法模型提供大量的真实数据训练它。对于大型组织来说,这可能不是问题,因为他们本身就拥有大量数据。但是,对于那些只想保护自己的网络安全的中小型企业用户呢?目前,安全厂商正在给用户营造的印象是,AI技术是包罗万象的,但事实却并非如此,因为对那些缺少大数据资源的企业或组织而言,几乎无法有效使用AI技术。


2、数据泄露 


就保护数据隐私而言,处理数据的人越少越好。因为在网络安全领域为实施AI技术创建基础环境既不容易也不便宜,它需要高水平专业技术技能支撑。当企业无法自己管理运营基于AI技术的安全解决方案时,将不得不将其外包给第三方供应商,虽然相关供应商可能会做出“保密”的承诺,但事实上,这个过程增加了企业的数据暴露面和攻击面。同时,第三方供应商也可能为了自身利益而滥用客户数据,并且难以被监控审计。


3、黑客的目标


网络犯罪分子也在将紧跟网络安全趋势视为首要任务。随着AI技术在网络安全方面应用受到广泛关注,他们正竭尽所能地利用这一趋势。当安全专家尝试用最新的算法加强安全防御时,网络犯罪分子很可能已经在这些算法中发现了新的安全漏洞。在网络安全领域,没人能垄断AI技术,独享其带来的优势。入侵者和防御者之间存在一场利益争夺。如果入侵者没能抢在防御者前面,他们的恶意企图就不会得逞,所以入侵者也同样会努力保持领先。


4、AI应用技能不足


拥有一个良好的网络安全环境并不是只靠部署最新的技术就能实现,而是需要能够理解安全防护技术的原理并有效地利用它。除非是专业的网络安全人士,否则很难具备彻底使用AI技术的知识和技能。即便雇佣了AI专业人士来管理网络安全,但如果相关负责人员不了解算法及其工作原理,也无法获得理想的结果。而且,供应商所使用的算法模型可能并不适合企业的网络,如果企业对此并不了解,也将无法获悉这一点。


5、没有创造力和自发性


网络安全技术的目标是为了解决安全问题,因此并不存在完全通用的网络安全方法。就好像在“地面”部署的防御机制可能阻止不了来之“空中”的打击。为了能够及时找出恶意活动,必须要能够应用自发策略来管理特定的攻击。网络专业人士拥有实时遏制网络攻击的专业知识,他们可以用自己的创造力和自发性来应对独特的环境。而这一点正是AI技术所缺乏的,因为它主要是通过持续训练来养成分析和处置行为的。当一些未经过AI算法训练的恶意活动出现时,它将无法保护您的系统,因为AI技术缺乏人类即兴发挥、随机应变的第六感。


6、不切实际的期望


AI技术在网络安全领域的过度炒作让很多用户产生了不切实际的期望。似乎有了AI,就可以不用担心网络攻击了。但这是一个不能实现的承诺,因为AI技术远非完美。AI安全系统是由人设计的,因此根本无法避免漏洞的存在。尽管,AI算法可以为企业提供更好的决策和分析所需的数据,但它并不能为组织的网络安全需求提供“万能的”解决方案。因此,企业在应用AI技术前,必须准确了解它可以为自身的网络安全增加哪些价值,以及应如何实现这种价值。


本文为收集整理,文章部分观点不代表本站观点,如有侵权或其它问题请反馈客服。https://www.wgj7.com/cjwt/16512.html