张一帆15180110001密码学实验_ex6

密码学

第一道题目

题目给了dsa参数，dsa公钥；以及一个签名样例，包括消息的hash‘h_m’以及消息的签名(r, s)；同时说明了随机数k的取值为 0 ~ 2^16。数据如下：

p = 0x800000000000000089e1855218a0e7dac38136ffafa72eda7859f2171e25e65eac698c1702578b07dc2a1076da241c76c62d374d8389ea5aeffd3226a0530cc565f3bf6b50929139ebeac04f48c3c84afb796d61e5a4f9a8fda812ab59494232c7d2b4deb50aa18ee9e132bfa85ac4374d7f9091abc3d015efc871a584471bb1
q = 0xf4f47f05794b256174bba6e9b396a7707e563c5b
g = 0x5958c9d3898b224b12672c0b98e06c60df923cb8bc999d119458fef538b8fa4046c8db53039db620c094c9fa077ef389b5322a559946a71903f990f1f7e0e025e2d7f7cf494aff1a0470f5b64c36b625a097f1651fe775323556fe00b3608c887892878480e99041be601a62166ca6894bdd41a7054ec89f756ba9fc95302291
y = 0x84ad4719d044495496a3201c8ff484feb45b962e7302e56a392aee4abab3e4bdebf2955b4736012f21a08084056b19bcd7fee56048e004e44984e2f411788efdc837a0d2e5abb7b555039fd243ac01f0fb2ed1dec568280ce678e931868d23eb095fde9d3779191b8c0299d6e07bbb283e6633451e535c45513b2d33c99ea17
m = b"""For those that envy a MC it can be hazardous to your health
So be friendly, a matter of life and death, just like a etch-a-sketch"""
h_m = 0xd2d0714f014a9784047eaeccf956520045c45265
r = 548099063082341131477253921760299949438196259240
s = 857042759984254168557880549501802188789837994940
h_k = "0954edd5e0afe5542a4adf012611a91912a3ec16"

因为k的取值空间太小了，2^16 == 65535 ，我们可以穷举k，并判断每一个k对应的x（私钥）的hash是否与给定的hash‘h_k’相同。完整代码如下：

import hashlib
from Crypto.Util.number import *
p = 0x800000000000000089e1855218a0e7dac38136ffafa72eda7859f2171e25e65eac698c1702578b07dc2a1076da241c76c62d374d8389ea5aeffd3226a0530cc565f3bf6b50929139ebeac04f48c3c84afb796d61e5a4f9a8fda812ab59494232c7d2b4deb50aa18ee9e132bfa85ac4374d7f9091abc3d015efc871a584471bb1
q = 0xf4f47f05794b256174bba6e9b396a7707e563c5b
g = 0x5958c9d3898b224b12672c0b98e06c60df923cb8bc999d119458fef538b8fa4046c8db53039db620c094c9fa077ef389b5322a559946a71903f990f1f7e0e025e2d7f7cf494aff1a0470f5b64c36b625a097f1651fe775323556fe00b3608c887892878480e99041be601a62166ca6894bdd41a7054ec89f756ba9fc95302291
y = 0x84ad4719d044495496a3201c8ff484feb45b962e7302e56a392aee4abab3e4bdebf2955b4736012f21a08084056b19bcd7fee56048e004e44984e2f411788efdc837a0d2e5abb7b555039fd243ac01f0fb2ed1dec568280ce678e931868d23eb095fde9d3779191b8c0299d6e07bbb283e6633451e535c45513b2d33c99ea17
h_m = 0xd2d0714f014a9784047eaeccf956520045c45265
r = 548099063082341131477253921760299949438196259240
s = 857042759984254168557880549501802188789837994940
h_k = "0954edd5e0afe5542a4adf012611a91912a3ec16"
for k in range(pow(2, 16)):
    x = ((s * k - h_m) * inverse(r, q)) % q
    x = bytes(hex(x)[2:], 'UTF-8')
    if hashlib.sha1(x).hexdigest() == h_k:
        print(x)
        print(k)
        break

输出：

15fb2873d16b3e129ff76d0918fd7ada54659e49
16575

第二道题目

题目给了一组消息和dsa签名，其中所有的dsa签名共用一组参数。在这些签名中，随机数k被重复的使用了，要求恢复x。

首先判断哪些数据使用了相同的k：判断依据是不同消息的签名r是否相同。找到三组r相同的签名：

0---8
1---9
2---10

然后随便找一组开始恢复k：

l = [
    [1267396447369736888040262262183731677867615804316,
        1105520928110492191417703162650245113664610474875, 0xa4db3de27e2db3e5ef085ced2bced91b82e0df19],
    [29097472083055673620219739525237952924429516683,
     51241962016175933742870323080382366896234169532, 0xa4db3de27e2db3e5ef085ced2bced91b82e0df19],
    [277954141006005142760672187124679727147013405915,
        228998983350752111397582948403934722619745721541, 0x21194f72fe39a80c9c20689b8cf6ce9b0e7e52d4],
    [1013310051748123261520038320957902085950122277350,
     1099349585689717635654222811555852075108857446485, 0x1d7aaaa05d2dee2f7dabdc6fa70b6ddab9c051c5],
    [203941148183364719753516612269608665183595279549,
     425320991325990345751346113277224109611205133736, 0x6bc188db6e9e6c7d796f7fdd7fa411776d7a9ff],
    [502033987625712840101435170279955665681605114553,
     486260321619055468276539425880393574698069264007, 0x5ff4d4e8be2f8aae8a5bfaabf7408bd7628f43c9],
    [1133410958677785175751131958546453870649059955513,
     537050122560927032962561247064393639163940220795, 0x7d9abd18bbecdaa93650ecc4da1b9fcae911412],
    [559339368782867010304266546527989050544914568162,
     826843595826780327326695197394862356805575316699, 0x88b9e184393408b133efef59fcef85576d69e249],
    [1021643638653719618255840562522049391608552714967,
        1105520928110492191417703162650245113664610474875, 0xd22804c4899b522b23eda34d2137cd8cc22b9ce8],
    [506591325247687166499867321330657300306462367256,
     51241962016175933742870323080382366896234169532, 0xbc7ec371d951977cba10381da08fe934dea80314],
    [458429062067186207052865988429747640462282138703,
        228998983350752111397582948403934722619745721541, 0xd6340bfcda59b6b75b59ca634813d572de800e8f]
]
d = {
    0: l[0],
    1: l[1],
    2: l[2],
    8: l[8],
    9: l[9],
    10: l[10]
}
k = ((d[0][2] - d[8][2]) * inverse(d[0][0] - d[8][0], q)) % q

然后恢复x，并判断结果是否正确

x0 = ((d[0][0] * k - d[0][2]) * inverse(d[0][1], q)) % q
print(x0)
x8 = ((d[8][0] * k - d[8][2]) * inverse(d[8][1], q)) % q
print(x8)
print(hashlib.sha1(bytes(hex(x0)[2:], 'UTF-8')).hexdigest())

输出：

1379952329417023174824742221952501647027600451162
1379952329417023174824742221952501647027600451162
ca8f6f7c66fa362d40760d135b763eb8527d3d52

和题目给出的x的hash对比，符合要求。