By

Contents
  1. 1. 前言
  2. 2. 简介
  3. 3. 原理
  4. 4. 代码

前言

密码学作业之RSA

简介

RSA公开密钥密码体制。所谓的公开密钥密码体制就是使用不同的加密密钥与解密密钥，是一种“由已知加密密钥推导出解密密钥在计算上是不可行的”密码体制。

原理

RSA 算法的可靠性基础：对极大整数做因数分解是很困难的。
RSA 是非对称算法，加解密使用不同的密钥。
两个密钥都可以用于加密，解密时需要使用另一个密钥。但是，通常用公钥加密私钥解密，因为公钥是近乎完全公开的，对于私钥加密的数据，有太多的人可以解密了。理论上 A 和 B 之间要通过 RSA 实现保密通信，需要 A 和 B 各自生成一组密钥，同时保管好自己的私钥；用对方的公钥加密要发送的消息，用自己的私钥解密对方发送过来的消息。

加密公式：
c=me mod n
解密公式：
m=cd mod n

加密过程：
（1） 获得接收方公钥（e,n）
（2） 把消息m分组为长度为L的消息分组
（3） 使用上面加密算法计算出密文
（4） 将密文c发送给接收方

解密过程:
（1） 接收方收到明文c
（2） 使用私钥d和上面的解密算法逐一恢复明文分组
（3） 得到明文消息m

生成公钥和私钥:

（1）随意选择两个大的质数 p 和 q，p 不等于 q，计算 N=pq。
（2）根据欧拉函数，求得 r=φ(N)=φ(p)φ(q)=(p−1)(q−1)
（3）选择一个小于 r 的整数 e，使 e 与 r 互质。并求得 e 关于 r 的模反元素，命名为 d（求 d 令 ed≡1(modr)）。（模反元素存在，当且仅当 e 与 r 互质）

将 p 和 q 的记录销毁
(N,e) 是公钥， (N,d)(N,d) 是私钥。公钥发送给所有的通信对象（对服务器来说就是所有的客户端），私钥则必须保管好，防止泄露。

核心代码
扩展欧几里得算法求模反元素

1
2
3
4
5
6
7
8
9
10
def ex_euclid(a, b, list):
    if b == 0:
        list[0] = 1L
        list[1] = 0L
        list[2] = a
    else:
        ex_euclid(b, a % b, list)
        temp = list[0]
        list[0] = list[1]
        list[1] = temp - a / b * list[1]

求模反元素

1
2
3
4
5
6
7
8
def mod_inverse(a, b):
    list = [0L, 0L, 0L]
    if a < b:
        a, b = b, a
    ex_euclid(a, b, list)
    if list[1] < 0:
        list[1] = a + list[1]
    	   return list[1]

快速幂模运算，把b拆分为二进制，遍历b的二进制，当二进制位为0时不计入计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def quick_pow_mod(a, b, c):
    a = a % c
    ans = 1
    while b != 0:
        if b & 1:
            ans = (ans * a) % c
        b >>= 1
        a = (a % c) * (a % c)
    	   return ans

def miller_rabin_witness(a, n):
    if n == 1:      # n为要检验的大数，a < n,k = n - 1
        return False
    if n == 2:
        return True
    k = n - 1
    q = int(math.floor(math.log(k, 2)))
    while q > 0:
        m = k / 2 ** q
        if k % 2 ** q == 0 and m % 2 == 1:
            break
        q = q - 1
    if quick_pow_mod(a, n - 1, n) != 1:
        return False
    b1 = quick_pow_mod(a, m, n)
    for i in range(1, q + 1):
        if b1 == n - 1 or b1 == 1:
            return True
        b2 = b1 ** 2 % n
        b1 = b2
    if b1 == 1:
        return True
    	   return False

Miller-Rabin素性检验算法,检验8次

1
2
3
4
5
6
7
def prime_test_miller_rabin(p, k):
    while k > 0:
        a = random.randint(1, p - 1)
        if not miller_rabin_witness(a, p):
            return False
        k = k - 1
    		   return True

判断 num 是否与 prime_arr 中的每一个数都互质

1
2
3
4
5
6
def prime_each(num, prime_arr):
    for prime in prime_arr:
        remainder = num % prime
        if remainder == 0:
            return False
    return True

