還記得那個(gè)時(shí)候電腦上有英特爾內(nèi)置的標(biāo)志嗎?嗯,很快,可能就會(huì)出現(xiàn)宣傳后量子robust的貼紙。這些貼紙將表明所使用的軟件不會(huì)被量子計(jì)算機(jī)
還記得那個(gè)時(shí)候電腦上有“英特爾內(nèi)置”的標(biāo)志嗎?嗯,很快,可能就會(huì)出現(xiàn)宣傳“后量子robust”的貼紙。這些貼紙將表明所使用的軟件不會(huì)被量子計(jì)算機(jī)的出現(xiàn)所破壞。不管你喜不喜歡,我們區(qū)塊鏈上現(xiàn)有的所有簽名都將被破壞,我們的大部分?jǐn)?shù)字簽名軟件也將隨之被破壞,因此Corda和IOTA等應(yīng)用程序正在為后量子時(shí)代做準(zhǔn)備,而其他許多應(yīng)用程序只是在睡夢(mèng)中走進(jìn)一個(gè)信任被破壞的世界。
介紹
公鑰方法為我們提供了驗(yàn)證發(fā)送方完整性的方法。不幸的是,大多數(shù)用于創(chuàng)建這些簽名的方法,如素?cái)?shù)因子分解(如RSA)和橢圓曲線方法,都將被量子計(jì)算機(jī)破解。本文概述了一些基于哈希值的簽名方法,這些方法可以用作基于哈希值的簽名的基礎(chǔ)。
我們?cè)诨ヂ?lián)網(wǎng)上看到的許多問題都與交易中缺乏信任有關(guān)。你收到的電子郵件和你訪問的網(wǎng)站往往沒有多少信任。為了獲得信任,我們檢查發(fā)件人的電子郵件地址,但是任何人都可以偽造該地址。因此,我們?cè)絹碓蕉嗟貏?chuàng)建數(shù)字簽名,并在其中使用私鑰對(duì)消息簽名。通過這種方式,我們可以檢查身份驗(yàn)證、完整性和不可否認(rèn)性。
通過這個(gè),Alice創(chuàng)建了一個(gè)密鑰對(duì):一個(gè)公鑰和一個(gè)私鑰。然后,她獲取消息的哈希值,并用她的私鑰加密這個(gè)哈西還(這是她的簽名),并將消息和簽名傳遞給Bob。然后Bob讀取消息并對(duì)其進(jìn)行哈希。然后他將Alice的簽名公開解密,并檢查哈希值。如果他們匹配,他就知道她簽了名,而且在此過程中沒有更改:
目前,我們經(jīng)常使用RSA、DSA和ECDSA對(duì)消息進(jìn)行簽名。這些都是基于找出一個(gè)數(shù)的因子難度和離散對(duì)數(shù)的處理。目前這些方法都存在計(jì)算困難的問題,但是有了量子計(jì)算機(jī),它們變得容易多了。Peter Shor證明了其在多項(xiàng)式時(shí)間內(nèi)是可以破解它們的。
在所有提出的方法中,基于哈希值的方法看起來有很大的機(jī)會(huì)成功地創(chuàng)建量子robust簽名?;诰W(wǎng)格和代碼的方法正在研究中,但哈希值方法的使用已經(jīng)得到了很好的定義,可以提供現(xiàn)有方法的最佳替代方法。哈希值方法也常常帶來其他優(yōu)點(diǎn),比如向前安全性,這意味著被破解的密鑰不會(huì)顯示所有以前的密鑰。
Lamport簽名
不久的將來,我們可能需要放棄現(xiàn)有的公鑰方法,轉(zhuǎn)而使用對(duì)量子計(jì)算機(jī)更具挑戰(zhàn)性的技術(shù)。隨著Shor 's alorigthm [here]在量子計(jì)算機(jī)上的實(shí)現(xiàn),我們將看到我們的RSA和橢圓曲線方法被量子robust方法所取代。一種方法是Lamport簽名方法,由Leslie B. Lamport于1979年創(chuàng)建:
目前,它被認(rèn)為是一種用于消息簽名的量子健壯技術(shù)。當(dāng)我們簽署一條消息時(shí),我們獲取它的哈希值,然后用我們的私鑰加密。然后使用公鑰來證明它,并將證明我們使用私鑰簽署了它。Lamport簽名使用512個(gè)隨機(jī)哈希值作為私鑰,它們被分成集合A和集合B。公鑰是這些哈希值。私鑰的大小為16KB(2×256×256位),公鑰的大小也是16KB(512哈希值,每個(gè)哈希值包含256位)。
創(chuàng)建Lamport哈希值簽名的基本方法是:
· 我們創(chuàng)建了兩個(gè)數(shù)據(jù)集,其中包含256個(gè)隨機(jī)256位數(shù)字(集合A和集合B)。
· 接下來我們?nèi)∶總€(gè)隨機(jī)數(shù)的哈希值。這將產(chǎn)生512個(gè)哈希值,并將作為公鑰。
· 然后我們使用SHA-256對(duì)消息進(jìn)行哈希,然后測(cè)試哈希值的每個(gè)位(0…255)。如果它是0,我們用集合A中的第i個(gè)數(shù),否則我們用集合B中的第i個(gè)數(shù)。
· 簽名是256個(gè)隨機(jī)數(shù)(來自集合A或集合B),公鑰是512個(gè)哈希值(來自集合A和集合B)。
該過程如下圖所示:
我們可以使用Lamport方法進(jìn)行一次性簽名,但是在其核心格式中,每次簽名都需要一個(gè)新的公鑰。Lamport的主要問題是我們只能使用每個(gè)公鑰簽名一次。不過,我們可以通過創(chuàng)建一個(gè)哈希值樹來克服這個(gè)問題,它是將多個(gè)公鑰合并到一個(gè)根目錄中。
一個(gè)示例運(yùn)行,它只顯示前幾個(gè)私鑰和第一個(gè)公鑰:
==== Private key (keep secret) =====
Priv[0][0] (SetA): 6f74f11f20953dc91af94e15b7df9ae00ef0ab55eb08900db03ebdf06d59556c
Priv[0][1] (SetB): 4b1012fc5669b45672e4ab4b659a6202dd56646371a258429ccc91cdbcf09619
Priv[1][0] (SetA): 19f0f71e913ca999a23e152edfe2ca3a94f9869ba973651a4b2cea3915e36721
Priv[1][1] (SetB): 04b05e62cc5201cafc2db9577570bf7d28c77e923610ad74a1377d64a993097e
Priv[2][0] (SetA): 15ef65eda3ee872f56c150a5eeecff8abd0457408357f2126d5d97b58fc3f24e
Priv[2][1] (SetB): 8b5e7513075ce3fbea71fbec9b7a1d43d049af613aa79c6f89c7671ab8921073
Priv[3][0] (SetA): 1c408e62f4c44d73a2fff722e6d6115bc614439fff02e410b127c8beeaa94346
Priv[3][1] (SetB): e9dcbdd63d53a1cfc4c23ccd55ce008d5a71e31803ed05e78b174a0cbaf43887
==== Public key (show everyone)=====
Pub[0][0]: 7f2c9414db83444c586c83ceb29333c550bedfd760a4c9a22549d9b4f03e9ba9
Pub[0][1]: 4bc371f8b242fa479a20f5b6b15d36c2f07f7379f788ea36111ebfaa331190a3
Pub[1][0]: 663cda4de0bf16a4650d651fc9cb7680039838d0ccb59c4300411db06d2e4c20
Pub[1][1]: 1a853fde7387761b4ea22fed06fd5a1446c45b4be9a9d14f26e33d845dd9005f
==== Message to sign ===============
Message: The quick brown fox jumps over the lazy dog
SHA-256: d7a8fbb307d7809469ca9abcb0082e4f8d5651e46d3cdb762d02d0bf37c9e592
==== Signature =====================
Sign[0]: 4b1012fc5669b45672e4ab4b659a6202dd56646371a258429ccc91cdbcf09619
Sign[1]: 04b05e62cc5201cafc2db9577570bf7d28c77e923610ad74a1377d64a993097e
Sign[2]: 8b5e7513075ce3fbea71fbec9b7a1d43d049af613aa79c6f89c7671ab8921073
Sign[3]: 1c408e62f4c44d73a2fff722e6d6115bc614439fff02e410b127c8beeaa94346
The signature test is True
在本例中,我們?nèi)‰S機(jī)數(shù),然后將其轉(zhuǎn)換為字符串。因此,“6f74f11f20953dc91af94e15…0db03ebdf06d59556c”的SHA-256簽名為7f2c9414db83444c586c…49d9b4f03e9ba9。如果可以看到消息哈希值(“the quick brown fox jumps over the lazy dog”)在開頭有一個(gè)十六進(jìn)制D值,在二進(jìn)制中是1101,我們看到我們從SetB[0]、SetB[1]、SetA[2]和SetB[3]中提取。
結(jié)論
Lamport OTS速度很快,但是密鑰大小和簽名相對(duì)較大。那么Lamport有什么問題呢?這是一次性使用,我們只能使用公鑰一次。但是,在比特幣中,我們可以用當(dāng)前的公鑰簽名,然后添加下一個(gè)公鑰。然而,ECDSA的最大優(yōu)點(diǎn)是公鑰只有33字節(jié)長(zhǎng),簽名是73字節(jié),而Lamport簽名的公鑰是16 KB(256位的512個(gè)版本),簽名是8KB(256個(gè)版本的256位)。
但是,EDCSA使用橢圓曲線密碼,量子計(jì)算機(jī)很容易破解它,所以我們的公鑰和簽名可能已經(jīng)成為過去。因此,IOTA和Corda等應(yīng)用程序已經(jīng)識(shí)別出了這種風(fēng)險(xiǎn),并用后量子技術(shù)取代了RSA和ECC方法。IOTA集成了Winternitz一次性簽名方案(W-OTS),該方案生成了有效的密鑰大小和壓縮簽名,Corda使用區(qū)塊鏈后量子簽名(BPQS) [Link]。()