encrypt

Hash 函数

将任意长度的数据映射到有限长度的域上。直观解释起来，就是对一串数据 m 进行杂糅，输出另一段固定长度的数据 h，作为这段数据的特征（指纹）

性质

正向快速：给定原文和 Hash 算法，在有限时间和有限资源内能
计算得到 Hash 值；
逆向困难：给定（若干） Hash 值，在有限时间内无法（基本不可
能）逆推出原文；
输入敏感：原始输入信息发生任何改变，新产生的 Hash 值都应
该发生很大变化；
碰撞避免：很难找到两段内容不同的明文，使得它们的 Hash 值
一致（即发生碰撞）。

算法实现

md4 md5遭遇碰撞破解，在商业领域应用较少

sha-2 sha-3使用较多

ETH 使用SHAKE256 (不满足标准的版本)

实际应用

银行中存储密码都是hash的value，通过value对比来判断密码正确性

数字签名

数字签名是一个带有密钥的消息摘要算法，这个密钥包括了公钥和私
钥，用于验证数据完整性、认证数据来源和抗否认。

常见的数字签名算法主要有 RSA、DSA、ECDSA
三种

实现过程

发送方通过哈希函数从内容中生成摘要，用私钥加密后，生成的摘要作为内容的数字签名和内容一起合并发给接收方

接收方先用发送方一样的哈希函数从原始内容计算出摘要，然后再用发送方的公钥来对数字签名进行解密，获得另一份摘要，对比两次摘要的结果来确认合法性。

RSA

RSA 既能用于数据加密也能用于数字签名 RSA 的算法涉及三个参数，

n、e1、e2。

其中，n 是两个大质数 p、q 的积，即n=p*q

欧拉函数
$$
fn = (p-1)(q-1)
$$
公钥e 为 1<e< fn 之间的数，e和fn互质

私钥d,
$$
(e*d)/fn 要求余数为1
$$

加密方式
$$
m^e / n 求余c
$$

解密方式
$$
c^d / n 求余m
$$

若e地d，必须求fn，要求p q，质因数分解n=pq，这里的质因数分解是大数，非常困难

n 的二进制表示时所占用的位数，就是所谓的密钥长度。e1 和 e2 是一对相关的值，e1 可以任意取，但要求 e1 与 (p − 1) ∗ (q − 1) 互质；再选择 e2，要求
$$
(e2 × e1) ≡ 1 (mod((p − 1) × (q − 1)))
$$

(n, e1),(n, e2) 就是密钥对。其中 (n, e1) 为公钥，(n, e2) 为私钥。RSA 加解密的算法完全相同，设 A 为明文，B 为密文，则：
$$
A ≡ Be2 (mod n)；B ≡ Ae1 (mod n)
$$

（公钥加密体制中，一般用公钥加密，私钥解密）e1 和 e2 可以互换使用，即：
$$
A ≡ B (mod ); B ≡ A (mod n)
$$

这里n分解成p q是很困难的

椭圆曲线

椭圆曲线数字签名加密算法 (Elliptic Curve Digital Signature Algorithm,ECDSA) 的基础是椭圆曲线密码学，给定参数 a, b, 我们选取如下的椭圆曲线：
$$
y^2 = x^3 + ax + b
$$

原理

红色曲线有4个点，PQTR。PQ连线延长与曲线相交为T，以X轴坐垂直线相交曲线另一点为R，因此椭圆曲线点相加
$$
P + Q = R
$$
代数上即可以通过PQ坐标解到R。

椭圆曲线数字签名

定义一组共同接受的椭圆曲线参数：
$$
(C, tt, n)
$$
其中，C 表示椭圆曲线点域和几何方程；tt 是所有点倍积运算的基点；

n 是该椭圆曲线的可倍积阶数。

签名者需要创建一对匙：即一个私钥和一个公钥，其中私匙 d 是一个小于 n 的标量，公匙是
$$
Q = d × tt
$$

签名过程

计算 e = Hash(m), 并截取二进制下其前 n 位为 z

选择一个随机数 k （比较重要，要随机）

计算椭圆曲线上的点 (x1, y1) = k × tt

计算 r ≡ x1 (mod n)

计算 s = k−1(z + rd) (mod n)

生成的数字签名就是 (r, s).

签名文件验证

计算 e = Hash(m)，验证前 n 位是否为 z

计算 w = s^−1 (mod n)

计算两个参数 u1 = zw mod n 和 u2 = rw mod n

计算 (x1, y − 1)，如果 (x1, y1) 不是椭圆曲线上一个点，验证失败

验证 r ≡ x1 (mod n)

环签名

环签名是一种特殊的群签名，当中只有环成员，没有管理者。

