RSA加密算法一:历史与数学原理

一、历史

在1976年以前,所有的加密算法都是使用对称加密思想。

A 明文– 加密算法1  –> 密文 –>发送给B

B 密文 — 解密算法1(基于加密1)–> 明文

加密和解密使用相同的密钥,故称作对称加密算法

此种方法依赖于AB两个人都知道加密算法,并且安全的传递密钥。

然后在1976年,两位美国数学家、计算学家 Whitfield Diffie 和 Martin Hellman 提出了著名的 Diffie-Hellman密钥交换算法   也就是DH算法

根据发表的论文,对其他数学家和计算机学家带来很大的启发,由此产生了 非对称加密算法

基本过程是:

(1)A –> 生成公钥和私钥 –> 发送B公钥(私钥A保留)

(2)B –> A公钥加密 –> 密文 –> 发送给A

(3)A –> A私钥解密 –> 明文

算法思想就是:产生公私钥对,公钥是公开的,任何人都可以得到,私钥是自己保留的,密文只有私钥才能解开,算法安全性依赖于私钥保密性。

基于此思想,在1977年,三位数学家Rivest、Shamir 和 Adleman 设计了一种算法,也就是 RSA算法

算法的密钥通常有1024位,更高安全要求的有2048位

扩展:

1973 年 9 月,年仅 26 岁的数学家 Clifford Cocks 听说非对称加密思想后,在完全不了解状况的心理状态下花不到半小时就找到了 Rivest 他们苦思冥想的方案。限于政府保密项目,直到1997 年底,时隔二十余年,这件事情才被公之于众。

二、数学原理

下面重点讲一下RSA算法的数学原理,主要使用的是数论知识

1、互质关系

定义:如果两个正整数,除了1之外,没有其他公因子,这两个数就是互质关系(coprime)

根据互质关系的定义,有六个推导结论:

(1)任意两个质数构成互质关系

(2)一个数是质数,另一个数不是次数的倍数,则两者互质

(3)两个数中较大的数是质数,则两者互质

(4)1和任意自然数都互质

(5)p为大于1的质数,则 p与 p-1 互质

(6)p为大于1的奇数,则 p 与 p-2 互质

2、欧拉函数

定义:正整数n,小于n的正整数中与n互质的数的个数,记做 φ(n)

例如 n = 8 ,有1,3,5,7与8互质,则 φ(8) = 4

如何计算φ(n)?

(1)n = 1 时,φ(1) = 1

(2)n为质数,则 φ(n) = n-1

(3)n为质数的某次方,即 n = p^k(p质数,k>=1)

(4)如果n = p1*p2(p1,p2互质)     (证明:中国剩余定理)

则φ(n) = φ(p1p2) = φ(p1)φ(p2)

(5)任意一个正整数n的因式分解可以得到

    (欧拉函数通用公式)

3、欧拉定理

定义:如果两个正整数a和n互质,则n的欧拉函数φ(n) 满足如下等式

应用:

欧拉定理可以大大简化某些计算

比如,7和10互质,根据欧拉定理有:

已知 φ(10) 等于4,所以马上得到7的4倍数次方的个位数肯定是1。

因此,7的任意次方的个位数(例如7的222次方)都可以简单算出来。

欧拉定理有一个特殊情况

假设正整数a与质数p互质,因为质数p的φ(p)等于p-1,则欧拉定理可以写成

   (费马小定理)

4、模反元素

定义:如果两个正整数a与n互质,则一定可以找到整数b,使得 ab-1 被n整除,或者 (a*b) mod n == 1

称b为a的模反元素

欧拉定理可以用来证明模反元素的必然存在性

a的 φ(n)-1 次方,就是a的模反元素。a的 φ(n)-1 次方,就是a的模反元素

并且,如果b是a的模反元素,则 b+kn 都是a的模反元素。

参考资料:

(1)阮一峰的网络日志

(2)《深入浅出密码学–常用加密原理与应用》

扩展阅读:

(1)Crypto: How the Code Rebels Beat the Government–Saving Privacy in the Digital AgeCrypto: How the Code Rebels Beat the Government–Saving Privacy in the Digital Age

(2)The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography

您可能还喜欢...