加密

简书不支持mathjax哎。

阅读资料

看了一些加密相关的资料，资料网上到处都是，看一遍很快就忘掉了,做个记录:

1. 离散对数加密，有简单的加密过程 http://blog.csdn.net/chen77716/article/details/7106485
2. RSA,DSA等加解密算法介绍 http://blog.sina.com.cn/s/blog_a9303fd90101cgw4.html
3. RSA加密算法 https://zh.wikipedia.org/wiki/RSA%E5%8A%A0%E5%AF%86%E6%BC%94%E7%AE%97%E6%B3%95
4. ElGamal加密算法 https://zh.wikipedia.org/wiki/ElGamal%E5%8A%A0%E5%AF%86%E7%AE%97%E6%B3%95
5. 椭圆曲线加密解释 https://www.zhihu.com/question/22399196/answer/96016340
6. 原根 https://zh.wikipedia.org/wiki/%E5%8E%9F%E6%A0%B9
7. 密码学原理与实践，这本书讲解了对称加密，公钥加密和hash算法的一些原理。

RSA和ECC

RSA用到了费马小定理，有些绕，常忘掉公私钥的关系。记下

1. $p$和$q$是素数，$ N=pq $，$ r=(p-1)(q-1) $。
2. 随机选取私钥$e$，只要$e$和$r$互质。
3. 计算出公钥$d$，满足$e*d \equiv 1 \pmod n$。
4. $(N,e)$是私钥，$(N,d)$是公钥。核心公式是${m^d}e \equiv m \pmod n$

RSA的难题是大数质因子分解：$N=p*q$，已知$N$，但是很难求出$p,q$。

ECC的数学原理复杂，椭圆曲线离散对数什么的不懂，算法过程就不记了，ECC是现在最强的公钥算法吧。

对称加密和哈希

《密码学原理与实践》里对称加密部分讲的比较好。
现在的对称加密如DES，AES是**乘积密码，增加加密次数来提升加密强度。
所选用的S代换P置换网络满足乘积密码的条件，代换和置换不能交换顺序。
S代换是一个字典，P置换是一个排序，两者是公开的。每轮加密时使用异或的方式混入密钥。
PS:代换、置换、异或都是可逆的，这也是对称密码的对称根源。

《密码学原理与实践》里Hash部分没理解出太多东西，只说md5、sha之类的输入迭代hash，没怎么说为啥sha的强度很高。也许hash才是数学层面最复杂的东西。

《密码学原理与实践》值得一读，没发现更好的书。

一个基于离散对数的加密和签名算法

根据普通离散对数整理了一个公钥算法，包含加密和签名两部分，也算不白看那么些资料。

离散对数难题

方程$a^x \equiv y \pmod n$，已知$a,n,x$，很难求出$x$。
据说选择合理参数，强度等同与RSA。

公钥加密算法

公钥生成

1. 选出$a,n$，满足$ a^n \not \equiv 0 \pmod n$。
2. 随机选择私钥$k$，算出$K = a^k \pmod n$。
3. $(a,n,k)$是私钥，$(a,n,K)$是公钥。

Alice传给Bob消息$m$，Alice知道Bob的公钥。

加密

1. Alice随机选择整数$r$，算出$R = a^r \pmod n$。
2. Alice算出混淆密钥$s = K^r \pmod n$。这个数字只有Bob可以求出来。
3. Alice加密消息$e = m \oplus s$。简单用异或吧。
4. Alice传输$(R,e)$给Bob。

解密

1. Bob算出混淆密钥$s = R^k \pmod n$。只要Bob知道$k$。
2. Bob解密消息$m = e \oplus s$。

算法和ElGamal加密算法一致，加密部分用异或，就不需要扩展欧几里德算法求逆元了。

PS:公钥算法挡不住中间人攻击，需要证书分发认证什么的。

签名算法

自己想出的一个，网上
没发现有类似的算法。
公钥生成和上面一致。Bob公开公钥$(a,n,K)$。对消息$m$做签名。

生成签名

1. Bob随机选择整数$r$，
   算出$R = a^r \pmod n$。
2. Bob算哈希$h = hash(m)$。公开的hash算法。
3. Bob算签名$e = h+r+k$。
4. Bob传输签名信息$(m,e,R)$给Alice。

验证签名

1. Alice算哈希$h = hash(m)$。
2. Alice验证等式${a^h * R * K} \equiv {a^e} \pmod n$是否成立，判断签名是否有效。

密码存储和校验

密码明文存储有风险。简单的方式就是存hash值。
用户保存passwd，服务器保存hash(passwd)。hash可以简单的选用md5。
一般验证公式$sign = md5(md5(passwd) + timestamp) = md5(hash + timestamp)$。
安全，且还可以加上时间戳，生成有时效的令牌。