幂加密

① 简述加密技术的基本原理，并指出有哪些常用的加密体制及其代表算法

1、对称加密算法
对称加密算法用来对敏感数据等信息进行加密，常用的算法包括：
DES（Data Encryption Standard）：数据加密标准，速度较快，适用于加密大量数据的场合。
3DES（Triple DES）：是基于DES，对一块数据用三个不同的密钥进行三次加密，强度更高。
AES（Advanced Encryption Standard）：高级加密标准，是下一代的加密算法标准，速度快，安全级别高；
算法原理
AES 算法基于排列和置换运算。排列是对数据重新进行安排，置换是将一个数据单元替换为另一个。AES 使用几种不同的方法来执行排列和置换运算。
2、非对称算法
常见的非对称加密算法如下：
RSA：由 RSA 公司发明，是一个支持变长密钥的公共密钥算法，需要加密的文件块的长度也是可变的；
DSA（Digital Signature Algorithm）：数字签名算法，是一种标准的 DSS（数字签名标准）；
ECC（Elliptic Curves Cryptography）：椭圆曲线密码编码学。
算法原理——椭圆曲线上的难题
椭圆曲线上离散对数问题ECDLP定义如下：给定素数p和椭圆曲线E，对Q＝kP，在已知P，Q 的情况下求出小于p的正整数k。可以证明由k和P计算Q比较容易，而由Q和P计算k则比较困难。
将椭圆曲线中的加法运算与离散对数中的模乘运算相对应，将椭圆曲线中的乘法运算与离散对数中的模幂运算相对应，我们就可以建立基于椭圆曲线的对应的密码体制。

② 给出p、q、e、M，求公钥，私钥，并且利用RSA算法加密和解密

假定用户A要发送消息m给用户B，1）用户B要产生两个素数p和q；2）用户B计算n=pq和φ(n)=(p-1)(q-1)；3）用户B选着一个数e（0<e<φ(n)),使得e和φ(n)互为素数；4）用户B通过计算得出d，使得de除φ(n)的余数为1；5）用户B将n和e作为公钥公开；6）用户A通过公开渠道查到n和e；7）用户A对消息m进行加密，即E=m^e mod n=c(也就是说m的e次方除n的余数为c）；8）用户B收到密文c后，进行解密D=c^d mod n。
公钥就是（n,e) 私钥就是（n,d)
ps:若不想产生数据溢出（mod后的数大于25）的话，n最好选取0~25之间的数；如若是解密后的明文不出现差错，选取的n最好大于m中十进制数最大的数。
example:令26个英文字母对应于0-25的整数，用户B产生两个素数p=3，q=11，φ(n)=2*10=20，取e=3，则d=7，用户B将n=33和e=3公开
如果A想发送in给B，则A会通过公共渠道找到（n,e),然后将信息加密，E(i)=8^3 mod 33=17,E（n）=13^3 mod 33=19 则它对应的密文为c=rt；用户B收到A给的密文解密：D（r）=17^7 mod 33=8即明文i,D(t)=19 ^7 mod 33=13,即明文n。

③ RSA加密算法，求大神帮解答

如果用一段已经知道的明文，经过公钥加密，得到密文。现在已知明文密文和n, 是不是就可以通过解密的公式不断的幂运算求出私钥d呢？

④ 如何进行幂模运算

模幂乘运算采用平方乘算法，将模幂乘运算转化为模乘和模平方运算实现．
平方-乘算法：一般地，求S=ABmodN，其中A<N，B<N；将指数B表示为二进制，即
观察算法，由于指数B化为二进制后的长度不确定，多数情况下高位会存在很多个0．如果完全按照该算法实现，指数B从最高位起开始运算，在第一个1出现以前，虽进行了多次运算，但D的值一直为1；当B出现第一个1后才进入有效的模乘运算．在具体实现时，设计专门的电路从高到低扫描指数B的每一位，当在找到第一个1之前，不做任何运算，找到第一个1时，使D=A，以后根据每次扫描的6[i]值，调用模乘实现运算．
经过对多种公钥加解密算法的分析——如RSA算法，通常公钥的有效位较短，而私钥有效位较长．加密中的模幂乘运算，指数有效位很少，所以上面的改进可大大减少模乘次数，加快加密过程．以目前常用的私钥和模数1 024 bit，公钥128bit情况为例，采用上述改进可减少896次不必要的模乘．解密过程使用中国余数定理(CRT)，可有效降低解密指数的长度，整个算法的执行效率得到进一步提高．
2．2 模乘及模加的实现方法
模乘采用改进的Blakley加法型算法，原理与平方-乘算法类似，核心是将模乘转化为模加实现．如通常S=(A×B)modN，A<N，B<N可以按如下方式考虑．
将B表示成二进制：
由上式可知，可以像平方一乘算法一样，将模乘转化为模加实现．
一般模加运算表示为S=(A+B)modN，观察以上模乘及模幂乘算法原理描述，可知在其调用的模加运算中，因为A<N且B<N，则(A+B)<2N，所以，
因此考虑在运算中同时计算(A+B)和(A+B-N)两个结果，运算完成后通过判断加法器与减法器的进位输出(CO)与借位输出(BO)．决定哪个为本次模加的正确结果．同上，A，B，N均为l位的二进制数，若CO=1，则说明(A+B)为l+1位二进制数，必大于l位的N；若CO=0，则(A+B)和N同为l位，当BO=1时(A+B)<N，当BO=0时N≤(A+B)．
从而可以在一次运算中完成加法和求模过程，使模加的运算速度提高1倍．

⑤ 高中生如何理解比特币加密算法

