如何使用量子計(jì)算機(jī)創(chuàng)建Lamport哈希值簽名

還記得那個(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］。