签名者利用其他人的公钥临时组建一个集合，被加入到这个集合的其他人都不一定知道自己被“加”进来了。

实际实现

monero 通过环签名隐藏交易者和发送者

陷门置换

是一类具有某种功能的函数，这类函数正向计算很容易，但是在不知道密钥的情况下求逆的概率可以忽略。例如 RSA 就是一种陷门置换，假设有公钥 (n, e1) 和私钥 (n, e2)，在已知公钥的情况下，任何人都可以从明文 A 计算密文 B，B ≡ Ae1 (mod n)，但是如果不知道私钥，从 B 计算出 A 的概率是可以忽略的；而如果知道私钥，那么就可以计算 A ≡ Be2 (mod n)，是很容易的。

我们用g(x) 来表示正向计算，g−1(x) 来表示求逆。

组合函数

输入一个密钥 k，一个初始值 v，以及一系列随机数

y1, y2, · · · , yn，对于每一个参数都使用一个对称加密函数 Ek，最终输出一个值 z ∈ {0, 1}b。我们构造如下函数：
$$
Ck,v (y1, y2, ..., yn) = Ek(y1 + Ek(y2 + Ek(...Ek(yn + v))))
$$
实际使用的时候令 Ck,v (y1, y2, , yn) = v，也就是令初始值和结果相等，这样就相当于将等式构成了一个环，再缺少其中任何一项时都可以用其他项算出缺少的那一项。

签名

签名者随机选择一个公钥集合 P1, P2, , Pn 作为混淆公钥，其中签名者自己的公钥对应的下标为 s，按照如下方式来产生对消息 m 最终的环签名：

计算 k = Hash(m)

选择一个随机数 v ∈ {0, 1}b

接着为所有公钥选择一个随机 xi ∈ {0, 1}b, 1 ≤ i ≤ n, i ≠ s 然后计算 yi = gi(xi)

签名者可以求解组合函数方程 Ck,v (y1, y2, , yn) = v 的解 ys，签名者使陷门置换由 ys 算出 xs, 即 xs = gs−1(ys)

输出最终的环签名，σ = (x1, x2, · · · , xn, v)

签名验证

验证者收到对于消息 m 的签名 (x1, x2, , xn, v) 后，按照如下步骤来进行验证：

对于所有的 i = 1, 2, · · · , r，计算 yi = gi(xi)

验证 k = Hash(m)

验证 Ck,v (y1, y2, , yn) = v

零知识证明

它指的是证明者能够在不向验证者提供任何有用的信息的情况下，使验证者相信某个论断是正确的。

零知识证明实质上是一种涉及两方或更多方的协议，即两方或更多方完成一项任务所需采取的一系列步骤。
证明者向验证者证明并使其相信自己知道或拥有某一消息，但证明过程不能向验证者泄漏任何关于被证明消息的信息。

验证

步骤一

编码成一个多项式问题: 把需要验证的程序编写成一个二次的多项式方程：
$$
t(x)h(x) = w(x)v(x)
$$
当且仅当程序的计算结果正确时这个等式才成立。证明者需要说服验证者这个等式成立。

步骤二

简单随机抽样:

验证者会选择一个私密评估点 s 来将多项式乘法和验证多项式函数相等的问题简化成简单乘法和验证等式 t(s)h(s) = w(s)v(s) 的问题。这样做不但可以减少证明量，还可以大量的减小验证所需的时间。

步骤三

同态编码加密:

我们使用一个拥有一些同态属性的（并不是完全同态的，至少在实际使用中有一些不是同态的) 加密函数 E。这个函数允许证明者在不知道 s 的情况下计算 E(t(s)), E(h(s)), E(w(s)), E(v(s))，她只知道 E(s) 和一些其他有用的加密信息。

步骤四

零知识:

证明者通过乘以一个数来替换 E(t(s)), E(h(s)), E(w(s)), E(v(s)) 的值，这样验证者就可以在不知道真实的编码值的情况下验证他们正确的结构了。

有一个粗糙的想法是这样的，因为校验 t(s)h(s) = w(s)v(s) 和校验

t(s)h(s)k = w(s)v(s)k（对于一个不等于 0 的私密的随机数 k 来说）几乎是完全一样的，而不同的地方在于如果你只接收到了 (t(s)h(s)k) 和 (w(s)v(s)k) 那么从中获取到 t(s)h(s) 或者 w(s)v(s) 的值就几乎是不可能了。

大素数获取方法

随机生成比较大的数，其次是可不可以通过素性测试

素性测试一种是通过费马素性测试，另一种是

Cryptographic Best Practices

https://gist.github.com/atoponce/07d8d4c833873be2f68c34f9afc5a78a