快速相關(guān)攻擊算法A和B的實驗報告

第二屆全國密碼數(shù)學挑戰(zhàn)賽西南賽區(qū)題目二參賽單位： 電子科技大學參賽隊員： 詹彤、王雨飛、方淳晟指導老師： 聯(lián)系電話： XXXXXXXXXXXXX聯(lián)系由B箱： XXXXXXXXXXXXXXXXXXXXXX摘要快速相關(guān)攻擊算法是解決流密碼問題的一種重要方法，也是密碼學中重要研究內(nèi)容之一。自Siegenthaler提出快速相關(guān)攻擊以來，不斷有更高效的算法被提出。本文基于Meier和Staffelbach提出的Fastcorrelationattacks中的兩種算法，根據(jù)提供的被加密的序列密碼以及其和原序列的相關(guān)概率，利用概率等相關(guān)知識，恢復線性移位寄存器的60位初始序列。本文所用的算法，不僅可以解決快速相關(guān)攻擊中，密碼和輸出序列的相關(guān)概率較高的流密碼問題，也可以解決對于線性移位寄存器的反饋多項式而言，抽頭數(shù)不高的流密碼。因此有著廣泛的應用前景。目錄TOC\o"1-5"\h\z.序列密碼的相關(guān)攻擊介紹 4.快速相關(guān)攻擊研究現(xiàn)狀 53-Meier-Staffelbach型算法的基本思想 5.快速相關(guān)攻擊算法I 6算法I實現(xiàn)步驟 6算法I計算復雜度分析 7.快速相關(guān)攻擊算法H 8算法H實現(xiàn)步驟 8算法H計算復雜度分析 9.結(jié)果部分 10\o"CurrentDocument".相關(guān)代碼 11校驗方程生成代碼 12\o"CurrentDocument"算法I實現(xiàn)代碼 14\o"CurrentDocument"算法I實現(xiàn)代碼 16\o"CurrentDocument".參考文獻 20

