密码学 |
您所在的位置：网站首页 › 扩展算法 › 密码学 |
密码学
|
一、前言
大学课程中，摆子们总是觉得密码学非常难学，那是因为密码学有一套完整的数学体系，这篇文章写的欧几里得扩展算法 学习前提是了解模的运算和欧几里得算法（辗转相除法） 二、欧几里得扩展算法首先以凯撒移位算法中的乘法算法为例 1、进行明文加密（不涉及欧几里得扩展算法）现在有一个26位字母表 (A~Z) 其中A的编号为'0'，Z的编号为'25'
我们创建明文 m = "CSDNZJHH" 以首字母C为例 C的序号为2 选择一个密钥k = 19 (密钥k的范围是1~25中，任意与26互素的整数，不一定是19，也可以是3、11、7.....) 然后运算 C*k mod 26的运算 2*19 mod 26 = 12 对照字母表中 序号12为M (A的序号是0) C在密钥为19的加密情况下 加密结果为M 同理对"CSDNZJHH"每一位单独加密 得出密文 s = "MEFNHPDD" 2、对密文进行解密（涉及欧几里得扩展算法） ①如何解密？由于咱们对明文进行加密的时候 加密公式是这样的
那么我们想要求 'C' 的话只需要改变一下式子就行了
M = 12 它再乘个19^(-1)这怎么乘啊？？ 原来19^(-1) (mod26)不等于 19^(-1)呀！ 那怎么求呢？ 上欧几里得扩展定理！ ②欧几里得扩展定理根据贝祖定理得出 gcd(k,26) = 1可以推导出 x*k + y*26 = 1 那么咱们就对整个式子进行mod 26
可以得到结论 x*k = 1(mod26) 式子变形一下 k^(-1) = x(mod26) 这里的k换成19 是不是一下就熟悉了？ 那我们只需要求x就能求出k^(-1)了 想求x 就只能从x*19 + y*26 = 1(mod26) 开始找起了 这时候就得用上欧几里得了（辗转相除）
这是推导gcd(19,26) = 1的式子 咱们只需要稍微变形一下
从下往上算！ 把所有出现在乘号之前的 2、5、7全换掉！（乘号后面的别换...） 只剩下26 19 1 ！ （别问为什么 因为要在式子：x*19 + y*26 = 1(mod26)里面找x 这式子里只有19 26 1） 下面是我的计算：
最后算出来了19*11-26*8 = 1 就相当于19*11 = 1(mod26) 那k^(-1)就等于11 也就是 密文'M' 序号12*11 mod 26 = 132 mod 26 132 mod 26 = 5*26 + 2 (mod 26) = 2 解密出密文'M'对应的明文序号就是2 也就是C！ 成功！ 三、总结 1、总结刚刚咱们已知k = 19 求 k^(-1)的情况叫做求k的逆元 求逆元的方法就叫做欧几里得扩展算法 我这里还有几个k和它对应的k^(-1) 你们可以计算一下 5^(-1) = 21 7^(-1) = 15 17^(-1) = 23 2、代码这是求逆元的代码（固定设置的模是26） #include #include // 扩展欧几里得算法，返回最大公约数，并通过指针传递 x 和 y int extendedGCD(int a, int b, int *x, int *y) { if (b == 0) { *x = 1; *y = 0; return a; } int x1, y1; int gcd = extendedGCD(b, a % b, &x1, &y1); *x = y1; *y = x1 - (a / b) * y1; return gcd; } // 计算乘法密钥的逆元 int multiplicativeInverse(int key, int m) { int x, y; int gcd = extendedGCD(key, m, &x, &y); // 如果 gcd 不是 1，表示 key 和 m 不互质，逆元不存在 if (gcd != 1) { printf("乘法密钥的逆元不存在（key 和 m 不互质）。\n"); exit(1); } // 确保结果在模 m 意义下为正 return (x % m + m) % m; } int main() { printf("请输入密钥："); int key = 0; // 乘法密钥 scanf("%d",&key); int modulus = 26; // 模数 // 计算乘法密钥的逆元 int keyInverse = multiplicativeInverse(key, modulus); // 输出结果 printf("%d 在模 %d 意义下的乘法逆元是: %d\n", key, modulus, keyInverse); return 0; }
|
【本文地址】
今日新闻 |
推荐新闻 |