摘要部分

理论部分

已有成果研究

Keccak 自诞生以来，经历了密码学界广泛的分析，全世界各高校与机构的研究对有关 Keccak 算法（及其相关的衍生算法）的研究成果以及 Keccak 团队的密码学分析被汇总在 Team Keccak 网站中，以方便研究者们相互讨论学习。另外该网站上还长期开放着 Keccak 原像与碰撞攻击挑战赛（The Keccak Crunchy Crypto Collision and Pre-image Contest），目前最好的原像攻击成果是 4 轮指定像值的攻击 ，由新加坡南洋理工大学郭建博士的和中国科学院信息工程研究所刘美成副研究员于 2016 年 12 月提交。从目前看，现有的 Keccak 密码分析仍集中在缩减论述后的 Keccak 算法，并不能威胁到其实际应用时的安全性。由于本次赛题二是对具备前缀 0 特征的 Keccak256 哈希值求其原像，求解过程更接近于密码分析中的原像攻击，已有的研究成果如下：

早期代表性的研究有，2011 年 Naya-Plasencia 等人提出了低轮 Keccak 算法的可行攻击方式，其中包括 2 轮 Keccak-256 第二原像的攻击方式（复杂度为\(O(2^{33})\)），以及 Morawiecki 等人于 2010 至 2013 年的一系列工作，包括基于 SAT 求解器的密码分析旋转密码分析，并据此完成了 Keccak 原像与碰撞攻击挑战赛中的 3 各 2 轮指定像值的原像攻击。

通过构造满足一些代数性质的形式来进行密码攻击的方式在后来被开发出来，拓宽了 Keccak 密码分析的思路并推进了其他 Keccak 实例的原像攻击进程。2016 年 Guo，Liu 和 Song 提出了“线性结构”（Linear Structure）的原像攻击设计思路并发现了最高达 4 轮的 Keccak 攻击方法。应用该结构，可在现实时间内实现 2 轮 Keccak-256（即 Keccak[1088,512]）的原像攻击（复杂度为\(O(1)\)），3 轮 Keccak[640,160]的原像攻击（复杂度为\(O(2^7)\)）和 3 轮 Keccak[1440,160]的原像攻击（复杂度为\(O(1)\)），同时也使另外一些形式的 Keccak 实例的原像攻击理论复杂度降低，如 3 轮 Keccak-256（复杂度为\(O(2^{192}\))），3 轮 Keccak-512（复杂度为\(O(2^{482})\)）以及 4 轮 Keccak[1440,160]（复杂度为\(O(2^{54})\)）。

在此之后 2017 年由 Li 等人提出“交叉线性结构”（Cross-Linear Structure），并将其应用在一些 Keccak 实例的原像攻击中，成功完成 3 轮 Keccak[240,160]的可行原像攻击（复杂度为\(O(2^{45})\)）。在这之后，Li 和 Sun 又发现了进一步优化复杂度的方法，将攻击过程划分为离线阶段与在线阶段两个子过程，成功实现 3 轮 Keccak-224 的可行原像攻击（复杂度为\(O(2^{39.39})\)）。

工具部分

NTL 数论库

NTL 数论库介绍

NTL 是由纽约大学 Victor Shoup 主持编写并维护的一个高性能可移植 C++库，该库提供了相当多的数据结构和算法用于数论研究中矢量，矩阵和多项式的计算。NTL 库在性能上非常优秀，其实现的多项式算法是目前世界上最快的可用方法之一，并已经成为建立多项式分解和确定椭圆曲线的“世界纪录”。

NTL 数论库使用 常用基本类

• ZZ: 大整数
• ZZ_p: 模 p 大整数
• GF2: 模 2 整数
• ZZX: ZZ 单变量多项式
• ZZ_pX: ZZ_p 大整数单变量多项式
• GF2X: GF2 单变量多项式
• ZZ_pE: 大整数环/域扩张
• GF2E: 模 2 整数环/域扩张
• ZZ_pEX: ZZ_pE 单变量多项式
• GF2EX: GF2E 单变量多项式 支持的运算符重载，其中%，%=只对大整数和其对应的多项式有意义。