正确性分析
ϕ(n)=(p−1)(q−1) 成立的正确性，ϕ(n)表示小于n且与n互质数的个数则小于等于n且与n非互质的数的个数为，n-ϕ(n) = n - (p-1)*(q-1) = n - (pq-q-p+1) = n-n+p+q-1 = p+q-1所以只要证明小于等于n且与n非互质的数的个数为p+q-1即能证明ϕ(n)=(p−1)(q−1) ：这点很容易证明，由于n只有两个素因子p，q。则所有与n非互质的数都可以写成p*x或q*x，对于p*x来讲，x的取值范围为1<=x<=q，对q*x来讲x的取值范围为1<=x<=p，p*x与q*x的唯一交集为p*q，所以结论成立。

合理性分析
RSA是目前最有影响力和最常用的公钥加密算法，它能够抵抗到目前为止已知的绝大多数密码攻击，已被ISO推荐为公钥数据加密标准。今天只有短的RSA钥匙才可能被强力方式解破。只要其钥匙的长度足够长，用RSA加密的信息实际上是不能被解破的。
但是RSA还是有缺陷的：
（1）产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。
（2）安全性，RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价，而且密码学界多数人士倾向于因子分解不是NP问题。
（3）速度太慢，由于RSA 的分组长度太大，为保证安全性，n 至少也要 600 bits以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级;且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。

安全性分析
RSA的安全性依赖于大数分解，这样攻击RSA系统的难度就是大整数因子分解的难度，一般认为这是一个NPC问题，但是否等同于大数分解一直未能得到理论上的证明，因为没有证明破解RSA就一定需要作大数分解。假设存在一种无须分解大数的算法，那它肯定可以修改成为大数分解算法。 RSA 的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最显然的攻击方法。人们已能分解多个十进制位的大素数。因此，模数n必须选大一些，因具体适用情况而定。
攻击方法：
（1） 共模攻击
（2） 分析RSA锁结构
（3） 素因子的分解
若用1台1 s能进行1亿次因子分解的高速计算机来计算，分解十进制长度为200位的n，其所需时间为3 800 000年.由此可见，对于RSA系统，如果用一个长度为200位（十进制）的n，认为它是比较安全的，如果n的长度更长，因子分解越困难，一般来说，每增加10位二进制数，分解的时间就要加长1倍.密码就越难以破译，加密强度就越高

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#coding:utf-8
import base64
import random

str1 = "abcdefg"

e = 65537	#公钥

#快速幂 大大减少了计算幂的时间复杂度
def quick(a,b,n):
	ans = 1
	a = a%n
	while b!=0:
		if b&1==1:
			ans = (ans*a)%n
		b>>=1
		a = (a*a)%n
	return ans

#Miller—Rabin素性判断
def miller_rabin(n,k=80):
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False
    r, s = 0, n - 1
    while s % 2 == 0:
        r += 1
        s //= 2
    for _ in xrange(k):
        a = random.randrange(2, n - 1)
        x = pow(a, s, n)
        if x == 1 or x == n - 1:
            continue
        for _ in xrange(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

def proBin():
	while True:
		p = "1"
		for i in range(0,1022):
			p = p+str(random.randint(0,1))
		p = p+"1"
		p = int(p,2)
		if miller_rabin(p):
			return p

#求模拟，用扩展欧几里得除法
def modReserse(a,m):
	u1,u2,u3 = 1,0,a
	v1,v2,v3 = 0,1,m
	while v3!=0:
		q = u3//v3
		v1,v2,v3,u1,u2,u3 = (u1-q*v1),(u2-q*v2),(u3-q*v3),v1,v2,v3
	return u1%m

def encrypt(m,n):
	c = str(quick(int(m),e,n))
	return c

def decrypt(c,p,q):
	n = p*q
	d = modReserse(e,(p-1)*(q-1))
	m = str(quick(int(c),d,n))
	return m

if __name__ == '__main__':
	m = base64.b16encode(str1)
	p=proBin()
	q=proBin()
	print 'p=',p
	print 'q=',q
	n = p*q
	c = encrypt(m,n)
	print "Encrypt："
	print c
	m = decrypt(c,p,q)
	print "Decrypt："
	print base64.b16decode(m)
Contents
  1. 1. 前言
  2. 2. 简介
  3. 3. 原理
  4. 4. 代码