admin

RSA加密算法
密码学之RSA加密RSA加密算法是一种非对称加密算法。在公开密钥加密和电子商业中RSA被广泛使用。RSA是1977...
扫描右侧二维码阅读全文
17
2018/09

RSA加密算法

密码学之RSA加密

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

根据密钥的使用方法,可以将密码分为对称密码和公钥密码
对称密码:加密和解密使用同一种密钥的方式
公钥密码:加密和解密使用不同的密码的方式,也被称作非对称密码

数学理论

在了解RSA算法之前需要了解一些数学基础理论

素数(质数)、合数、互质数
自然数中可以被2整除的数叫做偶数,省下的自然数称作为奇数。在奇数和偶数两大类下包含有素数、合数、0、1

素数:一个数如果除了1与它本身之外没有其他的因数,那么这个数就被称为素数(或者质数,取自英文单词prime的首字母)如:1,3,5,7,11......
合数:自然数中除了能被1和本身整除外,还能被其他数(0除外)整除的数 如 4、6、8、9、10...
互质数:两个或多个整数的公因数只有1的非零自然数 如2和3

欧拉函数

在数学中φ表示欧拉函数。φ(N)表示在所有比N小的自然数中,与N互质的数一共有多少个

欧拉定理

如果x与n互质那么有 xφ(n)% n = 1

RSA算法

RSA算法的实质是三个自然数:
n :模数(Modulus)

e :指数(exponent)

d:指数(exponent)

n和d构成一个密钥,n和e构成另一个密钥。对于(n, d)与(n, e)这两个密钥,无论用哪个密钥加密出来的密文都可以用另一个密钥解开。只要把公钥发出去,另一个作为私钥自己藏着就好了

生成RSA密钥

  1. 选择两个质数 p和q,则 n=p*q
  2. 计算 φ = (p-1) * (q-1)
  3. 选择一个比φ小且与φ互质的数
  4. 找到一个数d,使 e*d% φ = 1

这时得到的n、d、e就可以分组为公钥和密钥

RSA加密和解密

import math 
import random
import sys

#判断素数
def prime(n):
    for i in range(2,n):
        if n % i == 0:
            return False
    return True

# 获得素数列表maxnum为最大的取值范围

def get_prime(maxnum):
    temp_arr = []
    for i in range(2,maxnum):
        tem_num = prime(i)
        if tem_num:
            temp_arr.append(i)
    return temp_arr

# 获得比φ小且与φ互质的数e
def get_e(fac):
    while True:
        e = random.choice(range(100))
        temp = gcd(fac,e)
        if temp ==1 :
            break
    return e


#求最大公约数
def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a%b)

# 根据e*d% φ = 1获得d

def get_d(e,s):
    for d in range(sys.maxsize):
        if (e * d) % s == 1:
            return d

#生成密钥:
def encode_rsa():
    
    maxnum =int(input("输入一个最大范围值:"))
    #生成素数数组
    prime_arr = get_prime(maxnum)
    p = random.choice(prime_arr)
    q = random.choice(prime_arr)
    n = p * q
    s = (p-1)*(q-1)
    e =get_e(s)
    d = get_d(e,s)
    
    print("p is %d \n q is %d \n n is %d \n e is %d \n d is %d "%(p,q,n,e,d))
    print("公钥<n,e>:<",n,",",e,">")
    print("私钥<n,d>:<",n,",",d,">")
    #获得公钥和私钥
    pbk = (n,e)
    pvk = (n,d)
    enc_str = int(input("输入要加密的明文:"))
    
    enc_res = pow(enc_str,e)%n
    print("密文:",enc_res)
    return enc_res,pbk,pvk

def decode_rsa(encode_str,pvk):
    decode_res = pow(encode_str,pvk[1])%pvk[0]
    print("解密:",decode_res)
    return decode_res

if __name__ == '__main__':
    enc_str,pbk,pvk = encode_rsa()
    
    enc_str = int(input("输入解密的密文:"))
    decode_str = decode_rsa(enc_str,pvk)

CTF中rsa题型

  • 已知npqed

ed ≡ 1 (mod φ(n))所以可以求d的乘法逆元

python中有一个gmpy2的包,可以直接调用d = gmpy2.invert(e,φ(n)

山东网络安全竞赛选拔赛的Easy_RSA:

下载附件后有两个文件:

blog-180918-DG1eFIlJ1B

首先提取下public.pem的密钥参数可以使用openssl或者在线解析http://tool.chacuo.net/cryptrsakeyparse

blog-180918-f3HKjDlA4m

得到参数:

e : 65537

n:439AEAB34EAEE973E968EBDD11D6D3EF7302072C4BFD4F7FE2B0CF9889277F6D

把n转换为十进制:

>>> print(int('439AEAB34EAEE973E968EBDD11D6D3EF7302072C4BFD4F7FE2B0CF9889277F6D',16))
30578675145816634962204467309994126955968568987449100734690153203822106214253

使用http://factordb.com/或者yafu分解n得到p、q:

p:8767867843568934765983476584376578389

q:3487583947589437589237958723892346254777

接下来获得d并解密flag.enc:

import rsa

import gmpy



def get_info():

    p =8767867843568934765983476584376578389

    q =3487583947589437589237958723892346254777

    n =30578675145816634962204467309994126955968568987449100734690153203822106214253

    e = 65537
    #获得参数d
    d = int(gmpy.invert(e,(q-1)*(p-1)))
    #根据参数生成密钥
    prv_key = rsa.PrivateKey(n,e,d,p,q)
    #使用密钥解密内容
    with open('flag.enc','rb') as f:
        print("The content is :")
        print(rsa.decrypt(f.read(),prv_key).decode())

if __name__ == '__main__':

    get_info()

                                                                          

关于python中的rsa模块的使用在https://stuvel.eu/python-rsa-doc/自行查阅

blog-180919-75g6E492ef

Refer

RSA详解
CTF中常见的RSA相关问题总结

Last modification:January 26th, 2019 at 05:49 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment