数字签名算法 DSA

DSA全称为Digital Signature Algorithm（电子签名算法），被美国NIST选为DSS即Digital Signature Standard（电子签名标准）算法。DSA的椭圆曲线密码学版本是ECDSA。

参考：维基百科

DSA 算法包含了四种操作：密钥生成、密钥分发、签名、验证

密钥生成

1. 选取一个合适的哈希函数记为 $H$ 函数，例如SHA1。

2. 选择合适的密钥长度记$(L,N)$，其中DSS建议 $64|L$ ，且 $512\le L\le 1024$，$N$ 不能大于 $H$ 函数输出的长度。

3. 选取$N$ 比特的素数 $q$ 和 $L$ 比特的素数 $p$，并且满足 $q|(p-1)$ 。

4. 选择满足模 $p$ 意义下阶为 $q$ 的整数 $g$ ，这里可以通过关系式

5. $$g\equiv h^{(p-1)/q}modp$$

   得出，其中 $1<h<p-1$ 。

6. 选择整数 $x\in (0,q)$，记为私钥，并且计算 $y\equiv g^{x}modp$。

• 最终公钥为 $(p,q,g,y)$，私钥为 $x$。

签名

1. 选择临时密钥 $k$ ，满足 $0<k<q$。
2. 计算 $r\equiv (g^{k}modp)(modq)$
3. 计算 $s\equiv (H(m)+xr)k^{-1}(modq)$

最终签名为 $(r,s)$

验签

1. 设 $w\equiv s^{-1}modq$ ，$u_1\equiv H(m)wmodq$，$u_2\equiv rwmodq$

2. 设 $v\equiv g^{u_1}{y}^{u_2}modp(modq)$

3. 若 $v=r$，则签名有效，否则则为非法签名。

正确性推导

首先，$g$ 满足 $g^k\equiv 1modp$ 的最小正整数 $k$ 为 $q$ 。所以 $g^q\equiv 1modp$，所以 $g^x\equiv g^{xmodq}modp$ 。

进而有： $v=(g^{u_1}{y}^{u_2}modp)modq=g^{u_1}{y}^{x{u}_2}\equiv g^{H(m)w}{g}^{xrw}\equiv g^{H(m)w+xrw}$

又 $s\equiv (H(m)+xr)k^{-1}modq$ 且 $w=s^{-1}modq$

所以 $k\equiv s^{-1}(H(m)+xr)\equiv H(m)w+xrwmodq$

所以 $v\equiv g^k$ 。

安全性

已知 k

如果知道了随机密钥 k，那么我们就可以根据 $s\equiv (H(m)+xr)k^{-1}modq$ 计算私钥 $d$，几乎攻破了 DSA。

这里一般情况下，消息的 hash 值都会给出。

$x\equiv r^{-1}(ks-H(m))modq$

k 共享

如果在两次签名过程中共享了 $k$ ，我们就可以进行攻击。

假设签名的消息为 $m_1,m_2$ ，显然，两者的 $r$ 的值一样，此外：

$s_1\equiv (H(m_1)+xr)k^{-1}modq$

$s_2\equiv (H(m_2)+xr)k^{-1}modq$

这里我们除了 $x\mathrm{和}k$ 不知道，其余的我们都知道，那么：

$s_{1}k\equiv H(m_1)+xr$

$s_{2}k\equiv H(m_2)+xr$

两式相减：

$k(s_1-s_2)\equiv H(m_1)-H(m_2)modq$

此时即可解出 $k$ ，进一步我们可以解出 $x$。

例题1

task 附件

from Crypto.Util.number import *
import random
from gmpy2 import *

flag = b'******'
m = bytes_to_long(flag)

q = getPrime(160)
while True:
    t = 2 * getPrime(1024 - 160) * q
    if isPrime(t + 1):
        p = t + 1
        break

