比特币:密码学技术何以为信？深究背后的计算困难性理论_ALGOP币

作者：李昊轩?

来源：

微众银行区块链

隐私保护为何选用密码学算法？密码学算法背后有哪些神奇的数学理论？3何时比9大？计算可逆性错觉究竟是如何在数学领域被打破？

这里，我们将从密码学信任的理论基础出发，分享在隐私保护技术方案中应用密码学技术的一些思考：如何理解密码学算法的能力边界，如何客观地比较不同密码学算法对于隐私保护方案有效性的影响。

这一切，要从密码学神奇的“不对称性”说起。

神奇的“不对称性”

早在公元前，古埃及、古罗马、古希腊等古文明均已开始使用密码技术来保护信息的机密性，历史上最早的不对称性表现为选用特殊的信息编码方式，如果第三方不知道具体的编码方式，则难以解码对应的信息。

大约经过4000多年的发展，也就是近代20世纪初，现代密码学正式成型，引入了关于不对称性更为严谨的数学定义。比较有代表性的早期论文包括1929年LesterS.Hill在美国数学月刊上发表的《CryptographyinanAlgebraicAlphabet》。

上海市数据隐私安全计算企业重点实验室参与完成论文被密码学顶级会议PKC收录:近日，上海市数据隐私安全计算企业重点实验室谢翔博士联合香港大学学者共同合作的论文《Compact Zero-Knowledge Proofs for Threshold ECDSA with Trustless Setup》被公钥密码学领域国际顶级会议PKC 2021录用，该会议将在北京时间2021年5月9日至13日于线上举行。PKC是国际密码学会（IACR）主办的专注于公钥密码学方向的旗舰会议，每一年举办一次，今年是第24届，该会议一直是学术界和工业界共同关注的焦点。

本次上海市数据隐私安全计算企业重点实验室参与完成的论文亮点在于零知识证明（ZKP）方向的研究。在理论层面，我们提出的零知识证明包括HSM群中的离散对数关系和Castagnos-Laguillaumie（CL）密文的格式良好性。在实际应用层面，我们利用零知识证明改进了两方ECDSA和门限ECDSA的性能。

上海市数据隐私安全计算企业重点实验室以矩阵元科研中坚力量为基础，汇集国内密码学专家、学者组建而成。研究内容为针对数据融合与协同计算基础设施建设过程中保护数据安全与隐私的基础理论技术。[2021/4/7 19:55:55]

20世纪末，随着因特网的普及，大量敏感数据在网络上进行传输，产生了大量的数据内容保护的需求，密码学技术也因此得到飞速发展。

在现代密码学中，关于不对称性，大家最熟悉的概念莫过于“公钥”和“私钥”。

林煌博士：轻模式的隐私应用是密码学技术在隐私保护实践中很重要的一步:在今日的《金色深核》线上直播中，针对“假设我们要解决多公司之间数据需要保密且共同使用的问题，三个技术路线如何去做？去年Maskbook火了一下，各位如何看待这种“轻模式”的隐私应用？”Suterusu林煌博士表示关于多个公司之间进行保密数据的安全计算，这个需要结合零知识证明和安全多方计算才能解决。如果我们考虑一种简单的情况，只有两方进行安全计算，一方可以将自己的数据用门限同态加密方案的公钥加密后传输给另一方，另一方依据加密自己的数据生成密文，然后在两个密文上做预定的同态运算，最后双方合作把完成同态操作的密文解密。零知识证明可用于保证这个过程的计算可靠性（computational integrity），比如如何保证生成的加密密文确实是按照正确加密步骤生成的密文且加秘方知道原始明文呢？我们可以使用零知识证明算法针对加密电路生成能够验证明文和密文之间符合加密电路逻辑的证明。轻模式的隐私应用毫无疑问是密码学技术在隐私保护实践中很重要的一步，但这个领域还有很多可以做的事情。[2020/3/11]

以加密通信为例，主人公小华要向他的朋友美丽通过加密的方式发送一份电子邮件，可以先找到美丽的公钥，使用公钥对邮件内容进行加密，并将加密后的得到密文发送给美丽。美丽收到邮件内容的密文之后，通过自己的私钥进行解密，最终得到邮件内容的明文。

以上过程中，密码学算法神奇的不对称性体现在以下问题中：

现场 | 密码学专家杨光：实现百万级TPS几年内希望不大 领域内突破将有助发掘新应用场景:金色财经现场报道，在全球区块链开发者2018会议期间，金色财经采访了刚刚演讲的密码学专家杨光。他认为，目前扩容领域研究的主要方向是可验证计算、零知识证明等技术，分片技术也具有广阔的前景。他认为，区块链实现百万级TPS值得追求，但几年内希望不大。当前来看公链上的TPS对于运行当前的应用来讲是够用的，但未来在TPS上的突破，能够提供给我们新应用的探索可能。就像当今互联网速度的提升让我们实现了早期互联网时期人们难以想象的应用一样。[2018/12/16]

