墨滴

Shinkai005

V1

2023/02/27阅读：16主题：极简黑

【CSF】安全第五节课-Cryptography密码学下

【CSF】安全第五节课-Cryptography密码学下

总览

非对称加密

  • 保密vs.认证; Confidentiality vs. Authentication

  • 需求

算法

  • RSA

  • Diffie-Hellman密钥交换

非对称加密

image-20230226121618720
image-20230226121618720
  1. 密钥生成: 生成一个公钥和密钥
  2. 公钥是公开的(依旧需要保护, 因为有私人信息等) 密钥只有本人拥有.
  3. 发送给Alice, 使用alice的公钥加密, 然后alice收到用自己的私钥解密
  4. 只有alice可以解密.

非对称加密提供更高的安全性, 但是处理速度会慢很多, 所以使用场景一般不是对大量数据进行加密.

机密性.confidential

因为: 确保信息只能被意图接收者解密和读取，而被其他人无法获取和识别. 使用 公钥加密,私钥解密.

image-20230226123803232
image-20230226123803232

可认证性authentication

这里老师讲的逻辑我觉得有点不对~ 她想讲数字签名, 但是数字签名其实不是加密, 只是一种认证, 不需要考虑机密性. 所以说没有机密性

私钥加密, 公钥解密 不具有机密性. (数字签名.)

  • 使用alice的私钥进行加密, 然后拥有alice公钥的人就可以解开~ 这不具备机密性. 因为并不是指定的人获取,可能被其他人获取识别.
  • 下面介绍数字签名. 为什么会存在私钥加密, 公钥解密. 使用这种方式对一串代码加密解密, 然后接收方拿着解密后的原文使用相同的哈希算法计算原始哈希值, 和原文的哈希值进行比较. 如果相同证明信息没有篡改, 也就是保证了可认证性.

老师这里意思是, bob加密了明文, 你使用bob的公钥解密成功, 就可以认证这是bob发的. (个人觉得这个有点浅显...毕竟连基本安全都没保证,有了数字签名的比较,就更安全了)

非对称加密 条件

  • E()表示加密函数, PUb 表示 public key, M 表示 message 原文. C表示cipher-text密文
image-20230226124028581
image-20230226124028581
  • 这个就好理解了 PR是 private 下面的b是B用户生成的意思.
image-20230226124018431
image-20230226124018431

  • 知道公钥确定密钥是不可行的

  • 知道公钥和密文恢复原文也是不可行的.

也可以反过来 密钥加密另一个解密.

image-20230226162810484
image-20230226162810484

RSA算法(三种计算方式)公开密钥加密算法

  • Developed in 1977 by Ron Rivest, Adi Shamir, and Len Adleman // 取的姓的第一位
  • 非对称加密
  • Block Cipher 分组密码
  • 应用 : Secure Sockets Layer (SSL), Transport Layer Security (TLS)

计算过程:

image-20230227014512775
image-20230227014512775 
过程:
第一步: 选定 p, q
第二步: n = pq = 14
第三步: 欧拉函数(n) = (p-1)(q-1) = 6 记为x吧// 代码块里不能使用Latex.
第四步: 选取e   gcd(x,e) = 1  1<e<x. // 也就是2,3,4,5, 只有5和6公因数为1 => e=5
第五步: 求d 

过程1:

de mod 6 = 1 => 5d mod 6 = 1 => 5d-6k=1 (a)
// 两个数的系数5 6 取mod  6 mod 5 = 1 ....1   //大的对小的取余数 直到d的系数为1,k取0计算d.
上述式子变成 5d-k = 1(b) // 这里是k的系数为1,因此d取0 k = -1 (代入b) =>代入a d = -1. 
取d = 1 代入b k = 4 
取k = 4 代入a  d = 5
所以d可以取5.

过程2:

5d mod 6 = 1
5d - 6k = 1 取最大公约数 = > 6 = 1(5) +1 => 1 = 6-1(5)
5d mod 6 = [6-1(5) mod 6] // 这个没问题的, 一个数对于6的模再次对于6取模一定还是自己. 
5d mod 6 = (6mod6 - 1(5)mod6 )mod 6
5d mod 6 =  -1(5)  mod 6
5d mod 6 = -1(5)
d = -1
d = -1+6N (-1, 5, 11, 17)

(a×b) mod c=(a mod c * b mod c) mod c

(a+b) mod c=(a mod c+ b mod c) mod c

(a-b) mod c=(a mod c- b mod c) mod c

算法Diffie-Hellman 密钥交换

也叫密钥协商

最主要的是 可以在 "不安全"的网络上传输

目的: 两个用户安全地交换一个秘密密钥，然后可以用于随后的信息加密。

直接看可能看不懂, 我写写一些内容再过ppt

下面这个运算叫做模幂运算.

为什么要密钥交换?

RSA算法是做什么的, 是加密密钥的~ 就是通过RSA可以加密密钥后把密钥发送给另一个人~ 这样双方就有了相同的密钥.

那如果在不安全的网络上怎么办? 就出现了DH密钥交换.

这里出现两个问题,

  1. 最原始的交换方式是什么?

  2. DH密钥交换为什么就可以在不安全的网络上交换

  3. 最简单的交换方式就是物理传输, 你把密钥放到U盘~ 然后把u盘安全的送给别人~

