精华内容
下载资源
问答
  • RSA 算法 python

    2021-04-03 22:07:34
    def RSA(p,q,m): print(f"1: p: {p} q: {q} M: {m}") n = p*q print(f"2: n = p*q {p} *{q} = {n}") temp = (p-1)*(q-1) print(f"3: (p-1)*(q-1) = {p-1} *{q-1} = {temp}") e = 1 print(f"4:e should be less than ...
    def RSA(p,q,m):
    
        print(f"1: p: {p} q: {q} M: {m}")
        n = p*q
        print(f"2: n = p*q {p} *{q} = {n}")
        temp = (p-1)*(q-1)
        print(f"3: (p-1)*(q-1) = {p-1} *{q-1} = {temp}")
        e = 1
        print(f"4:e should be less than n and relatively prime to (p-1)*(q-1) = {p-1} *{q-1} = {temp}")
        for _ in range(1,n):
            if temp%_ is not 0:
                e = _
                break
        print(f"Hence, e is {e}")
        print("5: Here, we should find an integer d such that e*d mod((p-1)*(q-1)) = 1")
        d = 1
        for _ in range(1,temp):
           if e*_ % temp == 1:
            d = _
            print(f"Here d = {_}")
            print(f"we have e*d mod((p-1)*(q-1)) = {e*d} mod {temp} = 1")
        print(f"6: Public key = (e,n) = ({e},{n})")
        print(f"7: Private key = (d,n) = ({d},{n})")
        encrypted = m**e%n
        print(f"Encrypted message: c = m^e mod n = {m}^{e} mod {n} = {encrypted}")
        decrypted = encrypted**d%n
        print(f"Decrypted message: m = c^d mod n = {encrypted}^{d} mod {n} = {decrypted}")
    
    
    
    RSA(p = 17,q = 31,m = 5)
    
    # print(160%2)

    运行结果:

    1: p: 17 q: 31 M: 5
    2: n = p*q 17 *31 = 527
    3: (p-1)*(q-1) = 16 *30 = 480
    4:e should be less than n and relatively prime to (p-1)*(q-1) = 16 *30 = 480
    Hence, e is 7
    5: Here, we should find an interger d such that e*d mod((p-1)*(q-1)) = 1
    Here d = 343
    we have e*d mod((p-1)*(q-1)) = 2401 mod 480 = 1
    6: Public key = (e,n) = (7,527)
    7: Private key = (d,n) = (343,527)
    Encrypted message: c = m^e mod n = 5^7 mod 527 = 129
    Decrypted message: m = c^d mod n = 129^343 mod 527 = 5
    [Finished in 0.6s]

    展开全文
  • RSA算法python实现

    2018-06-05 10:04:08
    使用python2.7写的RSA加密解密,支持超过10^10的大素数,可以加解密大于64位的明文,注释详尽。
  • RSA算法Python实现

    千次阅读 2016-04-26 09:18:19
    RSA算法是一种非对称加密算法,是现在广泛使用的公钥加密算法,主要应用是加密信息和数字签名。详情请看维基:http://zh.wikipedia.org/wiki/RSA%E5%8A%A0%E5%AF%86%E6%BC%94%E7%AE%97%E6%B3%95算法基本思路:1.公钥...

    RSA算法是一种非对称加密算法,是现在广泛使用的公钥加密算法,主要应用是加密信息和数字签名。详情请看维基:http://zh.wikipedia.org/wiki/RSA%E5%8A%A0%E5%AF%86%E6%BC%94%E7%AE%97%E6%B3%95

    算法基本思路:

    1.公钥与私钥的生成:

    (1)随机挑选两个大质数 p 和 q,构造N = p*q;

    (2)计算欧拉函数φ(N) = (p-1) * (q-1);

    (3)随机挑选e,使得gcd(e, φ(N)) = 1,即 e 与 φ(N) 互素;

    (4)计算d,使得 e*d ≡ 1 (mod φ(N)),即d 是e 的乘法逆元。

    此时,公钥为(e, N),私钥为(d, N),公钥公开,私钥自己保管。

    2.加密信息:

    (1)待加密信息(明文)为 M,M < N;(因为要做模运算,若M大于N,则后面的运算不会成立,因此当信息比N要大时,应该分块加密)

    (2)密文C = Me mod N

    (3)解密Cd mod N = (Me)d mod N = Md*e mod N ;

    要理解为什么能解密?要用到欧拉定理(其实是费马小定理的推广)aφ(n) ≡ 1 (mod n),再推广:aφ(n)*k ≡ 1 (mod n),得:aφ(n)*k+1 ≡ a (mod n)

    注意到 e*d ≡ 1 mod φ(N),即:e*d = 1 + k*φ(N)。

    因此,Md*e mod N = M1 + k*φ(N) mod N = M

    简单来说,别人用我的公钥加密信息发给我,然后我用私钥解密。

    3.数字签名:

    (1)密文C = Md mod N

    (2)解密M = Ce mod N = (Md)e mod N = Md*e mod N = M ;(原理同上)

    简单来说,我用自己的密钥加密签名,别人用我的公钥解密可以看到这是我的签名。注意,这个不具有隐私性,即任何人都可以解密此签名。

    算法的安全性:基于大整数N难以分解出p和q,构造φ(N);或由N直接构造φ(N)同样难。

    算法的实现:

    1.快速幂取模:http://www.cnblogs.com/7hat/p/3398394.html

    2.素性测试:http://www.cnblogs.com/7hat/p/3400831.html

    3.扩展欧几里得求乘法逆元和最大公约数:http://www.cnblogs.com/7hat/p/3406494.html

    实现代码:

    import random
    
    def fastExpMod(b, e, m):
        """
        e = e0*(2^0) + e1*(2^1) + e2*(2^2) + ... + en * (2^n)
    
        b^e = b^(e0*(2^0) + e1*(2^1) + e2*(2^2) + ... + en * (2^n))
            = b^(e0*(2^0)) * b^(e1*(2^1)) * b^(e2*(2^2)) * ... * b^(en*(2^n)) 
    
        b^e mod m = ((b^(e0*(2^0)) mod m) * (b^(e1*(2^1)) mod m) * (b^(e2*(2^2)) mod m) * ... * (b^(en*(2^n)) mod m) mod m
        """
        result = 1
        while e != 0:
            if (e&1) == 1:
                # ei = 1, then mul
                result = (result * b) % m
            e >>= 1
            # b, b^2, b^4, b^8, ... , b^(2^n)
            b = (b*b) % m
        return result
    
    def primeTest(n):
        q = n - 1
        k = 0
        #Find k, q, satisfied 2^k * q = n - 1
        while q % 2 == 0:
            k += 1;
            q /= 2
        a = random.randint(2, n-2);
        #If a^q mod n= 1, n maybe is a prime number
        if fastExpMod(a, q, n) == 1:
            return "inconclusive"
        #If there exists j satisfy a ^ ((2 ^ j) * q) mod n == n-1, n maybe is a prime number
        for j in range(0, k):
            if fastExpMod(a, (2**j)*q, n) == n - 1:
                return "inconclusive"
        #a is not a prime number
        return "composite"
    
    def findPrime(halfkeyLength):
        while True:
            #Select a random number n 
            n = random.randint(0, 1<<halfkeyLength)
            if n % 2 != 0:
                found = True
                #If n satisfy primeTest 10 times, then n should be a prime number
                for i in range(0, 10):
                    if primeTest(n) == "composite":
                        found = False
                        break
                if found:
                    return n
    
    def extendedGCD(a, b):
        #a*xi + b*yi = ri
        if b == 0:
            return (1, 0, a)
        #a*x1 + b*y1 = a
        x1 = 1
        y1 = 0
        #a*x2 + b*y2 = b
        x2 = 0
        y2 = 1
        while b != 0:
            q = a / b
            #ri = r(i-2) % r(i-1)
            r = a % b
            a = b
            b = r
            #xi = x(i-2) - q*x(i-1)
            x = x1 - q*x2
            x1 = x2
            x2 = x
            #yi = y(i-2) - q*y(i-1)
            y = y1 - q*y2
            y1 = y2
            y2 = y
        return(x1, y1, a)
    
    def selectE(fn, halfkeyLength):
        while True:
            #e and fn are relatively prime
            e = random.randint(0, 1<<halfkeyLength)
            (x, y, r) = extendedGCD(e, fn)
            if r == 1:
                return e
    
    def computeD(fn, e):
        (x, y, r) = extendedGCD(fn, e)
        #y maybe < 0, so convert it 
        if y < 0:
            return fn + y
        return y
    
    def keyGeneration(keyLength):
        #generate public key and private key
        p = findPrime(keyLength/2)
        q = findPrime(keyLength/2)
        n = p * q
        fn = (p-1) * (q-1)
        e = selectE(fn, keyLength/2)
        d = computeD(fn, e)
        return (n, e, d)
    
    def encryption(M, e, n):
        #RSA C = M^e mod n
        return fastExpMod(M, e, n)
    
    def decryption(C, d, n):
        #RSA M = C^d mod n
        return fastExpMod(C, d, n)
    
    
    #Unit Testing
    (n, e, d) = keyGeneration(1024)
    #AES keyLength = 256
    X = random.randint(0, 1<<256)
    C = encryption(X, e, n)
    M = decryption(C, d, n)
    print "PlainText:", X
    print "Encryption of plainText:", C
    print "Decryption of cipherText:", M
    print "The algorithm is correct:", X == M
    

    转载自:http://www.cnblogs.com/7hat/p/3407897.html

    展开全文
  • PythonRSA Python 3 RSA算法实现 用法 生成ssh公钥和私钥在./keys/key.pub和./keys/key文件中生成2048位密钥的./keys/key.pub python3 rsa.py generate-key -l 2048 -o ./keys/key
  • RSA加密算法Python实现

    2021-02-11 11:13:42
    RSA加密算法Python实现 RSA加密算法是目前使用最广泛的加密方式,具体流程见RSA加密算法 之前想过用C语言实现,但是由于C语言对整型的位宽有要求,RSA加密算法中需要使用的数字大小远远超出C语言中long long int 的...

    RSA加密算法Python实现

    RSA加密算法是目前使用最广泛的加密方式,具体流程见RSA加密算法
    之前想过用C语言实现,但是由于C语言对整型的位宽有要求,RSA加密算法中需要使用的数字大小远远超出C语言中long long int 的最大值,最近学习了Python之后,发现Python没有这一要求,可以较容易的实现。
    在这里插入图片描述

    from random import randint
    from datetime import datetime
    
    """判断是否是素数"""
    def is_sushu(sushu):
        for i in range(2,sushu):
            if sushu % i == 0:
                return False
        return True
    
    """随机生成指定范围的大素数"""
    def Create_Sushu():
        while True:
            sushu = randint(100,1000 )#下限越大,加密越安全,此处考虑计算时间,取值较小
            if is_sushu(sushu):
                return sushu
    
    """计算欧拉函数"""
    def Oula(sushu1 , sushu2):
        return (sushu1-1)*(sushu2-1)
    
    """判断是否互质"""
    def Is_Huzhi(int_min,int_max):
        for i in range(2,int_min+1):
            if int_min % i == 0 and int_max % i == 0:
                return False
        return True
    
    """计算公钥,直接计算编程较简单,此处考虑了计算效率的优化"""
    def Creat_E(oula):
        top = oula
        while True:
            i = randint(2,top)
            for e in range(i,top):
                if Is_Huzhi(e,oula):
                    return e     
            top = i    
    
    """计算私钥"""
    def Compute_D(oula,e):
        k = 1
        while ( k*oula+1 )% e != 0:
            k+=1
        return int((k*oula+1)/e)
    
    """
    将字符串转成ASCII
    """
    def Transfer_To_Ascii(messages):
        result = []
        for message in messages:
            result.append(  ord(message) ) 
        return result
    
    """
    将列表转化成字符串
    """
    def Transfer_To_String(string_list):
        string = ''.join(string_list)
        return string
    
    
    if __name__ == "__main__":
        """
        p、q为大素数
        n=p*q
        oula = (p-1)* (q-1)
        e 为公钥
        d 为私钥
        """
    
        print("通信开始,正在计算公钥与私钥...")
        time_start = datetime.now()
        p = Create_Sushu()
        q = p
        while p ==q :
            q = Create_Sushu()
        n = p * q
        oula = Oula(p, q)
        e = Creat_E(oula)
        d = Compute_D(oula,e)
        time_end = datetime.now()
        print(f"计算完成,用时{str(time_end -time_start)}秒 ")
        print(f"公钥:n = {str(n)} , e = {str(e)}")
        print(f"私钥:n = {str(n)} , d = {str(d)}")
        #print('p='+str(p)+'\n'+'q='+str(q)+'\n'+'n='+str(n)+'\n'+'oula='+str(oula)+'\n'+'d='+str(d)+'\n')
    
        m = input('待加密信息:')
        m_list = Transfer_To_Ascii(m)
    
        print("正在加密...")
        c_list = []
        for m in m_list:
            c = m**e%n
            c_list.append(c)
        print(f"密文:{c_list}")
    
        print("正在解密...")
        decode_messages=[]
        for c in c_list:
            decode_message = c**d%n
            decode_messages.append(chr(decode_message))
        print(f"解密信息:{Transfer_To_String(decode_messages)}")
    
    展开全文
  • RSA 加解密的 Python 实现 环境 使用的 Python 版本是:Python 3.6.3。 无使用其他第三方库,根据密码学实验要求纯手工实现。 使用 进行加密 在得到的项目文件夹下使用如下命令即可启动 GUI 界面,先点击生成按钮...
  • RSA算法Python实现

    千次阅读 2018-08-08 21:59:55
    RSA算法Python实现 yangtf 功能 RSA加密是最常见的非对称加密算法,基于大数分解难题。 两个很大的素数相乘很容易,但想根据成绩解出因子则很难。 如果数不够大,还是很容易分解的。 素数 素数是这样的...

    RSA算法与Python实现

    yangtf

    功能

    RSA加密是最常见的非对称加密算法,基于大数分解难题。 两个很大的素数相乘很容易,但想根据成绩解出因子则很难。

    如果数不够大,还是很容易分解的。

    素数

    素数是这样的整数,它除了能表示为它自己和1的乘积以外,不能表示为任何其它两个整数的乘积。例如,15=3*5,所以15不是素数;又如,12=6*2=4*3,所以12也不是素数。另一方面,13除了等于13*1以外,不能表示为其它任何两个整数的乘积,所以13是一个素数。素数也称为“质数”。

    互质数(或互素数)

    公约数只有1的两个数,叫做互质数

    模指数运算

    取模就是 做一个整除,取余数作为结果,如 13 % 3 = 1 ,因为13除以3,余1
    模指数运算就是先做指数运算,取其结果再做模运算。

    RSA算法

    (1)先随机选择两个足够大的素数

    (2)计算乘积 n = pq ,这个n就是那个很难分解的大数,如果pq太小就尴尬了,很容易被爆破。

    (3)计算f(n) = (p-1)*(q-1) ,p和q 不能让任何人知道。n是公开的。

    (4)找到一个与f(n)互质的数e,使其1

    import math
    p=9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
    q=11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
    e=65537
    c=83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034
    n=p*q
    
    
    
    
    fn=long((p-1)*(q-1))
    
    # 计算d,使得 de≡1 mod f(n)    
    # 意思是  d*e % fn == 1 。 d和e的乘积取模等于1 
    # 也就是说 d*e = 1 + fn*i  (i为整数,就是 d*e / fn 的商)
    # 下面的算法是  ( fn*i+i ) % e  如果结果为零,得到结果就是d  
    
    i = 1
    while(True):
        x=(i*fn)+1
        if(x%e==0):
            d=x/e
            break
        i=i+1
    
    print "d=", d
    print "i=",i
    
    # 另外一个等价公式是  d ≡e-1 mod f(n)   , 意思为 d % f(n) == (e-1)%f(n) , 也就是说 (e-1)+ j*fn = d + f(n)*i 
    # 这个比较难算了。
    
    d= 56632047571190660567520341028861194862411428416862507034762587229995138605649836960220619903456392752115943299335385163216233744624623848874235303309636393446736347238627793022725260986466957974753004129210680401432377444984195145009801967391196615524488853620232925992387563270746297909112117451398527453977
    i= 32394
    
    KU = (e,n) # 公钥
    PU = (d,n) # 私钥
    M = 5577446633554466577768879988 # 明文
    C = pow(M,e,n ) # M的e次方 模上n
    print "C = " , C
    C =  83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034
    
    MC = pow(C,d,n)
    print "MC = ",MC
    MC =  5577446633554466577768879988
    
    M == MC
    True
    

    可以看到解密后的MC和原文M相等

    Cite :

    https://www.cnblogs.com/jiftle/p/7903762.html

    http://www.shiyanbar.com/ctf/1979

    https://blog.csdn.net/sinat_33769106/article/details/79999090

    还有另外一个计算D的方法,试一下。

    def computeD(fn, e):
        (x, y, r) = extendedGCD(fn, e)
        if y < 0:
            return fn + y
        return y
    
    def extendedGCD(a, b):
        if b == 0:
            return (1, 0, a)
        x1 = 1
        y1 = 0
        x2 = 0
        y2 = 1
        while b != 0:
            q = a / b
            r = a % b
            a = b
            b = r
            x = x1 - q*x2
            x1 = x2
            x2 = x
            y = y1 - q*y2
            y1 = y2
            y2 = y
        return(x1, y1, a)
    
    D = computeD(fn,e)
    print D
    56632047571190660567520341028861194862411428416862507034762587229995138605649836960220619903456392752115943299335385163216233744624623848874235303309636393446736347238627793022725260986466957974753004129210680401432377444984195145009801967391196615524488853620232925992387563270746297909112117451398527453977
    
    D == d
    True
    

    简单的证明

    C=Me%n
    M=Cd%n=Med%n=M1%n=M
    为什么ed = 1 ,在整个公式里,都是做的模运算 ,生成过程决定了 ed % n = 1
    上述公式用latex表述。

    展开全文
  • python实现RSA算法

    2019-12-02 16:41:16
    基于Python实现RSA算法,包括的函数有:判断一个数是否为素数、判断两个数是否互为素数、欧几里得算法求最大公约数、产生公私钥、扩展欧几里得算法求模逆、加密明文、解密密文以及代码测试。
  • RSA算法是当今使用最广泛,安全度最高的加密算法。 • RSA算法的安全性理论基础 [引]根据百科介绍,对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之,对一极大整数做因数分解愈困难,RSA算法愈可靠。假如...
  • 25行代码实现完整的RSA算法Python3.X版本)

    千次阅读 多人点赞 2019-02-13 19:47:05
    25行代码实现完整的RSA算法Python3.X版本)   python2.7版本的请点击这里25行代码实现完整的RSA算法   网络上很多关于RSA算法的原理介绍,但是翻来翻去就是没有一个靠谱、让人信服的算法代码实现,即使有代码...
  • RSA算法的纯Python实现

    2014-05-28 15:33:53
    RSA算法的纯Python实现,压缩包内共4个文件,分别是 1、大整数的运算库(当然不是算加减乘除的,这个python本身就有)。这个库是计算乘模运算,幂模运算(蒙哥马利算法),最大公约数算法及扩展最大公约数算法(扩展...
  • RSA算法原理 Python实现RSA加密算法 设p、q为质数 n = p*q fn = (p-1)*(q-1) 要满足: 1 < e < fn , 且 e 与 fn 互质 满足: e*d%fn = 1 (d>1) e 为公钥 , d 为私钥 把e 和 n 发给 客户端 m 为明文 c = m...
  • RSA算法是一种非对称加密算法,是现在广泛使用的公钥加密算法,主要应用是加密信息和数字签名。本文给大家介绍python实现rsa算法代码,感兴趣的朋友一起学习吧

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 495
精华内容 198
关键字:

rsa算法python

python 订阅