[密码学基础][每个信息安全博士生应该知道的52件事][Bristol Cryptography][第36篇]Index Calculus算法

爱被打了一巴掌 2022-10-15 07:55 114阅读 0赞

> 这是一系列博客文章中最新的一篇，该文章列举了“每个博士生在做密码学时应该知道的52件事”:一系列问题的汇编是为了让博士生们在第一年结束时知道些什么。  
> 我们这篇博客继续描述一种数学攻击，这种数学攻击被叫做Index Calculus(IC)算法。

注意这里Index Calculus算法没有找到合适的中文翻译。因为原文不是很通顺，我加入了很多自己的话。

### 我们要做什么 ###

Index Calculus攻击是一种企图解决DLP（离散对数问题）的方法。简单来说，算法把目标值写成在因子基数上的元素幂的乘积，对数已知的元素，然后利用对数定律提取目标值。我们现在详细的解释刚才那句话是什么意思。

### 算法工作原理 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]

### （预计算，非常的快）选择一个因子基数 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]

### （预计算，昂贵的但是可以并行）找出因子基数和DLP问题之间的关系 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]

### （预计算，相对有效率）求因子基数的DLP结果 ###

![在这里插入图片描述][2021052410584090.png]

### （在线的，昂贵的）把h写成因子基数的乘积 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]

### 一个简要的总结 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 4]  
转载链接：https://www.cnblogs.com/zhuowangy2k/p/12245633.html

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: /images/20221014/e221ff785581456d89dd3004b5a06f0e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: /images/20221014/e94f30208cb04274a7fb28a5354a2142.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]: /images/20221014/8b34420dadcd4f888d5515678cf2c55c.png
[2021052410584090.png]: /images/20221014/0a003751c579432cb48ccd6bdd29e399.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]: /images/20221014/96b18468fcbb4657bd7e1aa0e1858d29.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 4]: /images/20221014/4a4c89a7acef46c885b17ae11b977061.png