为什么只有美丽可以解密邮件内容？

为什么其他人不能通过美丽的公钥反推出她的私钥？

这些问题的答案，都要归结于密码学中的计算困难性理论。

计算困难性理论

在隐私保护场景中，计算困难性理论具体表现为，对同一隐私数据主体，通过不同计算路径，获得相同信息的计算难度具有不对称性。不对称性中，相对容易的计算方式被用来构造授权的数据访问，而困难的计算方式被用来避免非授权的数据泄露。

构造这样的不对称性的方式有很多，最经典的方式之一，就是千禧年七大难题之一——P和NP问题。

动态 | 亚马逊获得密码学及分布式数据存储方法的专利:据cointelegraph报道，电子商务巨头亚马逊获得了两项与保护数字签名完整性和改善分布式数据存储方法相关的专利。这两项专利于11月13日由美国专利商标局（USPTO）公布。[2018/11/14]

P问题是确定性图灵机，即通用计算机计算模型，在多项式时间(O(n^k))内可以计算获得答案的一类问题。NP问题是确定性图灵机在多项式时间内可以验证答案的正确性，但不一定能计算出答案的一类问题。

关于同一份答案，验证过程比计算过程要容易很多，由此我们可以构造出密码学算法所需要的计算难度不对称性。

NP问题是否能够通过有效的多项式时间算法转化成P问题，由此破解计算难度不对称性？目前学术界尚无定论。

理论研究进一步表明，对于NP问题集合中的核心问题，即NP完全问题，如果能够找一个有效的多项式时间算法来解决任何一个NP完全问题，那其他所有NP问题都可以基于这个算法来构造出有效的多项式时间算法。由此，之前提到的计算难度不对称性将不复存在。

幸运的是，经过将近70年的科学探索，这样的算法并没有被发现。在有限时间内，现代计算机难以求解这些问题的答案，所以现代密码学可以比较安全地基于这些NP完全问题来构造有效的密码学算法。

声音 | “公钥密码学之父”Diffie：区块链是降低和改变网络不安全性的一个主要方向:11月11日，2015年图灵奖得主、有“公钥密码学之父”之称的Whitfield Diffie在上海举行的区块链底层技术学术交流会上发表主题演讲。Diffie认为，互联网有三个主要性质：开放性、去中心化与支持社会变革，但它不可避免地存在一定不安全性，区块链则是降低和改变网络不安全性的一个主要方向。他称，网络安全涉及以下重要元素：一是安全计算，二是密码学，三是从发现恶意软件开始，防范它甚至回击它。Diffie最后提出对网络安全的几点意见：开发抗量子的公钥加密系统；重新审视未被解决的经典计算机安全问题，并用人工智能和其他新技术来解决；开发更多大规模的可信赖软件系统。[2018/11/11]

神奇的“计算困难问题”

形象地讲，计算困难性理论的核心就是构造一个迷宫，如果不知道捷径，是很难到达出口的。

我们日常所用的各类密码学算法，其有效性都与这一理论息息相关，这里重点以非对称密码学算法为例，介绍其中经典的迷宫构造蓝图，即三大计算困难问题：

大数分解困难问题

离散对数困难问题

椭圆曲线上的离散对数困难问题

大数分解困难问题

给定两个大素数p和q，计算n=p*q是容易的。然而，给定n，求解p、q则是困难的。

整数的素数分解是数论中最著名的问题之一，目前，求解素数分解最有效的方法称为数域筛法，即通过构造代数数域不停地对整数可能的集合进行迭代运算。

目前，大整数分解问题仍不存在更有效的分解方法，因此密码学一些方案利用大数分解困难问题构造相应协议，如RSA系列算法将其困难性规约为大数分解困难问题。如果大整数分解困难问题被破解，使用RSA密码方案保护的隐私数据也会相应遭到破译。

离散对数困难问题

在模为n，生成元为g的有限域中，给定整数a，计算g^a=b是容易的。然而，给定b和g计算a则是困难的。

许多新接触密码学的读者都会对离散对数问题产生计算可逆性的错觉，看起来就是进行一次log运算的事情，但真相并非如此。

在实数域，元素有一个非常重要的性质，全序关系，所以很容易比较大小。例如，在实数域中9>2且3>2，一定能推出9>2。

