P4454 [CQOI2018] 破解D-H协议 - 洛谷 (luogu.com.cn)终于做到密码学相关的啦好开心正好复习一下 BSGS学了这么多年的数论终于有用武之地这道题是板子很简单但我会拓展一些密码学、数论、群论相关内容自行选读。0.与解题无关Diffie-Hellman迪菲-赫尔曼密钥交换简称 D-H是一种在不安全通信信道上安全地交换加密密钥的密码学协议。大致流程双方公开约定两个数字一个大质数和一个底数原根。Enigma 选一个秘密数私钥计算把公钥发给 Ulrich。Ulrich 选一个秘密数私钥计算把公钥发给 Enigma。Enigma 计算Ulrich 计算由于模幂运算的交换律两者得出的是完全相同的。而外界黑客只知道想要算出就必须解决离散对数难题。在现有计算机能力下对大质数极其难解这就是 D-H 的安全性基石。概念解释原根Primitive Root也叫本原元。定义对于一个质数如果存在一个整数。使得的次方、次方、次方……一直到次方分别后得到的余数不重不漏地覆盖了到之间的所有整数。那么就是模的一个原根。初等数论定义设整数与模数互质阶是指让成立的最小正整数记作。在以上基础上的阶等于欧拉函数则称是模的原根。写成公式其中表示小于等于且与互质的正整数个数。另当为质数。群论定义是模乘法群​ 的生成元即这表示的幂次能遍历所有与互质的余数集合。模幂运算的交换律离散对数形如。因为操作导致结果并非连续而是在的余数域上不规律跳动。现有计算机与 D-H 的安全性离散对数在数学结构上是一个没有逆向公式的单向函数且其破译时间复杂度随着数据变大而指数级增长。但如果使用量子计算机能在多项式时间内快速求解离散对数。这也是为什么现在全球密码学界在大力推进后量子密码学PQC的原因。1.题意解读Diffie-Hellman 密钥交换过程中公开的信息有固定公开质数原根信道窃听得到要破解的是最终密钥已知但不知道私密的随机数或。破解思路只要算出其中一个私密数比如那么而就是以为底、的离散对数所以每组数据都是在解一个离散对数问题。BSGS 就是专门用来求解中的算法。它的时空复杂度都是。本题数据范围用 BSGS 轻松过。PS本人还是认为题意很有意思有真的在破译密码的感觉。虽然只是 BSGS 板子某种意义上还有隐私安全教育环节。2.代码#includebits/stdc.h using namespace std; typedef long long LL; mapLL, LL mp; // a ^ x b (mod p) LL BSGS(LL a, LL b, LL p) { a % p; b % p; if (b 1) { // 特判 return 0; } mp.clear(); mp[b] 0; // 不走小步 LL m ceil(sqrt(p)); LL am a; for (LL j 1, t b; j m; j ) { t t * a % p; mp[t] j; am am * a % p; } for (LL i 1, t 1; i m; i ) { t t * am % p; if (mp.count(t)) { return i * m - mp[t]; } } return -1; } LL g, P; LL q_pow(LL a, LL b) { LL c 1; while (b) { if (b 1) { c c * a % P; } a a * a % P; b 1; } return c; } int main () { ios::sync_with_stdio(false); cin.tie(0); cin g P; int n; cin n; for (int i 1; i n; i ) { LL A, B; cin A B; LL a BSGS(g, A, P); LL K q_pow(B, a); cout K \n; } return 0; }