简书不支持mathjax哎。
阅读资料
看了一些加密相关的资料，资料网上到处都是，看一遍很快就忘掉了,做个记录:
- 离散对数加密，有简单的加密过程 http://blog.csdn.net/chen77716/article/details/7106485
- RSA,DSA等加解密算法介绍 http://blog.sina.com.cn/s/blog_a9303fd90101cgw4.html
- RSA加密算法 https://zh.wikipedia.org/wiki/RSA%E5%8A%A0%E5%AF%86%E6%BC%94%E7%AE%97%E6%B3%95
- ElGamal加密算法 https://zh.wikipedia.org/wiki/ElGamal%E5%8A%A0%E5%AF%86%E7%AE%97%E6%B3%95
- 椭圆曲线加密解释 https://www.zhihu.com/question/22399196/answer/96016340
- 原根 https://zh.wikipedia.org/wiki/%E5%8E%9F%E6%A0%B9
- 密码学原理与实践，这本书讲解了对称加密，公钥加密和hash算法的一些原理。
RSA和ECC
RSA用到了费马小定理，有些绕，常忘掉公私钥的关系。记下
- $p$和$q$是素数，$ N=pq $，$ r=(p-1)(q-1) $。
- 随机选取私钥$e$，只要$e$和$r$互质。
- 计算出公钥$d$，满足$e*d \equiv 1 \pmod n$。
- $(N,e)$是私钥，$(N,d)$是公钥。核心公式是${md}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。
公钥加密算法
公钥生成
- 选出$a,n$，满足$ a^n \not \equiv 0 \pmod n$。
- 随机选择私钥$k$，算出$K = a^k \pmod n$。
- $(a,n,k)$是私钥，$(a,n,K)$是公钥。
Alice传给Bob消息$m$，Alice知道Bob的公钥。
加密
- Alice随机选择整数$r$，算出$R = a^r \pmod n$。
- Alice算出混淆密钥$s = K^r \pmod n$。这个数字只有Bob可以求出来。
- Alice加密消息$e = m \oplus s$。简单用异或吧。
- Alice传输$(R,e)$给Bob。
解密
- Bob算出混淆密钥$s = R^k \pmod n$。只要Bob知道$k$。
- Bob解密消息$m = e \oplus s$。
算法和ElGamal加密算法一致，加密部分用异或，就不需要扩展欧几里德算法求逆元了。
PS:公钥算法挡不住中间人攻击，需要证书分发认证什么的。
签名算法
自己想出的一个，网上
没发现有类似的算法。
公钥生成和上面一致。Bob公开公钥$(a,n,K)$。对消息$m$做签名。
生成签名
- Bob随机选择整数$r$，
算出$R = a^r \pmod n$。 - Bob算哈希$h = hash(m)$。公开的hash算法。
- Bob算签名$e = h+r+k$。
- Bob传输签名信息$(m,e,R)$给Alice。
验证签名
- Alice算哈希$h = hash(m)$。
- Alice验证等式${a^h * R * K} \equiv {a^e} \pmod n$是否成立，判断签名是否有效。
密码存储和校验
密码明文存储有风险。简单的方式就是存hash值。
用户保存passwd，服务器保存hash(passwd)。hash可以简单的选用md5。
一般验证公式$sign = md5(md5(passwd) + timestamp) = md5(hash + timestamp)$。
安全，且还可以加上时间戳，生成有时效的令牌。