加密算法是数字货币的基石，比特币的公钥体系采用椭圆曲线算法来保证交易的安全性。这是因为要攻破椭圆曲线加密就要面对离散对数难题，目前为止还没有找到在多项式时间内解决的办法，在算法所用的空间足够大的情况下，被认为是安全的。本文不涉及高深的数学理论，希望高中生都能看懂。

密码学具有久远的历史，几乎人人都可以构造出加解密的方法，比如说简单地循环移位。古老或简单的方法需要保密加密算法和秘钥。但是从历史上长期的攻防斗争来看，基于加密方式的保密并不可靠，同时，长期以来，秘钥的传递也是一个很大的问题，往往面临秘钥泄漏或遭遇中间人攻击的风险。

上世纪70年代，密码学迎来了突破。Ralph C. Merkle在1974年首先提出非对称加密的思想，两年以后，Whitfield Diffie和Whitfield Diffie两位学者以单向函数和单向暗门函数为基础提出了具体的思路。随后，大量的研究和算法涌现，其中最为着名的就是RSA算法和一系列的椭圆曲线算法。

无论哪一种算法，都是站在前人的肩膀之上，主要以素数为研究对象的数论的发展，群论和有限域理论为基础。内容加密的秘钥不再需要传递，而是通过运算产生，这样，即使在不安全的网络中进行通信也是安全的。密文的破解依赖于秘钥的破解，但秘钥的破解面临难题，对于RSA算法，这个难题是大数因式分解，对于椭圆曲线算法，这个难题是类离散对数求解。两者在目前都没有多项式时间内的解决办法，也就是说，当位数增多时，难度差不多时指数级上升的。

那么加解密如何在公私钥体系中进行的呢？一句话，通过在一个有限域内的运算进行，这是因为加解密都必须是精确的。一个有限域就是一个具有有限个元素的集合。加密就是在把其中一个元素映射到另一个元素，而解密就是再做一次映射。而有限域的构成与素数的性质有关。

前段时间，黎曼猜想（与素数定理关系密切）被热炒的时候，有一位区块链项目的技术总监说椭圆曲线算法与素数无关，不受黎曼猜想证明的影响，就完全是瞎说了。可见区块链项目内鱼龙混杂，确实需要好好洗洗。

比特币及多数区块链项目采用的公钥体系都是椭圆曲线算法，而非RSA。而介绍椭圆曲线算法之前，了解一下离散对数问题对其安全性的理解很有帮助。

先来看一下 费马小定理 ：

原根 定义：
设（a, p)=1 （a与p互素），满足

的最下正整数 l，叫作a模p的阶，模p阶为（最大值）p-1的整数a叫作模p的原根。

两个定理：

基于此，我们可以看到，{1, 2, 3, … p-1} 就是一个有限域，而且定义运算 gi (mod p), 落在这个有限域内，同时，当i取0～p-2的不同数时，运算结果不同。这和我们在高中学到的求幂基本上是一样的，只不过加了一层求模运算而已。

另一点需要说明的是，g的指数可以不限于0~p-2, 其实可以是所有自然数，但是由于

所以，所有的函数值都是在有限域内，而且是连续循环的。

离散对数定义：
设g为模p的原根，（a,p) = 1，

我们称 i 为a（对于模p的原根g）的指数，表示成：

这里ind 就是 index的前3个字母。
这个定义是不是和log的定义很像？其实这也就是我们高中学到的对数定义的扩展，只不过现在应用到一个有限域上。

但是，这与实数域上的对数计算不同，实数域是一个连续空间，其上的对数计算有公式和规律可循，但往往很难做到精确。我们的加密体系里需要精确，但是在一个有限域上的运算极为困难，当你知道幂值a和对数底g，求其离散对数值i非常困难。

当选择的素数P足够大时，求i在时间上和运算量上变得不可能。因此我们可以说i是不能被计算出来的，也就是说是安全的，不能被破解的。

比特币的椭圆曲线算法具体而言采用的是 secp256k1算法。网上关于椭圆曲线算法的介绍很多，这里不做详细阐述，大家只要知道其实它是一个三次曲线（不是一个椭圆函数），定义如下：

那么这里有参数a, b；取值不同，椭圆曲线也就不同，当然x, y 这里定义在实数域上，在密码体系里是行不通的，真正采用的时候，x, y要定义在一个有限域上，都是自然数，而且小于一个素数P。那么当这个椭圆曲线定义好后，它反应在坐标系中就是一些离散的点，一点也不像曲线。但是，在设定的有限域上，其各种运算是完备的。也就是说，能够通过加密运算找到对应的点，通过解密运算得到加密前的点。

同时，与前面讲到的离散对数问题一样，我们希望在这个椭圆曲线的离散点阵中找到一个有限的子群，其具有我们前面提到的遍历和循环性质。而我们的所有计算将使用这个子群。这样就建立好了我们需要的一个有限域。那么这里就需要子群的阶（一个素数n）和在子群中的基点G（一个坐标，它通过加法运算可以遍历n阶子群）。

根据上面的描述，我们知道椭圆曲线的定义包含一个五元祖（P, a, b, G, n, h)；具体的定义和概念如下：

P: 一个大素数，用来定义椭圆曲线的有限域（群）
a, b: 椭圆曲线的参数，定义椭圆曲线函数
G: 循环子群中的基点，运算的基础
n: 循环子群的阶（另一个大素数，< P ）
h：子群的相关因子，也即群的阶除以子群的阶的整数部分。

好了，是时候来看一下比特币的椭圆曲线算法是一个怎样的椭圆曲线了。简单地说，就是上述参数取以下值的椭圆曲线：

椭圆曲线定义了加法，其定义是两个点相连，交与图像的第三点的关于x轴的对称点为两个点的和。网上这部分内容已经有很多，这里不就其细节进行阐述。

