《A Graduate Coursse in Applied Cryptography》chapter 10 public key tools （1）

朴灿烈づ我的快乐病毒、 2023-01-13 09:27 98阅读 0赞

# 《A Graduate Coursse in Applied Cryptography》chapter 10 public key tools（1） #

*原文教材：*

*        Boneh D, Shoup V. A graduate course in applied cryptography\[J\]. Recuperado de https://crypto. stanford. edu/~ dabo/cryptobook/BonehShoup\_0\_4. pdf, 2017.*

*Boneh D, Shoup V. A Graduate Course in Applied Cryptography\[J\].*

**10.1 A toy problem: anonymous key exchange**

本小节构造了一个简单而不完善的密钥交换协议作为公钥密码学的引言，协议模型如下;

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70][]

安全模型如下描述：

挑战者在参与方A与B之间运行该协议，协议结束时将整个协议运行阶段的交互信息发送给敌手，如果敌手能够以不可忽略的优势得到目标秘密信息k，则敌手获胜。

安全模型的不足之处：

1.敌手这里是窃听敌手，非恶意敌手不具有修改信息的能力。

2.模型要求敌手不能完整猜测目标秘密信息，但是不能排除敌手可以获取一些有效信息比特。

3.该协议不能保证参与方的真实身份，是匿名(anonymous)的协议。

**10.2 One-way trapdoor function**

本小节通过使用单向陷门函数设计了一个简单的密钥交换协议，该协议如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 1][]

整个协议非常的简单，使用公钥密码思想设计了一个密钥交换协议。

安全模型：

挑战者运行Alice-Bob系统，将<pk,y>发送给敌手，敌手如果能够正确计算得出目标秘密值x,则敌手获胜。

安全模型不足之处：

再上一节提出的三个不足依然存在，该模型仅为一个演示demo, 不具有任何可行性。

陷门函数协议的形式化定义：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 3][]

值得注意的是，一个陷门函数形式化的定义要求：X的集合是根据安全参数而定义的，即整个协议系统定基于系统参数。

**10.3 A trapdoor permutation scheme based  on RSA**

RSA方案是最为著名与经典的一个密码学方案：普遍认为RSA问题是基于大数分解困难问题的协议。

该教材给出了一个简单的基于RSA方案的密钥交换协议描述如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 4][]

这里关于RSA方案有两个需要注意的点：

1.RSA方案并不是不是完全吻合陷门置换协议，因为其X定义域会随着公钥的改变而变化，但是这是可以修改为符合陷门置换协议的版本。

2.RSA方案要求生成两个大素数，生成素数的方法可能不一定在期待的多项式时间生成，涉及素性检验问题，如果生成素数失败，那么方案也就失败了。

**10.4 Diffe-Hellmen key exchange**

本节描述了一个基于离散对数的密钥交换协议diffe-hellmen假设：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 5][]

Diffie-Hellman 密钥交换协议亦被称作基于“CDH假设”，是关于离散对数假设的限制衍生品。

PS：离散对数问题可以参考该书附录、《现代密码学》、《信息安全数学基础》等基本教材内容。

**10.5  Discrete  logarithm and related assumptions**

本节主要描述了几个基本的困难问题：

DL离散对数问题，CDH问题，DDH问题，进一步介绍了CDH假设，DDH假设等，都是比较基础的密码学知识，不在赘述。

假设和问题在表述上还有一定的区别，问题只是困难问题的一个实例，是问题的表述。假设则是定义敌手获胜的概率是可忽略的，是对该问题以一种什么样的概率解决的假设，所以称之为假设。

随机自规约：

将一个给定的困难问题实例映射到一个随机的该困难问题实例，就称之为随机自规约。

随机自规约的目的：

为了证明最坏情况下困难问题的难度和平均问题下解决该困难问题的难度是相同的。如果一个困难问题在某些输入下是简单的，在某些输入下是困难的，那么该困难问题就无法作为一种密码学适宜的困难问题。如果一种困难问题能够实现随机自规约，即其在特定的困难问题实例的解决概率与均匀选择的困难问题的实例解决概率相同，则该困难问题是适用于密码学的。毕竟，一座桥的坚固程度取决于最薄弱的一环。格的困难问题就是一类典型的可以自规约的困难问题。

单词表：

emerge:<vi> 浮现，摆脱                                plausibly:<adv> 似真的                              exponent:<n> 指数                                    fancy<n,v,adj> 喜爱，幻想，精致

en-route: 在途中                                             property<n> 性质，性能                            wrinkle:<n>皱纹                                        convention<n> 大会，约定

onset:<n> 开始，发作                                    quantity<n> 数量                                        quite fit: 很合适                                         namely:插入语，即

tamper: <v> 做手脚，破坏 ；<n> 夯土          domain & range: 定义域与值域                  accommodate: <n> 容纳，泛化                fraction:<n> 分数，部分

anonymous:<adj> 匿名的                               conjecture: <n> 推测                                  recase<n/vt>重铸                                     attractive:<adj> 吸引

rule out：排除                                                 explicit:<n> 明确                                        alternatively:<n> 要不，或者，二选一

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70]: /images/20221022/9ca2827146e34494a0fd676aa68722b0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 1]: /images/20221022/1fb7d9a29ee04ae39f34a228e2f65815.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 2]: /images/20221022/f66616ce1eba4c1aae0d7764574a2448.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 3]: /images/20221022/979e38864b4d47d7b85bc5fab97b4dac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 4]: /images/20221022/6793e9329327482c86b8d914e8bf7046.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 5]: /images/20221022/2c9ba13cc6334f7d83738d9b7a17b738.png