发布于2022年10月15日3年前

学习笔记

各类算法

NedK7 · 2022-10-15T22:34:46+00:00

学习笔记分类密码学用于解决信息安全中的保密性，完整性，认证和不可否认性等问题。最初主要用于解决保密性。随着密码学技术的发展，逐渐应用到其它领域。常见密码学算法：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不能使用两次：分组密码：加密的明文和输出的密文长度相同，秘钥决定了输入明文和输出密文的映射关系，且是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加解密密文为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加密算法 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 加密数据具备加法同态

经典密码

凯撒密码

对称密码

加密和解密使用相同的秘钥。优点是加密解密效率高，缺点是秘钥的分发需要在隐秘通道进行。安全性取决于根据密文无法推出明文和秘钥。

基于异或的一次性密码。（多个密文可以解密出秘钥）(一次一密密码被证明是绝对安全的密码。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加解密

密文为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 = (g^a)b mod p = (g^b)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加密算法

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: g^m*hr. No one know the y such that h=g^y.
Elgamal: g^r, g^m*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/循环群

Comparation of ECDH and DH
Comparation of ECDSA and DSA
其它体系https://blog.csdn.net/jingzi123456789/article/details/104761739/
- ElGamal
  - 加密数据具备乘法同态
- Paillier
  - 加密数据具备加法同态

登录

游客您好，欢迎来到黑客世界论坛！您可以在这里进行注册。

常见密码学算法

精选回复

分类

各类算法

经典密码

对称密码

非对称密码

各种算法

RSA

数学基础

RSA构建

RSA加解密

RSA乘法同态

Diffie-Hellman key exchange

ECC椭圆曲线密码学

ElGamal 加密算法

Difference of pedersen and elgamal

各种安全假设

数学基础

集合论基础

Next

创建帐户或登录后发表意见

最近浏览 0

帐户

导航

搜索