【圖解DSA數(shù)字簽名算法】DSA簽名算法的Python實(shí)現(xiàn) | 物聯(lián)網(wǎng)安全

這篇具有很好參考價(jià)值的文章主要介紹了【圖解DSA數(shù)字簽名算法】DSA簽名算法的Python實(shí)現(xiàn) | 物聯(lián)網(wǎng)安全 | 信息安全。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問(wèn)。

【圖解DSA數(shù)字簽名算法】DSA簽名算法的Python實(shí)現(xiàn) | 物聯(lián)網(wǎng)安全 | 信息安全
系列索引：【圖解安全加密算法】加密算法系列索引 Python保姆級(jí)實(shí)現(xiàn)教程 | 物聯(lián)網(wǎng)安全 | 信息安全

DSA數(shù)字簽名算法基于SHA1哈希算法，關(guān)于SHA1的實(shí)現(xiàn)看另一篇文章。

一、什么是DSA

數(shù)字簽名標(biāo)準(zhǔn)(DSS)由NIST公布，該標(biāo)準(zhǔn)能夠使接收者能夠驗(yàn)證數(shù)據(jù)的完整性和數(shù)據(jù)發(fā)送者的身份而制定，所采用的算法稱(chēng)為DSA算法，也稱(chēng)為DSA簽名。

二、DSA簽名算法流程

【圖解DSA數(shù)字簽名算法】DSA簽名算法的Python實(shí)現(xiàn) | 物聯(lián)網(wǎng)安全 | 信息安全
DSA簽名涉及四個(gè)參數(shù)，p,q,g,y和x，中前四者構(gòu)成公鑰，x為私鑰（x<q）。

依據(jù)DSS標(biāo)準(zhǔn)，p為512~1024位，q是160位長(zhǎng)的素?cái)?shù)，且q|p-1；g=h(p-1)/q mod p，其中h是一整數(shù)，1<h<(p-1)且（h(p-1)/q mod p）>1；H(m)為參與簽名的雜湊值，DSS選用SHA雜湊算法

（1）DSA 簽名過(guò)程：

  用戶(hù)隨機(jī)選取k要求0<k<q，計(jì)算：

【圖解DSA數(shù)字簽名算法】DSA簽名算法的Python實(shí)現(xiàn) | 物聯(lián)網(wǎng)安全 | 信息安全

（2）DSA驗(yàn)證過(guò)程：

 接收者收到M,r,s后，首先驗(yàn)證0<r<q, 0<s<q，如果通過(guò)則計(jì)算：

【圖解DSA數(shù)字簽名算法】DSA簽名算法的Python實(shí)現(xiàn) | 物聯(lián)網(wǎng)安全 | 信息安全
如果v=r，則確認(rèn)簽名正確

三、具體實(shí)現(xiàn)過(guò)程（附代碼）

我們實(shí)驗(yàn)要求參數(shù)可以設(shè)置成較小的，方便計(jì)算，如果大家嚴(yán)格按照算法參數(shù)要求設(shè)置需要改動(dòng)。

（1）參數(shù)設(shè)置

算法的一些參數(shù)可以看要求設(shè)置成隨機(jī)數(shù)，符合大小要求即可，我這里直接使用固定值先進(jìn)行計(jì)算。
參數(shù)：
P、Q、H：人員輸入，P要求是素?cái)?shù)，512-1024位且位數(shù)L為64的倍數(shù)，Q為p-1的素因數(shù)比特長(zhǎng)度160位，H是一個(gè)整數(shù)且1<H<p-1，并且要求g=h^(p-1)/q modp>1
X：（私鑰）隨機(jī)或偽隨機(jī)整數(shù)，0<x<q，我這里設(shè)置成了75
K：隨機(jī)數(shù)，0<k<q，我這里設(shè)置成了50

pqh = input("請(qǐng)輸入P,Q,H的值：\n").split()
p, q, h = int(pqh[0]), int(pqh[1]), int(pqh[2])

g = int((h**(int((p-1)/q))) % p)

k = 50
x = 75
y = int(g**x % p)

print(f"P:{p},Q:{q},G:{g},x:{x},y:{y}")

（2）乘法逆元

乘法逆元：若存在正整數(shù)a,b,p, 滿(mǎn)足ab = 1(mod p), 則稱(chēng)a 是b 的乘法逆元, 或稱(chēng)b 是a 的乘法逆元。
【圖解DSA數(shù)字簽名算法】DSA簽名算法的Python實(shí)現(xiàn) | 物聯(lián)網(wǎng)安全 | 信息安全

def EX_GCD(a, b, arr):  # 擴(kuò)展歐幾里得
    if b == 0:
        arr[0] = 1
        arr[1] = 0
        return a
    g = EX_GCD(b, a % b, arr)
    t = arr[0]
    arr[0] = arr[1]
    arr[1] = t - int(a / b) * arr[1]
    return g


def ModReverse(a, n):  # ax=1(mod n) 求a模n的乘法逆x
    arr = [0, 1, ]
    gcd = EX_GCD(a, n, arr)
    if gcd == 1:
        return (arr[0] % n + n) % n
    else:
        return -1

