学习笔记
分类
密码学用于解决信息安全中的保密性，完整性，认证和不可否认性等问题。最初主要用于解决保密性。随着密码学技术的发展，逐渐应用到其它领域。
常见密码学算法：DES,AES; RSA, ECC; Hash; Signature等。
分类
- 对称密码
- 流密码
- 分组密码
- 非对称密码
不同阶段
古典/经典密码（凯撒密码），（1949 Shannon）近代密码（DES/AES），（1976 Diffie-Hellman, 1977 RSA）现代密码（RSA），（展望：量子密码等）
参考：
Ref https://mp.weixin.qq.com/s/wiblmEu14iB1yx6g6sTCnw
Ref Wikipedia
Ref 密码学发展史（https://github.com/guoshijiang/Cryptography_anyone_can_understand/blob/master/history/README.md）
各类算法
经典密码
凯撒密码
对称密码
加密和解密使用相同的秘钥。优点是加密解密效率高，缺点是秘钥的分发需要在隐秘通道进行。安全性取决于根据密文无法推出明文和秘钥。
-
基于异或的一次性密码。（多个密文可以解密出秘钥）(一次一密密码被证明是绝对安全的密码。1949 Shannon）
- 秘钥大于等于原消息，具备很好的安全性
- 问题是秘钥长度很大不易分配和管理
-
流密码。使用伪随机生成器，根据初始秘钥来生成一次性秘钥。安全性取决于与初始秘钥的保密性和伪随机生成器的随机性（不可预测性）。保密性较一次性密码弱，但秘钥容易分配和管理。
使用流密码要考虑安全性，例如同一个key不能使用两次：
Stream ciphers, where plaintext bits are combined with a cipher bit stream by an exclusive-or operation (xor), can be very secure if used properly[citation needed]. However, they are vulnerable to attacks if certain precautions are not followed:
keys must never be used twice
valid decryption should never be relied on to indicate authenticity
From https://en.wikipedia.org/wiki/Stream_cipher_attacks
- 分组密码：加密的明文和输出的密文长度相同，秘钥决定了输入明文和输出密文的映射关系，且是1对1映射。为了加密任意长度的明文，引入了电子密码本模式（Electronic codebook, ECB)和分组链接模式（Cipher block chaining, CBC)等。例如DES,AES
非对称密码
加密和解密使用不同的秘钥。优点是秘钥分发和管理更方便，且可以支持签名等功能。缺点是加密和解密效率低。安全性取决于根据密文和公钥无法推出明文和私钥。
RSA系列
- RSA
- Diffe-Hellman Key exchange
- DSA
ECC系列
- ECIES
- ECDH
- ECDSA
各种算法
RSA
RSA 原理、构建、加解密和大数分解的安全假设
Ref http://www.ruanyifeng.com/blog/2013/06/rsa_algorithm_part_one.html
Ref http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html
Ref wikipedia https://en.wikipedia.org/wiki/RSA_Security https://en.wikipedia.org/wiki/RSA
数学基础
欧拉函数
欧拉定理
模逆元
如果ab对n模1
- 则有ab = h*n + 1
- 进一步有 m^ab = m^(hn+1) = m^(hn) * m
RSA构建
- 取两 个质数p,q,求得n=p*q, 欧拉函数phi(n)=phi§phi(q)=(p-1)(q-1)
- 取两个质数方便求解欧拉函数phi(n)
- 取一个与n互质的数e,求解d使得e*d模phi(n)为1
- ed模phi(n)为1，则有 m^(ed) = m^(hphi(n) + 1) = m^(h*phi(n)) * m 模n的值为m
- (n,e)为公钥,(n,d)为私钥，其它数据如phi(n), q, p不公开
- RSA的安全性保障在于大整数因式分解是个难题，已知(n,e)很难求解d使得 e*d模phi(n)的值为1
- 求解d需要phi(n)
- 而求解phi(n)需要p,q
- 而从n求解p,q是个大整数因式分解问题
- RSA的安全性保障在于大整数因式分解是个难题，已知(n,e)很难求解d使得 e*d模phi(n)的值为1
RSA加解密
- 密文为m^d mod n
- 明文为m^(d*e) mod n = m^(phi(n)+1) mod n = m ^ phi(n) * m mod n
- 如果m和n互质，则明显明文解密后为m
- 如果m和不互质，也可证明明文解密后为m
RSA上的算法有加解密，签名，秘钥交换等
RSA的秘钥长度应该在1024以上，重要场景需要2048
RSA乘法同态
- A =Enc(a, pk_dn) = a ^d mod n
- B = Enc(b, pk_dn) = b ^d mod n
- A*B = Enc(ab, pk_dn) = (ab)^d mod n = a ^d * b ^d mod n
Diffie-Hellman key exchange
Diffie-Hellman密钥交换算法
基于离散对数难问题
p为素数，假定g是生成器，基于x (1,2,…,p-1)，有n使得x=g^n mod p
- p和g公开
- A: g^a mod p
- B: g^b mod p
- 则A*B = (ga)b mod p = (gb)a mod p
- A + B = g^a + g^b mod p = g^(a+b) mod p
加法同态
- A = g^a
- B = g^b
- A + B = g^a * g^b = g ^ (a + b)
ECC椭圆曲线密码学
定义在椭圆曲线上的加法群，其中无穷远点是单位元O。
- 然后可定义逆元，加法运算，结合律，交换律。
- 几何定义可参见上面的链接。加法的代数计算见上面链接。
- 如何在有限椭圆曲线上构造参数见上面链接
应用:
ECDH, ECDSA
Ref:
https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/
https://www.jianshu.com/p/3b810faff3ba
ElGamal 加密算法
基于Diffie-Hellman算法,基于离散对数难问题
https://zh.wikipedia.org/wiki/ElGamal%E5%8A%A0%E5%AF%86%E7%AE%97%E6%B3%95
- Diffie-hellman版本
- ECC版本
算法
- Alice的公钥和私钥(a,g^a)
- Bob的公钥和私钥(b,g^b)
- Bob对数据m的加密数据为: 将m映射到曲线上一点，如(m,m_y)，则加密为
(g^b, m_y*((g^a)^b))
Difference of pedersen and elgamal
https://crypto.stackexchange.com/questions/11923/difference-between-pedersen-commitment-and-commitment-based-on-elgamal
- Pedersen: gm*hr. No one know the y such that h=g^y.
- Elgamal: g^r, gm*hr. receiver knows the y such that h=g^y.
- If receiver knows the y such as h=g^y, then receiver can get g^m.
○ The main difference is that Pedersen commitments are unconditionally hiding. It will becomes to be computing hiding if - If sender knows the y such as h=g^y, then there is a trapdoor commitment in elgamal.
各种安全假设
http://blog.sciencenet.cn/blog-1362128-1095141.html
- 整数分解假设
- RSA假设
- 离散对数假设
数学基础
集合论基础
- 非空集合，满足封闭性，是广群；再满足结合律，是群；有单位元，是幺半群；有逆元是群；再满足交换律，是阿贝尔群。
- 群。<R,+>表示一个拥有满足封闭性、满足结合律、有单位元、有逆元的二元运算的代数结构，包括阿贝尔群、同态和共轭类。
- 满足交换律，则是阿贝尔群
- 环。<R,+,*)表示一个环。单位元不同。
- 在+上是一个阿贝尔群
- 在*上满足结合律，是一个半群
- 对+和*满足分配律
- 域。设<R，+，* >是环，如果<R，+>和<R-{0},>都是交换群（“0”为<R,+>的单位元）且满足分配律，则称<R，+，>是域。比如：有限整数环<R，+，*>是域。
循环群是—种很重要的群，也是已被完全解决了的—类群。其定义为若—个群G的每—个元都是G的某—个固定元a的乘方，则称G为循环群，记作G=(a)，a称为G的—个生成元。循环群有无阶循环群和有阶循环群两种类型。
From https://baike.baidu.com/item/循环群
Next
- Comparation of ECDH and DH
- Comparation of ECDSA and DSA
- 其它体系https://blog.csdn.net/jingzi123456789/article/details/104761739/
- ElGamal
- 加密数据具备乘法同态
- Paillier
- 加密数据具备加法同态
- ElGamal