网络信息安全学习笔记之公钥密码学与RSA

时间：2024-03-30 14:48:23

要点：

  • 非对称密码是一种密码*，其加密算法和解密算法使用不同的**，一个是公钥，一个是私钥，非对称密码也称为公钥密码
  • 非对称密码用两个**中的一个和加密算法将明文加密成密文，再用另一个**和解密算法将密文恢复出明文
  • 非对称密码可以用来保密或者认证都可以
  • 非对称密码不建议加密大量数据，但是对小型消息如验证码的加密或者签名的加密更合适
  • 应用最广泛的公钥密码*是RSA，**RSA的困难在于分解大合数的质因子困难

一、公钥密码*的基本原理

1.对称密码*存在的问题

  • 加密能力和解密能力捆绑在一起
  • **更换，传递和交换需要可靠信道，**分发困难
  • 如果有N个用户，每一对之间产生一对**，**管理十分困难
  • 无法满足不相识用户之间的保密要求
  • 不能实现数字签名

2.非对称密码*的基本特点

  • 加密能力和解密能力是分开的
  • **分发简单
  • 需要保存的**大大减少，N个用户只需要保存N个**
  • 可满足不相识人之间的保密通信
  • 可以是实现数字签名

3.公钥密码*

公钥算法依赖于一个加***和一个与之不相关的解***，算法有如下特点：

  • 仅依据算法和加***来确定解***在计算上是不可行的
  • 两个**的任何一个都可以用来加密，另一个用来解密

公钥密码*的组成：

  1. 明文：算法的输入，可读信息或数据
  2. 加密算法：对明文进行各种转换
  3. 公钥和私钥：算法的输入分别用于加密和解密
  4. 密文：算法的输出，依赖于明文和**
  5. 解密算法：根据**和密文还原明文

4.公钥算法的主要步骤

  1. 每个用户都产生**，用来加密和解密消息
  2. 每个用户将公钥存于公开的寄存器或其他可访问的文件中，另一**私有，每个用户可以拥有若干其他用户的公钥
  3. 若Bob发消息给Alice，则要用Alice（解密方）的公钥进行加密，
  4. Alice收到消息后，用自己的私钥进行解密
  5. 需要认证时，发送方用自己的私钥进行认证，接收方用对方的公钥就行验证
  6. 加密和认证可以同时结合起来，实现保密性和认证

一般情况下都是先签名再加密，这样效率比较高

公钥加密还可以用于**交换

公钥加密基于单线陷阱函数

网络信息安全学习笔记之公钥密码学与RSA

5.公钥密码*的应用

网络信息安全学习笔记之公钥密码学与RSA

6.对公钥系统密码编码的要求

  • 产生一对**在计算上是容易的
  • 不难计算C=E(Ke,P)和P=D(Kd,C)
  • 已知Ke（公钥）求Kd（私钥）不可行
  • 不知道Kd，已知Ke，E，D，和C，计算P也不可行
  • 对明文P，E（Ke，P）有定义，且D（Kd，E（Ke，P）） = P

  • 对密文c, D(kd, C)有定义，且E(ke, D(kd, C))=C

  • 加密变换和解密变换可以互相换顺序

7.公钥密码的分析

  • 公钥密码易受穷举攻击，解决方法是使用长**
  • 目前不能证明公钥和私钥的推导是完全不可行的，因此所有的公钥算法就都值得怀疑
  • 穷举消息攻击，攻击者用公钥对可能的消息加密并于密文匹配，解决方案是发送的消息后加随机数

二、RSA

RSA是一种分组密码体质，其明文与密文都是0~n-1之间的整数，n<网络信息安全学习笔记之公钥密码学与RSA

1.算法流程

  1. 随机选择两个秘密大素数p和q
  2. 计算公开模数n=p*q
  3. 计算秘密的欧拉指数函数φ(n)=(p-1)(q-1)
  4. 选择一个与φ(n)互素的数，作为e或者d
  5. 用欧几里得算法计算模φ(n)的乘法逆元素，即根据ed mod φ(n)=1求e或者d
  6. 加密：C = M(e) mod n
  7. 解密：M= C(d) mod n = (M(e) mod n)d mod n = M

网络信息安全学习笔记之公钥密码学与RSA

网络信息安全学习笔记之公钥密码学与RSA

网络信息安全学习笔记之公钥密码学与RSA

例题：p=17,q=11,e=7, M=88，求公钥KU和私钥KR分别为多少？加密计算后所得到的C为多少？并验证解密运算后，是否能恢复出明文M。

解：

p=17,q=11,n=pq=17x11=187,                     φ(n)=(p-1)(q-1) =16x10=160

选择e=7, gcd(7,160)=1, 23x7=161, 所以d=23

公钥KU={7,187}, 私钥KR={23,187}, M=88

加密计算C=887 mod 187

网络信息安全学习笔记之公钥密码学与RSA mod 187 =[(网络信息安全学习笔记之公钥密码学与RSAmod187)x网络信息安全学习笔记之公钥密码学与RSAmod187)x88mod187)]mod187

88mod187=88

网络信息安全学习笔记之公钥密码学与RSAmod187=7744mod187=77

网络信息安全学习笔记之公钥密码学与RSAmod187=59969536mod187=132

网络信息安全学习笔记之公钥密码学与RSAmod187=(88x77x132)mod187=894432mod187=11

解密计算M=网络信息安全学习笔记之公钥密码学与RSA mod 187 = 88

2.RSA体质基本原理

满足公开**加密的要求，符合下列条件

  • 有可能找到e, d, n的值, 使得对所有M<n有 Med mod n = M

  • 对于所有M<n的值, 要计算Me和Cd是相对容易的

  • 在给定e和n时, 计算d是不可行的

  • φ(n) = φ(pq)=φ(p)φ(q)=(p-1)(q-1), p,q are prime

  • ed mod φ(n)=1, ed = kφ(n)+1, 即ed≡1 mod φ(n),      d≡e-1 mod φ(n)

定理：给定ed mod φ(n) =1, m∈[0, n-1], gcd(m, n)=1, 则：

  (me mod n )d mod n = med mod n = m

证明：∵ ed mod φ(n) = 1

  ∴ ed = kφ(n)+1，对某些整数k

  ∴ med mod n = mkφ(n)+1 mod n

     = m(mkφ(n) mod n) mod n

  ∵mkφ(n) mod n = (mφ(n) mod n)k mod n

            = 1k mod n = 1

  ∴med mod n = (m* 1) mod n = m

网络信息安全学习笔记之公钥密码学与RSA 

网络信息安全学习笔记之公钥密码学与RSA

 

3.RSA的安全性

有三种对RSA可能的攻击方法

  • 强行攻击：尝试所有可能的**
  • 数学攻击：对两个素数乘积的因子分解
  • 计时攻击：依赖于解密算法的运行时间

针对RSA的计时攻击

类似通过观察他人转动保险柜拨号盘的时间长短来猜测密码

可能的解决办法：

不变的幂运行时间，可能会降低性能

在求幂运算中加入随机延时

隐蔽：在执行幂运算之前先将密文乘上一个随机数

RSA数据安全算法，用私钥实现操作M=Cd mod n的过程如下

  • 产生0－n-1之间的秘密随机数r
  • 计算C’=C(re) mod n, e是公开的指数
  • 计算M’=(C’)d mod n
  • 计算M=M’r -1 mod n, 其中r -1是r模n的乘法逆元，根据            redmod n=r，可以证明结论是正确的

 

 

相关文章