（3）簽名

def sign(g, p, q, x, M):
    r = int((g**k % p) % q)
    s = int((ModReverse(k, q)*(M+x*r)) % q)
    print(f"簽名為（{r}, {s}）")
    return r, s

（4）驗(yàn)證

def verify(g, p, q, y, M, r, s):
    w = int(ModReverse(s, q) % q)
    u1 = int((M*w) % q)
    u2 = int(r*w % q)
    v = int(((g**u1)*(y**u2) % p) % q)
    print(f"lc(w,u1,u2,v)=({w},{u1},{u2},{v})")
    if v == r:
        print("簽名有效")
    else:
        print("簽名無(wú)效")

四、跟著demo去debug

這里使用給出兩組數(shù)據(jù)供大家調(diào)試，一組來(lái)源于課本，一組來(lái)源于網(wǎng)絡(luò)。

（1）示例1：
【圖解DSA數(shù)字簽名算法】DSA簽名算法的Python實(shí)現(xiàn) | 物聯(lián)網(wǎng)安全 | 信息安全

（2）示例2：

五、完整代碼

代碼已補(bǔ)充，因?yàn)槲覀兝蠋煂?duì)參與運(yùn)算的雜湊碼要求只去前32位后右移八位參與運(yùn)算，故代碼中進(jìn)行了處理，同時(shí)一些變量的取值可能不那么嚴(yán)謹(jǐn)，對(duì)于代碼要求較高的大佬可以進(jìn)行修改。代碼未使用類(lèi)進(jìn)行封裝，也是待完善的地方。

import random

A, B, C, D, E = 0x67452301, 0xEFCDAB89, 0x98BADCFE, 0x10325476, 0xC3D2E1F0  # 常量
K = [0x5A827999, 0x6ED9EBA1, 0x8F1BBCDC, 0xCA62C1D6]  # 常量

str = input("輸入明文：\n").encode('utf-8')  # 這里對(duì)輸入明文進(jìn)行編碼，str為bytes型
l = len(str)*8  # 每個(gè)字符8位
# python中二進(jìn)制是字符串，不保留高位的0，這里使用zfill補(bǔ)高位0，如十進(jìn)制6->110->0110，M這里是用了一個(gè)很長(zhǎng)的字符串如:'11001010100011...'來(lái)表示原始數(shù)據(jù)
M = bin(int(str.hex(), 16))[2:].zfill(l)

# [可選項(xiàng)] 下面的函數(shù)僅僅顯示輸入明文的ascii，末尾為長(zhǎng)度，該段顯示的是補(bǔ)位后的
for i in range(64):
    if i < len(str):
        print(str[i], end=' ')
    elif i < len(str)+1:
        print('128', end=' ')
    elif i < 63:
        print('0', end=' ')
    else:
        print(l)

flag = 1  # 補(bǔ)1標(biāo)志位，補(bǔ)一次1后置0
while len(M) % 512 != 448:
    if flag:
        M += '1'
        flag = 0
    else:
        M += '0'
M += "{:064b}".format(l)  # 末尾64位寫(xiě)入長(zhǎng)度，空余補(bǔ)位補(bǔ)0
M = hex(int(M, 2))[2:]  # 這種轉(zhuǎn)換會(huì)用到很多次，2進(jìn)制轉(zhuǎn)16進(jìn)制，M現(xiàn)在是一個(gè)16進(jìn)制字符串，如'1342a2c12...'
Mn = []  # 存儲(chǔ)每個(gè)32位的字，因?yàn)镸中一個(gè)字符4位（16進(jìn)制），所以取M中的8個(gè)為一組，按要求將M分割成16個(gè)32位的字，故這里8*4=32，32*16=512
for i in range(16):
    Mn.append(M[8*i: 8*i+8])


def roll_left(num, k):
    """循環(huán)左移函數(shù)

    Parameters
    ----------
    num : int
        輸入一個(gè)數(shù)字，2進(jìn)制、10進(jìn)制等均可
    k : int
        左移位數(shù)

    Returns
    -------
    int
        返回一個(gè)int結(jié)果
    """
    num_bin = bin(num)[2:].zfill(
        32)  # 因?yàn)閜ython高位不會(huì)自動(dòng)補(bǔ)0，導(dǎo)致要手動(dòng)調(diào)整（也可能是我學(xué)藝不精），不然會(huì)忽略高位的0循環(huán)左移
    out = num_bin[k % len(num_bin):]+num_bin[:k % len(num_bin)]  # 注意預(yù)防溢出
    return int(out, 2)  # 二進(jìn)制左移完成后轉(zhuǎn)化成10進(jìn)制輸出


W = ['' for _ in range(80)]  # 存儲(chǔ)80份擴(kuò)展子明文
for i in range(80):
    if 16 <= i <= 79:
        # 16-79要進(jìn)行異或運(yùn)算，這里先轉(zhuǎn)換成十進(jìn)制（W中存的是16進(jìn)制字符串，str無(wú)法運(yùn)算）
        temp = int(W[i-3], 16) ^ int(W[i-8],
                                     16) ^ int(W[i-14], 16) ^ int(W[i-16], 16)

        W[i] = hex(roll_left(temp, 1))[2:].zfill(8)  # 循環(huán)左移1位
    else:
        W[i] = Mn[i]


