精华内容
下载资源
问答
  • rsa签名算法python
    万次阅读
    2022-07-09 16:28:29

    Program : Textbook RSA (on group)

    In this part, you are required to implement the textbook RSA algorithm for signing from scratch. The signing procedure is quite similar with encryption, but you should not be confused with them. It contains the following three procedures, KeyGen, Encrypt, and Decrypt.

    • KeyGen
      • Same as before.
    • Sign
      • Given a plaintext message m ∈ Z N m \in \mathbb{Z}_N mZN and a private key ( N , d ) (N,d) (N,d), return the signature s s s.
    • Verify
      • Given a plaintext message m ∈ Z N m \in \mathbb{Z}_N mZN, the signature s s s, and a public key ( N , e ) (N,e) (N,e), check whether the signature is valid or not.

    Your program does the following:

    • Generate a textbook RSA key pair. Print the private key and the public key as multiple decimal strings.
    • Read a decimal string representing a plaintext message m m m. Raise an exception if m m m is invalid.
    • Sign the message m m m. Print the signature s s s as a decimal string.
    • Verify the signature s s s of message m m m. Print valid if the signature is valid. Print invalid otherwise.
    • Randomly pick a number as a faked message m ′ m^\prime m, and verify the signature s s s of message m ′ m^\prime m. Print valid if the signature is valid. Print invalid otherwise.
    • Randomly pick a number as a faked signature s ′ s^\prime s, and verify the signature s ′ s^\prime s of message m m m. Print valid if the signature is valid. Print invalid otherwise.

    Note that in this program, you may only include third-party codes or libraries for:

    • Miller-Rabin Test
    • Extended Euclidean Algorithm

    Example Input & Output

    Input:

    34862844108815430278935886114814204661242105806196134451262421197958661737288465541172280522822644267285105893266043422314800759306377373320298160258654603531159702663926160107285223145666239673833817786345065431976764139550904726039902450456522584204556470321705267433321819673919640632299889369457498214445
    

    Output:

    Private key:
    N: 60578014255102269896133371904627262317416253087521326961353447386111108220456127698087451094233400895389904195033258942460533045725424252051031082346623918833115880605331217845541371778050413570487118811797680786863916249631173243202415281126677535724142072672389239932425514746354116788337452709735978693441
    d: 29794267204372868920195293823377577521348286669753768926422253485197790892996900859124258444603569195973796199037022534122349660497314477050901363975617785986341374781520104383687018770714375371190852092718547427166813248293087229107819441125188332290624176181241072609675470769160255268721140521999754996495
    Public key:
    N: 60578014255102269896133371904627262317416253087521326961353447386111108220456127698087451094233400895389904195033258942460533045725424252051031082346623918833115880605331217845541371778050413570487118811797680786863916249631173243202415281126677535724142072672389239932425514746354116788337452709735978693441
    e: 50236051684532724158959956908047535011547027752807918443381101532977239879805272363541815186678432878182913685573432227040470122555922161989827750747871310928207045877463632837569381571438481188390948780929921154288163100313907723263741344747325268803766335694293737307011671572842257344517928948772977494407
    Signature:
    s: 34580775293086014798734721087900779255336448150833662767477345836086991760074172833491041507919156367652845778336488884879942244053190133044473935740553882083350076369679814132582396981838752038660178872674779525999874634128284351865411689078895902069902392417208340043916976695929474980926586642060201969134
    Verify s of m:
    valid
    m' (faked): 50450048059881262533055051783615244680711671489653790401184574597060270328158473249590629579575748444416670136818805407617798193709438157542915258506987898524296742253334657876701634724978818355153836962043088167025161694157068501323069379606742460252729290661161539614496733300584141680283224222741900536312
    Verify s of m':
    invalid
    s' (faked): 28243222593155363957786267188064169499833133908722962853038127116797113724411953085666999176421008597106689088871876968450636497620934133534312574374692406966037865626499421933604018821681836276566498093397822394074799560633387005572367768063152314140663154660143389779133176949492679329809464448869998812303
    Verify s' of m:
    invalid
    

    solution code

    # Program 1: Textbook RSA (on group)
    from random import randrange
    import secrets
    import random
    
    
    def is_probably_prime_miller_rabin(n: int, k: int = 10) -> bool:
        # Miller-Rabin 素数判定
        # https://gist.github.com/bnlucas/5857478
        if n == 2 or n == 3:
            return True
        if not n & 1:
            return False
    
        def check(a: int, s: int, d: int, n: int) -> bool:
            x = pow(a, d, n)
            if x == 1:
                return True
            for _ in range(s - 1):
                if x == n - 1:
                    return True
                x = pow(x, 2, n)
            return x == n - 1
    
        s: int = 0
        d: int = n - 1
    
        while d % 2 == 0:
            d >>= 1
            s += 1
    
        for _ in range(k):
            a: int = randrange(2, n - 1)
            if not check(a, s, d, n):
                return False
    
        return True
    
    
    def get_big_prime(nbits: int) -> int:
        # http://ju.outofmemory.cn/entry/93761
        # 返回一个可能是素数的大整数
        while True:
            p: int = 2 ** (nbits - 1) | secrets.randbits(nbits)
            # Miller_Robin算法对2的倍数检测有异常,故如果生成2的倍数,则将其+1再进行判断:
            if p % 2 == 0:
                p = p + 1
            if is_probably_prime_miller_rabin(p):
                return p
    
    
    def E_create(min_num: int, max_num: int) -> int:
        while 1:
            prime_ran: int = random.randint(min_num, max_num)
            if prime_ran % 2 == 0:
                prime_ran += 1
            if is_probably_prime_miller_rabin(prime_ran):
                break
        return prime_ran
    
    
    # 定义扩展欧几里得算法:
    def ex_gcd(a, b) -> tuple:
        if b == 0:
            return 1, 0, a
        else:
            x, y, q = ex_gcd(b, a % b)
            x, y = y, (x - (a // b) * y)
            return x, y, q
    
    
    # 生成p,q:
    p: int = get_big_prime(512)
    q: int = get_big_prime(512)
    n: int = p * q
    # 求n:
    phi_n: int = (p - 1) * (q - 1)
    print('Private key:\n', 'N:\n', n)
    # 选择与n互素的e:
    e: int = E_create(pow(2, 1023), n)
    
    # 输出d(逆元):
    d: int = ex_gcd(e, phi_n)[0]
    print('d:\n', d)
    print('Public key:\n', 'N:\n', n)
    print('e:\n', e)
    # Read a decimal string representing a plaintext message m.
    # Raise an exception if m is invalid:
    plaintext: str = input('input the plaintext:\n')
    if int(plaintext) < 0:
        raise ValueError
    # Sign the message m. Print the signature as a decimal string.:
    s: int = pow(int(plaintext), d, n)
    print('\nSignature:\ns:\n', s)
    plaintext_ver: int = pow(s, e, n)
    print("Verify s of m:")
    # Verify the signature of message .
    if plaintext_ver == int(plaintext):
        print("valid")
    else:
        print("invalid")
    
    # Randomly pick a number as a faked message
    plaintext_rnd: int = random.randint(pow(2, 1023), pow(2, 1024))
    # verify the signature of message .
    s_1: int = pow(plaintext_rnd, d, n)
    plaintext_ver_1: int = pow(s_1, e, n)
    print("m' (faked):\n", plaintext_ver_1)
    print("Verify s of m':")
    if plaintext_ver_1 == int(plaintext):
        print("valid")
    else:
        print("invalid")
    
    # Randomly pick a number as a faked signature
    s_2: int = random.randint(pow(2, 1023), pow(2, 1024))
    # verify the signature of message .
    plaintext_ver_2: int = pow(s_2, e, n)
    print("s' (faked):\n", s_2)
    print("Verify s' of m:")
    if plaintext_ver_2 == int(plaintext):
        print("valid")
    else:
        print("invalid")
    
    

    output

    Private key:
     N:
     107992477274908164987809018982137465564341257948530534670895468253588173010564882417126177146346874580504385069923226798367938945288000617850204675720872151991186552635061582413680375021707167755890634233530984429873649065257813075105561239616924445227718402281860904991925881636947897086171490852246792807907
    d:
     17744715076567138746128060295691002556825632322161828767604820119356827152927789620314560931112894682961782585787136528959807210900338073162455547178040283671382890616336830904427664840597925533292107378532037380901265512367128033731853434723924570798499611024587619694890298771860154109313171748776601333531
    Public key:
     N:
     107992477274908164987809018982137465564341257948530534670895468253588173010564882417126177146346874580504385069923226798367938945288000617850204675720872151991186552635061582413680375021707167755890634233530984429873649065257813075105561239616924445227718402281860904991925881636947897086171490852246792807907
    e:
     100803639898282871899084573118859880269834136605111141139254190439351190893900619928757241680252089032822142221998467989929656318316845297145036079246329112459152582829874283395938059580016215735704690622809229105159553683337736444067606804910236012658551365119515445807535745830975271663875154185122545033491
    input the plaintext:
    34862844108815430278935886114814204661242105806196134451262421197958661737288465
    54117228052282264426728510589326604342231480075930637737332029816025865460353115
    97026639261601072852231456662396738338177863450654319767641395509047260399024504
    56522584204556470321705267433321819673919640632299889369457498214445
    Signature:
    s:
     1513270751288809861781429681060507518418033500789107714991292485468275765887699169898521568123488506773451069632714191529063001321406797834199470047305211644533172136649804510006662987613553008630342936317048697038496511225968282373331989596122475926265089012209697077873774877118997027968381890785849649178
    Verify s of m:
    valid
    m' (faked):
     100752093311910077742499757370470112147480890616144299651911253300500673042559683581450698353287657998135695042769358738816482816638086436658380699433222424662154214377632914864992524159313615028280496814879902273096128183574373734203981481552510513025517392392561681223897987300529620089982250914081084216265
    Verify s of m':
    invalid
    s' (faked):
     168822314496642584742692020936702019211695198104472330305707135494052699548229026068527368035464885976889603265835100106190989646443223382742932777599773760255418327460947037914104380927379145270494735030046695346724036443686835579839749199126417321843932478200276140840192924841477228546822936072321697722472
    Verify s' of m:
    invalid
    
    进程已结束,退出代码为 0
    

    A screenshot of the console output of the program:
    在这里插入图片描述
    受于文本篇幅原因,本文相关算法实现工程例如环境及相关库,无法展示出来,现已将资源上传,可自行点击下方链接下载。

    python实现签名RSA算法工程文件

    更多相关内容
  • 借助python的pycrypto库,使用公/私钥RSA加密和AES对称会话密钥加密,使用RSA算法进行签名。 具体实现: 事先生成好两对RSA公钥和密钥,分别保存在客户端和服务端本地,AES会话密钥由双方沟通确定。定义AESUtil类和...

    安全的代理

    加密方法:

    借助python的pycrypto库,使用公/私钥RSA加密和AES对称会话密钥加密,使用RSA算法进行签名。

    具体实现:

    事先生成好两对RSA公钥和密钥,分别保存在客户端和服务端本地,AES会话密钥由双方沟通确定。定义AESUtil类和RsaUtil类,用来保存各自的密钥和执行加密操作。对于要加密的bytes流,先用SHA256取出摘要,然后使用本地的RSA私钥进行签名,把签名后的结果接在bytes流后面。再对整体使用远端的公钥进行Rsa加密,对得到的结果再使用会话密钥进行AES加密后发出。对于要解密的bytes流,先用会话密钥进行第一次解密,再用本地的RSA私钥进行第二次解密,由于签名的长度是确定的,可以确定得到的结果的后128位是签名,前面的部分是传输内容。然后使用远端的公钥验签,认证不成功则报错。如上的签名过程可以确保数据的完整性。

    RSA加密要求明文长度不能超过某个特定值,解决办法是定义public_long_encrypt函数,将待加密数据分段后分别加密再接到一起,解密同理分段进行。这里需要注意的是明文和密文的长度关系,分段的时候长度必须对应。

    AES加密要求明文长度必须是{16, 24, 32}之一的倍数。本项目中以16为基数。对于长度不满足条件的串,用padding字符补足到只差一位,再在最后一位记录补足的个数。对于长度是16的整数倍的串,补上15个padding字符后再最后一位记录好16。解密时读出最后一位的数字,把后面对应的位抛弃掉即可。

    网络设计:

    使用了开源项目Lightsocks的Python版本Lightsocks-Python中网络框架的部分,主要做法是用python中的asyncio库来高效地实现协程的调度:

    • 先用TCP监听固定的端口(客户端是浏览器代理127.0.0.1:1080,服务器则是0.0.0.0:8388,后者端口可自己设置);
    • 选取完成三次握手的连接,进行socks5协议的通信,来由客户端代理告诉服务器真正的访问地址;
    • 服务器与真正的访问地址建立连接后,就可以形成一条完成的链路:浏览器-客户端-服务端-真正的访问地址的通路,然后浏览器到客户端以及服务端到真正的访问地址的通信是正常访问,而客户端和服务端则采用了上面提到的加密算法进行通信。然后两者不断转发数据即可。

    实验结果:

    从控制台输出可以看出,双方进行了大量的数据交换。但在Chrome浏览器中配置好代理设置后,只能很不稳定地加载出网页内容。其中对于微博网页weibo.com,浏览器可以比较稳定地加载出网站证书,但不能显示网页内容。加密算法经本地测试并无错误,但我们没能找到网页不能稳定显示的原因。

    在这里插入图片描述

    客户端控制台输出示例:
    在这里插入图片描述

    服务端控制台输出示例:
    在这里插入图片描述


    update:

    • 在去除AES加密算法之后,发现可以访问Google网站了,但是响应速度较慢。具体原因未知。
      在这里插入图片描述
    展开全文
  • python实现RSA算法

    2019-12-02 16:41:16
    基于Python实现RSA算法,包括的函数有:判断一个数是否为素数、判断两个数是否互为素数、欧几里得算法求最大公约数、产生公私钥、扩展欧几里得算法求模逆、加密明文、解密密文以及代码测试。
  • python实现RSA数字签名(纯算法实现)

    千次阅读 多人点赞 2022-01-14 19:22:56
    利用python实现RSA数字签名(纯算法实现),用到的hash256得到消息摘要,欧几里得,扩展欧几里得算法

    python实现RSA数字签名(纯算法实现)

    一:什么是数字签名

    数字签名是只有信息的发送者才能产生的别人无法伪造的一段数字串,这段数字串同时也是对信息的发送者发送信息真实性的一个有效证明。它是一种类似写在纸上的普通的物理签名,但是在使用了公钥加密领域的技术来实现的,用于鉴别数字信息的方法。一套数字签名通常定义两种互补的运算,一个用于签名,另一个用于验证。数字签名是非对称密钥加密技术与数字摘要技术的应用。

    请添加图片描述

    二:数字签名的原理

    请添加图片描述

    发送方将先生成一对公私钥,将公钥放到网络上,发送方利用私钥将文件或者消息进行签名。接收方得到发送方的文件或者消息、公钥以及生成的签名;首先利用公钥将得到签名生成消息摘要,在对比文件或者消息的消息摘要,如果匹配,则签名认证成功。

    三:数字签名的作用

    请添加图片描述

    四:实现数字签名的算法

    分为三种:RSA、DSA、ECDSA

    五:具备前提知识RSA算法

    RSA加密过程:

    步骤说明描述
    1选择一对不相等且足够大的质数p,q
    2计算p,q的乘积n=p*q
    3计算n的欧拉函数φ(n)=(p-1)*(q-1)
    4选一个与φ(n)互质的整数e1<e<φ(n)
    5计算出e对于φ(n)的模反元素dde mod φ(n)=1
    6公钥KU=(e,n)
    7私钥KR=(d,n)

    相关概念:

    质数:质数又称素数。一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的数叫做质数;否则称为合数(规定1既不是质数也不是合数)。

    欧拉函数:在数论,对正整数n,欧拉函数是小于n的正整数中与n互质的数的数目

    例如:

    请添加图片描述

    • 如果n可以分解成2个质数的整数之积,那么n的欧拉函数等于这两个因子的欧拉函数之积。
    • φ(n)= φ(pxq)=(p-1)*(q-1)

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

    六:消息摘要的前提知识

    消息摘要算法的特点:

    消息摘要是把任意长度的输入揉和而产生长度固定的伪随机输出的算法。消息摘要的主要特点有:

    ①无论输入的消息有多长,计算出来的消息摘要的长度总是固定的。例如应用MD5算法摘要的消息有128个比特位,用SHA-1算法摘要的消息最终有160比特位的输出,SHA-1的变体可以产生192比特位和256比特位的消息摘要。一般认为,摘要的最终输出越长,该摘要算法就越安全。

    ②消息摘要看起来是“随机的”。这些比特看上去是胡乱的杂凑在一起的。可以用大量的输入来检验其输出是否相同,一般,不同的输入会有不同的输出,而且输出的摘要消息可以通过随机性检验。但是,一个摘要并不是真正随机的,因为用相同的算法对相同的消息求两次摘要,其结果必然相同;而若是真正随机的,则无论如何都是无法重现的。因此消息摘要是“伪随机的”。

    ③一般地,只要输入的消息不同,对其进行摘要以后产生的摘要消息也必不相同;但相同的输入必会产生相同的输出。这正是好的消息摘要算法所具有的性质:输入改变了,输出也就改变了;两条相似的消息的摘要确不相近,甚至会大相径庭。

    ④消息摘要函数是无陷门的单向函数,即只能进行正向的信息摘要,而无法从摘要中恢复出任何的消息,甚至根本就找不到任何与原信息相关的信息。当然,可以采用强力攻击的方法,即尝试每一个可能的信息,计算其摘要,看看是否与已有的摘要相同,如果这样做,最终肯定会恢复出摘要的消息。但实际上,要得到的信息可能是无穷个消息之一,所以这种强力攻击几乎是无效的。

    ⑤好的摘要算法,没有人能从中找到“碰撞”,虽然“碰撞”是肯定存在的。即对于给定的一个摘要,不可能找到一条信息使其摘要正好是给定的。或者说,无法找到两条消息,使它们的摘要相同。

    七:python实现消息摘要

    该处我采用的是hash256: SHA256算法使用的哈希值长度是256位

    python代码:

    def Sha256sum(message: bytes) -> bytes:
        # 定义常量
        # 前8个素数2..19的平方根的小数部分的前32位
        h0 = 0x6a09e667
        h1 = 0xbb67ae85
        h2 = 0x3c6ef372
        h3 = 0xa54ff53a
        h4 = 0x510e527f
        h5 = 0x9b05688c
        h6 = 0x1f83d9ab
        h7 = 0x5be0cd19
    
        # 定义常数K 64
        # 前64个素数2..311的立方根的小数部分的前32位
        K = (0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1,
             0x923f82a4, 0xab1c5ed5, 0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3,
             0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174, 0xe49b69c1, 0xefbe4786,
             0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
             0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147,
             0x06ca6351, 0x14292967, 0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13,
             0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85, 0xa2bfe8a1, 0xa81a664b,
             0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
             0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a,
             0x5b9cca4f, 0x682e6ff3, 0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208,
             0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2)
    
        # R为循环右移,
        # 右移之后可能会超过32位,所以要和0xffffffff做与运算,确保结果为32位。
        R = lambda x, n: ((x >> n) | (x << (32 - n))) & 0xffffffff
        # 大端  0x12,0x34,0x56,0x78 -> 0x12345678
        W = lambda i1, i2, i3, i4: (i1 << 24) | (i2 << 16) | (i3 << 8) | i4
    
        # 对每一个输入先添加一个'0x80',即'10000000', 即128
        ascii_list = list(map(lambda x: x, message))
        msg_length = len(ascii_list) * 8
        ascii_list.append(128)
    
        # 补充0
        while (len(ascii_list) * 8 + 64) % 512 != 0:
            ascii_list.append(0)
    
        # 最后64为存放消息长度,以大端数存放。
        # 例如,消息为'a',则长度为'0x0000000000000008'
        for i in range(8):
            ascii_list.append(msg_length >> (8 * (7 - i)) & 0xff)
    
        # print(ascii_list)
        # print(len(ascii_list)//64)
        for i in range(len(ascii_list) // 64):  # 64*8=512bits
            # print(ascii_list[i*64:(i+1)*64])
            # 每个512bits的块进行循环
            w = []
            # 将512bits扩展到64*32bits=2048bits存入32位无符号数数组
            for j in range(16):
                s = i * 64 + j * 4
                w.append(W(ascii_list[s], ascii_list[s + 1], ascii_list[s + 2], ascii_list[s + 3]))
            for j in range(16, 64):
                s0 = (R(w[j - 15], 7)) ^ (R(w[j - 15], 18)) ^ (w[j - 15] >> 3)
                s1 = (R(w[j - 2], 17)) ^ (R(w[j - 2], 19)) ^ (w[j - 2] >> 10)
                w.append((w[j - 16] + s0 + w[j - 7] + s1) & 0xffffffff)
                # print(hex(s0)+':'+hex(s1)+':' + hex(R(w[j - 2], 17)))
            # 初始化
            a, b, c, d, e, f, g, h = h0, h1, h2, h3, h4, h5, h6, h7
            # for j in w:
            #    print(hex(j)[2:])
            for j in range(64):
                s0 = R(a, 2) ^ R(a, 13) ^ R(a, 22)
                maj = (a & b) ^ (a & c) ^ (b & c)
                t2 = s0 + maj
                s1 = R(e, 6) ^ R(e, 11) ^ R(e, 25)
                ch = (e & f) ^ ((~e) & g)
                t1 = h + s1 + ch + K[j] + w[j]
                h = g & 0xffffffff
                g = f & 0xffffffff
                f = e & 0xffffffff
                e = (d + t1) & 0xffffffff
                d = c & 0xffffffff
                c = b & 0xffffffff
                b = a & 0xffffffff
                a = (t1 + t2) & 0xffffffff
    
            h0 = (h0 + a) & 0xffffffff
            h1 = (h1 + b) & 0xffffffff
            h2 = (h2 + c) & 0xffffffff
            h3 = (h3 + d) & 0xffffffff
            h4 = (h4 + e) & 0xffffffff
            h5 = (h5 + f) & 0xffffffff
            h6 = (h6 + g) & 0xffffffff
            h7 = (h7 + h) & 0xffffffff
    
        digest = (h0 << 224) | (h1 << 192) | (h2 << 160) | (h3 << 128)
        digest |= (h4 << 96) | (h5 << 64) | (h6 << 32) | h7
        # print(hex(digest)[2:])  # .rjust(32, '0'))
        return hex(digest)[2:]  # .rjust(32, '0')
    if __name__=="__main__":
        aa='你好,中国'.encode('utf-8')
        print(Sha256sum(aa))
        print(len(Sha256sum(aa)))
    

    消息摘要运行效果:
    请添加图片描述

    八:RSA公私钥生成

    生成公钥与私钥:此步骤按照第五步

    明文 M 加密 Me mod n= C
    密文 C 解密 Cd mod n=M

    #D、E和N的密钥生成
    def generatePublicAndSecretKeys(size = 5):
        p, q = randPrime(size), randPrime(size) #生成一对不相等且足够大的质数
        N = p * q #计算p、q的乘积
        f = (p - 1) * (q - 1) #计算n的欧拉函数
        e = randGcd1(f) #选出一个与f互质的整数e
        d = liyuan(e, f)#计算出e对于f的模反元素d  de mod f =1
        keys = {'d' :  d, 'e' : e, 'n' : N} #得出公钥与私钥
        return keys
    

    1、选择一对不相等且足够大的质数 p,q

    #确定素数
    def isPrime(num):
        if (num < 2):
            return False
        else:
            i = 2
            flag=True
            while i < num:
                # 如果num能被i整除,说明num不是质数
                if num % i == 0:
                    # 只要num不是质数,将flag的值修改为 False
                    flag = False
                i += 1
            return  flag
    #大质数生成
    def randPrime(n):
        rangeStart = 10 ** (n-1) #10**4
        rangeEnd = (10 ** n) - 1  #10**5-1
        while True:
            num = random.randint(rangeStart, rangeEnd)  #返回rangestart到rangeend任意一个数
            if isPrime(num): #判断是否是质数,如果是则生成
                return num
    

    2、寻找与f互质的整数e,利用欧几里算法,如果值等于1·,那么这两个数互质

    #寻找与f互质整数e
    def randGcd1(b):
        rangeStart = 2
        rangeEnd = b - 1
        while True:
            num = random.randint(rangeStart, rangeEnd)
            if oujilide(num, b) == 1: #利用欧几里算法,如果值等于1,那么这个两个数互质
                return num
    #欧几里得算法
    def oujilide(a,b):
        if a > b:
            x = a
            y = b
        else:
            x = b
            y = a
        while True:
            if y == 0:
                return x
            else:
                r = x % y
                x = y
                y = r
    

    3、使用扩展欧几里得算法,计算出e对于φ(n)的模反元素d。

    #扩展欧几里得算法,求逆元
    def liyuan(a, n):
        x1, x2, x3 = 1, 0, n
        y1, y2, y3 = 0, 1, a
        while y3 != 1 and y3 != 0 and y3 > 0:
            Q = math.floor(x3 / y3)
            t1, t2, t3 = x1 - Q * y1, x2 - Q * y2, x3 - Q * y3
            x1, x2, x3 = y1, y2, y3
            y1, y2, y3 = t1, t2, t3
        if y3 == 0:
            return 0
        if y3 == 1:
            if y2 >0:
                return y2
            else:
                return n+y2
    

    4、SHA256算法得到消息摘要,并哈希值转为整型
    将消息摘要进行数字签名与验证

    #SHA256算法得到消息摘要
    def hashing(M, size = 5):
        aa=zy.Sha256sum(M) #得到哈希值
        cc=int(aa, 16) % 10 ** (size * 2 - 2)#将哈希值转化为整型
        return cc
    #将消息摘要进行签名
    def signMessage(M, d, N):
        s = power(M, d, N) #使用私钥签名 hashM**d mod N 得到签名内容
        return s
    #将得到
    def verifySign(s, e,n):
        w = power(s, e, n)
        return w
    
    

    九:实现数字签名的整体实现代码

    摘要:zaiyao.py

    def Sha256sum(message: bytes) -> bytes:
        # 定义常量
        # 前8个素数2..19的平方根的小数部分的前32位
        h0 = 0x6a09e667
        h1 = 0xbb67ae85
        h2 = 0x3c6ef372
        h3 = 0xa54ff53a
        h4 = 0x510e527f
        h5 = 0x9b05688c
        h6 = 0x1f83d9ab
        h7 = 0x5be0cd19
    
        # 定义常数K 64
        # 前64个素数2..311的立方根的小数部分的前32位
        K = (0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1,
             0x923f82a4, 0xab1c5ed5, 0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3,
             0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174, 0xe49b69c1, 0xefbe4786,
             0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
             0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147,
             0x06ca6351, 0x14292967, 0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13,
             0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85, 0xa2bfe8a1, 0xa81a664b,
             0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
             0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a,
             0x5b9cca4f, 0x682e6ff3, 0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208,
             0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2)
    
        # R为循环右移,
        # 右移之后可能会超过32位,所以要和0xffffffff做与运算,确保结果为32位。
        R = lambda x, n: ((x >> n) | (x << (32 - n))) & 0xffffffff
        # 大端  0x12,0x34,0x56,0x78 -> 0x12345678
        W = lambda i1, i2, i3, i4: (i1 << 24) | (i2 << 16) | (i3 << 8) | i4
    
        # 对每一个输入先添加一个'0x80',即'10000000', 即128
        ascii_list = list(map(lambda x: x, message))
        msg_length = len(ascii_list) * 8
        ascii_list.append(128)
    
        # 补充0
        while (len(ascii_list) * 8 + 64) % 512 != 0:
            ascii_list.append(0)
    
        # 最后64为存放消息长度,以大端数存放。
        # 例如,消息为'a',则长度为'0x0000000000000008'
        for i in range(8):
            ascii_list.append(msg_length >> (8 * (7 - i)) & 0xff)
    
        # print(ascii_list)
        # print(len(ascii_list)//64)
        for i in range(len(ascii_list) // 64):  # 64*8=512bits
            # print(ascii_list[i*64:(i+1)*64])
            # 每个512bits的块进行循环
            w = []
            # 将512bits扩展到64*32bits=2048bits存入32位无符号数数组
            for j in range(16):
                s = i * 64 + j * 4
                w.append(W(ascii_list[s], ascii_list[s + 1], ascii_list[s + 2], ascii_list[s + 3]))
            for j in range(16, 64):
                s0 = (R(w[j - 15], 7)) ^ (R(w[j - 15], 18)) ^ (w[j - 15] >> 3)
                s1 = (R(w[j - 2], 17)) ^ (R(w[j - 2], 19)) ^ (w[j - 2] >> 10)
                w.append((w[j - 16] + s0 + w[j - 7] + s1) & 0xffffffff)
                # print(hex(s0)+':'+hex(s1)+':' + hex(R(w[j - 2], 17)))
            # 初始化
            a, b, c, d, e, f, g, h = h0, h1, h2, h3, h4, h5, h6, h7
            # for j in w:
            #    print(hex(j)[2:])
            for j in range(64):
                s0 = R(a, 2) ^ R(a, 13) ^ R(a, 22)
                maj = (a & b) ^ (a & c) ^ (b & c)
                t2 = s0 + maj
                s1 = R(e, 6) ^ R(e, 11) ^ R(e, 25)
                ch = (e & f) ^ ((~e) & g)
                t1 = h + s1 + ch + K[j] + w[j]
                h = g & 0xffffffff
                g = f & 0xffffffff
                f = e & 0xffffffff
                e = (d + t1) & 0xffffffff
                d = c & 0xffffffff
                c = b & 0xffffffff
                b = a & 0xffffffff
                a = (t1 + t2) & 0xffffffff
    
            h0 = (h0 + a) & 0xffffffff
            h1 = (h1 + b) & 0xffffffff
            h2 = (h2 + c) & 0xffffffff
            h3 = (h3 + d) & 0xffffffff
            h4 = (h4 + e) & 0xffffffff
            h5 = (h5 + f) & 0xffffffff
            h6 = (h6 + g) & 0xffffffff
            h7 = (h7 + h) & 0xffffffff
    
        digest = (h0 << 224) | (h1 << 192) | (h2 << 160) | (h3 << 128)
        digest |= (h4 << 96) | (h5 << 64) | (h6 << 32) | h7
        # print(hex(digest)[2:])  # .rjust(32, '0'))
        return hex(digest)[2:]  # .rjust(32, '0')
    if __name__=="__main__":
        aa='你好,中国'.encode('utf-8')
        print(Sha256sum(aa))
        print(len(Sha256sum(aa)))
    

    RSA公私钥生成:shuziqianming.py

    import random
    import math
    import zhaiyao as zy
    #确定素数
    def isPrime(num):
        if (num < 2):
            return False
        else:
            i = 2
            flag=True
            while i < num:
                # 如果num能被i整除,说明num不是质数
                if num % i == 0:
                    # 只要num不是质数,将flag的值修改为 False
                    flag = False
                i += 1
            return  flag
    #大质数生成
    def randPrime(n):
        rangeStart = 10 ** (n-1) #10**4
        rangeEnd = (10 ** n) - 1  #10**5-1
        while True:
            num = random.randint(rangeStart, rangeEnd)  #返回rangestart到rangeend任意一个数
            if isPrime(num): #判断是否是质数,如果是则生成
                return num
    #扩展欧几里得算法,求逆元
    def liyuan(a, n):
        x1, x2, x3 = 1, 0, n
        y1, y2, y3 = 0, 1, a
        while y3 != 1 and y3 != 0 and y3 > 0:
            Q = math.floor(x3 / y3)
            t1, t2, t3 = x1 - Q * y1, x2 - Q * y2, x3 - Q * y3
            x1, x2, x3 = y1, y2, y3
            y1, y2, y3 = t1, t2, t3
        if y3 == 0:
            return 0
        if y3 == 1:
            if y2 >0:
                return y2
            else:
                return n+y2
    
    #寻找与f互质整数e
    def randGcd1(b):
        rangeStart = 2
        rangeEnd = b - 1
        while True:
            num = random.randint(rangeStart, rangeEnd)
            if oujilide(num, b) == 1: #利用欧几里算法,如果值等于1,那么这个两个数互质
                return num
    #欧几里得算法
    def oujilide(a,b):
        if a > b:
            x = a
            y = b
        else:
            x = b
            y = a
        while True:
            if y == 0:
                return x
            else:
                r = x % y
                x = y
                y = r
    #从数字幂快速搜索模块
    def power(x, n, mod):  #x**n mod mod
        if n == 0:
            return 1
        elif n % 2 == 0:
            p = power(x, n / 2, mod)
            return (p * p) % mod
        else:
            return (x * power(x, n - 1, mod)) % mod
    #D、E和N的密钥生成
    def generatePublicAndSecretKeys(size = 5):
        p, q = randPrime(size), randPrime(size) #生成一对不相等且足够大的质数
        N = p * q #计算p、q的乘积
        f = (p - 1) * (q - 1) #计算n的欧拉函数
        e = randGcd1(f) #选出一个与f互质的整数e
        d = liyuan(e, f)#计算出e对于f的模反元素d  de mod f =1
        keys = {'d' :  d, 'e' : e, 'n' : N} #得出公钥与私钥
        return keys
    #SHA256算法得到消息摘要
    def hashing(M, size = 5):
        aa=zy.Sha256sum(M) #得到哈希值
        cc=int(aa, 16) % 10 ** (size * 2 - 2)#将哈希值转化为整型
        return cc
    #将消息摘要进行签名
    def signMessage(M, d, N):
        s = power(M, d, N) #使用私钥签名 hashM**d mod N 得到签名内容
        return s
    #将得到
    def verifySign(s, e,n):
        w = power(s, e, n)
        return w
    
    

    十:运行截图

    1、对汉字的数字签名运行结果

    请添加图片描述

    2、对英文hello world 进行数字签名的运行结果

    请添加图片描述

    3、对后缀为.png图片生成数字签名的运行结果

    请添加图片描述

    4、对后缀为.doc的文档进行数字签名的运行结果

    请添加图片描述

    十一:整体代码

    此处没有写出主函数,如要参考,请参考github

    如要参加完整代码、ppt讲解、文档:请参考(纯算法,没有调用库)python实现RSA数字签名代码、ppt、文档.rar

    最后:如有任何问题,可以私信博主

    看到博主编写文章不容易,不点赞,关注,收藏在走吗???

    请添加图片描述

    展开全文
  • python 实现RSA签名

    2021-10-17 14:42:27
    在这之前 记得用pip install 安装几个包: Crypto,base64, 反正环境缺什么就加什么...4.生成签名之后,再加到请求参数内 即可访问 import hashlib import Crypto from Crypto.PublicKey import RSA from Crypto

    在这之前 记得用pip install 安装几个包:

     

    Crypto,base64, 反正环境缺什么就加什么呗

    首先梳理下思路:

    1.私钥由开发提供

    2.规则基本是按参数名从小到大排序拼接 至于具体规则 参数名和值之间是否有=链接 都得问清楚规则

    3.拼接之后是否MD5加密之后再加密等 都需要问清楚

    4.生成签名之后,再加到请求参数内 即可访问

    import hashlib
    
    import Crypto
    from Crypto.PublicKey import RSA
    from Crypto.Signature import PKCS1_v1_5
    from Crypto.Hash import SHA
    import base64
    
    
    privateKey = """-----BEGIN PRIVATE KEY-----
    私钥问开发要就可以了
    -----END PRIVATE KEY-----"""
    
    def sign_body(body):
    
    #参数拼接,用=连接
        a = ["=".join(i) for i in body.items() if(i[1] and i[0] != "sign" and i[1] and i[0] !="sign_type")]
    #参数与参数之间排序,用&连接
        strA =  "&".join(sorted(a))
        # print("AA"+strA)
    
        # MD5加密
        # def jiamimd5(src):
        #     m = hashlib.md5()
        #     m.update(src.encode('UTF-8'))
        #     return m.hexdigest()
        # sign = jiamimd5(strA.lower())
    
        # body["sign"] = sign
    
        return strA
    
    def RSA_sign(data):
    #获取私钥用户加签
        priKey = RSA.importKey(privateKey)
         #priKey = RSA.importKey(privateKey)
    #创建用于执行PKS 加密或者解密的密码
        signature = PKCS1_v1_5.new(priKey)
    #内容进行sha加密
        hash_val = SHA.new(data.encode("utf-8"))
        re =signature.sign(hash_val)
    #对于内容进行PKS加密,再使用base64进行编码
        result = base64.b64encode(re)
        red = result.decode()
        # data["sign"] = red
        return red
    
    if __name__ == '__main__':
        a='1232323231hfgds45123@¥%'
        print(RSA_sign(a))
    
    
    
    
    

    经过测试:结果正确

    import requests
    from api2.sgin import RSA_sign,sign_body
    
    
    def way(body):
        url="http://xxx.xx.xx.xx:xxxx/api-xxx/xxx/gateway"
        print(body)
    
        r=requests.post(url,data=body)
        # print(r)
    
        return  r
    
    if __name__ == '__main__':
        body={
        "xx": "xxx",
        "xxx":"xx",
        "xx": "utf-8",
        "content":'xxxxx',
        "method": "open.api.xx.xx.xx.xx",
        "sign_type": "RSA",
        "timestamp": "1634347347053",
        "version": "1.0"
        }
    
    
        striSignTemp=sign_body(body)
        print(striSignTemp)
        sign=RSA_sign(striSignTemp)
        print("ssssssssssssssss:"+sign)
        body["sign"] = sign
        print(body)
        print(way(body))
    
    

    调用前一个python文件 获取签名 加到入参内

    然后请求,执行结束

    展开全文
  • RSA是第一个能同时用于加密和数字签名算法,它能够抵抗到目前为止已知的所有密码攻击。Python代码: # -*- coding: UTF-8 -*- # reference codes: https://www.jianshu.com/p/7a4645691c68 import base64 ...
  • RSA算法的纯Python实现,压缩包内共4个文件,分别是 1、大整数的运算库(当然不是算加减乘除的,这个python本身就有)。这个库是计算乘模运算,幂模运算(蒙哥马利算法),最大公约数算法及扩展最大公约数算法(扩展...
  • 本文实例讲述了Python下实现的RSA加密/解密及签名/验证功能。分享给大家供大家参考,具体如下: 原文是py2环境,而我的环境是py3,所以对原代码做了修改:decode(), encode() import rsa # 生成密钥 (pubkey, ...
  • RSA签名算法

    千次阅读 2021-11-16 20:59:09
    文章目录RSA签名算法简介RSA签名的过程全部代码运行结果 RSA签名算法简介 签名就是在这份资料后面增加一段强而有力的证明,以此证明这段信息的发布者和这段信息的有效性完整性。 RSA签名常用的就是将这份信息进行...
  • 程序要求清单: 基本流程: 运行结果: INPUT: ...
  • RSA算法是一种非对称加密算法,是现在广泛使用的公钥加密算法,主要应用是加密信息和数字签名。维基百科给出的RSA算法简介如下:假设Alice想要通过一个不可靠的媒体接收Bob的一条私人讯息。她可以用以下的方式来产生...
  • python实现签名RSA算法工程文件 详解博客地址:https://blog.csdn.net/m0_52316372/article/details/125695341
  • (纯算法,没有调用库)python实现RSA数字签名代码、ppt、文档
  • Python实现RSA签名和验签

    千次阅读 2018-07-26 17:54:09
    RSA是一种非对称加密算法,简单理解就是两个密钥:一个公钥,一个私钥。  同时它也可以用来签名和验签,正好与加密相反。 加密:公钥加密,私钥解密; 签名:私钥签名,公钥验签。 有意思的是有些人分不清公钥...
  • 1 环境Windows7 x64Python 2.7.142 步骤i)输入明文;ii)生成公匙、私匙;iii)输出密文;iv)检验。3 代码3.1 配置RSA库该方案通过rsa库实现,可以在shell通过以下代码安装rsa库。输入pip install rsa输出通过pip安装...
  • RSA算法python实现

    2021-02-04 19:42:43
    算法基本思路: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 ...
  • python使用RSA加密算法

    万次阅读 多人点赞 2018-05-27 18:41:26
    最近换了工作,由于新公司是做个人和企业征信业务的,所以对数据的隐私性看的非常重要,所有涉及隐私的...基于我用python语言搞,那我这里就说说我是如何实现python对数据进行RSA加解密的吧。。 一、查找python支...
  • 调用编程语言现有的RSA接口,完成数字签名产生和验证的演示程序实现。 ![图片说明](https://img-ask.csdn.net/upload/201709/27/1506503880_870831.jpg) 基本要求: 1、RSA算法实现可以直接调用编程语言提供的接口...
  • 本篇文章主要说明pythonrsa生成密钥对,数据的加密解密,api接口的签名和验签,如有抄袭,请留言联系我。 先安装 pip install rsa 安装好后,请看代码 注意: api签名时:签名用私钥,验签用公钥 数据加密时:...
  • Python实现RSA数字签名

    千次阅读 2021-12-28 20:05:57
    利用Python实现RSA数字签名的产生和验证过程。 任务1:准备一个私钥文件,一个公钥文件,一个数据文件;   任务2:定义一个函数,能够使用指定的私钥对数据文件进行签 名,并将签名结果输出到文件返回;   任务3...
  • Python实现RSA算法

    千次阅读 2020-01-14 15:54:48
    RSA是第一个比较完善的公开密钥算法,它既能用于加密,也能用于数字签名RSA的安全基于大数分解的难度。其公钥和私钥是一对大素数(100到200位十进制数或更大)的函数。从一个公钥和密文恢复出明文的难度,等价于...
  • RSA非对称(公钥)密码算法Python实现【物联网安全】【信息安全】
  • OpenSSL和Python实现RSA Key数字签名和验证,基于非对称算法RSA Key主要有两个用途,数字签名和验证(私钥签名,公钥验证),以及非对称加解密(公钥加密,私钥解密)。本文提供一个基于OpenSSL命令行和Python的数字...
  • RSA算法的纯Python实现

    2014-05-28 15:33:53
    RSA算法的纯Python实现,压缩包内共4个文件,分别是 1、大整数的运算库(当然不是算加减乘除的,这个python本身就有)。这个库是计算乘模运算,幂模运算(蒙哥马利算法),最大公约数算法及扩展最大公约数算法(扩展...
  • Python使用私钥生成签名串,支持SHAWithRSA,SHA256WithRSA import rsa import base64 __pem_begin = '-----BEGIN RSA PRIVATE KEY-----\n' __pem_end = '\n-----END RSA PRIVATE KEY-----' def sign(content, ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,061
精华内容 1,624
关键字:

rsa签名算法python