關(guān)于我們
書(shū)單推薦
新書(shū)推薦
|
密碼學(xué)中的可證明安全性
本書(shū)全面介紹可證明安全性的發(fā)展歷史及研究成果, 分為五章, 第1章介紹可證明安全性用到的一些數(shù)學(xué)知識(shí)和基本工具, 第2章介紹語(yǔ)義安全的公鑰密碼體制的定義, 第3章介紹幾類常用的語(yǔ)義安全的公鑰機(jī)密體制, 第4章介紹基于身份的密碼體制, 第5章介紹基于屬性的密碼體制。
本書(shū)由教育部高等學(xué)校信息安全專業(yè)教學(xué)指導(dǎo)委員會(huì)、中國(guó)計(jì)算機(jī)學(xué)會(huì)教育專業(yè)委員會(huì)共同指導(dǎo),符合《高等學(xué)校信息安全專業(yè)指導(dǎo)性專業(yè)規(guī)范》。
本書(shū)全面介紹可證明安全性的發(fā)展歷史及研究成果。全書(shū)共5章,第1章介紹可證明安全性涉及的數(shù)學(xué)知識(shí)和基本工具,第2章介紹語(yǔ)義安全的公鑰密碼體制的定義,第3章介紹幾類常用的語(yǔ)義安全的公鑰機(jī)密體制,第4章介紹基于身份的密碼體制,第5章介紹基于屬性的密碼體制。
本書(shū)取材新穎,不僅包括可證明安全性的基礎(chǔ)理論和實(shí)用算法,同時(shí)也涵蓋了可證明安全性的密碼學(xué)的*新研究成果,力求使讀者通過(guò)本書(shū)的學(xué)習(xí)了解本學(xué)科*新的發(fā)展方向。
本書(shū)特別適合作為高等院校信息安全、計(jì)算機(jī)工程和信息對(duì)抗等專業(yè)的本科生和網(wǎng)絡(luò)空間安全學(xué)科研究生教材,也可作為通信工程師和計(jì)算機(jī)網(wǎng)絡(luò)工程師的參考讀物。
21世紀(jì)是信息時(shí)代,信息已成為社會(huì)發(fā)展的重要戰(zhàn)略資源,社會(huì)的信息化已成為當(dāng)今世界發(fā)展的潮流和核心,而信息安全在信息社會(huì)中將扮演極為重要的角色,它會(huì)直接關(guān)系到國(guó)家安全、企業(yè)經(jīng)營(yíng)和人們的日常生活。 隨著信息安全產(chǎn)業(yè)的快速發(fā)展,全球?qū)π畔踩瞬诺男枨罅坎粩嘣黾,但我?guó)目前信息安全人才極度匱乏,遠(yuǎn)遠(yuǎn)不能滿足金融、商業(yè)、公安、軍事和政府等部門的需求。要解決供需矛盾,必須加快信息安全人才的培養(yǎng),以滿足社會(huì)對(duì)信息安全人才的需求。為此,教育部繼2001年批準(zhǔn)在武漢大學(xué)開(kāi)設(shè)信息安全本科專業(yè)之后,又批準(zhǔn)了多所高等院校設(shè)立信息安全本科專業(yè),而且許多高校和科研院所已設(shè)立了信息安全方向的具有碩士和博士學(xué)位授予權(quán)的學(xué)科點(diǎn)。
信息安全是計(jì)算機(jī)、通信、物理、數(shù)學(xué)等領(lǐng)域的交叉學(xué)科,對(duì)于這一新興學(xué)科的培養(yǎng)模式和課程設(shè)置,各高校普遍缺乏經(jīng)驗(yàn),因此中國(guó)計(jì)算機(jī)學(xué)會(huì)教育專業(yè)委員會(huì)和清華大學(xué)出版社聯(lián)合主辦了“信息安全專業(yè)教育教學(xué)研討會(huì)”等一系列研討活動(dòng),并成立了“高等院校信息安全專業(yè)系列教材”編審委員會(huì),由我國(guó)信息安全領(lǐng)域著名專家肖國(guó)鎮(zhèn)教授擔(dān)任編委會(huì)主任,指導(dǎo)“高等院校信息安全專業(yè)系列教材”的編寫工作。編委會(huì)本著研究先行的指導(dǎo)原則,認(rèn)真研討國(guó)內(nèi)外高等院校信息安全專業(yè)的教學(xué)體系和課程設(shè)置,進(jìn)行了大量前瞻性的研究工作,而且這種研究工作將隨著我國(guó)信息安全專業(yè)的發(fā)展不斷深入。系列教材的作者都是既在本專業(yè)領(lǐng)域有深厚的學(xué)術(shù)造詣、又在教學(xué)*線有豐富的教學(xué)經(jīng)驗(yàn)的學(xué)者、專家。
該系列教材是我國(guó)*套專門針對(duì)信息安全專業(yè)的教材,其特點(diǎn)是:
① 體系完整、結(jié)構(gòu)合理、內(nèi)容先進(jìn)。
② 適應(yīng)面廣:能夠滿足信息安全、計(jì)算機(jī)、通信工程等相關(guān)專業(yè)對(duì)信息安全領(lǐng)域課程的教材要求。
③ 立體配套:除主教材外,還配有多媒體電子教案、習(xí)題與實(shí)驗(yàn)指導(dǎo)等。
④ 版本更新及時(shí),緊跟科學(xué)技術(shù)的新發(fā)展。
在全力做好本版教材,滿足學(xué)生用書(shū)的基礎(chǔ)上,還經(jīng)由專家的推薦和審定,遴選了一批國(guó)外信息安全領(lǐng)域優(yōu)秀的教材加入到系列教材中,以進(jìn)一步滿足大家對(duì)外版書(shū)的需求。“高等院校信息安全專業(yè)系列教材”已于2006年年初正式列入普通高等教育“十一五”*教材規(guī)劃。
2007年6月,教育部高等學(xué)校信息安全類專業(yè)教學(xué)指導(dǎo)委員會(huì)成立大會(huì)暨*次會(huì)議在北京勝利召開(kāi)。本次會(huì)議由教育部高等學(xué)校信息安全類專業(yè)教學(xué)指導(dǎo)委員會(huì)主任單位北京工業(yè)大學(xué)和北京電子科技學(xué)院主辦,清華大學(xué)出版社協(xié)辦。教育部高等學(xué)校信息安全類專業(yè)教學(xué)指導(dǎo)委員會(huì)的成立對(duì)我國(guó)信息安全專業(yè)的發(fā)展起到重要的指導(dǎo)和推動(dòng)作用。2006年教育部給武漢大學(xué)下達(dá)了“信息安全專業(yè)指導(dǎo)性專業(yè)規(guī)范研制”的教學(xué)科研項(xiàng)目。2007年起該項(xiàng)目由教育部高等學(xué)校信息安全類專業(yè)教學(xué)指導(dǎo)委員會(huì)組織實(shí)施。在高教司和教指委的指導(dǎo)下,項(xiàng)目組團(tuán)結(jié)一致,努力工作,克服困難,歷時(shí)5年,制定出我國(guó)*個(gè)信息安全專業(yè)指導(dǎo)性專業(yè)規(guī)范,于2012年年底通過(guò)經(jīng)教育部高等教育司理工科教育處授權(quán)組織的專家組評(píng)審,并且已經(jīng)得到武漢大學(xué)等許多高校的實(shí)際使用。2013年,新一屆“教育部高等學(xué)校信息安全專業(yè)教學(xué)指導(dǎo)委員會(huì)”成立。經(jīng)組織審查和研究決定,2014年以“教育部高等學(xué)校信息安全專業(yè)教學(xué)指導(dǎo)委員會(huì)”的名義正式發(fā)布《高等學(xué)校信息安全專業(yè)指導(dǎo)性專業(yè)規(guī)范》(由清華大學(xué)出版社正式出版)。
密碼學(xué)中的可證明安全性出版說(shuō)明2015年6月,國(guó)務(wù)院學(xué)位委員會(huì)、教育部出臺(tái)增設(shè)“網(wǎng)絡(luò)空間安全”為一級(jí)學(xué)科的決定,將高校培養(yǎng)網(wǎng)絡(luò)空間安全人才提到新的高度。2016年6月,中央網(wǎng)絡(luò)安全和信息化領(lǐng)導(dǎo)小組辦公室(下文簡(jiǎn)稱中央網(wǎng)信辦)、國(guó)家發(fā)展和改革委員會(huì)、教育部、科學(xué)技術(shù)部、工業(yè)和信息化部及人力資源和社會(huì)保障部六大部門聯(lián)合發(fā)布《關(guān)于加強(qiáng)網(wǎng)絡(luò)安全學(xué)科建設(shè)和人才培養(yǎng)的意見(jiàn)》(中網(wǎng)辦發(fā)文\[2016\]4號(hào))。為貫徹落實(shí)《關(guān)于加強(qiáng)網(wǎng)絡(luò)安全學(xué)科建設(shè)和人才培養(yǎng)的意見(jiàn)》,進(jìn)一步深化高等教育教學(xué)改革,促進(jìn)網(wǎng)絡(luò)安全學(xué)科專業(yè)建設(shè)和人才培養(yǎng),促進(jìn)網(wǎng)絡(luò)空間安全相關(guān)核心課程和教材建設(shè),在教育部高等學(xué)校信息安全專業(yè)教學(xué)指導(dǎo)委員會(huì)和中央網(wǎng)信辦資助的網(wǎng)絡(luò)空間安全教材建設(shè)課題組的指導(dǎo)下,啟動(dòng)了“網(wǎng)絡(luò)空間安全重點(diǎn)規(guī)劃叢書(shū)”的工作,由教育部高等學(xué)校信息安全專業(yè)教學(xué)指導(dǎo)委員會(huì)秘書(shū)長(zhǎng)封化民校長(zhǎng)擔(dān)任編委會(huì)主任。本規(guī)劃叢書(shū)基于“高等院校信息安全專業(yè)系列教材”堅(jiān)實(shí)的工作基礎(chǔ)和成果、陣容強(qiáng)大的編審委員會(huì)和優(yōu)秀的作者隊(duì)伍,目前已經(jīng)有多本圖書(shū)獲得教育部和中央網(wǎng)信辦等機(jī)構(gòu)評(píng)選的“普通高等教育本科*規(guī)劃教材”“普通高等教育精品教材”“中國(guó)大學(xué)出版社圖書(shū)獎(jiǎng)”和“國(guó)家網(wǎng)絡(luò)安全優(yōu)秀教材獎(jiǎng)”等多個(gè)獎(jiǎng)項(xiàng)。
“網(wǎng)絡(luò)空間安全重點(diǎn)規(guī)劃叢書(shū)”將根據(jù)《高等學(xué)校信息安全專業(yè)指導(dǎo)性專業(yè)規(guī)范》(及后續(xù)版本)和相關(guān)教材建設(shè)課題組的研究成果不斷更新和擴(kuò)展,進(jìn)一步體現(xiàn)科學(xué)性、系統(tǒng)性和新穎性,及時(shí)反映教學(xué)改革和課程建設(shè)的新成果,并隨著我國(guó)網(wǎng)絡(luò)空間安全學(xué)科的發(fā)展不斷完善,力爭(zhēng)為我國(guó)網(wǎng)絡(luò)空間安全相關(guān)學(xué)科專業(yè)的本科和研究生教材建設(shè)、學(xué)術(shù)出版與人才培養(yǎng)做出更大的貢獻(xiàn)。
我們的E.mail地址是: zhangm@tup.tsinghua.edu.cn,聯(lián)系人: 張民。
“網(wǎng)絡(luò)空間安全重點(diǎn)規(guī)劃叢書(shū)”編審委員會(huì)信息安全是一個(gè)綜合、交叉的學(xué)科領(lǐng)域,涉及數(shù)學(xué)、電子、信息、通信、計(jì)算機(jī)等諸多學(xué)科的長(zhǎng)期知識(shí)積累和*新發(fā)展成果,密碼學(xué)是信息安全的核心技術(shù),密碼技術(shù)中的加密方法包括單鑰密碼體制和公鑰密碼體制?坍嫻密碼體制的安全性包括兩部分: 首先是刻畫敵手的模型,說(shuō)明敵手訪問(wèn)系統(tǒng)的方式和計(jì)算能力;其次是刻畫安全性概念,說(shuō)明敵手攻破了方案的安全性意味著什么。公鑰加密方案語(yǔ)義安全的概念由Goldwasser和Micali于1984年提出,它以一種思維實(shí)驗(yàn)的模型刻畫了敵手通過(guò)密文得不到明文的任何部分信息,即使是1比特的信息。這一概念的提出開(kāi)創(chuàng)了可證明安全性領(lǐng)域的先河,將密碼學(xué)建立在了計(jì)算復(fù)雜性理論之上,奠定了現(xiàn)代密碼學(xué)理論的數(shù)學(xué)基礎(chǔ),從而將密碼學(xué)從一門藝術(shù)變?yōu)橐婚T科學(xué)。所以說(shuō)可證明安全性是密碼學(xué)和計(jì)算復(fù)雜性理論的天作之合。
本書(shū)全面介紹可證明安全性的發(fā)展歷史及研究成果,共5章。第1章介紹可證明安全性用到的一些數(shù)學(xué)知識(shí)和基本工具,包括密碼學(xué)中一些常用的數(shù)論知識(shí)和代數(shù)知識(shí)、計(jì)算復(fù)雜性、陷門置換、零知識(shí)證明、張成方案與秘密分割方案、歸約。第2章介紹語(yǔ)義安全的公鑰密碼體制的定義,包括公鑰加密方案在選擇明文攻擊下的不可區(qū)分性,公鑰加密方案在選擇密文攻擊下的不可區(qū)分性,公鑰加密方案在適應(yīng)性選擇密文攻擊下的不可區(qū)分性。第3章介紹幾類常用的語(yǔ)義安全的公鑰機(jī)密體制,包括語(yǔ)義安全的RSA加密方案、Paillier公鑰密碼系統(tǒng)、Cramer.Shoup密碼系統(tǒng)、RSA.FDH簽名方案、BLS短簽名方案、抗密鑰泄露的公鑰加密系統(tǒng)。第4章介紹基于身份的密碼體制,包括基于身份的密碼體制定義和安全模型,隨機(jī)諭言機(jī)模型下的基于身份的密碼體制,無(wú)隨機(jī)諭言機(jī)模型的選定身份安全的IBE,無(wú)隨機(jī)諭言機(jī)模型下的完全安全的IBE,密文長(zhǎng)度固定的分層次IBE,基于對(duì)偶系統(tǒng)加密的完全安全的IBE和HIBE、從選擇明文安全到選擇密文安全。第5章介紹基于屬性的密碼體制,包括基于屬性的密碼體制的一般概念,基于模糊身份的加密方案,基于密鑰策略的屬性加密方案,基于密文策略的屬性加密方案,基于對(duì)偶系統(tǒng)加密的完全安全的屬性加密,非單調(diào)訪問(wèn)結(jié)構(gòu)的屬性加密方案,函數(shù)加密。本書(shū)在編寫過(guò)程中得到了課題組成員的大力支持和幫助,他們是4位博士后: 王濤博士、王鑫博士、來(lái)齊齊博士、張麗娜博士,5位博士生: 程灝、乜國(guó)雷、侯紅霞、周彥偉、趙一,5位碩士生: 武朵朵、馬曉敏、李士強(qiáng)、孟茹、趙艷琪,在此一并表示感謝。另外,本書(shū)的編寫得到國(guó)家自然科學(xué)基金項(xiàng)目(批準(zhǔn)號(hào): 61272436, 61572303)的資助,還得到陜西師范大學(xué)優(yōu)秀著作出版基金和陜西師范大學(xué)重點(diǎn)學(xué)科建設(shè)項(xiàng)目的資助,在此表示感謝。
由于作者水平有限,書(shū)中不足在所難免,懇請(qǐng)讀者批評(píng)指正。
密碼學(xué)中的可證明安全性前言
作者2017年1月
楊波,北京大學(xué)學(xué)士,西安電子科技大學(xué)碩士、博士,陜西師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院教授、博士生導(dǎo)師,陜西省百人計(jì)劃特聘教授,中國(guó)密碼學(xué)會(huì)理事,中國(guó)密碼學(xué)會(huì)密碼算法專業(yè)委員會(huì)委員,《密碼學(xué)報(bào)》編委。曾任華南農(nóng)業(yè)大學(xué)信息學(xué)院、軟件學(xué)院院長(zhǎng)。2011年起在陜西師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院工作。2005年擔(dān)任第四屆中國(guó)信息和通信安全學(xué)術(shù)會(huì)議程序委員會(huì)主席,2009年擔(dān)任中國(guó)密碼學(xué)會(huì)年會(huì)副主席,2010年起擔(dān)任The Joint Workshop on Information Security (JWIS ) Co-General Chair。主持多項(xiàng)國(guó)家自然科學(xué)基金、863計(jì)劃、國(guó)家密碼發(fā)展基金、國(guó)防科技重點(diǎn)實(shí)驗(yàn)室基金、陜西省自然科學(xué)基金項(xiàng)目。
第1章一些基本概念和工具1
1.1密碼學(xué)中一些常用的數(shù)學(xué)知識(shí)1
1.1.1群、環(huán)、域1
1.1.2素?cái)?shù)和互素?cái)?shù)3
1.1.3模運(yùn)算4
1.1.4模指數(shù)運(yùn)算6
1.1.5費(fèi)馬定理、歐拉定理和卡米歇爾定理7
1.1.6歐幾里得算法10
1.1.7中國(guó)剩余定理13
1.1.8離散對(duì)數(shù)16
1.1.9二次剩余17
1.1.10循環(huán)群20
1.1.11循環(huán)群的選取20
1.1.12雙線性映射22
1.2計(jì)算復(fù)雜性22
1.3陷門置換25
1.3.1陷門置換的定義25
1.3.2單向陷門置換26
1.3.3陷門置換的簡(jiǎn)化定義27
1.4零知識(shí)證明27
1.4.1交互證明系統(tǒng)27
1.4.2交互證明系統(tǒng)的定義28
1.4.3交互證明系統(tǒng)的零知識(shí)性29
1.4.4非交互式證明系統(tǒng)31
1.4.5適應(yīng)性安全的非交互式零知識(shí)證明31
1.5張成方案與秘密分割方案33
1.5.1秘密分割方案33
1.5.2線性秘密分割方案34密碼學(xué)中的可證明安全性目錄
1.5.3張成方案35
1.5.4由張成方案建立秘密分割方案35
1.6歸約36
第1章參考文獻(xiàn)38第2章語(yǔ)義安全的公鑰密碼體制的定義39
2.1公鑰密碼體制的基本概念39
2.1.1公鑰加密方案39
2.1.2選擇明文攻擊下的不可區(qū)分性定義40
2.1.3基于陷門置換的語(yǔ)義安全的公鑰加密方案構(gòu)造41
2.1.4群上的離散對(duì)數(shù)問(wèn)題43
2.1.5判定性Diffie\|Hellman(DDH)假設(shè)44
2.2公鑰加密方案在選擇密文攻擊下的不可區(qū)分性46
2.3公鑰加密方案在適應(yīng)性選擇密文攻擊下的不可區(qū)分性55
第2章參考文獻(xiàn)61
第3章幾類語(yǔ)義安全的公鑰密碼體制63
3.1語(yǔ)義安全的RSA加密方案63
3.1.1RSA加密算法63
3.1.2RSA問(wèn)題和RSA假設(shè)64
3.1.3選擇明文安全的RSA加密64
3.1.4選擇密文安全的RSA加密67
3.2Paillier公鑰密碼系統(tǒng)69
3.2.1合數(shù)冪剩余類的判定70
3.2.2合數(shù)冪剩余類的計(jì)算71
3.2.3基于合數(shù)冪剩余類問(wèn)題的概率加密方案73
3.2.4基于合數(shù)冪剩余類問(wèn)題的單向陷門置換74
3.2.5Paillier密碼系統(tǒng)的性質(zhì)75
3.3CramerShoup密碼系統(tǒng)76
3.3.1CramerShoup密碼系統(tǒng)的基本機(jī)制76
3.3.2CramerShoup密碼系統(tǒng)的安全性證明77
3.4RSAFDH簽名方案79
3.4.1RSA簽名方案79
3.4.2RSAFDH簽名方案的描述80
3.4.3RSAFDH簽名方案的改進(jìn)83
3.5BLS短簽名方案84
3.5.1BLS短簽名方案所基于的安全性假設(shè)84
3.5.2BLS短簽名方案描述84
3.5.3BLS短簽名方案的改進(jìn)一86
3.5.4BLS短簽名方案的改進(jìn)二86
3.6抗密鑰泄露的公鑰加密系統(tǒng)87
3.6.1抗泄露密碼體制介紹87
3.6.2密鑰泄露攻擊模型92
3.6.3基于哈希證明系統(tǒng)的抗泄露攻擊的公鑰加密方案94
3.6.4基于推廣的DDH假設(shè)的抗泄露攻擊的公鑰加密方案97
3.6.5抗選擇密文的密鑰泄露攻擊99
3.6.6抗弱密鑰泄露攻擊109
第3章參考文獻(xiàn)111
第4章基于身份的密碼體制113
4.1基于身份的密碼體制定義和安全模型113
4.1.1基于身份的密碼體制簡(jiǎn)介113
4.1.2選擇明文安全的IBE114
4.1.3選擇密文安全的IBE方案115
4.1.4選定身份攻擊下的IBE方案116
4.1.5分層次的IBE系統(tǒng)117
4.2隨機(jī)諭言機(jī)模型下的基于身份的密碼體制118
4.2.1BF方案所基于的困難問(wèn)題118
4.2.2BF方案描述119
4.2.3BF方案的安全性120
4.2.4選擇密文安全的BF方案124
4.3無(wú)隨機(jī)諭言機(jī)模型的選定身份安全的IBE128
4.3.1雙線性DiffieHellman求逆假設(shè)128
4.3.2基于判定性BDH假設(shè)的IBE和HIBE方案129
4.3.3基于判定性BDHI假設(shè)的IBE和HIBE方案131
4.4無(wú)隨機(jī)諭言機(jī)模型下的基于身份的密碼體制134
4.4.1判定性雙線性DiffieHellman假設(shè)134
4.4.2無(wú)隨機(jī)諭言機(jī)模型下的IBE構(gòu)造134
4.5密文長(zhǎng)度固定的分層次IBE143
4.5.1弱雙線性DiffieHellman求逆假設(shè)143
4.5.2一個(gè)密文長(zhǎng)度固定的HIBE系統(tǒng)144
第3章幾類語(yǔ)義安全的公鑰密碼體制 3.1語(yǔ)義安全的RSA加密方案3.1.1RSA加密算法 RSA算法是1978年由Rivest、Shamir和Adleman提出的一種用數(shù)論構(gòu)造的,也是迄今理論上*為成熟完善的公鑰密碼體制,該體制已得到廣泛的應(yīng)用。它作為陷門置換在1.3.1節(jié)中有過(guò)介紹,下面是算法的詳細(xì)描述。 設(shè)GenPrime是大素?cái)?shù)產(chǎn)生算法。 密鑰產(chǎn)生過(guò)程: GenRSA(): p,q←GenPrime(); n=pq,φ(n)=(p-1)(q-1); 選e,滿足1計(jì)算d,滿足d·e≡1 mod φ(n) pk=(n,e),sk=(n,d). 加密(其中Mpk(M): CT=Me mod n. 解密: sk(CT): M=CTd mod n. 下面證明RSA算法中解密過(guò)程的正確性。 證明: 由加密過(guò)程知CT≡Me mod n,所以 CTd mod n≡Med mod n≡Mkφ(n)+1 mod n 下面分兩種情況: (1) M與n互素。由歐拉定理: Mφ(n)≡1 mod n,Mkφ(n)≡1 mod n,Mkφ(n)+1≡M mod n 即CTd mod n≡M。密碼學(xué)中的可證明安全性第3章幾類語(yǔ)義安全的公鑰密碼體制 (2) (M,n)≠1。先看(M,n)=1的含義,由于n=pq,所以(M,n)=1意味著M不是p的倍數(shù)也不是q的倍數(shù)。因此(M,n)≠1意味著M是p的倍數(shù)或q的倍數(shù),不妨設(shè)M=tp,其中t為正整數(shù)。此時(shí)必有(M,q)=1,否則M也是q的倍數(shù),從而是pq的倍數(shù),與M由(M,q)=1及歐拉定理得Mφ(q)≡1 mod q,所以Mkφ(q)≡1 mod q,Mkφ(q)φ(p)≡1 mod q,Mkφ(n)≡1 mod q,因此存在一個(gè)整數(shù)r,使得Mkφ(n)=1+rq,兩邊同乘以M=tp得Mkφ(n)+1=M+rtpq=M+rtn,即Mkφ(n)+1≡M mod n,所以CTd mod n≡M。 (證畢) 如果消息M是Z*n中均勻隨機(jī)的,用公開(kāi)鑰(n,e)對(duì)M加密,則敵手不能恢復(fù)M。然而如果敵手發(fā)起選擇密文攻擊,以上性質(zhì)不再成立。比如敵手截獲密文CT≡Me mod n后,選擇隨機(jī)數(shù)r←RZ*n,計(jì)算密文CT′≡re·CT mod n,將CT′給挑戰(zhàn)者,獲得CT′的明文M′后,可由M≡M′r-1 mod n恢復(fù)M,這是因?yàn)?M′r-1≡CT′dr-1≡reMedr-1≡redMedr-1≡rMr-1≡M mod n 為使RSA加密方案可抵抗敵手的選擇明文攻擊和選擇密文攻擊,需對(duì)其加以修改。 3.1.2RSA問(wèn)題和RSA假設(shè) RSA問(wèn)題: 已知大整數(shù)n,e,y∈Zn,滿足1RSA假定: 沒(méi)有概率多項(xiàng)式時(shí)間的算法解決RSA問(wèn)題。 3.1.3選擇明文安全的RSA加密 設(shè)GenRSA是RSA加密方案的密鑰產(chǎn)生算法,它的輸入為,輸出為模數(shù)n(為2個(gè)比特素?cái)?shù)的乘積)、整數(shù)e、d滿足ed≡1 mod φ(n)。又設(shè)H:0,12→0,1()是一個(gè)哈希函數(shù),其中()是一個(gè)任意的多項(xiàng)式。 加密方案Π(稱為RSACPA方案)如下: (1) 密鑰產(chǎn)生過(guò)程: KeyGen(): n,e,d←GenRSA(); pk=(n,e),sk=n,d. (2) 加密過(guò)程(其中M∈0,1()): pk(M): r←RZ*n; 輸出re mod n,H(r)M. (3) 解密過(guò)程: skC1,C2: r=Cd1 mod n; 輸出H(r)C2. 解密過(guò)程的正確性顯然。 在對(duì)方案進(jìn)行安全性分析時(shí),將其中的哈希函數(shù)視為隨機(jī)諭言機(jī)。隨機(jī)諭言機(jī)(random oracle)是一個(gè)魔盒,對(duì)用戶(包括敵手)來(lái)說(shuō),魔盒內(nèi)部的工作原理及狀態(tài)都是未知的。用戶能夠與這個(gè)魔盒交互,方式是向魔盒輸入一個(gè)比特串x,魔盒輸出比特串y(對(duì)用戶來(lái)說(shuō)y是均勻分布的)。 這一過(guò)程稱為用戶向隨機(jī)諭言機(jī)的詢問(wèn)。 因?yàn)檫@種哈希函數(shù)工作原理及內(nèi)部狀態(tài)是未知的,因此不能用通常的公開(kāi)哈希函數(shù)。在安全性的歸約證明中(見(jiàn)圖17),敵手需要哈希函數(shù)值時(shí),只能由敵手為他產(chǎn)生。之所以以這種方式使用哈希函數(shù),是因?yàn)橐延舻睦щy問(wèn)題嵌入到哈希函數(shù)值中。這種安全性稱為隨機(jī)諭言機(jī)模型下的。如果不把哈希函數(shù)當(dāng)作隨機(jī)諭言機(jī),則安全性稱為標(biāo)準(zhǔn)模型下的,如3.2節(jié)的Paillier公鑰密碼系統(tǒng)和3.3節(jié)的CramerShoup密碼系統(tǒng)。 定理31設(shè)H是一個(gè)隨機(jī)諭言機(jī),如果與GenRSA相關(guān)的RSA問(wèn)題是困難的,則RSACPA方案Π是INDCPA安全的。 具體來(lái)說(shuō),假設(shè)存在一個(gè)INDCPA敵手以()的優(yōu)勢(shì)攻破RSACPA方案Π,那么一定存在一個(gè)敵手至少以 AdvRSA()≥2() 的優(yōu)勢(shì)解決RSA問(wèn)題。 證明: Π的INDCPA游戲如下。 ExpRSACPAΠ,() n,e,d←GenRSA(); pk=(n,e),sk=n,d; H←RH:0,12→0,1(); M0,M1←sk(·),H(·)(pk),其中M0=M1=(); β←R0,1,r←RZ*n,C=re mod n,H(r)Mβ; β′←sk,≠C(·),H(·)(pk,C); 如果β′=β,則返回1;否則返回0. 其中H:0,12→0,1()表示0,12到0,1()的哈希函數(shù)族,sk,≠C(·)表示敵手不能對(duì)C訪問(wèn)sk(·)。敵手的優(yōu)勢(shì)定義為安全參數(shù)的函數(shù): AdvRSACPAΠ,()=PrExpRSACPAΠ,()=1-12 下面證明RSACPA方案可歸約到RSA假設(shè)。 敵手已知(n,e,c^1),以(攻擊RSACPA方案)作為子程序,進(jìn)行如下過(guò)程(圖31),目標(biāo)是計(jì)算r^≡(c^1)1/e mod n。 圖31RSACPA方案到RSA的歸約 (1) 選取一個(gè)隨機(jī)串h^←R{0,1}(),作為對(duì)H(r^)的猜測(cè)值(但是實(shí)際上并不知道r^)。將公開(kāi)鑰(n,e)給。 (2) H詢問(wèn): 建立一個(gè)表Hlist(初始為空),元素類型xi,hi,在任何時(shí)候都能發(fā)出對(duì)Hlist的詢問(wèn),做如下應(yīng)答(設(shè)詢問(wèn)為x): 如果x已經(jīng)在Hlist,則以x,h中的h應(yīng)答。 如果xe≡c^1 mod n,以h^應(yīng)答,將(x,h^)存入表中,并記下r^=x。 否則隨機(jī)選擇h←R{0,1}(),以h應(yīng)答,并將(x,h)存入表中。 (3) 挑戰(zhàn)。輸出兩個(gè)要挑戰(zhàn)的消息M0和M1,隨機(jī)選擇β←R{0,1},并令c^2=h^Mβ,將c^1,c^2給作為密文。 (4) 在執(zhí)行結(jié)束后(在輸出其猜測(cè)β′之后),輸出第(2)步記下的r^=x。 設(shè)表示事件: 在模擬中發(fā)出H(r^)詢問(wèn),即H(r^)出現(xiàn)在Hlist中。 斷言31在以上模擬過(guò)程中,的模擬是完備的。 證明: 在以上模擬中,的視圖與其在真實(shí)攻擊中的視圖是同分布的。這是因?yàn)?(1) 的H詢問(wèn)中的每一個(gè)都是用隨機(jī)值來(lái)回答的。而在對(duì)Π的真實(shí)攻擊中,得到的是H的函數(shù)值,由于假定H是隨機(jī)諭言機(jī),所以得到的H的函數(shù)值是均勻的。 (2) 對(duì)來(lái)說(shuō),h^Mβ為h^對(duì)Mβ做一次一密加密。由h^的隨機(jī)性,h^Mβ對(duì)來(lái)說(shuō)是隨機(jī)的。 所以兩種視圖不可區(qū)分。 (斷言31證畢) 斷言32在上述模擬攻擊中Pr≥2。 證明: 顯然有PrExpRSACPAΠ,()=1=12。又由在真實(shí)攻擊中的定義知的優(yōu)勢(shì)大于等于,得在模擬攻擊中的優(yōu)勢(shì)也為 Pr[ExpRSACPAΠ,()=1]-12≥ PrExpRSACPAΠ,()=1=PrExpRSACPAΠ,()=1|Pr +PrExpRSACPAΠ,()=1|Pr ≤PrExpRSACPAΠ,()=1|Pr+Pr =12Pr+Pr=12(1-Pr)+Pr =12+12Pr 又知: PrExpRSACPAΠ,()=1≥PrExpRSACPAΠ,()=1Pr =12(1-Pr) =12-12Pr 所以≤PrExpCPAΠ,()=1-12≤12Pr,即模擬攻擊中Pr≥2。 (斷言32證畢) 由以上兩個(gè)斷言,在上述模擬過(guò)程中r^以至少2的概率出現(xiàn)在Hlist。若發(fā)生,則在第(2)步可找到x滿足xe=c^1 mod n,即x≡r^≡(c^1)1/e mod n。所以成功的概率與發(fā)生的概率相同。 (定理31證畢) 定理31已證明Π是INDCPA安全的,然而它不是INDCCA安全的。敵手已知密文CT=C1,C2,構(gòu)造CT′=C1,C2M′,給解密諭言機(jī),收到解密結(jié)果為M″=MM′,再由M″M′即獲得CT對(duì)應(yīng)的明文M。 3.1.4選擇密文安全的RSA加密 因?yàn)檫x擇密文安全的單鑰加密方案的構(gòu)造較容易,本節(jié)利用選擇密文安全的單鑰加密方案構(gòu)造選擇密文安全的公鑰加密方案。 單鑰加密方案Π=(PrivGen,Enc,Dec)的選擇密文安全性由以下INDCCA游戲來(lái)刻畫。 ExpPrivCCAΠ,(): kpriv←PrivGen(); M0,M1←Enckpriv(·),Deckpriv(·),其中M0=M1=(); β←R0,1,C=Enckpriv(Mβ); β′←Enckpriv(·),Deckpriv,≠C(·)(C); 如果β′=β,則返回1;否則返回0. 其中Deckpriv,≠C(·)表示敵手不能對(duì)C訪問(wèn)Deckpriv(·)。敵手的優(yōu)勢(shì)可定義為安全參數(shù)的函數(shù): AdvPrivCCAΠ,()=PrExpPrivCCAΠ,()=1-12 單鑰加密方案Π的安全性定義與定義22、定義26、定義27類似。 設(shè)GenRSA及H如前,Π=(PrivGen,Enc,Dec)是一個(gè)密鑰長(zhǎng)度為,消息長(zhǎng)度為()的INDCCA安全的單鑰加密方案。 選擇密文安全的RSA加密方案Π′=(KeyGen,,)(稱為RSACCA方案)構(gòu)造如下。 (1) 密鑰產(chǎn)生過(guò)程: KeyGen(): n,e,d←GenRSA(); pk=(n,e),sk=n,d. (2) 加密過(guò)程(其中M∈0,1()): pk(M): r←RZ*n; h=H(r); 輸出re mod n,Ench(M). (3) 解密過(guò)程: skC1,C2: r=Cd1 mod n; h=H(r); 輸出Dech(C2). 定理32設(shè)H是隨機(jī)諭言機(jī),如果與GenRSA相關(guān)的RSA問(wèn)題是困難的,且Π是INDCCA安全的,則RSACCA方案Π′是INDCCA安全的。 具體來(lái)說(shuō),假設(shè)存在一個(gè)INDCCA敵手以()的優(yōu)勢(shì)攻破RSACCA方案Π′,那么一定存在一個(gè)敵手至少以 AdvRSA()≥2() ……
你還可能感興趣
我要評(píng)論
|