公钥密码学经典方案30篇学习笔记（初次阅读）

Posted on 2024-09-27 Edited on 2024-09-29

本文是荔枝橙味拱腰觅马糕守一文的后继，主要内容是对于 方案构造学习 一章中的 尝试发现方案构造错误 一节下的 30个经典方案的学习笔记

经过初次阅读尝试，发现笔者英文阅读能力较低，不足以在短暂时间内完成大量论文的阅读；故选择了在翻译器和人工智能的帮助下来进行阅读，以提升效率，并为第二次阅读打好基础

1984, A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. [34]

1976年，Diffie和Hellman首次提出了公钥密码的概念，并依赖离散对数问题和素数域上的计算复杂性来构造其密钥交换协议。ElGamal的工作正是基于这种思想，进一步提出了一个可以实现消息加密和解密的公钥加密系统，以及一个数字签名方案。

公钥密码体制的基本思想是使用 Diffie-Hellman 密钥交换的基础

首先，通信双方选择一个大质数和生成元，这些参数都是公开的

然后双方分别选取自己的私钥（分别是和），并计算相应的公钥然后就可以计算共享的公钥

这提供了一个安全的共享密钥，但计算此密钥的过程难度等同于计算离散对数。该系统的加密过程与Diffie-Hellman方案相关，但使用了随机数来加密每条消息，从而避免了密文重放攻击。解密过程中，接收方根据私钥恢复密钥并解密消息

ElGamal提出的数字签名方案依赖于消息的签名和验证。具体来说，签名生成过程如下：

验证方只需使用公钥和签名来验证以下等式：

签名方案的安全性依赖于离散对数问题的计算难度。ElGamal指出，攻击者试图伪造签名或推导私钥将面临离散对数问题的挑战。文章还讨论了在某些情况下可能的攻击方式，但大多无法打破系统的安全性

本质上就是用 DH 获得一个密钥，然后用它加解密消息。

详细代码见 ElGamal是个啥子玩意（和本篇论文内容不尽相同，但是殊途同归）

文章详细探讨了针对签名方案的可能攻击方式，并指出这些攻击大多数情况下等价于计算离散对数问题。虽然尚未严格证明破解此签名方案与计算离散对数之间的等价性，但已知的攻击方式都未能有效破坏该系统。

与其他基于整数分解问题的公钥系统（如RSA）相比，ElGamal系统在某些方面有所不同。

ElGamal离散对数问题的算法复杂性与因子分解问题类似，都是次指数级的复杂度。因此系统的安全性与RSA类似，公共文件的大小相对较大，但这是可接受的

RSA算法：
- 构造方法：通过选择两个大素数和，计算。公钥是，私钥是，其中是的模的逆元。
- 安全性：基于大数分解问题的困难性。
椭圆曲线密码学（ECC）：
- 构造方法：在椭圆曲线上定义操作，利用点加法和标量乘法生成公钥和私钥。
- 安全性：基于椭圆曲线离散对数问题的困难性，ECC提供了更小的密钥长度而保持相同的安全性。
ElGamal密码方案：
- 构造方法：基于离散对数问题。生成一个大素数和生成元，然后选择一个私钥计算公钥。
- 安全性：依赖于离散对数问题的复杂性。

安全性定义：
- 通常包括选择明文攻击（CPA）和选择密文攻击（CCA）的安全性。
安全性证明方法：
- 归约法：将密码方案的安全性归约到已知的难题上。例如，证明RSA的安全性可以归约到大数分解的难度。
- 随机预言机模型：假设存在一个理想的随机预言机，用于模拟加密和解密过程，从而分析方案的安全性。