但细心的同学可能有个疑问，离散对数问题的难题表现在求幂容易，但求其指数非常难，然而，椭圆曲线算法中，没有求幂，只有求乘积。这怎么体现的是离散对数问题呢？

其实，这是一个定义问题，最初椭圆曲线算法定义的时候把这种运算定义为求和，但是，你只要把这种运算定义为求积，整个体系也是没有问题的。而且如果定义为求积，你会发现所有的操作形式上和离散对数问题一致，在有限域的选择的原则上也是一致的。所以，本质上这还是一个离散对数问题。但又不完全是简单的离散对数问题，实际上比一般的离散对数问题要难，因为这里不是简单地求数的离散对数，而是在一个自定义的计算上求类似于离散对数的值。这也是为什么椭圆曲线算法采用比RSA所需要的（一般2048位）少得多的私钥位数（256位）就非常安全了。

⑥ 理论分析和举例说明RSA的加密和解密是互逆的

由于没有办法打出fai这个希腊字母 n的欧拉函数我用@（n）来表示
^ 代表幂的意思
e*d=1(mod @(n))
m为明文 c为密文
加密：c=m^e(mod n)
解密：m=c^d(mod n)
证明加密解密互逆也就是证明：
m=(m^e)^d(mod n) //把加密式子过程的c 带到解密过程那个式子中
也就是证明 m=m^(e*d) (mod n)

因为 e*d=1(mod @(n)) 可以推导出 e*d=k*@（n）+1
所以m=m*（k*@（n）+1） （mod n）
也就可以写出m=m*m^(k*@(n)) (mod n)
因为根据费马定理 m^（@(n)）=1 (mod n)
所以m^(k*@(n)) =1^k（mod n）=1（mod n）
m*m^(k*@(n)) (mod n)=m*1 （mod n）=m（mod n）证明就ok了

主要把握2点： 费马定理
公私钥关于@（n）互逆 就松松搞定

⑦ 零知识证明

https://arxiv.org/abs/1906.07221

零知识简洁的非交互知识论证（zk SNARK）是一种真正巧妙的方法，可以在不透露任何其他信息的情况下证明某件事是真的，然而，为什么它首先是有用的呢？

零知识证明在无数应用中是有利的，包括:

关于私人数据的证明声明:

匿名授权：

匿名付款：

外包计算：

尽管表面上听起来很棒，但底层方法是数学和密码学的“奇迹”，自 1985 年在主要着作“交互式证明系统的知识复杂性中引入以来，已经进行了第四个十年的研究 随后引入了非交互式证明，这在区块链的背景下尤为重要。

在任何零知识证明系统中，都有一个验证人想要说服验证人某些陈述是真实的，而不披露任何其他信息，例如，验证人了解到验证人的银行账户中有X多个，但没有其他信息（即，未披露实际金额）。协议应满足三个属性：

让我们从简单开始，并尝试证明某些东西，而不必担心零知识，非交互性，其形式和适用性。

想象一下，我们有一个长度为 10 数组，我们想向验证者（例如程序）证明所有这些位都设置为 1，即我们知道一个数组，使得每个元素都等于 1。

验证者一次只能检查 (即读取) 一个元素。为了验证语句，可以通过以某种任意顺序读取元素，并检查它是否真正等于1，如果是，则在第一次检查后该语句的置信度为10%，或者如果该位不等于1，则语句完全无效。验证者必须进入下一轮，直到他获得足够的信心。在一些情况下，可以信任证明者并且只需要50% 置信度，在需要95% 置信度的其他情况下，必须检查所有单元。很明显，这种证明协议的缺点是，必须进行与元素数量成比例的检查数量，如果我们考虑数百万个元素的数组，这是不切实际的。

让我们考虑多项式，有一个曲线对应于多项式： 。多项式有一个有利的性质，即如果我们有两个不相等的次数最多为 d 的多项式，它们相交的点不超过 d。 例如，让我们稍微修改原始多项式 。如果我们想找到两个多项式的交点，我们需要将它们等同起来。例如，要找到多项式与x轴相交的位置 (即 )，我们将 等同，并且此类方程的解将是那些共享点: ， 和 。

同样，我们可以将多项式的原始版本和修改版本等同起来，以找到它们的交点。所得的多项式为1，且有明显的解 。因此只有一个交点。

对于任意次数为 d 的多项式，任何此类方程的结果始终是另一个次数最多为 d 的多项式，因为没有乘法可以产生更高的次数。 示例： ，简化为 。代数基本定理告诉我们，d 次多项式最多可以有 d 个解。因此，我们可以得出结论，任意点处的任何多项式的求值类似于其唯一身份的表示。让我们在x = 10处评估我们的示例多项式。

事实上，在所有要计算的x选项中，最多只有3个选项在这些多项式中具有相同的计算，而所有其他选项都会不同。这就是为什么如果证明者声称知道一些多项式 (无论其次数有多大)，他们可以遵循一个简单的协议来验证语句:

例如，如果我们考虑 x 从 1 到 的整数范围，则评估不同的点数为 。 此后，x 意外“击中”任何 个共享点的概率等于 ，这被认为可以忽略不计。

注意：与无效位检查协议相比，新协议只需要一轮，并且在声明中给出了压倒性的信心（假设 d 充分小于范围的上限，几乎 100%）。

这就是为什么多项式是zk-SNARK的核心，尽管也可能存在其他证明介质。

我们从证明多项式知识的问题开始，然后采用通用方法。 在此过程中，我们将发现多项式的许多其他性质。 到目前为止的讨论集中，关注一个弱的证明概念上，即各方必须相互信任，因为还没有措施来执行协议的规则。 例如，证明者不需要知道多项式，他可以使用任何其他可用的方法来得出正确的结果。 此外，如果验证者的多项式评估的幅度不大，比如说 10，验证者可以猜测一个数字，并且它被接受的概率是不可忽略的。 我们必须解决协议的这种弱点，但首先知道多项式意味着什么？ 多项式可以表示为以下形式（其中 n 是多项式的次数）：

