![](\"https:\/\/www.jarvisw.com\/wp-content\/uploads\/2016\/12\/12.png\")
<\/p>\n\u6700\u8fd1\u57fa\u672c\u90fd\u5728\u5fd9\u5f00\u53d1\uff0c\u5f88\u5c11\u73a9CTF\uff0c\u6e56\u6e58\u676f\u5c31\u770b\u4e86dsa\u8fd9\u9898\uff0c\u8003\u8651\u5230\u6211\u4e4b\u524d\u5bf9DSA\u4e0d\u592a\u719f\uff0c\u6240\u4ee5\u8fd9\u91cc\u5bf9\u77e5\u8bc6\u70b9\u505a\u4e2a\u6574\u7406\uff1a<\/p>\n
DSA\u53ef\u4ee5\u770b\u4f5c\u662fELGamel\u7684\u53d8\u79cd\uff0c\u5b89\u5168\u6027\u4e5f\u662f\u57fa\u4e8e\u79bb\u6563\u5bf9\u6570\u96be\u9898\uff0c\u4e14\u5176\u8ba1\u7b97\u901f\u5ea6\u6bd4RSA\u5feb\u3002<\/p>\n
\u8fd9\u91cc\u5bf9DSA\u7684\u76f8\u5173\u77e5\u8bc6\u70b9\u505a\u4e00\u4e2a\u6574\u7406\uff1a<\/p>\n
\u5bc6\u94a5\u751f\u6210\u65b9\u5f0f\uff1a<\/p>\n
1.\u786e\u5b9a\u5bc6\u94a5\u957f\u5ea6L\u548cN\uff0c\u5176\u4e2dL\u662f64\u7684\u500d\u6570\uff0c\u4e14\u6ee1\u8db3$512\\leq L \\leq 1024$\uff0c\u5f53\u7136\uff0c\u968f\u7740\u76ee\u524d\u5bf9\u5b89\u5168\u6027\u8981\u6c42\u7684\u63d0\u9ad8\uff0c\u4e5f\u6709\u6807\u51c6\u5141\u8bb8\u66f4\u957f\u7684L\uff0c\u5176\u4e2dN\u7684\u957f\u5ea6\u5fc5\u987b\u5c0f\u4e8e\u7b49\u4e8e\u7b7e\u540d\u6240\u4f7f\u7528\u7684\u54c8\u5e0c\u7b97\u6cd5\u7684\u8f93\u51fa\u4f4d\u957f\u5ea6\uff0c\u5e38\u89c1\u7684L\uff0cN\u53d6\u503c(1024,160),(2048,224),(2048,256)\u548c(3072,256)<\/p>\n
2. \u53d6\u4e00\u4e2a\u957f\u5ea6\u4e3aN\u7684\u8d28\u6570q\u3002<\/p>\n
3. \u53d6\u4e00\u4e2a\u957f\u5ea6\u4e3aL\u7684\u8d28\u6570p\uff0c\u4e14\u6ee1\u8db3p-1\u662fq\u7684\u500d\u6570\u3002<\/p>\n
4.\u53d6\u4e00\u4e2a\u6570$g\\neq 1$\u6ee1\u8db3$ g = h^\\frac{p-1}{q}\\;(mod\\;p)$,\u5176\u4e2d$1< h<p-1$\u3002<\/p>\n
5.\u79c1\u94a5x\uff0c\u53d6\u968f\u673a\u503cx\u6ee1\u8db3$0< x < q$\u3002\u53d6$y = g^x \\;(mod\\;p)$<\/p>\n
\u4e8e\u662f\uff0c\u516c\u94a5\u4e3a(y,p,q,g)\u3002<\/p>\n
\u7b7e\u540d\u8fc7\u7a0b\u5982\u4e0b\uff0c\u5047\u8bbe\u5f85\u7b7e\u540d\u5185\u5bb9\u4e3am\uff0c\u54c8\u5e0c\u7b97\u6cd5\u4e3aH(x)\uff1a<\/p>\n
\u5bf9\u6bcf\u4e2a\u5f85\u7b7e\u540d\u7684\u5185\u5bb9\u53d6\u968f\u673a\u503ck\u6ee1\u8db3$1<k< q$\u3002<\/p>\n
\u8ba1\u7b97\uff1a$r = (g^k\\;mod\\;p)\\;mod\\;q$<\/p>\n
\u8ba1\u7b97\uff1a$s = k^{-1}(H(m)+xr)\\;mod\\;q$<\/p>\n
\u5982\u679c\u8ba1\u7b97\u7ed3\u679c\u4e2ds = 0\uff0c\u5219\u91cd\u65b0\u9009\u62e9k\u8ba1\u7b97<\/p>\n
\u6700\u540e\u5c06(r,s)\u5143\u7ec4\u4f5c\u4e3a\u7b7e\u540d\u3002<\/p>\n
\u7b7e\u540d\u6821\u9a8c\u8fc7\u7a0b\u5982\u4e0b\uff1a<\/p>\n
\u5982\u679c\u7b7e\u540d\u4e0d\u6ee1\u8db3$0< r < q$\u6216\u8005$0< s < q$\uff0c\u5219\u8be5\u7b7e\u540d\u4e0d\u5408\u6cd5\u3002\u5982\u679c\u6ee1\u8db3\u8fd9\u4e24\u4e2a\u6761\u4ef6\uff1a<\/p>\n
\u8ba1\u7b97\uff1a$w = s^{-1}\\;mod\\;q$<\/p>\n
\u8ba1\u7b97\uff1a$u_1 = H(m)\\cdot w\\;mod\\;q$<\/p>\n
\u8ba1\u7b97\uff1a$u_2= r \\cdot w\\;mod\\;q$<\/p>\n
\u8ba1\u7b97\uff1a$v =(g^{u_1}y^{u_2}\\;mod\\;p)\\;mod\\;q$<\/p>\n
\u5982\u679c\u6700\u7ec8v\u4e0er\u76f8\u7b49\uff0c\u5219\u6821\u9a8c\u6210\u529f\uff0c\u5426\u5219\u5931\u8d25\u3002<\/p>\n
\u7b97\u6cd5\u8bc1\u660e\uff1a<\/p>\n
\u9996\u5148\uff0c\u6211\u4eec\u5728\u751f\u6210g\u65f6\u9700\u8981\u6ee1\u8db3$ g = h^\\frac{p-1}{q}\\;(mod \\;p)$\uff0c\u90a3\u4e48$g^q = \u00a0h^{p-1}\\;mod\\;p$\uff0c\u6839\u636e\u8d39\u9a6c\u5c0f\u5b9a\u7406\uff0c\u56e0\u4e3ap\u662f\u8d28\u6570\uff0c\u6240\u4ee5$h^{p-1} \\equiv 1\\;(mod\\; p)$\uff0c\u56e0\u6b64\u6709$g^q \\equiv \u00a0h^{p-1}\\equiv 1 \\;(mod\\;p)$\u3002<\/p>\n
\u7531\u4e8eg>0\u4e14q\u662f\u8d28\u6570\uff0c\u6240\u4ee5$g^{x}\\;mod\\; p = g^{x\\;mod\\;q}\\;mod\\;p$<\/p>\n
\u7136\u540e\u518d\u770b\u6821\u9a8c\u7684\u8fc7\u7a0b\uff1a<\/p>\n
$s = k^{-1}(H(m)+xr)\\;mod\\;q$\uff0c\u53d8\u5316\u53ef\u5f97\uff1a<\/p>\n
$k \\equiv \u00a0s^{-1}(H(m)+xr) $<\/p>\n
$\\equiv H(m)w+xrw\\; (mod\\; q)$<\/p>\n
\u90a3\u4e48<\/p>\n
$g^k \\equiv g^{H(m)w}g^{xrw}$<\/p>\n
$\\equiv\u00a0g^{H(m)w}y^{rw} $<\/p>\n
$\\equiv g^{u_1}y^{u_2}\\; (mod\\; p)$<\/p>\n
\u5907\u6ce8\uff1a\u8fd9\u4e00\u6b65\u5229\u7528\u4e86\uff1a<\/p>\n
$g^{H(m)w}\\;mod\\; p $<\/p>\n
$= g^{H(m)w\\;(mod\\;q)}\\;\\;(mod\\;p)$<\/p>\n
$ =g^{u_1} \\;(mod\\;p)$<\/p>\n
\u548c<\/p>\n
$g^{xrw}\\;(mod\\; p) $<\/p>\n
$= g^{xrw\\;(mod\\;q)}\\;mod\\;p$<\/p>\n
$=g^{xu_2} \\;(mod\\;p)$<\/p>\n
$=y^{u_2}\\; (mod\\; p) $<\/p>\n
\u6240\u4ee5\u6700\u540e\u6709\uff1a<\/p>\n
$r = (g^k\\;mod\\;p)\\;mod\\;q $<\/p>\n
$= (g^{u_1}y^{u_2}\\;mod\\;p)\\;mod\\;q$<\/p>\n
$ =v $<\/p>\n
\u8bc1\u6bd5\u3002<\/p>\n
\u6700\u540e\u8ba8\u8bba\u4e00\u4e0b\u5b89\u5168\u6027\uff0cDSA\u7684\u7b7e\u540d\u8fc7\u7a0b\u4e2d\uff0ck\u662f\u968f\u673a\u800c\u4e14\u4fdd\u5bc6\u7684\uff0c\u5982\u679c\u77e5\u9053k\uff0c\u53ef\u4ee5\u6839\u636er\u548cs\u8ba1\u7b97\u51fa\u79c1\u94a5x\uff1a<\/p>\n
$x = r^{-1}(s\\cdot k-H(m))\\;(mod\\;q)$<\/p>\n
\u540c\u7406\uff0c\u5982\u679c\u4e24\u4e2a\u6d88\u606f\u4f7f\u7528\u4e86\u76f8\u540c\u7684k\uff0c\u6216\u8005\u4e24\u4e2ak\u4e4b\u95f4\u6709\u8054\u7cfb\uff0c\u6bd4\u5982\u4f7f\u7528\u7684\u662fk\u548ck+1\uff0c\u8fd9\u6837\u7684\u60c5\u51b5\u4e0b\u5373\u4f7fk\u4fdd\u5bc6\uff0c\u4e5f\u662f\u5371\u9669\u7684\uff0c\u56e0\u4e3a\u8fd9\u65f6\u5019\u6211\u4eec\u6709\uff1a<\/p>\n
$s_1 = k^{-1}(H(m_{1})+xr)\\;(mod\\; q)$<\/p>\n
$s_2 = k^{-1}(H(m_{2})+xr)\\;(mod\\; q)$<\/p>\n
\u76f8\u540c\u7684k\u4f1a\u5bfc\u81f4\u76f8\u540c\u7684r\uff0c\u4ee5\u4e0a\u4e24\u4e2a\u65b9\u7a0b\u6070\u597d2\u4e2a\u672a\u77e5\u6570\uff0c\u53ea\u9700\u89e3\u51fa\u540c\u4f59\u65b9\u7a0b\u7ec4\u5373\u53ef\u77e5\u9053k\u548cx\u3002<\/p>\n
\u6700\u540e\u56de\u5230\u672c\u9898\uff0c\u672c\u9898\u7ed9\u51fa\u7684message3\u548cmessage4\u7684\u7b7e\u540d\u4e2d$r$\u662f\u76f8\u540c\u7684\uff1a<\/p>\n
<\/p>\n
\u4e5f\u5c31\u662f\u8bf4\uff0c\u8fd9\u4e24\u4e2a\u7b7e\u540d\u4f7f\u7528\u4e86\u76f8\u540c\u7684k\uff0c\u53ef\u4ee5\u901a\u8fc7\u4e0a\u9762\u6240\u8ff0\u7684\u65b9\u6cd5\u6c42\u89e3\u51fa\u79c1\u94a5\u3002\u4f46\u662f\uff0c\u672c\u9898\u6709\u4e2a\u5751\uff0c\u90a3\u5c31\u662fmessage4\u88ab\u4eba\u4e3a\u4fee\u6539\u4e86\uff0c\u6700\u540e\u7b7e\u540d\u6821\u9a8c\u662f\u8fc7\u4e0d\u4e86\u7684\uff1a<\/p>\n
![](\"https:\/\/www.jarvisw.com\/wp-content\/uploads\/2016\/12\/qm.png\")
<\/p>\n
\u8fd8\u771f\u4e0d\u77e5\u9053\u662f\u4ec0\u4e48\u8111\u6d1e\uff0c\u540e\u6765\u4e00\u76f4\u89c9\u5f97\u662f\u4e0d\u662f\u4f5c\u8005\u6587\u4ef6\u6539\u9519\u4e86\uff0c\u5b9e\u5728\u6ca1\u529e\u6cd5\u53ea\u80fd\u7206\u7834\u6587\u4ef6\u5185\u5bb9\uff0c\u4e0d\u8fc7\u8fd9\u6837\u6ca1\u5565\u610f\u601d\u4e86\u3002\u601d\u8def\u5e94\u8be5\u5c31\u662f\u8fd9\u4e2a\u3002<\/p>\n
\u6700\u540e\uff0c\u5982\u679c\u4f60\u60f3\u81ea\u5df1\u60f3\u5f04\u4e2a\u9898\u76ee\u5c1d\u8bd5\u4e00\u4e0b\u7684\u8bdd\uff0c\u6211\u81ea\u5df1\u4fee\u8ba2\u4e86\u9053\u9898\uff0c\u628a\u5751\u7ed9\u53bb\u6389\u4e86\uff0c\u7cbe\u534e\u7559\u4e0b\u7ed9\u5927\u5bb6\u5b66\u4e60\u3002\u53ef\u4ee5\u5728\u6211\u7684Jarvis OJ<\/a> – Challenges – Crypto \u5206\u7c7b\u4e0b\u627e\u5230DSA\u8fd9\u9898\uff0c\u5927\u5bb6\u53ef\u4ee5\u81ea\u884c\u505a\u4e2a\u5c1d\u8bd5\u3002<\/p>\n <\/p>\n","protected":false},"excerpt":{"rendered":" \u6700\u8fd1\u57fa\u672c\u90fd\u5728\u5fd9\u5f00\u53d1\uff0c\u5f88\u5c11\u73a9CTF\uff0c\u6e56\u6e58\u676f\u5c31\u770b\u4e86dsa\u8fd9\u9898\uff0c\u8003\u8651\u5230\u6211\u4e4b\u524d\u5bf9DSA\u4e0d\u592a\u719f\uff0c\u6240\u4ee5\u8fd9\u91cc\u5bf9\u77e5\u8bc6\u70b9\u505a\u4e2a\u6574\u7406 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[33,54,53],"class_list":["post-169","post","type-post","status-publish","format-standard","hentry","category-ctf","tag-ctf","tag-dsa","tag-53"],"_links":{"self":[{"href":"https:\/\/www.jarvisw.com\/index.php?rest_route=\/wp\/v2\/posts\/169","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.jarvisw.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.jarvisw.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.jarvisw.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.jarvisw.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=169"}],"version-history":[{"count":43,"href":"https:\/\/www.jarvisw.com\/index.php?rest_route=\/wp\/v2\/posts\/169\/revisions"}],"predecessor-version":[{"id":233,"href":"https:\/\/www.jarvisw.com\/index.php?rest_route=\/wp\/v2\/posts\/169\/revisions\/233"}],"wp:attachment":[{"href":"https:\/\/www.jarvisw.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=169"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.jarvisw.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=169"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.jarvisw.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=169"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}