+， -， (unary) -， +=， -=， ++， —， *， *=， /， /=， %， %=

向量和矩阵，NTL 向量与 C++ STL 中的向量实现类似，类命名方式为对应基本类前加‘vec’前缀和‘mat’前缀

• vec_ZZ
• vec_GF2
• mat_GF2

多项式常用函数

• IsIdent 单元矩阵判断
• transpose 矩阵转置
• solve 解矩阵方程（高斯消元法）
• inv 矩阵求逆

并行编程

CUDA 并行编程

CUDA (Compute Unified Device Architecture，统一计算架构) 是 NVIDIA 提出，可在 NVIDIA 图形处理器进行并行计算的计算环境。程序设计这可以利用 CUDA 的 C 语言扩充 (extension) 直接编程，CUDA 会将运费算分配到大量线程(threads)以及图形处理器中数以百计的计算核心中(cores)。

GPU 不是独立的计算平台，需要与 CPU 协同工作。我们常说的用 GPU 并行计算时，其实是指 CPU+GPU 的异构计算架构。CPU 所在位置为主机端（host），而 GPU 所在位置成为设备端（device）。

典型的 CUDA 程序的执行流程如下：

1. 分配 host 内存，进行数据初始化（initalize）
2. 分配 device 内存，host => device 内存拷贝
3. 调用 CUDA 和函数，（GPU 上）完成指定运算
4. 讲 device 上的运算结果拷贝回 host
5. 释放 host 和 device 的内存。

CUDA 这个异构模型通过函数类型限定词开区别 host 和 device 上的函数，主要的三个函数类型限定词如下:

• __global__：在 device 上执行，从 host 中调用（一些特定的 GPU 也可以从 device 上调用），返回类型必须是 void，不支持可变参数，不能成为类成员函数。注意用__global__定义的 kernel 是异步的，这意味着 host 不会等待 kernel 执行完就执行下一步。
• __device__：在 device 上执行，单仅可以从 device 中调用，不可以和__global__同时用。
• __host__：在 host 上执行，仅可以从 host 上调用，一般省略不写，不可以和__global__同时用，但可和__device__同时使用，此时函数会在 device 和 host 都编译。

OpenMP 并行编程

OpenMP（Open Multi-Processing）是一套支持跨平台共享内存方式的多线程并发的编程 API，使用 C,C++和 Fortran 语言，可以在大多数的处理器体系和操作系统中运行，包括 Solaris, AIX, HP-UX, GNU/Linux, Mac OS X, 和 Microsoft Windows。包括一套编译器指令、库和一些能够影响运行行为的环境变量。

OpenMP 采用可移植的、可扩展的模型，为程序员提供了一个简单而灵活的开发平台，从标准桌面电脑到超级计算机的并行应用程序接口。

混合并行编程模型构建的应用程序可以同时使用 OpenMP 和 MPI，或更透明地通过使用 OpenMP 扩展的非共享内存系统上运行的计算机集群。

OpenMP 是由 OpenMP Architecture Review Board 牵头提出的，并已被广泛接受的，用于共享内存并行系统的多线程程序设计的一套指导性注释（Compiler Directive）。OpenMP 支持的编程语言包括 C 语言、C++和 Fortran；而支持 OpenMP 的编译器包括 Sun Studio 和 Intel Compiler，以及开放源码的 GCC 和 Open64 编译器。OpenMP 提供了对并行算法的高层的抽象描述，程序员通过在源代码中加入专用的 pragma 来指明自己的意图，由此编译器可以自动将程序进行并行化，并在必要之处加入同步互斥以及通信。当选择忽略这些 pragma，或者编译器不支持 OpenMP 时，程序又可退化为通常的程序（一般为串行），程序码仍然可以正常运作，只是不能利用多线程来加速程序执行。

结果部分

等待完善