如果有人说他知道一个 1 次多项式（即 ），那意味着他真正知道的是系数 。 此外，系数可以有任何值，包括 0。让我们说，证明者声称知道3次多项式，使得x = 1和x = 2是所有可能解中的两个。这样的有效多项式之一是 。

代数的基本定理指出，只要多项式是可解的，任何多项式都可以分解为线性多项式 (即代表直线的1次多项式)。因此，我们可以将任何有效多项式表示为其因子的乘积:

同样，如果这些因子中的任何一个为零，则整个方程为零，因此，所有 都是唯一的解。我们的示例可以分解为以下多项式:

x的值是：0，1，2，你可以很容易地在多项式的任一形式上检查这一点。

回到证明者声称他知道根为 1 和 2 的 3 次多项式，这意味着他的多项式具有以下形式：

换句话说，(x − 1) 和 (x − 2) 是所讨论的多项式的余因子。因此，如果证明者想要证明他的多项式确实具有这些根而不公开多项式本身，则他需要证明他的多项式p(x) 是那些协因子 的乘法，称为目标多项式，和一些任意多项式h(x) ，即:

换句话说，p(x) 具有t(x) 的所有根。找到h(x) 的自然方法是通过除法 。如果证明者找不到这样的h(x)，这意味着p(x) 没有必要的协因子t(x)，在这种情况下，多项式除法将具有余数。在我们的示例中，如果我们将 除以 。我们得到了无余数的结果 。

使用我们的多项式身份检查协议，我们可以比较多项式 和 ：

为了将其付诸实践，让我们在示例中执行此协议:

相反，如果证明者使用不同的 ，它没有正确的辅因子，例如 ，那么：

我们将得到 ，余数为 ，即: 。这意味着证明者必须将余数除以 才能评估 。因此，由于验证者对x的随机选择，因此对于余数 被t(x) 整除的概率很低，因此，如果验证者将检查p和h补是整数，这样的证明将被拒绝。但是，该检查要求多项式系数也必须是整数。

现在，我们可以在不学习多项式本身的情况下检查多项式的特定属性，因此这已经为我们提供了某种形式的零知识和简洁。尽管如此，此构造仍存在多个问题:

我们将在以下部分解决所有问题。

在上文中，如果将 和 不是明文给出，而是作为黑匣子给出，那将是理想的选择，因此人们无法篡改协议，但仍然能够计算对这些模糊值。类似于哈希函数，因此在计算时很难返回到原始输入。

这正是同态加密的目的。也就是说，它允许对一个值进行加密，并能够对这种加密应用算术运算。有多种方法可以实现加密的同态特性，我们将简要介绍一种简单的方法。

一般的想法是，我们选择一个基数的自然数g（比如5），然后对一个值进行加密，我们将g乘以该值的幂。例如，如果我们想要加密数字3：

其中125是3的加密。如果要将这个加密的数字乘以2，则将其提高为2的指数:

我们能够将未知值乘以2，并对其进行加密。我们还可以通过乘法添加两个加密值，例如3+2：

同样，我们可以通过除法减去加密的数字，例如5 − 3:

但是，由于基数5是公共的，因此很容易回到秘密数字，将加密的数字除以5，直到结果为1。除法的次数即为明文。

这就是模算法发挥作用的地方。模运算的思想如下：我们声明只选择前n个自然数，即0，1，…，n-1而不是拥有一个无限的数字集。如果任何给定的整数不在这个范围内，我们将其“环绕”。例如，让我们先选择六个数字。为了说明这一点，请考虑一个具有六个相等单位刻度的圆；这是我们的射程。

现在让我们看看数字8将落在哪里。 打个比方，我们可以把它想象成一根绳子，它的长度是八个单位。如果我们把绳子连接到圆圈的开头并开始将绳子缠绕在它周围，旋转一圈后，我们还剩下一部分绳子.因此，如果我们继续这个过程，绳子将在2处结束。

它是模运算的结果。 不管绳子有多长，它总是会停在圆圈的刻度之一处。 因此，模运算将使其保持在一定范围内。 15 个单位的绳索将在 3 处停止，即 6 + 6 + 3（两个完整的圆圈，剩余 3 个单位）。 负数的工作方式相同，唯一的区别是我们将其包装在相反的方向，对于 -8，结果将是 4。

而且，我们可以进行算术运算，结果总是在n个数的范围内。 我们现在将使用符号“mod ”来表示数字的范围。 例如：3 × 5 = 3 (mod 6); 5 + 2 = 1 (mod 6).

此外，最重要的特性是运算顺序无关紧要，例如，我们可以先执行所有运算，然后在每次运算后应用模或应用模。例如: 相当于：2 × 4 = 2 (mod 6); 2 − 1 = 1 (mod 6); 1 × 3 = 3 (mod 6).

那到底为什么有帮助呢？事实证明，如果我们使用模算术，则具有运算结果，回到原始数字是不平凡的，因为许多不同的组合将具有相同的结果: 5 × 4 = 2 (mod 6); 4 × 2 = 2 (mod 6); 2 × 1 = 2 (mod 6).

如果没有模算术，结果的大小为它的解决方案提供了线索。 否则，这条信息会被隐藏，而常见的算术属性会被保留。

如果我们回到同态加密并使用模运算，例如模 7，我们将得到：

和不同的指数会有相同的结果:

这是很难找到指数的地方。 事实上，如果模数足够大，这样做就变得不可行，而现代密码学的很大一部分是基于这个问题的“难度”。该方案的所有同态属性都保留在模领域中：