这也是在谍战片里最常见的~ 而且如今也依旧再用...毕竟所有通过网络的都不是完全安全..

  1. 首先需要知道 DH密钥交换不是简单的交换自身的加密密钥, 而是双方协定生成一个协商密钥或者叫做共享密钥.

这个密钥实际上是计算得来的, 也就是协商~

2.1 以下内容来自 廖雪峰廖老师的网站(没直接cv.改了点)

  1. 甲首选选择一个素数p，例如97，底数g是p的一个原根，例如5，随机数a，例如123，然后计算A=g^a mod p，结果是34，然后，甲发送p＝97，g=5，A=34给乙；//随机数a没有发
  2. 乙方收到后，也选择一个随机数b，例如，456，然后计算B = g^b mod p，结果是75，乙再同时计算s = A^b mod p，结果是22；//随机数b没有发
  3. 乙把计算的B=75发给甲，甲计算s ＝ B^a mod p，计算结果与乙算出的结果一样，都是22。

这是整个流程, 即使每个流程发送内容都被截取, 1.pgA收到, 没有随机数a,要计算随机数a的复杂度也会非常高, 因为是指数级的运算. 2. 只有结果22没有意义, 发送的B也没有意义, 破解难度很高~

如果a和b泄露一个也可以认为是安全的~ 同时泄露就不安全了.

接下来开始ppt

image-20230226222437409
image-20230226222437409

  1. Alice, 和 Bob 分享一个 q和 , <q 并且是q的一个源根.

  2. Alice生成一个私有key a Bob生成一个私有key b (都要小于q)

  3. Alice计算 Bob计算

  4. 明文形式, Alice获取bob的结果, Bob接受Alice的结果

  5. 计算Alice 计算 K = Bob计算 K =

  6. 结果一样生成的key就是协商好的共享key

这里再说一个 源根的概念 primitive root.

在指定的素数p上，如果对于任意一个小于p的正整数x，都存在一个正整数k，使得 ，那么g就是p的一个原根。

原根

  1. q是选择出来的原始数
  2. 也是选择出来的, 但是需要满足条件小于q,并且是q的原根

q=13, = 2

最简单的方式算原根就是

image-20230227003017291
image-20230227003017291

技巧:

原根数量一般是 欧拉函数的欧拉函数. 比如 结果可以从下面原根表看到2,6,7,11都可.

这里解释一下老师的方法, 为什么要划线.

首先1. 原根不会重复~ 13的结果 一般就是1-12,有重复的一般就g了

看第二个 直接就重复很多~ 所以就不是原根

要找原根最简单的方法就是~ 向老师这样 一个一个算~ 不然还需要学很多新概念~

私钥 公钥

image-20230227004411768
image-20230227004411768

刚开始理解建议直接不思考他们是私钥公钥就是自己随机选的数和计算的数. 因为私钥公钥在我们思想里不都会非常大么~

实际上这个q值 也很大~

image-20230227005002055
image-20230227005002055

最后计算Key

image-20230227005141108
image-20230227005141108

这两个K最后结果是一样的 .

计算完整过程

image-20230227005318272
image-20230227005318272

可以看到, 唯一没有公开的就是 两方的私钥.

如何破解这个过程? 也就是需要找到私钥

image-20230227005755539
image-20230227005755539

// 都用x不太好..应该一个x一个y的.

  • 强行计算~ 但是这个计算是指数级的, 数字大了这个计算量非常大.

攻击

中间人攻击

简单解释下中间人~

首先本身DH算法就不一定是双方的~ 可能是3方.

这个时候, 如果一个中间人加入进来, 双方就变成了三方, 但是其他人不知道.

因此, ABC三个人. 本身是AB之间的沟通, 变成了AC CB 两两之间, 他们都认为传输给的是正确的人.

这样AC之间会共享密钥, BC之间共享了密钥.

在其中, C可以给B假的信息也可以给真的信息, 这就回到了最初的安全基础, 可以更改和只是非法看~

公开密钥加密是否比对称加密更安全?

不, 是否安全取决于key的长度以及计算难度

对称加密是否落伍了?

  • 对称加密计算开销最小
  • 例子: 使用AES加密静态和传输中的数据,SSD和谷歌云

公钥分配是微不足道的么?

• No — need a central agent and protocols

  • 我理解是, 需要使用适当的协议和工具，并且采取适当的管理和安全措施来确保公钥的安全和正确性。
  • 因为1.一些协议需要公钥分发, 同时公钥会带着一些隐私信息, 所以要保证公钥分发的安全和保密,所以需要适当的工具(通道)和协议.
  • 2.出现了一些新的协议来分发公钥, 使公钥分发更方便,这个时候管理和保护公钥就更重要了.

附录

欧拉函数表

image-20230227002801130
image-20230227002801130

原根表

image-20230227003104624
image-20230227003104624

推荐阅读

https://www.liaoxuefeng.com/wiki/1252599548343744/1304227905273889 廖雪峰DH算法

https://zh.wikipedia.org/zh-hans/%E5%8E%9F%E6%A0%B9 原根

https://blog.csdn.net/a843511/article/details/48579899 RSA算法中利用欧几里得算法求d详细过程

- END -

分类：

后端

标签：

后端

作者介绍

Shinkai005
V1

公众号:深海笔记Shinkai