密码学算法笔记type
status
date
slug
summary
tags
category
icon
password
柯克霍夫原则 ( Kerckhoff ’s Principle ) : 除了密钥之外，即使密码系统的一切均被公开，它仍然应当是安全的香农箴言 ( Shannon’s Maxim ) : 敌人了解系统
引理
(1) 对于整数 p,q 和正整数 r, 有：
证明：设 则
Diffie-Hellman 密钥协商
公开大素数 p 和整数 g，g 为 p 的原根
若 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 互质, 由费马小定理:则显然如此 , 根据中国剩余定理:即
- 作者:Dale
- 链接:http://www.dalechu.cn/article/crypto
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