encryption:
multiplication:
addition:

让我们明确说明加密函数： ，其中 v 是我们要加密的值。

这种同态加密方案存在局限性，尽管我们可以将加密值乘以未加密值，但我们不能将两个加密值乘以 (和除以)，也不能对加密值求幂。虽然从第一印象来看是不幸的，但这些属性将成为zk-SNARK的基石。

有了这样的工具，我们现在可以评估一个加密随机值为x的多项式，并相应地修改零知识协议。

让我们看看如何评估多项式 。正如我们以前建立的那样，多项式就是知道它的系数，在这种情况下，它们是: 1,-3,2。因为同态加密不允许对加密值求幂，所以我们必须得到从1到3的x幂的加密值: ， ， ，这样我们可以对加密多项式求值如下:

作为这些操作的结果，我们在我们未知的某个 x 处对我们的多项式进行了加密。 这是一个非常强大的机制，并且由于同态特性，相同多项式的加密计算在加密空间中总是相同的。我们现在可以更新协议的先前版本，对于d次多项式:

Verifier:

Prover:

Verifier:

由于证明者对s一无所知，因此很难提出不合法但仍匹配的评估。

虽然在这样的协议中，证明者的敏捷性是有限的，但他仍然可以使用任何其他方法来伪造证明，而无需实际使用所提供的 s 幂的加密，例如，如果证明者声称仅使用 2 次幂 和 有一个令人满意的多项式 ，这在当前协议中无法验证。

多项式的知识是其系数 。 我们在协议中“分配”这些系数的方式是通过对秘密值 s 的相应加密幂求幂（即 ）。 我们已经在选择 s 的加密幂时限制了证明者，但这种限制并未强制执行，例如，可以使用任何可能的方法来找到满足方程 的任意值 和 并将它们提供给验证者而不是 和 。 例如，对于一些随机 ， 和 ，其中 可以从提供的 s 的加密幂计算。 这就是为什么验证者需要证明仅使用 s 的幂的加密来计算 和 而没有别的。

让我们考虑一个1次多项式的基本例子，该多项式具有一个变量和一个系数 ，相应地，s的加密 。我们正在寻找的是确保只有s的加密，即 ，被一些任意系数c同态“乘以”，而不是其他任何东西。所以对于任意的c，结果必须是 形式。

一种方法是要求对另一个移位的加密值与原始值一起执行相同的操作，充当“校验和”的算术模拟，确保结果是原始值的取幂。这是通过引入的指数知识假设Knowledge-of-Exponent Assumption (或KEA) 来实现的，更确切地说:

Alice有一个值a，她希望Bob指数到任何幂，唯一的要求是只有这个a可以指数，没有别的，以确保她：

因为 Bob 无法从元组 中提取 ，因此推测 Bob 可以产生有效响应的唯一方法是通过以下过程：

最终，这样的协议向Alice提供了一个证据，证明Bob确实将a乘以他已知的某个值，并且他不能进行任何其他操作，例如乘法、加法，因为这将消除 移位关系。

在同态加密上下文中，幂运算是加密值的乘法。我们可以在简单的单系数多项式 的情况下应用相同的构造：

这种结构限制证明者仅使用提供的加密 s，因此证明者可以仅将系数 c 分配给验证者提供的多项式。 我们现在可以将这种单项多项式方法缩放为多项多项式，因为每个项的系数分配是单独计算的，然后同态地“相加”在一起。 因此，如果向证明者提供 s 的加密幂以及它们的移位值，他可以评估原始多项式和移位多项式，其中必须进行相同的检查。 特别是对于 d 次多项式：

对于我们之前的示例多项式 ，这将是：

现在我们可以确定，验证程序除了使用验证程序提供的多项式外，没有使用任何其他方法，因为没有其他方法来保持 移位。此外，如果验证者希望确保在验证者的多项式中排除一些s的幂，例如j，他将不提供加密 及其移位 。

与我们一开始的相比，我们现在有了一个健壮的协议。 然而，无论加密如何，零知识属性仍然存在一个明显的缺点：虽然理论上多项式系数 可以有很大范围的值，但实际上它可能非常有限（上例中为 6），这意味着 验证者可以暴力破解有限范围的系数组合，直到结果等于证明者的答案。 例如，如果我们考虑每个系数的 100 个值的范围，则 2 次多项式将总共有 100 万个不同的组合，考虑到蛮力将需要不到 100 万次迭代。 此外，即使在只有一个系数且其值为 1 的情况下，安全协议也应该是安全的。

因为验证器只能从验证器发送的数据中提取关于未知多项式p（x）的知识，所以让我们考虑那些提供的值（证明）： 。他们参与以下检查：

gp=gh（多项式p（x）有t（x）的根）

（gp）α=gp′t（s）（使用正确形式的多项式）

问题是我们如何改变证据，使支票仍然有效，但无法提取任何知识？从上一节可以得出一个答案：我们可以用一些随机数δ（δ）来“移位”这些值，例如（gp）δ。现在，为了提取知识，首先需要找到被认为不可行的δ。此外，这种随机化在统计学上与随机性是无法区分的。

为了保持关系，让我们检查验证者的检查。证明者的值之一位于方程式的每一侧。因此，如果我们用相同的 δ “移动” 它们中的每一个，方程必须保持平衡。

具体地，证明者对随机 δ 进行采样，并用g α p(s) δ gh(s) δ 对其证明值求幂，并提供给验证者进行验证:

(gp)δ = gh δ t(s) (gp)δ α = gp′ δ

合并后，我们可以观察到支票仍然有效：

注意: 零知识是多么容易被编织到建筑中，这通常被称为 “免费” 零知识。

