Jump to content
  • Hello visitors, welcome to the Hacker World Forum!

    Red Team 1949  (formerly CHT Attack and Defense Team) In this rapidly changing Internet era, we maintain our original intention and create the best community to jointly exchange network technologies. You can obtain hacker attack and defense skills and knowledge in the forum, or you can join our Telegram communication group to discuss and communicate in real time. All kinds of advertisements are prohibited in the forum. Please register as a registered user to check our usage and privacy policy. Thank you for your cooperation.

    TheHackerWorld Official

常见密码学算法

 Share


Recommended Posts

学习笔记

分类


密码学用于解决信息安全中的保密性,完整性,认证和不可否认性等问题。最初主要用于解决保密性。随着密码学技术的发展,逐渐应用到其它领域。
常见密码学算法: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加解密

  • 密文为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
      • 加密数据具备加法同态
Link to post
Link to comment
Share on other sites

 Share

discussion group

discussion group

    You don't have permission to chat.
    • Recently Browsing   0 members

      • No registered users viewing this page.
    ×
    ×
    • Create New...