当前位置: 首页 > news >正文

密码学学习记录(四)

密码学学习记录(四)

《图解密码技术》[1]学习记录

对称密码由于解密和加密的密钥相同,无法解决密钥配送问题(key distribution problem)

而解决这个问题的方法有以下几种:

  • 通过事先共享密钥
  • 通过密钥分配中心
  • 通过Diffie-Hellman密钥交换
  • 通过公钥密码

解决密钥配送问题的方法

通过事先共享密钥

事先用安全的方法把密钥给对方,称为密钥的事先共享,比如线下给予密钥。

局限性就是如果两个是线上认识的,无法安全传递密钥。

通过密钥分配中心

每次加密通话时,密钥分配中心(Key Distribution Center, KDC)都会生成一个通信密钥,每个人只需要事先和KDC共享密钥即可,步骤大致为:

  1. 发出通信请求
  2. KDC随机生成一个会话密钥,用于双方本次通信的临时密钥
  3. KDC从数据库取出双方密钥
  4. KDC分别用双方密钥对会话密钥加密,然后发给双方(例如用A的密钥加密会话密钥然后发给A)
  5. 双方解密得到会话密钥,发送方使用会话密钥加密发送信息
  6. 接收方使用会话密钥对收到的密文进行解密
  7. 双方删除会话密钥

局限性:可以看到,由于每个人都需要在KDC事先存储密钥,如果人非常多,导致KDC负荷太大而故障,整个加密通信都会瘫痪;同时,如果入侵者入侵了KDC的计算机,就能得到所有人的密钥,从而能够破译存储密钥的所有人的加密信息。

通过Diffie-Hellman密钥交换

进行加密的双方交换一些信息,然后各种生成相同的密钥,在这个过程中,即使信息被截取到也无法生成和通信双方相同的密钥

通过公钥密码

和对称密码不同,公钥密码的加密和解密密钥是不同的,所以任何人都可以进行加密,但没有解密密钥就无法对其进行解密。这就是公钥密码的一个重要性质:只有拥有解密密钥的人才能进行解密。

公钥密码(public-key cryptography)中,密钥分为加密密钥(public key)和解密密钥两种,分析两者关系可以总结出几个特点:

  • 发送者只需要加密密钥
  • 接收者只需要解密密钥
  • 解密密钥不能被窃听者获取
  • 加密密钥被窃听者获取也没问题

加密密钥是公开的,可以公开展示,在任何地方分享,而解密密钥则不能公开,只能自己使用,所以解密密钥一般称作私钥(private key)。私钥不能告诉任何人,包括通信对象。

1978年,Ron Rivest、Adi Shamir 和 Reonard Adlema 共同发表了一种公钥密码算法——RSA,是现在公钥密码的事实标准。

公钥通信流程

在刚开始,A有两个密钥,一个公钥和一个私钥,将公钥发给B,接着B使用A的公钥对消息进行加密,在这个过程中,即使有人获取到公钥也不用担心,使用A的公钥加密后的消息只有A的私钥才能解密,此时B发送的消息被窃听者获取到也无法解密。

其他术语

公钥密码有很多称谓,如非对称密码(asymmetric cryptography)和公钥密码是相同含义。

私钥也有很多其他别名,如 个人密钥、私有密钥、非公开密钥、私密密钥、私有秘密密钥等。

其中公钥和私钥是最普遍的叫法。

RSA

RSA是目前使用最广泛的公钥密钥算法,很多CTF比赛也喜欢出RSA相关的密码学题目。

什么是RSA

RSA是一种公钥密码算法,它的名字是由它的三位开发者的姓氏的首字母组成的(Rivest-Shamir-Adlema)。

1983年,RSA算法在美国取得专利,但该专利已经过期。

RSA加密

RSA的加密流程很简单:

\[密文=明文^E \ mod \ N \]

将明文表示的数字和自己相乘E次再对N取模,得到的就是密文,在这个过程中,得到密文需要用到E(Encryption的首字母)和N(Number的首字母),也就是说,E和N的组合就是公钥。

公钥一般写作{E,N}或者(E,N)

注:E和N不是密钥对,E和N组成公钥,密钥对是公钥和私钥的密钥对

RSA解密

解密就和加密一样简单:

\[明文 = 密文^D \ mod \ N \]

也就是将表示密文的数字的D次方求mod N就可以得到明文。

和加密同理,D(Decryption的首字母)和N组成了私钥,这里的N和加密使用的N是相同的。

因为N是公钥的一部分,所以也可以单独将D称为私钥。