h = random.randint(1, p - 2)
g = powmod(h, (p - 1) // q, p)
x = 2
while GCD(x, (p - 1) * (q - 1)) != 1:
    x = random.randint(1, q - 1)
y = powmod(g, x, p)

k = random.randint(1, q - 1)
h = bytes_to_long(flag)
r = powmod(g, k, p) % q
s = (h + x * r) * invert(k, q) % q

print(x)
print(p, q, g, y, k, r, s, sep=',')

'''
744392159315109570754116310771983851757551344975
165782721341339198412647993666509464235357438316955509380916536942999719934859010719239181505641131541336732746487869057254501408932088525210132219812538680103588209858056965704513469397456062462997922579153889365949881483945374353249663615049625464936863731146786939940008455162889222224637559655206650740263,1298650860243423121422960080767774504714070643307,111120374776599326576102904326033963036086162316292379631154390419503544061132194157167377090305717398988633361879833651682909127515227791094298812966962611270373961642366936114520363598605101136319314592110825225829682824742733558890102442848946833269792264526631952031522242050722574666760289342904184078147,58676530010022270392556756451520166345533492569982892999884013280223267213196327908109838779404799027430871002478198309765681524297432684079224431376866288514458611451837344124101552983430964624885275562335163386558368543421816902968921004905903289705261286520219762327567450079657631837085261332809902779541,1202934132268354747046504251953952503269375110119,556505026580608336190454039247331999698427391838,643380837304587319829716195016078835692377111801
'''

根据已知条件可知：$s=(flag+x\ast r)\ast k^{-1}modq$

h = bytes_to_long(flag)
r = powmod(g, k, p) % q
s = (h + x * r) * invert(k, q) % q

所以，$flag=(s\ast k-x\ast r)modq$，实现 EXP为：

m = (k*s-x*r) % q
print(long_to_bytes(m))

例题2(已知k)

题目：

from Crypto.Util.number import *
from gmpy2 import *
import random
from hashlib import sha1

flag = b'NSSCTF{******}'
x = bytes_to_long(flag[7:-1])
q = getPrime(160)
while True:
    t = 2 * getPrime(1024 - 160) * q
    if isPrime(t + 1):
        p = t + 1
        break

h = random.randint(1, p - 2)
g = powmod(h, (p - 1) // q, p)
y = powmod(g, x, p)

k = random.randint(1, q - 1)
h = bytes_to_long(sha1(flag).digest())
r = powmod(g, k, p) % q
s = (h + x * r) * invert(k, q) % q

print(k)
print(p, q, g, y, h, r, s, sep=',')

'''
516081660287290857303106041337362876434325919397
180085593791508295346273423844236672339529319991924110327255270917858493493345299800615314524299320066806895354429976173332282295460587950377809600292446537411907628568599603375827769404064672706774870194085492090905235979942093907713387405089913530830285562903861798734400682400477696202626239784027815756743,1104557835344327388179959575459485168270179811873,12123130287415691980412799115852211438041361537629665887505875653480334758768653356186670191369220495071169163684628920472799820550702077504266995537429931375859921727628448675950283799950650147579085064551465705638988147809494939857856057753379728219901701640783558562051528103036368234500856431719560283977,153241032666637708500087115670945288942606390433856489794132009126475826308531535572154555100639916171117128048502364849141148971767208837503665967407569265064568891309540988565553839914146806227763059644757144119318730674662405727893965437702774458275036467867455574739153189363237418960939893039809283051396,1385824418563203380722890100218787157930069255720,183925646270847239867260215378432900916502633028,436799484642842219800973572361673811756031905793
'''

这里我们已知随机密钥 $k$，则根据解密公式：$x\equiv r^{-1}(ks-H(m))modq$ 即可求解 flag值。

EXP:

from Crypto.Util.number import *
from gmpy2 import *

k = 516081660287290857303106041337362876434325919397
p, q, g, y, h, r, s = 

x = pow(r,-1,q)*(k*s - h) % q
print(long_to_bytes(x))

例题3(爆破k)

例题：

from Crypto.Util.number import *
from gmpy2 import *
import random
from hashlib import sha1

flag = b'NSSCTF{******}'
x = bytes_to_long(flag[7:-1])
q = getPrime(160)
while True:
    t = 2 * getPrime(1024 - 160) * q
    if isPrime(t + 1):
        p = t + 1
        break

h = random.randint(1, p - 2)
g = powmod(h, (p - 1) // q, p)
y = powmod(g, x, p)

k = random.randint(1, 2 ** 20)
h = bytes_to_long(sha1(flag).digest())
r = powmod(g, k, p) % q
s = (h + x * r) * invert(k, q) % q

print(p, q, g, y, h, r, s, sep=',')

'''
232417151883368054516605830055952160880670978405659642430490266526812173832260694367747527073710881837011446979721612305292421320659024746677762768546062204667982434421909069699232443934954948621989591579797868456092114070836952969434575376001506929674552348068770008372122577006292508896861736763536866927803,1060620588842972438899442975440075622760455989309,44768917997338391084473070795826454686235133633449491548990823774293785572926447629504858779348089685405258929615166589878059445496157877609271409247291851051458981907101186579608794375285071749267992568084274340113631398343686417217303951367225442028660036057697482769986378944452588020590255584155269256494,15138996987998119707598289320039109142321006894939822519880182224518520081477043981280071391740009592471003140567144801380938339219351181199631326928072076701047098027574156016825986846074561729606049521802900128625422690773497399889659856302120776644163941218439800480424839747421786767043056933847090680182,1234324463386109858490857668286337914111126412605,83059873905640807538034110870406547173849277486,1037113405299161333909263662048616171640477800689
'''

EXP:

from Crypto.Util.number import *
from gmpy2 import *

p, q, g, y, h, r, s = 232417151883368054516605830055952160880670978405659642430490266526812173832260694367747527073710881837011446979721612305292421320659024746677762768546062204667982434421909069699232443934954948621989591579797868456092114070836952969434575376001506929674552348068770008372122577006292508896861736763536866927803, 1060620588842972438899442975440075622760455989309, 44768917997338391084473070795826454686235133633449491548990823774293785572926447629504858779348089685405258929615166589878059445496157877609271409247291851051458981907101186579608794375285071749267992568084274340113631398343686417217303951367225442028660036057697482769986378944452588020590255584155269256494, 15138996987998119707598289320039109142321006894939822519880182224518520081477043981280071391740009592471003140567144801380938339219351181199631326928072076701047098027574156016825986846074561729606049521802900128625422690773497399889659856302120776644163941218439800480424839747421786767043056933847090680182, 1234324463386109858490857668286337914111126412605, 83059873905640807538034110870406547173849277486, 1037113405299161333909263662048616171640477800689

for k in range(2 ** 19, 2 ** 20):
    x = pow(r, -1, q) * (k * s - h) % q
    if pow(g, x, p) == y:
        print(long_to_bytes(x))

例题4(k共享)

题目：

from Crypto.Util.number import *
from gmpy2 import *
import random, os
from hashlib import sha1

flag = b'NSSCTF{******}'
x = bytes_to_long(flag[7:-1])
q = getPrime(160)
while True:
    t = 2 * getPrime(1024 - 160) * q
    if isPrime(t + 1):
        p = t + 1
        break

h = random.randint(1, p - 2)
g = powmod(h, (p - 1) // q, p)
y = powmod(g, x, p)

k = random.randint(1, q - 1)
h1 = bytes_to_long(sha1(os.urandom(20)).digest())
h2 = bytes_to_long(sha1(os.urandom(20)).digest())

r1 = powmod(g, k, p) % q
s1 = (h1 + x * r1) * invert(k, q) % q

r2 = powmod(g, k, p) % q
s2 = (h2 + x * r2) * invert(k, q) % q

print(p, q, g, y, sep=',')
print(f'(h1, r1, s1) = {h1}, {r1}, {s1}')
print(f'(h2, r2, s2) = {h2}, {r2}, {s2}')

'''
210145691501773578738377348033311975109097030624229264466788375283767533919326464465174636163332688722224581089450096402386769629298291083760904660611942708672827379160413284668161925839781496461631351601204438246469229385099502482935026018822981911090812522940670041497153171870525509599105379465080807836739,1198259187878727821038260641949026509111920270433,196070047258907618917994526171930725445041293594930451395813866076072912063450682578080857729624238303488600108328510272125657269217146364809009485238108834676036204139548225631723795405961936284355847299908680455823548490632994637690236187388967162639874250381038952479751971000815634264164616859879415711204,113892660154815927896065262713895897930759494276164055918916161302422466569511088272910136873131800900714081704069756811621255412857706485959053239368822240528099295009222226245910132521725945595438150866573053321959800267582969690297868819195328552315818030736239776841162267931134372314713955308734418315441
(h1, r1, s1) = 288608925920757761908146359265652114672439915971, 70578181835631077171027353972389074292538336310, 10138006399945530096316239936933893062913122896
(h2, r2, s2) = 292826952671130597654686220387088149924959682815, 70578181835631077171027353972389074292538336310, 601690991376973737187439170192344609140533841457
'''

由题目条件可知两次加密过程中采用了相同的随机密钥 $k$ ，那么我们就可以推导出 $k$ 的值：$k(s_1-s_2)\equiv H(m_1)-H(m_2)modq$

EXP:

from Crypto.Util.number import *
from gmpy2 import *

p, q, g, y = 
(h1, r1, s1) = 288608925920757761908146359265652114672439915971, 70578181835631077171027353972389074292538336310, 10138006399945530096316239936933893062913122896
(h2, r2, s2) = 292826952671130597654686220387088149924959682815, 70578181835631077171027353972389074292538336310, 601690991376973737187439170192344609140533841457

k = (h1 - h2) * invert(s1 - s2, q) % q
assert r1 == pow(g, k, p) % q
print("k =",k)

x = pow(r1, -1, q) * (k * s1 - h1) % q
print("x =",long_to_bytes(x))

例题5(线性K攻击)

题目：

from Crypto.Util.number import *
from gmpy2 import *
import random, os
from hashlib import sha1

flag = b'NSSCTF{******}'
x = bytes_to_long(flag[7:-1])
q = getPrime(160)
while True:
    t = 2 * getPrime(1024 - 160) * q
    if isPrime(t + 1):
        p = t + 1
        break

h = random.randint(1, p - 2)
g = powmod(h, (p - 1) // q, p)
y = powmod(g, x, p)

k1 = random.randint(1, q - 1)
h1 = bytes_to_long(sha1(os.urandom(20)).digest())
h2 = bytes_to_long(sha1(os.urandom(20)).digest())

r1 = powmod(g, k1, p) % q
s1 = (h1 + x * r1) * invert(k1, q) % q

k2 = 123123 * k1 + 213123
r2 = powmod(g, k2, p) % q
s2 = (h2 + x * r2) * invert(k2, q) % q

print(p, q, g, y, sep=',')
print(f'(h1, r1, s1) = {h1}, {r1}, {s1}')
print(f'(h2, r2, s2) = {h2}, {r2}, {s2}')

'''
248604602422910519027498055793201627104398247250051630675851204123046532565091226817355596701504144088229653099743376808895289529496613830342512762129413510736292280512125238597842272278759062316841642879931389189133077729867472969222059167595875408174942099331637968192646102751148170581062955479624795726803,1104888844039545494900451432921843691528361275421,179257043110102699137458477420103918554872480317804287592976758715562911175633485646459879116166908433112797107120185385797578936816467598792615613604506581942838034541566199558185747738124918980520382612117236824821289695971682490339435434475068166996448327818163252231908864987994621701200833277417006819871,159005646554391816923406887830979293509940608900317516799440723663025433835806129396573183140255812264469834382283265708315756408213239261422711978866078853083466087419416562334241054267280145144390020259686908268717687033486580768464112616050989149109970819378634556467410938187635262996429292198522330176893
(h1, r1, s1) = 1120509804671964533658263171593312514868852942664, 1092962395012982010125401435695438064740884031414, 870170073609429297690585216747619586014108208356
(h2, r2, s2) = 656005973206825385654744797203106611919992582404, 670071713626039247317315700175834986360787995677, 628224540815786948931138021701729862880600004465
'''

题目分析：

$s_1\equiv (h_1+x\ast r_1)k_1^{-1}modq$

$s_2\equiv (h_2+x\ast r_2)k_2^{-1}modq$

$k_2=123123\ast k_1+213123$

这里未知量有 $x\mathrm{和}{k}_1,k_2$ 推导有：

$s_1\ast k_1\equiv h1+x\ast r_1$

$s_2\ast k_2\equiv h2+x\ast r_2$

利用消元法，化简方程组：

$s_1\ast k_1\ast r_2\equiv (h1+x\ast r_1)\ast r_2$

$s_2\ast k_2\ast r_1\equiv (h2+x\ast r_2)\ast r_1$

两式相减：

$k_1\ast s_1\ast r_2-s_2\ast r_1\ast (123123\ast k_1+213123))\equiv h_1\ast r_2-h_2\ast r_{1}modq$

$k_1\ast (s_1\ast r_2-s_2\ast r_1\ast 123123)\equiv h_1\ast r_2-h_2\ast r_1+s_2\ast r_1\ast 213123modq$

$k_1=\frac{h_1\ast r_2-h_2\ast r_1+s_2\ast r_1\ast 213123}{s_1\ast r_2-s_2\ast r_1\ast 123123}$

EXP:

from Crypto.Util.number import *
from gmpy2 import *

p, q, g, y = 
(h1, r1,
 s1) = 1120509804671964533658263171593312514868852942664, 1092962395012982010125401435695438064740884031414, 870170073609429297690585216747619586014108208356
(h2, r2,
 s2) = 656005973206825385654744797203106611919992582404, 670071713626039247317315700175834986360787995677, 628224540815786948931138021701729862880600004465

a = 123123
b = 213123
k1 = (h1 * r2 - h2 * r1 + s2 * r1 * b) * pow(s1 * r2 - s2 * r1 * a, -1, q) % q
assert pow(g, k1, p) % q == r1
print("k1 =",k1)

x = pow(r1, -1, q) * (k1 * s1 - h1) % q
print("x =",long_to_bytes(x))

例题6(构造k多项式求根)

题目：

from Crypto.Util.number import *
from gmpy2 import *
import random, os
from hashlib import sha1

flag = b'NSSCTF{******}'
x = bytes_to_long(flag[7:-1])
q = getPrime(160)
while True:
    t = 2 * getPrime(1024 - 160) * q
    if isPrime(t + 1):
        p = t + 1
        break

h = random.randint(1, p - 2)
g = powmod(h, (p - 1) // q, p)
y = powmod(g, x, p)

k1 = getPrime(64)
h1 = bytes_to_long(sha1(os.urandom(20)).digest())
h2 = bytes_to_long(sha1(os.urandom(20)).digest())

r1 = powmod(g, k1, p) % q
s1 = (h1 + x * r1) * invert(k1, q) % q

k2 = k1 ** 2
r2 = powmod(g, k2, p) % q
s2 = (h2 + x * r2) * invert(k2, q) % q

print(p, q, g, y, sep=',')
print(f'(h1, r1, s1) = {h1}, {r1}, {s1}')
print(f'(h2, r2, s2) = {h2}, {r2}, {s2}')

'''
149328490045436942604988875802116489621328828898285420947715311349436861817490291824444921097051302371708542907256342876547658101870212721747647670430302669064864905380294108258544172347364992433926644937979367545128905469215614628012983692577094048505556341118385280805187867314256525730071844236934151633203,829396411171540475587755762866203184101195238207,66574026244680091069518316704198662248616273869450543744119730925010741440009253221024269611702409992941009990810332788277765645172259247006372628490621965540198848398426564970679555614131868432980284836439911133867262442690193568710848637395672849408343310213459158340521055585119320384998345666167582343319,113160705347753807573510544961675737216163465780410091146961355899888740070887609372690358436441644814541660853774651122835982545831124611677315480368181887207540230682166723644914975259836636643623433521449469020855846403587460946141523029279424148079870427795307567353090927085416942020200370785081813797653
(h1, r1, s1) = 592632528802360292619666791193487295190074169778, 795968565942507694843762914966982971870045417145, 487794348943414262409771614228723658312500553511
(h2, r2, s2) = 1058580579731370773060403038853538332541169097744, 583365243104095833266690387387608816520877657593, 382650490310903109923939919364642244260295044662
'''

已知条件 : $k_2=k_1^2$

$s_1\equiv (h_1+x\ast r_1)k_1^{-1}modq$

$s_2\equiv (h_2+x\ast r_2)k_2^{-1}modq$

这里未知量有 $x\mathrm{和}{k}_1,k_2$ 推导有：

$s_1\ast k_1\equiv h1+x\ast r_1$

$s_2\ast k_2\equiv h2+x\ast r_2$

利用消元法，化简方程组：

$s_1\ast k_1\ast r_2\equiv (h1+x\ast r_1)\ast r_2$

$s_2\ast k_2\ast r_1\equiv (h2+x\ast r_2)\ast r_1$

两式相减得到：$k_1\ast s_1\ast r_2-k_2\ast s_2\ast r_1\equiv h_1\ast r_2-h_2\ast r_{1}modq$

构造有限域 $GF(q)$ 上的模多项式：$f=k_1\ast s_1\ast r_2-k_2\ast s_2\ast r_1-h_1\ast r_2+h_2\ast r_1$

然后计算多项式的根值即可：f.roots()

from gmpy2 import *
from Crypto.Util.number import *

p, q, g, y = 
(h1, r1,
 s1) = 592632528802360292619666791193487295190074169778, 795968565942507694843762914966982971870045417145, 487794348943414262409771614228723658312500553511
(h2, r2,
 s2) = 1058580579731370773060403038853538332541169097744, 583365243104095833266690387387608816520877657593, 382650490310903109923939919364642244260295044662

PR.<k1> = PolynomialRing(GF(q))
f = s1 * k1 * r2 - s2 * k1 ^ 2 * r1 - h1 * r2 + h2 * r1
k1 = f.roots()[1][0]
print("k1 =",k1)
assert int(k1).bit_length() == 64
assert pow(int(g), int(k1), int(p)) % int(q) == int(r1)

x = pow(r1, -1, q) * (k1 * s1 - h1) % q
print("x =",long_to_bytes(int(x)))