def ft(b, c, d, t):
    """ft為邏輯函數(shù)

    Parameters
    ----------
    b : int
        B值
    c : int
        C值
    d : int
        D值
    t : int
        輪次

    Returns
    -------
    int
        運(yùn)算結(jié)果
    """
    if t >= 0 and t <= 19:
        return ((b & c) | (~b & d))
    elif t >= 20 and t <= 39:
        return (b ^ c ^ d)
    elif t >= 40 and t <= 59:
        return ((b & c) | (b & d) | (d & c))
    elif t >= 60 and t <= 79:
        return (b ^ c ^ d)


Ap, Bp, Cp, Dp, Ep = A, B, C, D, E  # 暫存初始值
for t in range(80):
    tmp = B
    B = A
    A = ((((E + ft(tmp, C, D, t)) % (2**32)+roll_left(A, 5)) %
         (2**32)+int(W[t], 16)) % (2**32)+K[t//20]) % (2**32)  # 預(yù)防溢出進(jìn)行取模運(yùn)算
    E = D
    D = C
    C = roll_left(tmp, 30)

    #print(f" round{t+1} : {hex(A)} {hex(B)} {hex(C)} {hex(D)} {hex(E)}\n")
A, B, C, D, E = (Ap+A) % (2**32), (Bp+B) % (2**32), (Cp +
                                                     C) % (2**32), (Dp+D) % (2**32), (Ep+E) % (2**32)
# 相加運(yùn)算，因?yàn)閜ython不像c/c++可以使用unsigned char_32直接限制位數(shù)，因此要對(duì)位數(shù)進(jìn)行限制
print("明文對(duì)應(yīng)的雜湊碼：\n", hex(A), hex(B), hex(C), hex(D), hex(E))

num_bin = bin(A)[2:].zfill(32)
out = '0'*8+num_bin[:-8 % len(num_bin)]
M = int(out, 2)

pqh = input("請(qǐng)輸入P,Q,H的值：\n").split()
p, q, h = int(pqh[0]), int(pqh[1]), int(pqh[2])

g = int((h**(int((p-1)/q))) % p)

x = 75

y = int(g**x % p)
print(f"P:{p},Q:{q},G:{g},x:{x},y:{y}")

k = 50
print(f"用于簽名的雜湊碼為：{M}")


def EX_GCD(a, b, arr):  # 擴(kuò)展歐幾里得
    if b == 0:
        arr[0] = 1
        arr[1] = 0
        return a
    g = EX_GCD(b, a % b, arr)
    t = arr[0]
    arr[0] = arr[1]
    arr[1] = t - int(a / b) * arr[1]
    return g


def ModReverse(a, n):  # ax=1(mod n) 求a模n的乘法逆x
    arr = [0, 1, ]
    gcd = EX_GCD(a, n, arr)
    if gcd == 1:
        return (arr[0] % n + n) % n
    else:
        return -1


def sign(g, p, q, x, M):
    r = int((g**k % p) % q)
    s = int((ModReverse(k, q)*(M+x*r)) % q)
    print(f"簽名為（{r}, {s}）")
    return r, s


def verify(g, p, q, y, M, r, s):
    w = int(ModReverse(s, q) % q)
    u1 = int((M*w) % q)
    u2 = int(r*w % q)
    v = int(((g**u1)*(y**u2) % p) % q)
    print(f"lc(w,u1,u2,v)=({w},{u1},{u2},{v})")
    if v == r:
        print("簽名有效")
    else:
        print("簽名無(wú)效")


r, s = sign(g, p, q, x, M)
verify(g, p, q, y, M, r, s)

圖解安全加密算法系列持續(xù)更新，歡迎點(diǎn)贊收藏＋關(guān)注

上一篇：【圖解AES加密算法】AES算法的Python實(shí)現(xiàn) | Rijndael-128 | 對(duì)稱(chēng)加密 | 物聯(lián)網(wǎng)安全
下一篇：【圖解SHA1雜湊算法】SHA1雜湊算法的Python實(shí)現(xiàn)保姆級(jí)教程 | 物聯(lián)網(wǎng)安全 | 信息安全

本人水平有限，文章中不足之處歡迎下方??評(píng)論區(qū)批評(píng)指正~

如果感覺(jué)對(duì)你有幫助，點(diǎn)個(gè)贊?? 支持一下吧 ~

不定期分享有趣、有料、有營(yíng)養(yǎng)內(nèi)容，歡迎訂閱關(guān)注 ?? 我的博客，期待在這與你相遇 ~文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-463616.html

到了這里，關(guān)于【圖解DSA數(shù)字簽名算法】DSA簽名算法的Python實(shí)現(xiàn) | 物聯(lián)網(wǎng)安全 | 信息安全的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！