.序列密碼的相關(guān)攻擊介紹本問題是基于線性反饋移位寄存器LFSR的相關(guān)攻擊問題。令LFSR的反饋多項式為/(x)，一個60位的初始密鑰a,a,經(jīng)過LFSR的線性反饋多項式0I59的運算，輸出序列u=(u,u,...u)，經(jīng)由二元無記憶對稱信道(BSC)加密，得到截0IN-1取序列z=(z,z,...z)。實現(xiàn)過程如圖1所示。0IN-I初始狀態(tài)為(。0,a]，二元無記憶對稱信道初始狀態(tài)為(。0,a]，二元無記憶對稱信道圖1加密過程演示如果線性函數(shù)/的某個輸入分量u與輸出Z之間存在相關(guān)性，即n np=[P(u=z)]>0.5o那么可以窮搜索LFSR的初始序列，找出使LFSR的輸出與對nn應密鑰流序列Z的距離最小的初始序列作為該LFSR的初始序列(種子密鑰)。假設(shè)LFSR產(chǎn)生最大周期序列，設(shè)級數(shù)為n,則周期為2「1。該系統(tǒng)的密鑰量為:K=2,-l (1)如果窮搜索密鑰攻擊算法，n足夠大的時候，計算量是無法實現(xiàn)的，事實上,隨著n的增大，算法的復雜度呈指數(shù)增長。如果相關(guān)攻擊不對種子密鑰進行枚舉搜索，就稱為快速相關(guān)攻擊。.快速相關(guān)攻擊研究現(xiàn)狀相關(guān)攻擊最早是由Siegenthaler提出，其原理是利用密鑰發(fā)生器的輸出序列與其源LFSR的輸出序列之間具有的相關(guān)性還原LFSR的初始狀態(tài)。Meier和Staffelbach在此基礎(chǔ)上提出利用概率迭代譯碼的快速相關(guān)攻擊算法⑴，該方法接收到的密鑰流序列的每一比特位代入原序列的反饋多項式組成的方程組中，利用方程組是否滿足原序列的反饋多項式的概率，通過一定次數(shù)的迭代，來最終找到序列的初始狀態(tài)，實現(xiàn)解密。在LFSR的特征多項式重量較小(<10)的情況下取得了較好的效果，之后有學者提出了一些改進算法。LFSR的抽頭數(shù)一直是Meier-Staffelbach型相關(guān)攻擊算法的頸瓶。1999年T.Johansson和F.Jonsson把快速相關(guān)攻擊應用到LFSR的一般情形，他們的攻擊的關(guān)鍵是把LFSR序列轉(zhuǎn)化成卷積碼，使用卷積碼的譯碼算法恢復LFSR的初態(tài)，仿真結(jié)果表明，使用Viterbi譯碼算法，在抽頭數(shù)較大時，和以往算法比較，攻擊成功時的相關(guān)系數(shù)減小；接著他們把卷積碼和迭代概率譯碼融合起來，把LFSR序列轉(zhuǎn)變成turbo碼，繼而使用turbo譯碼算法恢復LFSR的初態(tài)。2000年，V.Chepyzhov,T.Joansson和B.Smeets的部分思想⑵提出一個較為簡單而有效的快速相關(guān)攻擊算法。T.Johansson和F.Jonsson提出不同于以往的BSC攻擊模型即線性多項式重構(gòu)模型，吸取了多項式學習的已有成果進行攻擊。近年來，快速相關(guān)攻擊技術(shù)有了很大的發(fā)展，許多文獻給出了新的快速相關(guān)攻擊算法。大多數(shù)快速相關(guān)攻擊算法利用窮舉搜索猜測LFSR部分初始狀態(tài)，再結(jié)合密鑰流和校驗方程集合逐步恢復其余的LFSR初始狀態(tài)?？焖傧嚓P(guān)攻擊新的發(fā)展方向是：算法可由高速軟件或簡單硬件實現(xiàn)，并適于并行運算。.基于Meier-Staffelbach型的算法本文提到的算法I和算法n,其基本思想是考慮到輸出序列z和原序列。之間存在相關(guān)性p,通常情況下p>0.53,因此可以將輸出序列Z看作是原序列a的一種擾亂，故可以把序列z的每一比特位代入LFSR反饋多項式組成的方程組中?？紤]在模二域GF(2)上有f2i(X)=f(X2i) ⑵所以通過對f(x)的重復乘方可以得到多個LFSR的校驗多項式，對每一個街區(qū)序列z上的比特位而言，如果某一比特位上，關(guān)于該比特位，這些校驗多項式成立的個數(shù)越多，用該比特位代替LFSR序列的相應比特是正確的概率就越大,在求解概率問題中主要利用形如式⑶的概率迭代公式TOC\o"1-5"\h\zS(p,f)=pS(/M—l)+(l-p)(l-S(p,f-l)) (3)以及求解條件概率公式P(A\B)=^—1 (4)P(B)貝葉斯公式主要用于求解算法II中的概率問題一件/⑷外 ⑸iZ"P(B)P(AIB)J=lj j而上面提到的漢明距離，既是指表示兩個(相同長度)字對應位不同的數(shù)量。.快速相關(guān)攻擊I4.1算法I實現(xiàn)步驟設(shè)反饋多項式級數(shù)為"，抽頭數(shù)為f,相關(guān)概率p=P(〃=z),截取序列z的nn長度為N。第1步：計算序列z每比特所需要的校驗方程平均數(shù)：NM=log(―)x(r+l) (6)22n第2步：計算截取序列z的比特的模二加(含有r個比特)和原LFSR序列的相應比特的模二加相同的概率s：s(p,D=pS(p1)=pS(p/-l)+(l-p)(l-S(p,5l)) (7)第3步：計算在歷個校驗方程中，至少有〃個方程成立的概率Q(p,M/)：Q(p,M,h)=芝d(^?5.x(1-S)m-<+(1-<7)?(1-S>xSm-0

i斗M (8)第4步：計算在M個校驗方程中，至少有〃個方程成立，且它是正確比特位的概率，即z=w概率為nnV(p,M,h)=^TOC\o"1-5"\h\z,M ⑼因此，在給定M個方程中至少有〃個方程成立的條件下，z=u的概率為：nnT(p,M,/?)=3 (10)第5步：求出一個最大的〃，記為人，使。*計算在〃個比特中錯誤max的平均數(shù)r：r=(1-T)xn (11)第6步：找出在M個方程中至少滿足〃個方程的比特位，用這些比特位作為max相應下標位置上LFSR序列的“正確”比特，然后適當?shù)剡x取包含〃個比特的一個集合記為I。，固定〃個連續(xù)比特位。第7步：對中的每一比特位利用LFSR的反饋多項式組建成一個線性方程，即把它表示成固定〃個比特位的一個線性組合，然后將這〃個線性方程組合在一起組成一個線性方程組。第8步：解線性方程，若是線性相關(guān)的，則用幾個附加比特位選擇一個線性無關(guān)的子方程組，將解出來的〃個連續(xù)比特擴展為整個LFSR序列，并與原來截取到的序列z的N位進行比較，若相關(guān)概率在(p-e,p+e)之間(通常認為e取0.05),則認為求解成功。若相關(guān)概率不在區(qū)間之內(nèi)，則認為求解失敗，從而以漢明距1,2,...檢驗/的所有變換，每進行以此漢明變換都轉(zhuǎn)入第7步。直到成功求解為止。4.2算法I計算復雜度分析算法I的主要求解時間耗費在進行漢明變換上。我們可以假設(shè)解方程和添加附加位這一過程所用時間為f,進行漢明變換的距離為〃，則總時間為T=A(n,d)xt= Cixti=。M (12)則有T42"?,其中H(e)表示二進制的端函數(shù)，e=-o整個算法復雜度為n0(2a),C取決于p、t、n,N,且0VCV1。5.快速相關(guān)攻擊n該算法的基本思想：根據(jù)截取序列的每一比特位所滿足的方程數(shù)。來計算截取序列每一比特的新概率，當這些新概率小于給定值的數(shù)目超過另一給定值，或者計算新概率的總的次數(shù)超過5,就對新概率小于給定值的截取序列的比特位進行取補，接著以新序列代替原序列，并將各比特位的概率重新置為原相關(guān)概率，重復上述過程，直到成功。算法n實現(xiàn)步驟：第1步：計算序列z每比特所需要的校驗方程平均數(shù)M=log2(N/2*n))*(t+l) (13)第2步：計算截取序列z的比特的模二加(含有r個比特)和原LFSR序列的相應比特的模二加相同的概率SS(p,l)=pS(p,t)=pxS(p,Z-1)+(1-p)G-S(p,/-l)) (14)第3步：計算在m個校驗方程中，至少有〃個方程成立的概率Q(p,M,〃)TOC\o"1-5"\h\zQ(p,M,h)=￡C(qxS?Q-S)m-，+(1-q)x(1-S)，xSmt)?M (15)計算在朋個校驗方程中，對不滿足〃個方程的比特位進行取補，取補后增加的正確的比特位概率為I(p,M,h)=XC<(1-o)x(1-S)ixSm-)-XCtqxSiX(\-S)M-i

M M\=h \=h (16)計算在M個校驗方程中，有h個方程成立時每個比特位的后驗概率為pn{p,M,h)=pSh(\-S)m-h/(pSh(1-S)m-h+(l-p)(l-S)h(l-S)m-h)(17)\o"CurrentDocument"第4步：找出使得I最大的萬記為人，若I(p,M,h)<0,則表示該算法失max max敗，若>0,則計算尸，用以表示各比特位的一個閾值，若后驗概率P<P,thr nthr就對該比特位進行取補P=(p"M,h+1)4-p{p,M,h))/2 (18)fhrn max n max第5步：用N表示產(chǎn)〈尸的比特位的數(shù)目N,N>N則可結(jié)束此次thr nthr wwihr迭代，也就是直接對p<p的比特位進行取補，開始下一次迭代：nihrTOC\o"1-5"\h\zN=Q(p,M,h)xN (19)thr max第6步：重置迭代次數(shù)i為。第7步：對截取序列z的每一位比特位和原LFSR序列相應比特位的和是相同的概率S(p,p,...,p,t):1 2 tS(p,\)=p,

' (20)S(p,p,...p,t)=pS(p,p,t-l)+(l-p)(\-S(p,p，…,p,t-\))

I2tt\ 2M t I2 f-1第8步：由貝葉斯公式計算各比特位的新概率尸*:Y=pxSx...Sx(l-S+l)x...x(l-S)ijijhjh jM (21)pi*=Y/(Y+(l-p)x(l-S)x...(l-s)x(l-S )x...xS))i ji jh j(h+l) jMpi*:表示第i位比特的薪概率，而pi表示元概率j1,j2,...,jh-在統(tǒng)計校驗方程成立的數(shù)目時，其表示使得方程成立的S的下標。而剩下的人則表示不成立的S的下標。第9步：確定尸〈尸的總比數(shù)目N,若N>N或i<a,則i++,轉(zhuǎn)到第7nthr w wthr步。否則，對截取序列z的那些滿足p<p的比特位進行取補，并重置比特位nthr的概率位PO第10步：若取補后的截取序列中出現(xiàn)了有不滿足反饋多項式的比特位時，則轉(zhuǎn)到第6步。直到攻擊成功。5.2算法II計算復雜度分析其算法復雜度為。在p、f給定的情況下，復雜度隨LFSR的級數(shù)增大而增大。在其他條件不變的情況下，復雜度隨r增大而增大，隨〃增大而減小。缺點也很明顯，在迭代過程中，可能出現(xiàn)分母為0的情況。6.結(jié)果部分下面給出各序列的從“到。的解。0 59(1)第一個序列Z0,0,1,0,1,0,1,1,1,1,1,0,0,1,1,0,0,0,1,1,1,1,1,0,0,1,0,0,0,0,1,0,1,1,0,1,1,1,0,0,0,1,1,1,1,0,1,0,14,0,0,0,1,0,0,0,1,1,1(2)第二個序列z1,1,0,0,0,1,1,1,0,0,0,0,0,1,0,0,1,0,0,1,1,0,1,0,1,1,1,0,1,1,0,0,1,1,0,1,0,0,0,1,1,1,1,0,0,0,0,1,0,0,1,1,0,1,1,0,0,0,14(3)第三個序列z1,1,0,1,1,1,1,1,0,0,0,1,1,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,14,1,0,0,1,0,0,0,14,1,0,0,1,1,1,0,1,1,0,0,0,1,1,0,0,1,1,0,1(4)第四個序列Z1,0,1,1,1,0,0,1,1,0,1,0,1,1,0,1,1,1,0,1,0,1,1,0,0,1,0,0,1,1,0,1,1,1,0,0,1,1,1,1,1,0,1,1,1,0,LL0,LLL0,1,1,1,0,L0,0,0(5)第五個序列z1,0,1,0,1,0,1,1,0,1,1,0,0,1,1,0,0,0,1,1,1,1,1,0,0,1,0,0,0,0,1,0,1,1,0,1,1,1,0,0,0,1,1,1,1,0,1,0,1,1,0,0,0,1,0,0,04,1,1(6)第六個序列Z1,1,0,0,0,1,1,1,1,0,0,0,0,1,0,0,1,0,0,1,1,0,1,0,1,1,0,0,1,1,0,0,1,1,0,1,0,0,04,1,L1,0,0,0(7)第七個序列Z1,0,0,1,1,1,1,1,0,0,0,1,1,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,1,1,0,0,1,0,0,0,1,1,0,0,0,1,14,1,1,1,0,0,0,1,1,0,0,1,1,0,1(8)第八個序列Z0,14,1,0,0,1,1,0,1,1,1,1,0,1,1,1,0,1,0,1,1,0,0,1,0,0,1,1,0,1,1,1,0,04444,1,0,1,1,1,0,1,1,0,1,1,1,0,1,1,1,0,1,0,0,0(9)第九個序列Z0,0,L0,l,0,LLLl,L0,Ll,0,0,L0,0,0,0,L0,LL0,l,1,L0,0Q,LLLL0(10)第十個序列z1,1,0,0,0,1,1,1,0,0,0,1,0,1,0,0,1,001,1,0,1,0,1,1,1,0,1,1,0,0,1,1,0,1,0,0,0,1,1,1,1,0,0,0,0,1,0,0,14,0,1,1,0,0,0,1,1(11)第十一個序列Z1,1,0,1,1,1,1,1,0,0,0,0,1,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,1,1,0,0,1,0,0,0,1,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,0,0,14,0,1(12)第十二個序列z0,1,1,1,0,0,1,1,0,1,0,1,1,0,1,1,1,0,1,0,1,1,0,0,1,1,0,1,1,0,1,1,1,0,0,1,1,1,1,1,0,1,1,1,0,1

7.7.相關(guān)代碼1生成校驗方程importscipyimportsys,timefromscipy.specialimportcombimportreimportmathN=4000000#序列數(shù)n=60 #級數(shù)p=0.75#相關(guān)概率#反饋多項式的系數(shù)#計算抽頭數(shù)fx=[3,#反饋多項式的系數(shù)#計算抽頭數(shù)#fx=[l,2,3,5]t=len(fx)importscipyimportsys,timeimportreimportmath#讀取序列zdefReadFile(filename):datafile=open(filename)try:text=datafile.read()returnevalC[*+text[4：-1]+*Y)finally:datafile.closeOdefwriteFile(fi1ename,datawrite):try:file_object=open(filename,'w')#file_object.write(*0.75\n'+str(data).replace(>','')[1:T]+',')file_object.write,0.75\n'+str(data_write).replace(*finally:file_object.close()N=4000000 #序列數(shù)n=60 #級數(shù)fx=[3,9,16,35,37,47,56,60] #反饋多項式的系數(shù)fx=[l,2,3,5]t=len(fx) #計算抽頭數(shù)M=round(math.log(N/(2*n),2)*(t+D) #計算每位平均需妾校驗方程數(shù)imax=math.floor(math,log(N/n,2))an=[[0foriinrange(t+1)]foriinrange(3*M)]#用于存儲最終校驗多項式print(imax)defCreatePoly(w): 為檢測第幾位imax=math.floor(math.log(N/n,2)) #乘方的最大值counts #記錄校驗方程的個數(shù)al=[[0foriinrange(t)]foriinrange(imax+1)] #用以保存校驗方程的序號al[0]=fx生成倍式(第一行為原反饋多項式)foriinranged,imax+1):forjinrange(t):al[i][j]=al[0][j]*pow(2,i)print(al)牲成校驗方程a2=[[0foriinrange(t+1)]forinrange(imax+1)]print(a2)forcolumninrange(imax+1): #將校驗等式左邊寫通2的最后一列a2[column][t]=al[column][t-1]print(a2)foriinrange(imax+1):forjinrange(t):a2[i][t-j-l]=a2[i] [j]print(a2)foriinrange(imax+1):forjinrange(t+1):ifw>=a2[i][j]:offset=w-a2[i][j]if(offset+a2[i][t])>N:continueelse:forkinrange(t+1):an[count][k]=offset+a2[i][k]count=count+lreturncount #返回校驗方程總數(shù)deffindBitel():rightnum=[]data=ReadFile(*data-l.txt*)forwinrange(4000000):count=0a=CreatePoly(w)ifa>=92:foriinrange(a):try:ifdata[an[i][0]]data[an[i][1]]data[an[i][2]]*data[an[i][3]]data[an[i][4]]\data[an[i][5]]-data[an[i][6]]"data[an[i][7]]==data[an[i][8]]:#f=open(*testl.txt",'a')#f.write(str(an[1!)+>,J)count=count+l#f.close()except:print(an[i][8])print(count)ifcount>92:rightnum.append(w)print(w)deffindBite2():f=open(*test2.txt*)a=f.read()data=eval(a)f.closeOb=len(data)an=[[0foriinrange(60)]]foriinrange(60):count=0forkinrange(10000):forjinrange(9):ifdata[k][j]==12800+i:an[i]=12800+icount=count+1print("找到"，count,"個了")break

print(an)2算法I實現(xiàn)代碼importscipyimportsys,timefromscipy.specialimportcombimportreimportmathN=4000000#序列數(shù)n=60 #級數(shù)p=0.75#相關(guān)概率反饋多項式的系數(shù)計算抽頭數(shù)計算每位平均需要校驗方程數(shù)反饋多項式的系數(shù)計算抽頭數(shù)計算每位平均需要校驗方程數(shù)fx=[l,2,3,5]t=len(fx)step1:M二round(math.1og(N/(2*n),2)*(t+1))step2:defS(p,t):ift==l:returnpreturnp*S(p,t-l)+(l-p)*(l-S(p,t-1))step3:defQ(p,M,h):q=0foriinrange(h,M+l):q=comb(M,i)*(p*pow(S(p,t),i)*pow((l-S(p,t)),M-i)+(l-p)*pow(l-S(p,t),i)*pow(S(p,t),M-i))+qreturnqprint(Q(p,M,1))step4:defV(p,M,h):v=0foriinrange(h,M+1):v=comb(M,i)*(p*pow(S(p,i),i)*pow((l-S(p,i)),M-i))+vreturnvdefT(p,M,h):t=V(p,M,h)/Q(p,M,h)step5:deffindHmax():count=0forhinranged,M+l):ifQ(p,M,h)*N>=n:count=count+lreturncountdefcalRO:r=(1-T(p,M,h=findHmax()))*n#step6從python下標為n的位的連續(xù)60個數(shù)組defProspective(n,zn_temp2):point=nttprint(zn_temp)zn_temp=zn_temp2.copy()whilepoint:temp=zn_temp[3]zn_temp[12]*zn_temp[22]zn_temp[24]zn_temp[43]zn_temp[50]"zn_temp[56]zn_temp[59]zn_temp.insert(0,temp)zntemp.pop()point=point-1print(zn_temp)returnzn_temp#step7defLastCheck(zn_temp):count_right=0point=60whilepoint<=4000000~l:temp=zn_temp[0]zn_temp[4]zn_temp[13]zn_temp[23]zn_temp[25]zn_temp[44]zn_temp[51]zn_temp[57]zn_temp.append(temp)zn_temp=zn_temp[1:]if(zn_temp[59]=zn[point]):count_right=count_right+lpoint=point+lreturncount_right/(4000000-60)#step8defChangeHaming(zn_temp):flag=lcount=0zn_temp_copy=zn_temp.copy()whileflagandcount<=59:Pros_zn=Prospective(l2800,zn_temp_copy)resu1t=LastCheck(Pros_zn)print(result,count)print('開頭序列'，Proszn)print('選取序列'，zn_temp_copy)ifresult>0.8orresult<0.70:zn_tempcopy=zn_temp.copy()zn_temp_copy[count]=zn_temp_copy[count]-1count=count+lelse:flag=0zn=ReadFile(,data-1.txt')ChangeHaming(zn[12800:12860])3算法II實現(xiàn)代碼importscipyfromscipy.specialimportcombimportsys,timeimportrandoman=[[0foriinrange(9)]foriinrange(180)]data=[0foriinrange(4000000)]list_p=[0foriinrange(160)]list_S=[0foriinrange(160)]pn=[0.75foriinrange(4000000)]的概率pn#存儲校驗正確與錯誤的校驗方程系數(shù)correctpos=[0foriinrange(160)]errorpos=[0foriinrange(160)]defReadFile(filename):datafile=open(fi1ename)try:text=datafile,read()returnevalC[*+text[4：-l]+*Y)finally:datafile.closeOdefWriteFile(filename):try:file_object=open(fi1ename,'w')file_object.write(10.75\0*+str(data).replaceC','')[1：-l]+,,')finally:file_object.closeOdefCreatePoly(n):imax=0count=0aO=[0,4,13,23,25,44,51,57,60]ai=[[0,4,13,23,25,44,51,57,60]foriinrange(20)]whilepow(2,imax)*60<4000000:forjinrange(9):ai[imax][j]=pow(2,imax)*aO[j]imax=imax+lforiinrange(imax):forjinrange(9):offset=n-ai[i][j]ifoffset>=0:ifai[i][8]+offset>=4000000:continueforzinrange(9):an[count][z]=ai[i][z]+offsetcount=count+l即rint("成功生成T,count,"個校驗方稗)#foriinrange(count):#print(an[i])returncount松defCalusp_t(p,t):ift==0:returnpow(l-p,t)return(pow(2*p-l,t-1)*(p-0.5)+0.5)#將pi的值打表defMakeListOfValue_p(p):foriinrange(160):list_p[i]=Calusp_t(p,i)#第i個校驗式的t位相等的概率defCalcuS(i,t):ift==l:returnpn[an[i-l][0]]else:return(l-pn[an[i-l][t-l]])*(l-CalcuS(i-l,t-l))+pn[an[i-l][t-l]]*CalcuS(i-l,t-l)defMakeListOfValue_S():foriinrange(160):1ist_S[i]=CalcuS(i,8)#計算第i個位置的條件概時4defCalcuP(h,i,M):Y=1foriinranged,h+1):Y=CalcuS(correctpos[i]?8)*Yforiinrange(h+1,M+l):Y=Y*(l-CalcuS(errorposfi],8))Y=Y*pn[i]T=1foriinranged,h+1):T=(l-CalcuS(correctpos[i],8))*Tforiinrange(h+1,M+l):T=T*CalcuS(errorpos[i]?8)T=(l-pn[i])*TreturnY/(Y+T)#QdefCalcuU(p,M,h):Q二0s=CalcuS(O,8)foriinrange(h,M+l):Q=comb(Mfi)*(p*pow(s,i)*pow((l-s),M-i)+(l-p)*pow(1-s,i)*pow(s,M-i))+QreturnQ#RdefCalcuV(p,M,h):T=0s=CalcuS(0,8)foriinranged,h):T=comb(M,i)*(p*pow(s,i)*pow((1-s),M-i))+TreturnTdefCalcuT(p,M,h):returnCalcuV(p,M,h)/CalcuU(p,M,h)defCalcuW(p,M,h):T=0s=CalcuS(0,8)foriinranged,h+1):T=comb(M,i)*((l-p)*pow(l-s,i)*pow(s,M-i))+TreturnTdeffindllmax(p,M):Hmax=0Imax=0foriinrange(M):#print(CalcuW(p,M,i),CalcuV(p,M,i))ifCalcuW(p,M,i)-CalcuV(p,M,i)>Imax:Hmax=ittprint(Hmax)return0.5*(CalcuP(Hmax,p,M)+CalcuP(Hmax+l,p,M)),HmaxdefGetEvenVerify(n):M=CreatePoly(n)Pthr,Hmax=findHmax(0.75,M)Nthr=CalcuU(0.75,M,Hmax)*4000000S=CalusS(0.75,8)llmax=findllmax(0.75,M,S)currentnum=0errornum=0forjinrange(M):ifdata[an[j][0]]-data[an[j][1]]-data[an[j][2]]-data[an[j][3]]-data[an[j][4]]"\data[an[j][5]]data[an[j][6]]*data[an[j][7]]*data[an[j][8]]=0: