2023年全國碩士研究生考試考研英語一試題真題(含答案詳解+作文范文)_第1頁
已閱讀1頁,還剩45頁未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

1、公鑰密碼體制基于的困難問題主要有:大整數(shù)的素分解問題、有限域上的離散對數(shù)問題(DLP)和橢圓曲線上的離散對數(shù)問題等。本文研究的是有限域上的離散對數(shù)問題。關(guān)于這個問題,人們已進(jìn)行了許多深入的研究,相繼提出了許多求離散對數(shù)的方法,如大步小步法[1]、Pollard'sRho方法[2]、Kangaroo方法[3]、指標(biāo)計算法[4]和Pohlig-Hellman算法[5]等。但到目前為止,還沒有找到一個多項式時間算法來計算有限域上的離散對數(shù)。<

2、br>  設(shè)p為素數(shù),t≥2,F(xiàn)pt表示含有pt個元素的有限域。設(shè)h(x)=xt+ht-1xt-1+…+h1x+h0,hi∈Fp,0≤i≤t-1為Fp上的t次不可約多項式。則Fp[x]/為域,且Fpt≌Fp[x]/,其中,為Fp[x]中的一個主理想。因此,有限域Fpt中的所有元素都可以寫成Fp上的多項式。即對任意的g∈Fpt,都存在g0,…,gt-1∈Fp使得g=gt-1xt-1+gt-2xt-2+…

3、+g1x+g0.Fpt中元素之間的加法運(yùn)算和乘法運(yùn)算都是模h(x)的多項式運(yùn)算。為了方便,將g的i次項系數(shù)記為[g]i,即[g]i=gi.
  在2013年,N.Fazio等[6]給出了有限域Fp2上的一類新的Diffie-Hellman問題:
  -Partial-CDH問題:設(shè)g是Fp2的乘法群的一個生成元。給定g,ga,gb∈Fp2,計算[gab]1∈Fp(即gab的一次項系數(shù))。
  在假設(shè)Partial-CD

4、H問題是困難的前提下,作者證明了計算[gab]1與計算[gab]1的任意一位是等價的。在文章結(jié)尾,N.Fazio等留下了兩個公開問題:第一,是把有限域Fp2上的結(jié)果擴(kuò)展到有限域Fpt(t>2)上;第二,是研究Partial-CDH問題的困難性。對這兩個問題,王明強(qiáng)[7]部分地解決了第一個問題,完全地解決了第二個問題。
  首先,[7]對[6]中的Partial-CDH問題的定義進(jìn)行了擴(kuò)展,提出了有限域Fpt(t>1)上新的Diff

5、ie-Hellman問題:
  -(t,k)-P-CDH問題:設(shè)F*pt=,k≤t是正整數(shù),給定g,ga,gb∈Fp2,計算([gab]t-1,[gab]t-2,…,[gab]t-k)∈(Fp)k.
  -對偶(t,k)-P-CDH問題:設(shè)F*pt=,k≤t是正整數(shù),給定g,ga,gb∈Fp2,計算([gab]0,[gab]1,…,[gab]k-1)∈(Fp)k.其次,[7]對上面新問題以及Partial-CDH

6、問題的困難性進(jìn)行了詳細(xì)的研究,得到:在有限域Fp2上,Partial-CDH問題及對偶Partial-CDH問題的困難性與原始CDH問題的困難性等價,并證明了在CDH問題假設(shè)下,gab的每個坐標(biāo)的每一位都是不可預(yù)測的。
  本文在有限域Fpt(t≥2)上提出了新的離散對數(shù)問題,即(t,k)-P-DLP問題和對偶(t,k)-P-DLP問題:
  -(t,k)-P-DLP問題:設(shè)F*pt=,a∈Zpt-1,給定([ga]t

7、-1,…,[ga]t-k),求一個a'∈Zpt-1,使得([ga']t-1,…,[ga']t-k)=([ga]t-1,…,[ga]t-k).
  -對偶(t,k)-P-DLP問題:設(shè)F*pt=,a∈Zpt-1,給定([ga]0,…,[ga]k-1),求一個a'∈Zpt-1,使得([ga']0,…,[ga']k-1)=([ga]0,…,[ga]k-1).
  利用窮舉法對這兩個問題求解的空間復(fù)雜度均可以忽略,時間復(fù)雜度均

8、為O(pk)次迭代運(yùn)算。這個復(fù)雜度和利用窮舉法求解Fpk上的原始離散對數(shù)問題的時間復(fù)雜度相等。利用Pollard'sRho方法對這兩個問題求解的空間復(fù)雜度均為O(d),時間復(fù)雜度均為O(d+√(pt-1)d),其中1≤d≤pt-k.因此,取d=1.此時空間復(fù)雜度可以忽略,時間復(fù)雜度為O(√pt-1).這個復(fù)雜度與利用Pollard'sRho方法求解Fpt上的原始離散對數(shù)的時間復(fù)雜度相等。這說明,窮舉法和Rho方法并不能有效求解上述新的離

9、散對數(shù)問題。
  關(guān)于新的離散對數(shù)問題的困難性,具體地,我們得到了:-(t,k)-P-DLP問題和對偶(t,k)-P-DLP問題不會比Fpt上的原始離散對數(shù)問題更困難。
  -當(dāng)k|t時,F(xiàn)pt上的對偶(t,k)-P-DLP問題可以歸約到Fpk的DLP問題。
  新的離散對數(shù)問題和原來的離散對數(shù)問題相比,給出的已知信息更少。如果可以保證新問題的困難性,則把它們應(yīng)用在基于離散對數(shù)問題的相關(guān)密碼體制或密碼協(xié)議中,將會大大提

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論