## # Digital Signature

• 完整性 integrity

保证该消息在传输过程中没有发生更改，简单的说就是如果消息被更改，则签名失效；

对于比较长的消息或大的文档来说，通常需要对其先进行压缩 通常是进行哈希方法 Hash Function获取哈希值作为可以代表该消息或文档的message digest又称为指纹 fingerprint ，然后对哈希值进行签名，这里选用的哈希函数需要具备以下属性：

• Arbitrary message size h(x) can be applied to messages x of any size.

• Fixed output length h(x) produces a hash value z of fixed length.

• Efficiency h(x) is relatively easy to compute.

• 抗原像性 Preimage resistance：对于给定的输出z，不可能找到任何输入x使得h（x）= z，即h（x）是单向的计算。

例子：Bob发送签名消息给Alice： kpr,B=d, kpub,B=e (ek(x), sigkpr,B(z)). ek是双方的对称加密如AES密钥，然后Bob使用RSA进行签名，s=sigkpr,B(z)) ≡ zd mod n，任何人都可以通过Bob的公钥计算出哈希值 se ≡ z mod n.，如果hash function不是单向的，则任何人都可以反向计算出对应的消息x h−1(z) = x.从而就绕过了双方的对称加密

• 抗第二原像性 Second preimage resistance：给定x1，因此给定h（x1），通过计算找到任何x2使得h（x1）= h（x2）是不可行的。 根据pigeonhole principle或Dirichlet’s drawer principle这是不可能的，所以只能退而求其次我们要尽可能保证实践中无法构造出x2，意味着不存在analytical attack，至于避免爆破攻击（exhaustive brute force）我们可以增加哈希方法输出的长度。

• 耐碰撞性 Collision resistance：通过计算找到任何一对值 x1≠x2使得h（x1）= h（x2）是不可行的（跟前面不同，这里是任意x1 x2而不是给定x1）

This property is harder to achieve than weak collision resistance since an attacker has two degrees of freedom: Both messages can be altered to achieve similar hash values. We show now how Oscar could turn his ability to find collisions into an attack. He starts with two messages, for instance: x1 = Transfer \$10 into Oscar’s account x2 = Transfer \$10,000 into Oscar’s account He now alters x1 and x2 at “nonvisible” locations, e.g., he replaces spaces by tabs, adds spaces or return signs at the end of the message, etc.

The most important consequence of the birthday attack is that the number of messages we need to hash to find a collision is roughly equal to the square root of the number of possible output values, i.e., about √2n = 2n/2.

Hash functions should have at least 160-bit output length in order to withstand collision attacks; 256 bit or more is desirable for long-term security. MD5, which was widely used, is insecure. Serious security weaknesses have been found in SHA-1, and the hash function should be phased out. The SHA-2 algorithms all appear to be secure. The ongoing SHA-3 competition will result in new standardized hash functions in a few years.

除此之外，特别对于签名的有效性来说，还需要具备另外一个属性：找不到有效可行的方法来修改信息或哈希摘要以及签名，并且让修改后的新签名变成新消息的有效签名

• 真实性 authenticity

某个签名必须只能是对应的私钥持有者签的名，所以通过签名可以认定其身份，使接收者非常有理由相信该消息是由已知的发件人创建的；

反例：对称加密算法就不适用于签名，因为大家持有的是一样的密钥

• 不可否认性 Non-repudiation

已对某些信息进行签名的有关方不能否认自己做过这个签名，当然其他人也不能仅通过访问公钥来伪造有效签名；

### # Note: 关于哈希 Hash Function和MAC-message authentication codes

digital signature VS Hmac

- Hash MAC(keyed hash function) Digital signature
Integrity Yes Yes Yes
Authentication No Yes Yes
Non-repudiation No No Yes
Kind of keys None Symmetric Asymmetric

Message Authentication Code (MAC) 又称为keyed hash function以及cryptographic checksum

secret key suffix 虽然没有延展性攻击，但是存在birthday attack

secret key suffix VS HMAC

However, the big advantage of HMAC over H(m||k) is that collision-resistance of the underlying hashing function is not needed. https://crypto.stackexchange.com/questions/5725/why-is-hmk-insecure My opinion: the biggest advantage of hmac construction is that the attacker can't compute hmac value without knowing the secret key while with H(m||s) attacker still can simply compute H(random messge) to find a collision(存在birthday attack)

## # RSA Signature

P.S. 有意思的是RSA后两个字母刚好跟 Signatrue Algorithm缩写一样，但实际上是 Rivest–Shamir–Adleman 三位大佬姓氏的缩写

RSA安全性是基于大素数分解问题 Large Prime factorization

## # Elgamal Digital Signature

Elgamal signature

## # ECDSA - Elliptic Curve Digital Signature Algorithm

ECDSA secp256k1

keccak

secp256k1's elliptic curve y2 = x3 + ax+b (a=0,b=7) over the real numbers: the graph is

secp256k1 is actually defined over the field: y2 = x3+ax+b over Fp graph will in reality look like random scattered points...

https://github.com/bitcoinbook/bitcoinbook/blob/97df56f77c06813b1e028b5b1f2dbc036f27b1fc/ch04.asciidoc#L128 https://github.com/jimmysong/programmingbitcoin/blob/master/ch03.asciidoc

ECC位长度在160–256位的范围内, 其安全性与1024–3072位的RSA和DL相同，更短的位长，处理时间越短，并且签名也短，由于这些原因，1998年椭圆曲线数字签名算法（ECDSA）被ANSI 美国国家标准研究所进行了标准化。

ECDSA的构建步骤跟DSA很接近，但是其离散对数问题是构造在基于素数域Zp或者是伽罗华域 Galois fields GF(2^m) 的椭圆曲线上，所以在实际计算过程上完全跟DSA不同。

https://hackernoon.com/hacking-a-bitcoin-wallet-642u36sa

https://github.com/bitcoinbook/bitcoinbook/blob/db678d15c08e7be4180ba9e9fbc60ee004eb5c3c/ch06.asciidoc

https://www.mycryptopedia.com/public-key-private-key-explained/

Sig = Fsig(Fhash(m),dA)

dA is the signing private key

m is the transaction

Fhash is the hashing function

Fsig is the signing algorithm

Sig is the resulting signature

The signing function (Fsig) produces a signature (Sig) that comprises of two values: R and S:

Sig = (R, S)

Once R and S have been calculated, they are serialized into a byte stream that is encoded using an international standard encoding scheme that is known as the Distinguished Encoding Rules (or DER). In order to verify that the signature is valid, a signature verification algorithm is used. Verification of a digital signature requires the following:

Signature (R and S)

Transaction hash

The public key that corresponds to the private key that was used to create the signature

Verification of a signature effectively means that only the owner of the private key (that generated the public key) could have produced the signature on the transaction. The signature verification algorithm will return ‘TRUE’ if the signature is indeed valid.

Sig = (R, S, SIGHASH) R and S are serialized into a byte-stream using an international standard encoding scheme called the Distinguished Encoding Rules, or DER. Signature Hash Types (SIGHASH): - ALL - NONE - SINGLE - ANYONECANPAY ECDSA Math AND The Importance of Randomness in Signatures If the same value k is used in the signing algorithm on two different transactions, the private key can be calculated and exposed to the world! To avoid this vulnerability, the industry best practice is to not generate k with a random-number generator seeded with entropy, but instead to use a deterministic-random process seeded with the transaction data itself. This ensures that each transaction produces a different k. The industry-standard algorithm for deterministic initialization of k is defined in RFC 6979, published by the Internet Engineering Task Force