从某种程度上来说这是我的作业。最后python写的不好,不要借鉴了。。。

首先我们先来回顾一下RSA算法(有点忘了)

  • 生成两个不相等的质数p和q
  • 计算n=p*q
  • 计算n的欧拉函数Euler_n
  • 选择一个整数e,大于1且小于Euler_n并与Euler_n互质,一般为65537
  • 用辗转相除求出e对Euler_n的模反元素d
  • n,e为公钥,n,d为私钥
  • 用公钥(n,e)加密,求出C=pow(M,e,n)
  • 用私钥(n,d)解密,求出M=pow(C,d,n)

那么其实DSA也大概是这个过程,只是算法不一样

1.生成系统参数p,q,g

  • q 为素数,长度为160位,也就是
  • p 为L位长度的素数,且L在且L可被64整除
  • g 为随机整数 其中

2.封装私钥,公钥

用户选取一个私钥x,其中x为
随后生成公钥为y(g,x,p),其中并公开

此外还有一个参数k,k为$$0由此我们得到五个参数 p q g x k

3.用签名过程

我们这里要计算两个东西

如果算出来s=0那就必须重新生成一个k再次进行运算
其中是SHA1对M的加密的散列吗
最后输出的(r,s)是签名人对M的前民

r的生成和消息无关,但是由于k随机,所以一个消息可以有多个签名。
从r恢复k简单,从s恢复x不可行

由此我们得到五个参数p q g x k,以及签名后的消息(r,s),还有消息的散列值H(M)

4.验证过程

  • 计算
  • 计算
  • 计算

如果v=r那么签名有效




5.openssl命令相关


def dsa_openssl(): os.system("openssl dsaparam -out ./DSA/dsaparam.pem 1024") os.system("openssl gendsa -out ./DSA/dsa_private_key.pem ./DSA/dsaparam.pem") # 从格式中提取私钥 os.system("openssl dsa -in ./DSA/dsa_private_key.pem -pubout -out ./DSA/dsa_public_key.pem") # 利用私钥生成公钥 os.system( "openssl dgst -sign ./DSA/dsa_private_key.pem -sha256 -out ./DSA/sign.txt ./DSA/raw.txt") # 利用 sha256 生成消息摘要并对用私钥加密 os.system( "openssl dgst -verify ./DSA/dsa_public_key.pem -sha256 -signature ./DSA/sign.txt ./DSA/raw.txt") # 利用公钥验证签名 child = spawn("openssl dgst -verify ./DSA/dsa_public_key.pem -sha256 -signature ./DSA/sign.txt ./DSA/raw.txt") x = child.read() return "OK" in x # 预期返回的值

6.用python实现DSA


class DSA: def __init__(self): self.p, self.q = self.q_generate() self.g = self.g_generate() self.x = random.randint(1, self.q - 1) self.y = pow(self.g, self.x, self.p) self.k = gmpy2.mpz(random.randint(0, self.q)) def __str__(self): return "p=" + str(self.p) + "\n" + "q=" + str(self.q) + "\n" "g=" + str( self.g) + "\n" + "x=" + str(self.x) + "\n" "y=" + str(self.y) + "\n" + "k=" + str(self.k) def start(self, p, q, g, x, y, k): self.p, self.q, self.g, self.x, self.y = p, q, g, x, y self.k = gmpy2.mpz(random.randint(pow(2, 100), self.q)) # 这里的p,q生成其实写的并不符合DSA的位数规范。比较明智的选择是从openssl生成的秘钥中提取公钥和私钥。 def q_generate(self): while True: q = gmpy2.mpz(random.randint(pow(2, 159), pow(2, 160))) if gmpy2.is_prime(q): self.q = q break k = 408138805224325729123715286 while True: p = gmpy2.mpz(q * k - 1) print p if gmpy2.is_prime(q) and p < gmpy2.mpz(pow(2, 1023)) and p > gmpy2.mpz(pow(2, 1024)): self.p = p break elif p > gmpy2.mpz(pow(2, 128)): print "error" break else: k += 1 return self.p, self.q def g_generate(self): h = 2 self.g = pow(h, (self.p - 1) / self.q, self.p) return self.g def encode(self, message): M = SHA.new() M.update(bytes(message)) M = M.hexdigest() M = gmpy2.mpz("0x" + M) while True: r = pow(self.g, self.k, self.p) % self.q s = (M + self.x * r) % self.q / self.k if s == 0: self.k = gmpy2.mpz(random.randint(pow(2, 100), self.q)) continue else: break return (r, s, M) def verify(self, r, s, M): w = 1 / s % self.q u1 = (M * w) % self.q u2 = r * w % self.q v = (pow(self.g, u1, self.p) * pow(self.y, u2, self.p)) % self.p % self.q print "v=" + str(v) if v == r: return True else: return False dsa = DSA() message = "Shaobaobaoerfdsfadfawafwewfa" dsa.start(private_key_reader.p, private_key_reader.q, private_key_reader.g, x=private_key_reader.priv, y=private_key_reader.pub, k=0) print dsa r, s, M = dsa.encode(message) print dsa.verify(r, s, M) # 由于p和q实在太大,最后运算最终会出错。 # 还有个问题就是大数运算的问题,由于u1比p小很多,导致小费马定理失效,但是python对于大数运算的支持并不是这么优秀,就算用了大数运算库也无济于事。这也是为啥最后还是采用openssl的原因