Schnorr身份识别方案
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)容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 主成分分析法(PCA)原理漫谈
- 下一篇: Android JNI开发流程介绍