Schnorr身份識別協(xié)議是又一個(gè)零知識證明協(xié)議，相比Fiamt協(xié)議有兩點(diǎn)不同，一是其安全性依賴于離散對數(shù)的困難性，二是該方案使用乘法群，從而可以提前計(jì)算了一些參數(shù)，減小了證明者實(shí)時(shí)計(jì)算開銷，特別適合計(jì)算能力有限的環(huán)境下運(yùn)行，例如嵌入式設(shè)備，介紹Schnorr之前，先對Schnorr所依據(jù)的乘法群和離散對數(shù)的背景進(jìn)行介紹。

1.首先理解一下群(goup)的概念

現(xiàn)在我們的微信和qq上有各種群，如同事群、校友群、攝影群或者其他臨時(shí)發(fā)起的群，群的一個(gè)特點(diǎn)是成員具有某種程度上的相似性，例如同事群是所有成員在一個(gè)公司工作，攝影群成員則是成員有共同的愛好，但群不僅是成員的簡單集合，還可以描述群成員之間的關(guān)系，例如同事群中有些成員是其他成員的領(lǐng)導(dǎo)從而可以指揮其他成員，這種對象之間的互相作用我們稱之為操作或者運(yùn)算。

再來看數(shù)學(xué)上的群概念，其實(shí)和生活中的微信群有那么一點(diǎn)點(diǎn)相似之處，既包括元素的集合，也包括了元素的運(yùn)算或者相互之間的操作，舉一個(gè)乘法群作為例子，其定義如下：

設(shè)G為某種元素組成的一個(gè)非空集合，若在G內(nèi)定義一個(gè)稱為乘法的運(yùn)算“·”，滿足以下條件：
（1）（封閉性）,有；
（2）（結(jié)合性），有a·（b·c）=（a·b）·c；
（3）在G中有一個(gè)元素e，對G中任意元素g，有e·g=g·e=g，元素e稱為單位元；

??(4）對G中任一元素g都存在G中的一個(gè)元素g'，使得g·g'=g'·g=e，g稱為可逆元，g'稱為g的逆元，記作，

則稱G關(guān)于“·”形成一個(gè)群（Group），記作（G，·）。

這個(gè)定義看起來就很數(shù)學(xué)，很讓人頭暈。逐條來看一下，首先是G，G表示元素的集合，這比較容易理解，這里用全體非零實(shí)數(shù)R*集合作為例子，再來看四個(gè)條件，第一個(gè)是封閉性，意思是說集合里的元素相乘后還是在群里，例如2.2=4，而4還是屬于非零實(shí)數(shù)集合，用通俗的話理解封閉性就是肥水不流外人田，群成員按照規(guī)則相互（這里的規(guī)則是相乘）仍在群里；第二個(gè)是結(jié)合性，例如(2.3).4=2.(3.4)，比較容易理解；第三個(gè)是存在單位元，這個(gè)單位元跟誰作用都得到這個(gè)成員本身，非零實(shí)數(shù)乘法群的單位元就是1，因?yàn)槠渌麛?shù)和1相乘仍得到它本身，什么都沒變，如果是加法群，那么單位元就是0，因?yàn)槿魏螖?shù)和0相加等于沒加;最后一個(gè)條件是逆元，元素和元素的逆元相乘后得到單位元，例如，。

因?yàn)樗膫€(gè)條件都滿足，因此全體非零實(shí)數(shù)R*對于的乘法形成一個(gè)群。數(shù)學(xué)家定義了群的概念后，就可以圍繞著群做更多深入研究（玩出花了），這里再補(bǔ)充兩個(gè)概念：

1.有限群和無限群。群G中元素的個(gè)數(shù)稱為G的階，記作｜G｜，如果個(gè)數(shù)無限，則稱群G為無限群，例如全體非零實(shí)數(shù)R*集合乘法群是一個(gè)無限群，反過來如果個(gè)數(shù)有限，則稱群G為有限群，有限群得到的研究更多，“吾生也有涯，而知也無涯。以有涯隨無涯，殆已”，先把有限的研究明白再說無限吧；

2.循環(huán)群。說到研究明白，循環(huán)群是目前已被完全解決了的—類群，循環(huán)群的定義是當(dāng)一個(gè)群G由一個(gè)元素a生成時(shí)，稱為循環(huán)群（Cyclic Group），記為G=<a>，a被稱為生成元(generator)。先舉一個(gè)不太嚴(yán)謹(jǐn)?shù)睦?#xff0c;按照老子的宇宙論理論，假設(shè)萬物是一個(gè)群的話，那么這個(gè)萬物群是一個(gè)循環(huán)群，而這個(gè)循環(huán)群的生成元就是老子指的道，因?yàn)椤暗郎?#xff0c;一生二，二生三，三生萬物”

再舉一個(gè)嚴(yán)謹(jǐn)?shù)睦?#xff0c;模5乘法群=<2>=<4>,即為4階循環(huán)群，2和4均為其生成元。事實(shí)上，由群中乘法定義知：

=2 mod 5=2 ? ? ? ? ? ? ? ? ?=4 mod 5=4

=4 mod 5=4 ? ? ? ? ? ? ? ? ?=16 mod 5=1

=8 mod 5=3 ? ? ? ? ? ? ? ? ?=64 mod 5= 3

=16 mod 5=1 ? ? ? ? ? ? ? ??=256 mod 5=2

可以看出，由2可以生成群，由4也可以生成群，因此2和4均是群的生成元。

