//r: 027a872f87c98bf7aead3c514ffb9e5f25719c7d5d4591aa34f3e3388110807d
//s: 4ed20d3dc3265e845fd13c021ca8dce97f2361565e030e5b05d2ccf58dc5357f
//x: 04df4bd35d60b090d6a9da5360479e08fc6fc2b6ece2d5f989735836bb0e508a
//y: 7349916cdf36d4830f752a47ac7ff518bfa8ac92cbad4ad66e9f06e7943deedf
以上是本題的橢圓曲線數位簽章,可以用來證明本題的確是出題者出的(雖然這是廢話)。
什麼?你說你不知道橢圓曲線數位簽章是什麼?
ECDSA (Elliptic Curve Digital Signature Algorithm) 是一種基於橢圓曲線密碼學的數位簽章算法。
在了解什麼是 ECDSA 前,我們要先來簡單了解一下橢圓曲線是怎麼運作的。
在密碼學中,我們在意的是在模某個質數
給定一個質數
我們說一個點
此外,我們特別定義一個無限遠的點
對於
第三點
如果
如果是
此時以
可以證明
給定一兩的點
這類問題通常很難在合理的時間內解出,除非有特殊的性質(
這也是橢圓曲線數位簽章(ECDSA)的基礎。
數位簽章是一種使用了公鑰密碼學的技術。數位簽章就如同紙本簽章一樣,能被用來確認訊息發送者的身份是否正確,同時使發送者無法否認。
而 ECDSA 則是透過了 ECDLP 的難度來達到難以偽造及難以否認的特點。
更準確來說,ECDSA 需要滿足「正確性」(被正確簽署的簽章總是要被驗證為正確的)和「難以偽造」(沒辦法在合理時間內偽造)兩個性質。
具體來說,假設愛麗絲要用他的私鑰
那麼最常見的實作方式是他們先決定好:
以上的資訊皆可以被公布,不會影響到簽章的安全性及完整性。
接下來,給定一個訊息
特別注意,若
而鮑伯可以由以下步驟驗證簽章
可以注意到簽章通過檢驗並不百分之百保證是愛麗絲簽的,因為就算
在本題實作中,我們考慮以 SHA256 作為
現在,請你實作驗證簽章的演算法,也就是給你
secp256k1 的參數如下:(來源:https://en.bitcoin.it/wiki/Secp256k1 )
0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
55066263022277343669578718895168534326250603453777594175500187360389116729240
32670510020758816978083085130507043184471273380659243275938904335757337482424
0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
115792089237316195423570985008687907852837564279074904382605163141518161494337
TIOJ 上的 python 有 SHA256 可以使用。
每筆測資有五行輸入。
第一行會輸入以十六進位表示的
第二行會輸入以十六進位表示的
第三行會輸入以十六進位表示的
第四行會輸入以十六進位表示的
第五行會輸入以十六進位表示的
如果你判斷簽章是正確的,請輸出 True
,否則請輸出 False
。
TIOJ April Fools Day Contest 2024 pI
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~1 | 範例測試資料。 | 0 |
2 | 0~3 | 無額外限制。 | 99 |
3 | 0~7 | 有額外限制。 | 1 |