浅识RSA算法 |

RSA的历史

RSA加密算法是一种非对称加密算法，在互联网领域里被广泛使用。RSA是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。

RSA的具体原理

RSA主要利用了极大整数的因数分解的难度来保证算法的可靠性。

产生公钥和私钥

随便选择两个大的质数$p$和$q$，计算$N=p \cdot q$
利用欧拉函数，求得$r=\varphi((N)=\varphi((p) \cdot \varphi((q) = (p-1) \cdot (q-1) $
选择一个数$e$，满足$1 < e < r$且$e$与$r$互质，取$e$关于$d$的模逆元$d$,满足$ed \equiv {1 \bmod {r}}$
销毁$p$和$p$

现在$(N,e)$是公钥，$(N,d)$是私钥。

加密消息

假设Alice想要给Bob发送一条信息$m$，那么Alice有两步需要做：

把$m$按照一定规则转化成非负整数$n$，如果太长可以分几段加密
将$n$加密为$c$ $c \equiv { n^e\bmod N}$

然后就可以把$c$发送给Bob了。

解密消息

Bob接受到消息之后，就可以利用密钥$d$来解码

$n \equiv {c^d \bmod N}$

取到$n$之后，就可以按照约定的$m$转换成$n$的规则，倒回去得到$m$。

RSA的简单实现

###朴素欧几里得算法

def gcb(a,b):
    if b == 0 :
        return a 
    else:
        print(b,a%b)
        return gcb(b , a%b)

### 拓展欧几里得算法
### 根据１所述，设a,b的最大公约数为gcd(a,b),则存在整数x,y使得gcd(a,b)＝ax+by。扩展欧几里得则是用来求出这个x,y的，并且同时可以求出a,b的最大公约数
###  $$ \begin{cases} x_1=y_2 \\ y_1=x_2-(n/m) \cdot y_2 \end{cases} $$

def ex_gcb(a,b):
    if b == 0:
        return 1,0
    else:
        x,y = ex_gcb(b,a%b)
        return y,(x-(a//b)*y)

1	ex_gcb(43,23)

(-8, 15)

###  蒙哥马利幂模运算
### (a*b)%n = (a%n*b%n)%n

#整数转化为二进制
def int2Bin(n):
    binlist=[]
    while n!=0:
        binlist.append(n%2)
        n >>= 1
    return binlist
    
# 蒙哥马利幂模运算 a^d%n 
def modExp(a,d,n):
    binlist = int2bin(d)
    res = 1  
    for i in binlist:
        if i :
            res = ( res * a ) % n 
        a = ( a * a ) % n
    return res


modExp(2,16,7)

# 检测大整数是否是素数,如果是素数,就返回True,否则返回False
# 来自网上大佬的代码
# 素数生成逻辑 还是有点问题

import random
def rabin_miller(num):
    s = num - 1
    t = 0
    while s % 2 == 0:
        s = s // 2
        t += 1

    for trials in range(5):
        a = random.randrange(2, num - 1)
        v = pow(a, s, num)
        if v != 1:
            i = 0
            while v != (num - 1):
                if i == t - 1:
                    return False
                else:
                    i = i + 1
                    v = (v ** 2) % num
    return True


def is_prime(num):
    # 排除0,1和负数
    if num < 2:
        return False

    # 创建小素数的列表,可以大幅加快速度
    # 如果是小素数,那么直接返回true
    small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
    if num in small_primes:
        return True

    # 如果大数是这些小素数的倍数,那么就是合数,返回false
    for prime in small_primes:
        if num % prime == 0:
            return False

    # 如果这样没有分辨出来,就一定是大整数,那么就调用rabin算法
    return rabin_miller(num)


# 得到大整数,默认位数为1024
def get_prime(key_size=1024):
    while True:
        num = random.randrange(2**(key_size-1), 2**key_size)
        if is_prime(num):
            return num

1	get_prime(1024)

162678631691829774667522629535073160955825399182602693661545242792106676238539472548234877060876228787484523858207867783251387491999600134388980090439045215608645863076210778718260527620108430686424624076200773582708629154239529895125774945352642184329001660453968578704168280059308704550631900163173081902239

def gen_key(p,q):
    N = p * q  # 计算N
    r = (p-1) * (q-1) # 计算r 
    e = 65537 # 取e
    d,x = ex_gcb(e,r) ### ed \equiv { 1 \pmod r} -> ed + yn = 1 ，类似于扩展欧几里得形式
    d = abs(d)
    return e,d,N

def encrypt(m,N,e):
    return modExp(m,e,N)
    
def decrypt(c,N,d):
    return modExp(c,d,N)

## 测试整体过程

p,q = get_prime(1024),get_prime(1024)
m = 1995101219950817
e,d,N = gen_key(p,q)

enc = encrypt(m,N,e)
res = decrypt(enc,N,d)

if res == m :
    print('解密成功')
    print('密文是%d'%(enc))
    print('明文是%d'%(res))
else:
    print('加密失败')

解密成功
密文是14005144118830483850652822657072015923931651283373191007705567320344608498783170654858772312139590781517022245572740058228425238815700795267975461803686242362890194249947123896021635220125683107528036663909234677369590244069330529163467280287893994970335492795549817696086606381221855273000994999391165045098621373956100419478927732414261552853418860553749988881775967955441571219829233196014735356284125413142119509579602440902130879271195998880056144148006467107689489924816408971514890284627704928072054400838999570987152631984324906697106158618432179795774465341559150912656124918370457081515488677503660447595363
明文是1995101219950817

浅识RSA算法