密码学算法笔记type
status
date
slug
summary
tags
category
icon
password
柯克霍夫原则 ( Kerckhoff ’s Principle ) : 除了密钥之外，即使密码系统的一切均被公开，它仍然应当是安全的香农箴言 ( Shannon’s Maxim ) : 敌人了解系统
mod 运算的性质
(1) 对于整数 p,q 和正整数 r, 有：
证明：设 则
(2) 对于整数 p,q 和正整数 r, 有：
证明：设
则
Diffie-Hellman 密钥协商
公开大素数 p 和它的原根 g
若 g 是模 p 的原根，那么 g 的幂模 p 可以生成模 p 的乘法群 的所有元素即使用原根 g 可以保证此算法的公钥在最大的范围内分布
Alice 随机选取 [1,p-2] 范围内的整数 a, 计算 ，发布 A 为公钥
Bob 随机选取 [1,p-2] 范围内的整数 b, 计算 ，发布 B 为公钥
Alice 计算
Bob 计算
, 即 Alice 与 Bob 协商后，计算出了相同的密钥
RSA 算法
选择两个大素数 p 和 q
计算 , 并公开 n
计算欧拉函数
选择公钥指数 e, 满足： 且 e 与 ϕ(n) 互质. 公钥即为 (en)
用扩展欧几里得算法计算私钥指数 d, 满足：. 私钥即为 (dn)
销毁 p、q、ϕ(n)
加密：
解密：
RSA 的数学原理
由于 , 设
下面分两种情况讨论:
(i) 当 与 互质时, 由欧拉定理:
显然,
易得
即
RSA 要求 , 所以
即
(ii) 若 与 非互质, 由于
根据算术基本定理, 一定是 p 的倍数或 q 的倍数
RSA 要求 , 所以 不可能是 p 和 q 的公倍数 (否则 )
不妨设 是 p 的倍数, 即 , 这时 与 q 互质
显然
与 q 互质, 由费马小定理:
则
显然
如此
由中国剩余定理:
即
综上：RSA 加解密在计算上是成立的
对 RSA 的选择密文攻击
RSA 具有同态性:
- 假设 是由 加密得到的, 攻击者想要解密
- 私钥持有者说：”我可以帮你解密 以外的其他任何密文，但就不给你解 ”
- 攻击者随便选了个数字 , 加密 得到 , 计算
- 攻击者对私钥持有者说，那你帮我解密 吧
- 私钥持有者说好的， 解密后的数字是
- 假设 , 根据 RSA 的同态性, 可知
- 攻击者计算 即得到
- 一般的， 与 n 的大小关系未知, 只能推导出
- 可利用扩展的欧几里得算法计算出 的乘法逆元
- 即
- 作者:Dale
- 链接:http://www.dalechu.cn/article/crypto
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