密钥对的生成

密钥对的生成步骤如下:

  1. 求N
  2. 求L(过程中使用的数)
  3. 求E
  4. 求D
(1) 求N

准备两个很大的质数:p和q

使得 $ N=p \times q $ ( p和q为质数)

(2) 求L

在RSA的加密和解密中都未曾出现L,它只出现在生成密钥对的过程中。

L是p-1和q-1的最小公倍数(least common multiple, lcm),令lcm(x,y)表示“x和y的最小公倍数”,则:

\[L = lcm(p-1,q-1) \]

(3) 求E

E和L的最大公约数(greatest common divisor, gcd)为1,并且1<E<L

也就是同时具备以下关系:

\[1<E<L \]

\[gcd(E,L)=1 \]

此时已经有了E和N,即公钥(E,N)

(4) 求D

D是由E计算得出的,D、E和L需要具备如下关系:

\[1<D<L \]

\[E \times D \ mod \ L = 1 \]

D如果满足以上条件,那么就可以解密E和N加密的密文。而\(gcd(E,L)=1\)就是为了确保存在满足条件的D。

RSA加解密示例

生成密钥对

(1) 求N

准备两个质数p、q,例如p = 23, q = 29

\[\begin{align} N &= p \times q \notag \\ &= 23 \times 29 \notag \\ &= 667 \notag \end{align} \]

(2)求L

\[\begin{align} L &= lcm(p-1,q-1) \\ &= lcm(22,28) \\ &= 308 \end{align} \]

(3)求E

\[\begin{align} gcd(E,L) &= 1 \end{align} \]

这里可以使用欧几里得辗转相除法,如果结果是1,那么就说明两者互质,也就找到了可能的E,核心算法如下:

// 注意 E < L ,所以不需要比较大小
int data = L % E;while (data)
{L = E;E = data;data = L % E;
}

最后的E就是最大公约数。把上面的算法写成函数,使用循环就可以找到一定范围内(小于L)和L互质的E了。

L=308时,可能的E有3、5、9、13、15、17、19、23 ···

这里要注意一下,和L互质的不一定是质数,比如9就不是质数。

令E = 3,则已知E = 3,N = 667,公钥已知。

(4)求D

已知D满足条件:

\[1 < D < L \]

\[E \times D \ mod \ L = 1 \]

也就是要找出和E相乘后再mod L = 1的数。

一个循环加一个判断条件很容易就能找到E对应的D,E=3时,D=103。

此时知道私钥为D=103,N=667。

密钥对如下:

公钥:

​ E = 3

​ N = 667

私钥:

​ D = 103

​ N = 667

加密

要加密的明文所表示的数字必须小于N,也就是小于667(需要mod N)

假设需要加密的明文是233,公钥是E=3,N=667,则:

\[\begin{align} 明文^E \ mod \ N &= 233^3 \ mod \ 667 \\ &= 349 \end{align} \]

因此密文就是349

解密

对密文349进行解密,已知私钥D=103,N=667

\[\begin{align} 密文 D \ mod \ N &= 349^{103} \ mod \ 667 \\ &= 233 \end{align} \]

得到明文233。

较大指数计算再取模的算法可以使用欧拉降幂和快速幂,参考欧拉降幂 | 公式 / 例题分析 / 代码实现-CSDN博客,也可自行搜索学习。

对RSA的攻击

通过密文

$ 密文 = 明文^E \ mod \ N $

求明文相当于求离散对数,目前没有较为高效求离散对数的算法,比较困难。

暴力破解求D

一般RSA使用的p和q都是512比特以上,求D需要进行至少1024比特的暴力破解,比较困难。

通过E和N求D

求D的公式为$ E \times D \ mod \ L = 1$

E和N是已知的,其中$ L = lcm(q-1,p-1) $

因此要求出D需要知道p和q,而$ N = p \times q$

此时不知道p和q因此无法破译(如果知道p和q,那么就和知道D没有区别)

对N进行质因数分解

目前对大整数进行质因数分解的算法都不够高效,如果一旦发现了能够对大整数进行质因数分解的高效算法,RSA算法加密的密文就能够被破译。

推测p和q进行攻击

如果p和q是使用某种简单的伪随机数生成器生成的质数,并且这个伪随机数生成器的算法很差,攻击者就有可能推测出p和q。

中间人攻击

中间人攻击(man-in-the-middle attack)不能破译RSA,但仍然可以获取机密信息(如果可以拦截并且修改信息)

(1)A向B发送消息询问B的公钥