群還有同構(gòu)...等一下，本文不是介紹Schnorr身份識別方案嗎，怎么在群論上狂奔了？另外群論和本文主題有啥關(guān)系？正如前文提了一下，Schnorr身份識別方案基于整數(shù)模p的階為q的乘法循環(huán)群，因?yàn)槿菏窃睾瓦\(yùn)算的集合，也就是說其中的元素和運(yùn)算規(guī)則都確定了，因此給定了一個(gè)群，證明者和驗(yàn)證者都以此為基礎(chǔ)，減少了雙方需要溝通交流確定協(xié)議參數(shù)的時(shí)間，從而改進(jìn)了效率。

2.離散對數(shù)的困難性

離散對數(shù)也使用了循環(huán)群的概念：給定一個(gè)素?cái)?shù)p，有限乘法群上的一個(gè)生成元g和群里的一個(gè)元素，找到整數(shù)x，其中，滿足(mod p)，x就是要求的值，因?yàn)榭梢詫懽?#xff0c;因此被稱為離散對數(shù)，注意這里的對數(shù)運(yùn)算符和普通對數(shù)運(yùn)算符不一樣，因?yàn)檫@里是同余計(jì)算，不是通常所理解的等號。

另外“”符號這里表示同余，意思是對p求余和對p求余相等，例如p=11，生成元g=2，β=9，有(mod 11)。

那么離散對數(shù)困難性又是什么難題？其指的是當(dāng)已知大素?cái)?shù)p和它的一個(gè)生成元g，(mod p)，對于給定的β，計(jì)算x被認(rèn)為是很困難的，而給定x計(jì)算β卻相對容易,目前普遍認(rèn)為離散對數(shù)難題被認(rèn)為比大數(shù)分解還難一點(diǎn)，和大數(shù)分解一樣，這類難題被稱為陷阱函數(shù)：正向計(jì)算容易，反向計(jì)算困難，和生活中的各種陷阱一樣，例如一些培訓(xùn)機(jī)構(gòu)交錢容易退錢困難，正是陷阱函數(shù)的困難性保證了運(yùn)用陷阱函數(shù)的各類加密算法的安全性。

3.Schnorr 身份識別協(xié)議

介紹了群的概念和離散對數(shù)困難性的背景知識后，可以來了解Schnorr身份協(xié)議了。為了方便理解 Schnorr 身份識別協(xié)議，再次請出Alice和Bob，同樣的Alice作為一個(gè)擁有眾多秘密的女子，她擁有一個(gè)私鑰，并想向Bob證明這一點(diǎn)，但是又不能透露自己的私鑰給Bob，他們再次運(yùn)用零知識證明協(xié)議完成這個(gè)過程，這里的零知識證明協(xié)議是Schnorr算法。

在開始之前，他們要先確定一些公共參數(shù)

• p = 任何的素?cái)?shù)；
• q = p-1 的因數(shù)，即q整除p-1；
• 生成元g；
• 公鑰（mod p），其中s是Alice擁有的私鑰， 0<s<q；

{p,q,g,v}四個(gè)參數(shù)是全局變量，Alice和Bob都知道，s是Alice的秘密，只有Alice知道。

a.首先Alice使用她的私鑰s加密一條消息 "M"，并發(fā)送給Bob，過程如下：

Alice選擇一個(gè)隨機(jī)數(shù) r，其中0<r<q，計(jì)算得到X值：?X = (mod p)?,接著 Alice 將 X 值與她要發(fā)送的消息"M"連接起來，得到?(M||X)，然后對 (M||X) 進(jìn)行哈希運(yùn)算，得到相應(yīng)哈希值?e = Hash(M||X)?，其中Hash()是哈希函數(shù)，但工作還沒結(jié)束，Alice還要計(jì)算一個(gè)值y= r + s*e，最后Alice將下列信息發(fā)送給Bob：

• 消息M
• 數(shù)字簽名 e 和 y

b.Bob對接收到消息進(jìn)行驗(yàn)證，過程如下：

Bob從 Alice 那兒拿到了消息M?和數(shù)字簽名（e 和 y），除此之外，Bob 同樣知道公共參數(shù)，分別是：

• 公鑰 "v";
• 素?cái)?shù) "p";
• 素?cái)?shù)"q";
• 生成元"g"。

現(xiàn)在 Bob 計(jì)算 X'= (mod p)?，如果X'=X，則Bob確認(rèn)Alice說的為真，否則為假;?

驗(yàn)證過程如下：

因?yàn)?#xff08;mod p），代入X'的等式的互換：X'=(mod p)=(mod p)

又因?yàn)閥=r+s*e，得r=y-s*e，代入該值得到X'=(mod p)，因此X=X'。

得到了X'后，Bob可以進(jìn)一步計(jì)算消息e' = H ( M||X')并和Alice發(fā)送過來的e是否相等。

如果Alice沒有私鑰，她很難構(gòu)造私鑰以便通過Bob的驗(yàn)證，因?yàn)殡x散對數(shù)的困難性，而Bob也很難反推出Alice的私鑰，因?yàn)锳lice并沒有發(fā)送隨機(jī)數(shù)r給Bob，同樣因?yàn)殡x散對數(shù)的困難性，Bob不能從X = (mod p)?反推出r從而想通過y=r+s*e反推出Alice的私鑰s。

?

總結(jié)

以上是生活随笔為你收集整理的Schnorr身份识别方案的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。