到目前为止，我们有一个交互式零知识方案。为什么会这样？由于该证明仅对原始验证者有效，其他任何人（其他验证者）都不能信任同一证明，因为：

因此，为了证明语句（在这种情况下是多项式的知识），需要与每个验证者进行单独的交互。

虽然交互式证明系统有其使用案例，例如，当证明人只想说服一个专用的验证人（称为指定验证人），这样证明就不能再用于向其他人证明同一陈述时，当一个人需要同时（例如，在区块链等分布式系统中）或永久地说服多方时，这是非常有效的。验证方需要始终保持在线，并对每个验证方执行相同的计算。

因此，我们需要的秘密参数是可重用的，公开的，可信的和不可滥用的。

让我们首先考虑在秘密 (t(s)，α) 产生后如何保护它们。我们可以像验证者在发送给证明者之前对s的指数进行加密一样对它们进行加密。然而，我们使用的同态加密不支持两个加密值的乘法，这对于验证检查以使t(s) 和h以及p和 α 的加密相乘都是必需的。这就是密码配对的地方。

密码配对（双线性映射）是一种数学构造，用函数 , 给定来自一组数字的两个加密输入（例如， ，允许将它们确定地映射到不同数字输出集中的乘法表示，即， 。

由于源和输出编号集合不同，因此配对的结果不能用作另一个配对操作的输入。我们可以将输出集 (也称为 “目标集”) 视为来自 “不同的宇宙”。因此，我们不能将结果乘以另一个加密值，并通过名称本身建议我们一次只能乘以两个加密值。在某种意义上，它类似于一个散列函数，它将所有可能的输入值映射到一组可能的输出值中的一个元素，并且它不是平凡可逆的。

注意: 乍一看，这种限制只能阻碍依赖的功能，具有讽刺意味的是，在zk-SNARK情况下，它是该方案的安全性所拥有的最重要的属性。

配对函数 的一个基本（技术上不正确）的数学类比是说明有一种方法可以“交换”每个输入的基数和指数，这样基数 在转换过程中会被修改成指数，例如 。 然后将两个“交换的”输入相乘，使得原始 a 和 b 值在相同的指数下相乘，例如：

因此，由于在“交换”期间使用结果 在另一个配对（例如， ）中改变了碱基，因此不会产生所需的加密乘法 。配对的核心属性可以用等式表示：

e(ga, gb) = e(gb, ga) = e(gab, g1) = e(g1, gab) = e(g1, ga)b= e(g1, g1) ab= . . .

从技术上讲，配对的结果是目标集不同生成器g下原始值的加密产物，即 。因此，它具有同态加密的特性，例如，我们可以将多对的加密产物添加到一起：

注意：加密配对利用椭圆曲线来实现这些属性，因此从现在起，符号 将表示曲线上的生成器点，该点将被添加到自身 次，而不是我们在前面部分中使用的乘法群生成器。

有了加密配对，我们现在可以设置安全的公共和可重用参数。让我们假设我们信任一个诚实的一方来生成秘密 s 和 α。一旦 α 和具有相应 α 位移的 s 的所有必要幂被加密（gα, gsi , gαsi for i in 0, 1, ..., d），必须删除原始值。

这些参数通常被称为公共参考字符串common reference string或CRS。CRS生成后，任何prover和verifier都可以使用它来执行非交互式零知识证明协议。虽然不重要，但CRS的优化版本将包括对目标多项式target polynomial 的加密评估。

此外，CRS分为两组（对于 中的 ）：

由于能够乘以加密值，verifier可以在协议的最后一步检查多项式，让verification key verifier进程从证明者那里接收到加密多项式评估 gp、gh、gp'：

虽然可信设置是有效的，但它并不有效，因为 CRS 的多个用户将不得不相信一个删除的 和 ，因为目前没有办法证明这一点。 因此，有必要最小化或消除这种信任。 否则，不诚实的一方将能够在不被发现的情况下制作假证据。

实现这一点的一种方法是由多方使用前面部分中介绍的数学工具生成复合 CRS，这样这些方都不知道秘密。这是一种方法，让我们考虑三个参与者 Alice、Bob 和 Carol，对应的索引为 A、B 和 C，对于 i 在 1、2、...中。 . . , d:

作为这种协议的结果，我们有复合 和 并且没有参与者知道其他参与者的秘密参数，除非他们串通。事实上，为了学习 和 ，必须与其他所有参与者串通一气。因此，即使一个人是诚实的，也无法提供假证明。

注意：此过程可以根据需要对尽可能多的参与者重复。

可能存在的问题是如何验证参与者是否与 CRS 的每个值一致，因为对手可以采样多个不同的 s1、s2、...。 . . 和α1, α2, . . .，并将它们随机用于 s 的不同幂（或提供随机数作为增强的公共参考字符串），从而使 CRS 无效且不可用。

幸运的是，因为我们可以使用配对来乘以加密值，所以我们能够执行一致性检查，从第一个参数开始，并确保每个下一个参数都是从它派生的。参与者发布的每个 CRS 都可以检查如下：

请注意，虽然我们验证每个参与者都与他们的秘密参数一致，但使用先前发布的 CRS 的要求并未对每个下一个参与者强制执行（在我们的示例中为 Bob 和 Carol）。因此，如果对手是链中的最后一个，他可以忽略先前的 CRS 并从头开始构造有效参数，就好像他是链中的第一个，因此是唯一知道秘密 s 和 α 的人。

我们可以通过额外要求除第一个参与者之外的每个参与者加密和发布他的秘密参数来解决这个问题，例如，Bob 还发布：

这允许验证 Bob 的 CRS 是 Alice 参数的适当倍数，因为 i in 1, 2, . . . , d:

同样，Carol必须证明她的CRS是Alice-Bob的CRS的适当倍数。