在计算log2(9)时，计算机会对以元素9为输入的函数结果进行二分查找法，首先计算(9/2)^2和9进行比较，再计算/2)^2…。通过不停比较元素大小的性质，从而计算log最终的结果。

然而，在有限域中，元素之间并不存在全序关系。在模为7的有限域中，可以看到诸如9等于2，3比9大的关系存在。

因此，无法通过有效的算法计算上述过程中的a。许多著名的密码协议安全性都是建立在离散对数困难性上的，如Diffie-Hellman密钥交换协议、ElGamal加密、DSA算法等。

椭圆曲线上的离散对数困难问题

当前，椭圆曲线密码学算法是当前密码应用的主流，每一个隐私数据都能以坐标(x,y)的形式，表示为椭圆曲线上的一个点。与一般离散对数困难问题类似，椭圆曲线上的离散对数困难问题可以表示为：

在有限域F上的椭圆曲线群，点P为曲线上某个点，给定整数a，计算a*P=Q是容易的。然而，根据P和Q计算a则是困难的。

有别于普通代数运算，椭圆曲线上的点运算定义如下：

可以看到，椭圆曲线上的点运算和普通实数域上的运算有很大差别，当前尚未存在一种有效的算法对椭圆曲线离散对数问题进行破译。目前，最常用的公钥密码算法体系ECDSA、EdDSA、国密SM2等都是基于这一困难问题。

客观比较不同的密码学算法

由于不同的密码学算法构造使用了不同的困难问题，对应地，不同的困难问题也势必会引入不同的安全假设。

理解这些安全假设，是企业进行技术选型，客观地判断基于不同密码学算法构造隐私保护方案孰强孰弱的关键。

这里，我们需要进一步引入“安全参数”的概念。

安全参数是一个衡量密码学算法保护隐私数据强度的数值。对位于“同一等级"的安全参数值来说，不同密码学算法的安全级别基本相同，即面对已知最有效的攻击方式，算法被破解导致隐私数据泄露的概率相同。

一般情况下，安全参数值的大小，直接体现为密钥长度的长短。在同一等级下，安全参数值有大有小，对应的密钥长度也有长有短。

基于不同困难问题的密码学算法密钥最小长度，美国国家标准与技术研究院NIST作如下推荐，其中，每个单元格表示需要使用密钥长度的最小比特数。

通过上表，我们可以看到，即便密钥长度相同，选用不同困难问题获得的安全级别是不同的。一般而言，基于同一困难问题构造的技术方案，密钥长度越长，安全性越高，相应地，系统效率越低，其中往往也伴随其他系统设计上的取舍。

不同场景应按照业务需求选择适合的技术方案和密钥长度，具体有以下几点需要特别注意：

隐私保护技术方案的安全性取决于其使用的密码学算法实现中最低的安全参数等级。

在未指明安全参数的前提下，进行密码学算法的安全性比较没有实际意义。

如果安全参数值很小，一般表现为对应的密钥长度很短时，无论密码学算法设计多么精妙，实际效果可能都是不安全的。

由于困难问题选用上的差异，密码学算法的理论强度没有最强，只有在满足特定安全假设下的够强，强行比较基于不同困难问题的密码学算法哪个更强通常没有实际意义。

计算困难问题归根结底还是一个计算问题，随着计算机计算能力的增强，或是算法理论研究进展的推进，这些困难问题的安全性都会发生变化。如RSA加密算法，NIST密钥管理准则认为，2010年后，1024位的密钥不再安全，需要增加到2048位的密钥长度，预计其安全有效性可以保持至2030年。

对于企业而言，这里的启示在于，不能简单地认为，隐私保护技术方案现在有效，就保证了10年后依旧有效。无论什么样的隐私保护技术方案都有其时效性。

企业如果能够根据权威技术组织推荐的安全参数、算法方案及时更新现有的系统，困难性理论就能够有效保障隐私保护技术方案的有效性历久如新。

正是：密码学技术易守难攻，困难性理论当居首功！

作为密码学安全的基石，计算困难问题和相关的安全参数，是企业有效进行密码学算法选型的关键考察点。企业应用落地时，需充分考虑隐私数据保密的有效期，选择合适的密码学算法和密钥长度，对数据安全性和系统效率进行必要衡量。

除了与密码学算法直接相关的计算困难问题，一个完整的隐私保护技术方案通常还需要构造密码学协议，来组合多种密码学算法。密码学协议引入了多方之间的交互，由此也引入其他重要的安全假设。

这些安全假设对评价隐私保护技术方案的整体安全性、有效性、实用性至关重要，具体分析，敬请关注下文分解。

标签：比特币DSABTCALG买比特币会被局抓吗知乎maidsafecoinbtc价格今日行情价格ALGOP币

ETH热门资讯