DAY 19-数位签章- DSA

「快点签名啦。」

今天要来介绍数位签章。
首先澄清一点，数位签章是以数学运算的方式进行的签章，「签章」只是模拟签章的行为与功能的词。
我们刷卡消费时在电子版上签的那个东西并不叫数位签章。

数位签章是靠公钥密码学来实现的，我们之前讲过他的原理，
用私钥加密，用公钥解密。
而我们要做到的就是可以让人确认资讯来源、确认是否被修改。
而另一方面，数位签章的签署人无法否认所为，因为只有他可以签出这样的数位签章。

那麽今天就来实际说一下怎麽操作。

RSA数位签章

RSA的数位签章非常简单，就是直接将RSA的算法颠倒过来，用私钥加密用公钥解密。
这里就不再赘述。

DSA（digital signature algorithm）

这里指的DSA是数位签章演算法，
不是 Driving Safety Alerting 也不是 Democratic Socialists of America，
我室友修的资料结构与演算法那也叫 DSA。

我要讲的是一种数位签章的演算法。

密钥建立

1. 选定一个1024位元的质数 p

2. 找一个160位元的 q 整除 ( p-1 )

3. 寻找一个整数 使得

   方法是寻找

   这里会用到费马小定理跟循环群的概念

4. 再选择一个 d 介於0跟q之间。

5. 计算

经过上面的运算就建立好了密钥，

其中公钥是（p, q, , ），私钥是 d。

签章

1. 临时密钥（ephemeral key） 介於 0 到 q 之间。
2. 计算
3. 计算 ，其中 x 是要签章的讯息。

这里的SHA( ) 就是杂凑函数，我们签章的对象是讯息的杂凑值，这样可避免过长的结果。

於是签章的结果就是( r, s )，总共有320位元。

验章

1. 计算

2. 

3. 

4. 

如过运算结果 v 跟 r 相同，那就确认是本人所签署。
今天先介绍DSA演算法，算法相较於之前都较复杂一些，
有兴趣的读者可以试着证明 DSA 的正确性。

明天我们将来看看由bitcoin所使用的数位签章方法，ECDSA，椭圆曲线数位签章。

图片来源：
https://twitter.com/maj33dullah/status/1401605392195522566
https://memegenerator.net/instance/58480943/correction-guy-stop-look-at-my-beautiful-e-signature