这是一个强大的CRS设置方案，不完全依赖任何一方。实际上，即使只有一方是诚实的，并且删除并且从不共享其秘密参数，即使所有其他各方都合谋，它也是非常明智的。因此，CRS 设置中不相关的参与者越多，伪造证据的可能性就越小，如果竞争方参与，其可能性就可以忽略不计。该方案允许涉及对设置的易读性有疑问的其他不受信任的各方，因为验证步骤确保他们不会破坏最终的公共参考字符串 (也包括使用弱 α 和s)。

我们现在准备巩固进化的zk-SNARKOP协议。形式上，为简洁起见，我们将使用大括号来表示由其旁边的下标填充的一组元素，例如si i ∈[d] 表示集合s1，s2，...，sd。

已商定目标多项式t（x）和校准仪多项式的d次：

Setup：

⑧ RSA加密解密问题，我现在有公钥和幂，怎么使用来给数据加密，最好有C/C++代码，谢谢

rsa算法利用的是大素数分解的困难性来保证安全的
加密：明文的公钥次幂，在模n（应该就是你说的幂了）
解密：密文的密匙次幂，在模n，即可得到明文

⑨ 加密技术06-加密总结

对称密码是一种用相同的密钥进行加密和解密的技术，用于确保消息的机密性。在对称密码的算法方面，目前主要使用的是 AES。尽管对称密码能够确保消息的机密性，但需要解决将解密密钥配送给接受者的密钥配送问题。

主要算法

DES

数据加密标准（英语：Data Encryption Standard，缩写为 DES）是一种对称密钥加密块密码算法，1976年被美国联邦政府的国家标准局确定为联邦资料处理标准（FIPS），随后在国际上广泛流传开来。它基于使用56位密钥的对称算法。

DES现在已经不是一种安全的加密方法，主要因为它使用的56位密钥过短。

原理请参考： 加密技术01-对称加密-DES原理

3DES

三重数据加密算法（英语：Triple Data Encryption Algorithm，缩写为TDEA，Triple DEA），或称3DES（Triple DES），是一种对称密钥加密块密码，相当于是对每个数据块应用三次DES算法。由于计算机运算能力的增强，原版DES由于密钥长度过低容易被暴力破解；3DES即是设计用来提供一种相对简单的方法，即通过增加DES的密钥长度来避免类似的攻击，而不是设计一种全新的块密码算法。

注意：有3个独立密钥的3DES的密钥安全性为168位，但由于中途相遇攻击（知道明文和密文），它的有效安全性仅为112位。

3DES使用“密钥包”，其包含3个DES密钥，K1，K2和K3，均为56位（除去奇偶校验位）。

密文 = E k3 (D k2 (E k1 (明文)))

而解密则为其反过程：

明文 = D k3 (E k2 (D k1 (密文)))

AES

AES 全称 Advanced Encryption Standard（高级加密标准）。它的出现主要是为了取代 DES 加密算法的，因为 DES 算法的密钥长度是 56 位，因此算法的理论安全强度是 56 位。于是 1997 年 1 月 2 号，美国国家标准技术研究所宣布什望征集高级加密标准，用以取代 DES。AES 也得到了全世界很多密码工作者的响应，先后有很多人提交了自己设计的算法。最终有5个候选算法进入最后一轮：Rijndael，Serpent，Twofish，RC6 和 MARS。最终经过安全性分析、软硬件性能评估等严格的步骤，Rijndael 算法获胜。

AES 密码与分组密码 Rijndael 基本上完全一致，Rijndael 分组大小和密钥大小都可以为 128 位、192 位和 256 位。然而 AES 只要求分组大小为 128 位，因此只有分组长度为 128 位的 Rijndael 才称为 AES 算法。

本文 AES 默认是分组长度为 128 位的 Rijndael 算法

原理请参考： 加密技术02-对称加密-AES原理

算法对比

公钥密码是一种用不同的密钥进行加密和解密的技术，和对称密码一样用于确保消息的机密性。使用最广泛的一种公钥密码算法是 RAS。和对称密码相比，公钥密码的速度非常慢，因此一般都会和对称密码一起组成混合密码系统来使用。公钥密码能够解决对称密码中的密钥交换问题，但存在通过中间人攻击被伪装的风险，因此需要对带有数字签名的公钥进行认证。

公钥密码学的概念是为了解决对称密码学中最困难的两个问题而提出

应用场景

几个误解

主要算法

Diffie–Hellman 密钥交换

迪菲-赫尔曼密钥交换（英语：Diffie–Hellman key exchange，缩写为D-H） 是一种安全协议。它可以让双方在完全没有对方任何预先信息的条件下通过不安全信道创建起一个密钥。这个密钥可以在后续的通讯中作为对称密钥来加密通讯内容。公钥交换的概念最早由瑞夫·墨克（Ralph C. Merkle）提出，而这个密钥交换方法，由惠特菲尔德·迪菲（Bailey Whitfield Diffie）和马丁·赫尔曼（Martin Edward Hellman）在1976年发表，也是在公开文献中发布的第一个非对称方案。

Diffie–Hellman 算法的有效性是建立在计算离散对数很困难的基础上。简单地说，我们可如下定义离散对数。首先定义素数 p 的本原跟。素数 p 的本原根是一个整数，且其幂可以产生 1 到 p-1 之间所有整数，也就是说若 a 是素数 p 的本原根，则

a mod p, a 2 mod p,..., a p-1 mod p 各不相同，它是整数 1 到 p-1 的一个置换。

对任意整数 b 和素数 p 的本原跟 a，我们可以找到唯一的指数 i 使得

b ≡ a i (mod p) 其中 0 <= i <= p-1