(2)假设M是中间人,M可以拦截和篡改A向B或者B向A发送的消息。

(3)B将自己的公钥发给了A

(4)M拦截了B的消息,保存了B的公钥,然后将自己的公钥发给了A

(5)A使用B的(其实是M的)公钥加密后发送消息:你好

(6)M再次拦截了消息,使用自己的私钥解密获取到消息内容,然后将消息修改为:我不好,接着用B的公钥加密后发送给B

(7)B收到消息后解密看到的内容是:我不好

以上过程可以反复多次,这种中间人攻击可以针对任何公钥密码,为了防御中间人工具,需要认证公钥是否属于B,也就是公钥的证书。

其他公钥密码

ElGamal

ElGamal算法是由Tather ElGamal在1985年提出的,它是一种基于离散对数难题的加密体系,与RAS算法一样,既能用于数据加密,也能用于数字签名。ElGamal算法是基于因数分解,而ElGamal算法是基于离散对数问题。与RSA算法相比,ElGamal算法哪怕是使用相同的私钥,对相同的明文进行加密,每次加密后得到的签名也各不相同,有效的防止了网络中可能出现的重放攻击。特点是密文是明文的两倍长度。

Rabin

Rabin算法是一种基于模平方和模平方根的非对称加密算法,由Michael O. Rabin于1979年提出。它是RSA加密算法的一种变体,但与RSA不同,Rabin算法不是基于单向陷门函数,而是基于计算大整数的模平方根的难度。这意味着对于同一个密文,可能存在多个对应的明文。破解Rabin算法等同于分解大整数,和RAS求N的质因数分解等价,这是一个已知的困难问题。

椭圆曲线密码

椭圆曲线密码学(Elliptic Curve Cryptography, ECC)属于现代非对称密码体系的核心技术,通过将传统离散对数问题(DLP)映射到代数曲线上的有理点群,构建了兼具高安全性和低计算开销的密码系统。相较于RSA算法,ECC通过将曲线上特定点进行特殊的乘法运算实现加密,实现同等安全强度时密钥长度可缩减到1/6。利用了这种乘法运算的逆运算非常困难这一特性。


  1. 结城浩. 图解密码技术[M]. 周自恒,译. 第2版. 北京:人民邮电出版社, 2014. ↩︎

http://www.hskmm.com/?act=detail&tid=20859

相关文章:

  • Sharding-Proxy、ShardingSphere 和 Sharding-JDBC区别
  • echarts4升级为echarts5的常见问题
  • ISO 周计算 记录
  • 从 “被动耗能” 到 “主动优化”:MyEMS 开启商业建筑能源管理 “新范式”
  • 【故障排查】视频汇聚EasyCVR接入设备通道数为0?通道编码长度不规范导致
  • 来信小程序管理系统:匿名信息传递与社交互动平台
  • PCIe加速卡设计资料:416-基于Kintex Ultrasacle的万兆网络光纤 PCIe加速卡
  • 多生产者,多消费者
  • GEO优化实战指南:一周内让豆包、Deepseek、Kimi等推荐了我的插件
  • 房产楼盘小程序管理系统:助力房产营销数字化升级的优质解决方案
  • 高速信号处理设计方案:413-基于双XCVU9P+C6678的100G光纤加速卡
  • Teamcenter:结构管理器查询(又称:BOM结构查询)
  • 2025年最好用的同步云盘是哪个?一个老用户的真实体验分享
  • 使用 ShedLock 实现多实例定时任务单执行的常见错误及解决办法
  • 1_二分查找
  • AI元人文:悟空博弈专用芯片
  • 【ACM出版】第五届管理科学和软件工程国际学术会议(ICMSSE 2025)
  • PiXYZ Studio 2021下载地址与安装教程
  • coremail日常操作
  • Win 10 LSTC 使用 Podman - tfel
  • 一生一芯学习:程序,运行时环境与AM(一)
  • 如何用Java25编译Java17的项目
  • [MCP] MCP Resources
  • 【ACM出版】2025年第二届人工智能与未来教育国际学术会议(AIFE 2025)
  • HL工作日志
  • Halcon基础——图像增强
  • HTML 开发工具有哪些?常用 HTML 开发工具推荐、学习路线与实战经验分享
  • PS 商业级人像修图插件:Infinite Retouch V1.0.3 全面指南
  • NVIDIA 开源 Audio2Face:音频生成逼真面部动画;Gemini Live API 支持思考能力 丨日报
  • 深入解析:4、urbane-commerce 认证请求 DTO 设计规范