其中 a, b, p 这些是公开的，i 是私有的，破解难度就是计算 i 的难度。

Elgamal

1985年，T.Elgamal 提出了一种基于离散对数的公开密钥体制，一种与 Diffie-Hellman 密钥分配体制密切相关。Elgamal 密码体系应用于一些技术标准中，如数字签名标准(DSS) 和 S/MIME 电子邮件标准。

基本原理就是利用 Diffie–Hellman 进行密钥交换，假设交换的密钥为 K，然后用 K 对要发送的消息 M，进行加密处理。

所以 Elgamal 的安全系数取决于 Diffie–Hellman 密钥交换。

另外 Elgamal 加密后消息发送的长度会增加一倍。

RSA

MIT 的罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）在 1977 年提出并于 1978 年首次发表的算法。RSA 是最早满足要求的公钥算法之一，自诞生日起就成为被广泛接受且被实现的通用的公钥加密方法。

RSA 算法的有效性主要依据是大数因式分解是很困难的。

原理请参考： 加密技术03-非对称加密-RSA原理

ECC

大多数使用公钥密码学进行加密和数字签名的产品和标准都使用 RSA 算法。我们知道，为了保证 RSA 使用的安全性，最近这些年来密钥的位数一直在增加，这对使用 RSA 的应用是很重的负担，对进行大量安全交易的电子商务更是如此。近来，出现的一种具有强大竞争力的椭圆曲线密码学（ECC）对 RSA 提出了挑战。在标准化过程中，如关于公钥密码学的 IEEE P1363 标准中，人们也已考虑了 ECC。

与 RSA 相比，ECC 的主要诱人之处在于，它可以使用比 RSA 短得多的密钥得到相同安全性，因此可以减少处理负荷。

ECC 比 RSA 或 Diffie-Hellman 原理复杂很多，本文就不多阐述了。

算法对比

公钥密码体制的应用

密码分析所需计算量（ NIST SP-800-57 ）

注：L=公钥的大小，N=私钥的大小

散列函数是一种将长消息转换为短散列值的技术，用于确保消息的完整性。在散列算法方面，SHA-1 曾被广泛使用，但由于人们已经发现了一些针对该算法理论上可行的攻击方式，因此该算法不应再被用于新的用途。今后我们应该主要使用的算法包括目前已经在广泛使用的 SHA-2，以及具有全新结构的 SHA-3 算法。散列函数可以单独使用，也可以作为消息认证、数字签名以及伪随机数生成器等技术的组成元素来使用。

主要应用

主要算法

MD5

MD5消息摘要算法（英语：MD5 Message-Digest Algorithm），一种被广泛使用的密码散列函数，可以产生出一个 128 位（ 16 字节，被表示为 32 位十六进制数字）的散列值（hash value），用于确保信息传输完整一致。MD5 由美国密码学家罗纳德·李维斯特（Ronald Linn Rivest）设计，于 1992 年公开，用以取代 MD4 算法。这套算法的程序在 RFC 1321 中被加以规范。

2009年，中国科学院的谢涛和冯登国仅用了 2 20.96 的碰撞算法复杂度，破解了MD5的碰撞抵抗，该攻击在普通计算机上运行只需要数秒钟。2011年，RFC 6151 禁止MD5用作密钥散列消息认证码。

原理请参考： 加密技术04-哈希算法-MD5原理

SHA-1

SHA-1（英语：Secure Hash Algorithm 1，中文名：安全散列算法1）是一种密码散列函数，美国国家安全局设计，并由美国国家标准技术研究所（NIST）发布为联邦资料处理标准（FIPS）。SHA-1可以生成一个被称为消息摘要的160位（20字节）散列值，散列值通常的呈现形式为40个十六进制数。

2005年，密码分析人员发现了对SHA-1的有效攻击方法，这表明该算法可能不够安全，不能继续使用，自2010年以来，许多组织建议用SHA-2或SHA-3来替换SHA-1。Microsoft、Google以及Mozilla都宣布，它们旗下的浏览器将在2017年停止接受使用SHA-1算法签名的SSL证书。

2017年2月23日，CWI Amsterdam与Google宣布了一个成功的SHA-1碰撞攻击，发布了两份内容不同但SHA-1散列值相同的PDF文件作为概念证明。

2020年，针对SHA-1的选择前缀冲突攻击已经实际可行。建议尽可能用SHA-2或SHA-3取代SHA-1。

原理请参考： 加密技术05-哈希算法-SHA系列原理

SHA-2

SHA-2，名称来自于安全散列算法2（英语：Secure Hash Algorithm 2）的缩写，一种密码散列函数算法标准，由美国国家安全局研发，由美国国家标准与技术研究院（NIST）在2001年发布。属于SHA算法之一，是SHA-1的后继者。其下又可再分为六个不同的算法标准，包括了：SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224、SHA-512/256。

SHA-2 系列的算法主要思路和 SHA-1 基本一致

原理请参考： 加密技术05-哈希算法-SHA系列原理

SHA-3

SHA-3 第三代安全散列算法(Secure Hash Algorithm 3)，之前名为 Keccak 算法。

Keccak 是一个加密散列算法，由 Guido Bertoni，Joan Daemen，Michaël Peeters，以及 Gilles Van Assche 在 RadioGatún 上设计。

2012年10月2日，Keccak 被选为 NIST 散列函数竞赛的胜利者。SHA-2 目前没有出现明显的弱点。由于对 MD5、SHA-0 和 SHA-1 出现成功的破解，NIST 感觉需要一个与之前算法不同的，可替换的加密散列算法，也就是现在的 SHA-3。

SHA-3 在2015年8月5日由 NIST 通过 FIPS 202 正式发表。

原理请参考： 加密技术05-哈希算法-SHA系列原理

算法对比