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

第二屆全國密碼數(shù)學(xué)挑戰(zhàn)賽西南賽區(qū)題目二參賽單位：電子科技大學(xué)參賽隊員：詹彤、王雨飛、方淳晟指導(dǎo)老師：李小平聯(lián)系電話：xxxxxxxxxxxxx聯(lián)系郵箱：xxxxxxxxxxxxxxxxxxxxxx摘要快速相關(guān)攻擊算法是解決流密碼問題的一種重要方法，也是密碼學(xué)中重要研究內(nèi)容之一。自Siegenthaler提出快速相關(guān)攻擊以來，不斷有更高效的算法被提出。本文基于Meier和Staffelbach提出的Fastcorrelationattacks中的兩種算法，根據(jù)提供的被加密的序列密碼以及其和原序列的相關(guān)概率，利用概率等相關(guān)知識，恢復(fù)線性移位寄存器的60位初始序列。本文所用的算法，不僅可以解決快速相關(guān)攻擊中，密碼和輸出序列的相關(guān)概率較高的流密碼問題，也可以解決對于線性移位寄存器的反饋多項式而言，抽頭數(shù)不高的流密碼。因此有著廣泛的應(yīng)用前景。目錄1.序列密碼的相關(guān)攻擊介紹42.快速相關(guān)攻擊研究現(xiàn)狀53.Meier-Staffelbach型算法的基本思想54.快速相關(guān)攻擊算法Ⅰ64.1算法Ⅰ實現(xiàn)步驟64.2算法Ⅰ計算復(fù)雜度分析75.快速相關(guān)攻擊算法Ⅱ85.1算法Ⅱ?qū)崿F(xiàn)步驟85.2算法Ⅱ計算復(fù)雜度分析96.結(jié)果部分107.相關(guān)代碼117.1校驗方程生成代碼127.2算法Ⅰ實現(xiàn)代碼147.3算法Ⅰ實現(xiàn)代碼168.參考文獻(xiàn)201.序列密碼的相關(guān)攻擊介紹本問題是基于線性反饋移位寄存器LFSR的相關(guān)攻擊問題。令LFSR的反饋多項式為，一個60位的初始密鑰，經(jīng)過LFSR的線性反饋多項式的運(yùn)算，輸出序列,經(jīng)由二元無記憶對稱信道(BSC)加密，得到截取序列。實現(xiàn)過程如圖1所示。圖1加密過程演示如果線性函數(shù)的某個輸入分量un與輸出zn之間存在相關(guān)性，即p=[P(un=zn)]>0.5。那么可以窮搜索LFSR的初始序列，找出使LFSR的輸出與對應(yīng)密鑰流序列z的距離最小的初始序列作為該LFSR的初始序列（種子密鑰）。假設(shè)LFSR產(chǎn)生最大周期序列，設(shè)級數(shù)為n，則周期為2n-1。該系統(tǒng)的密鑰量為：K=2n-1(1)如果窮搜索密鑰攻擊算法，n足夠大的時候，計算量是無法實現(xiàn)的，事實上，隨著n的增大，算法的復(fù)雜度呈指數(shù)增長。如果相關(guān)攻擊不對種子密鑰進(jìn)行枚舉搜索，就稱為快速相關(guān)攻擊。2.快速相關(guān)攻擊研究現(xiàn)狀相關(guān)攻擊最早是由Siegenthaler提出，其原理是利用密鑰發(fā)生器的輸出序列與其源LFSR的輸出序列之間具有的相關(guān)性還原LFSR的初始狀態(tài)。Meier和Staffelbach在此基礎(chǔ)上提出利用概率迭代譯碼的快速相關(guān)攻擊算法[1]，該方法接收到的密鑰流序列的每一比特位代入原序列的反饋多項式組成的方程組中，利用方程組是否滿足原序列的反饋多項式的概率，通過一定次數(shù)的迭代，來最終找到序列的初始狀態(tài)，實現(xiàn)解密。在LFSR的特征多項式重量較?。ǎ┑那闆r下取得了較好的效果，之后有學(xué)者提出了一些改進(jìn)算法。LFSR的抽頭數(shù)一直是Meier-Staffelbach型相關(guān)攻擊算法的頸瓶。1999年T．Johansson和F.Jonsson把快速相關(guān)攻擊應(yīng)用到LFSR的一般情形，他們的攻擊的關(guān)鍵是把LFSR序列轉(zhuǎn)化成卷積碼，使用卷積碼的譯碼算法恢復(fù)LFSR的初態(tài)，仿真結(jié)果表明，使用Viterbi譯碼算法，在抽頭數(shù)較大時，和以往算法比較，攻擊成功時的相關(guān)系數(shù)減小；接著他們把卷積碼和迭代概率譯碼融合起來，把LFSR序列轉(zhuǎn)變成turbo碼，繼而使用turbo譯碼算法恢復(fù)LFSR的初態(tài)。2000年，V．Chepyzhov，T.Joansson和B．Smeets的部分思想[2]，提出一個較為簡單而有效的快速相關(guān)攻擊算法。T.Johansson和F.Jonsson提出不同于以往的BSC攻擊模型即線性多項式重構(gòu)模型，吸取了多項式學(xué)習(xí)的已有成果進(jìn)行攻擊。近年來，快速相關(guān)攻擊技術(shù)有了很大的發(fā)展，許多文獻(xiàn)給出了新的快速相關(guān)攻擊算法。大多數(shù)快速相關(guān)攻擊算法利用窮舉搜索猜測LFSR部分初始狀態(tài)，再結(jié)合密鑰流和校驗方程集合逐步恢復(fù)其余的LFSR初始狀態(tài)?？焖傧嚓P(guān)攻擊新的發(fā)展方向是：算法可由高速軟件或簡單硬件實現(xiàn)，并適于并行運(yùn)算。3.基于Meier-Staffelbach型的算法本文提到的算法Ⅰ和算法Ⅱ，其基本思想是考慮到輸出序列和原序列之間存在相關(guān)性，通常情況下，因此可以將輸出序列看作是原序列的一種擾亂，故可以把序列的每一比特位代入LFSR反饋多項式組成的方程組中?？紤]在模二域上有(2)所以通過對的重復(fù)乘方可以得到多個LFSR的校驗多項式，對每一個街區(qū)序列上的比特位而言，如果某一比特位上，關(guān)于該比特位，這些校驗多項式成立的個數(shù)越多，用該比特位代替LFSR序列的相應(yīng)比特是正確的概率就越大，在求解概率問題中主要利用形如式(3)的概率迭代公式(3)以及求解條件概率公式(4)貝葉斯公式主要用于求解算法Ⅱ中的概率問題(5)而上面提到的漢明距離，既是指表示兩個（相同長度）字對應(yīng)位不同的數(shù)量。4.快速相關(guān)攻擊Ⅰ4.1算法Ⅰ實現(xiàn)步驟設(shè)反饋多項式級數(shù)為，抽頭數(shù)為，相關(guān)概率，截取序列的長度為。第1步：計算序列每比特所需要的校驗方程平均數(shù)：(6)第2步：計算截取序列的比特的模二加（含有個比特）和原LFSR序列的相應(yīng)比特的模二加相同的概率：......(7)第3步：計算在個校驗方程中，至少有個方程成立的概率：(8)第4步：計算在個校驗方程中，至少有個方程成立，且它是正確比特位的概率，即概率為：(9)因此，在給定個方程中至少有個方程成立的條件下，的概率為：(10)第5步：求出一個最大的，記為，使。計算在個比特中錯誤的平均數(shù)r：(11)第6步：找出在個方程中至少滿足個方程的比特位，用這些比特位作為相應(yīng)下標(biāo)位置上LFSR序列的“正確”比特，然后適當(dāng)?shù)剡x取包含個比特的一個集合記為Io，固定個連續(xù)比特位。第7步：對Io中的每一比特位利用LFSR的反饋多項式組建成一個線性方程，即把它表示成固定個比特位的一個線性組合，然后將這個線性方程組合在一起組成一個線性方程組。第8步：解線性方程，若是線性相關(guān)的，則用幾個附加比特位選擇一個線性無關(guān)的子方程組，將解出來的個連續(xù)比特擴(kuò)展為整個LFSR序列，并與原來截取到的序列的位進(jìn)行比較，若相關(guān)概率在之間(通常認(rèn)為e取0.05)，則認(rèn)為求解成功。若相關(guān)概率不在區(qū)間之內(nèi)，則認(rèn)為求解失敗，從而以漢明距1,2,...檢驗的所有變換，每進(jìn)行以此漢明變換都轉(zhuǎn)入第7步。直到成功求解為止。4.2算法Ⅰ計算復(fù)雜度分析算法Ⅰ的主要求解時間耗費(fèi)在進(jìn)行漢明變換上。我們可以假設(shè)解方程和添加附加位這一過程所用時間為，進(jìn)行漢明變換的距離為，則總時間為(12)則有T≤，其中H(e)表示二進(jìn)制的熵函數(shù)，。整個算法復(fù)雜度為O（），C取決于p、t、n，N，且0＜C＜1。5.快速相關(guān)攻擊Ⅱ該算法的基本思想：根據(jù)截取序列的每一比特位所滿足的方程數(shù)。來計算截取序列每一比特的新概率，當(dāng)這些新概率小于給定值的數(shù)目超過另一給定值，或者計算新概率的總的次數(shù)超過5，就對新概率小于給定值的截取序列的比特位進(jìn)行取補(bǔ)，接著以新序列代替原序列，并將各比特位的概率重新置為原相關(guān)概率，重復(fù)上述過程，直到成功。5.1算法Ⅱ?qū)崿F(xiàn)步驟：第1步：計算序列每比特所需要的校驗方程平均數(shù)(13)第2步：計算截取序列的比特的模二加（含有個比特）和原LFSR序列的相應(yīng)比特的模二加相同的概率......(14)第3步：計算在個校驗方程中，至少有個方程成立的概率(15)計算在個校驗方程中，對不滿足個方程的比特位進(jìn)行取補(bǔ)，取補(bǔ)后增加的正確的比特位概率為(16)計算在個校驗方程中，有個方程成立時每個比特位的后驗概率為(17)第4步：找出使得I最大的記為，若，則表示該算法失敗，若，則計算，用以表示各比特位的一個閾值，若后驗概率,就對該比特位進(jìn)行取補(bǔ)(18)第5步：用表示的比特位的數(shù)目，則可結(jié)束此次迭代，也就是直接對的比特位進(jìn)行取補(bǔ)，開始下一次迭代：(19)第6步：重置迭代次數(shù)i為0第7步：對截取序列z的每一位比特位和原LFSR序列相應(yīng)比特位的和是相同的概率S(p1,p2,...,pt,t):(20)第8步：由貝葉斯公式計算各比特位的新概率：(21)pi*:表示第i位比特的薪概率，而pi表示元概率：在統(tǒng)計校驗方程成立的數(shù)目時，其表示使得方程成立的的下標(biāo)。而剩下的則表示不成立的的下標(biāo)。第9步：確定的總比數(shù)目，若或,則，轉(zhuǎn)到第7步。否則，對截取序列的那些滿足的比特位進(jìn)行取補(bǔ)，并重置比特位的概率位。第10步：若取補(bǔ)后的截取序列中出現(xiàn)了有不滿足反饋多項式的比特位時,則轉(zhuǎn)到第6步。直到攻擊成功。5.2算法Ⅱ計算復(fù)雜度分析其算法復(fù)雜度為。在、給定的情況下，復(fù)雜度隨LFSR的級數(shù)增大而增大。在其他條件不變的情況下，復(fù)雜度隨增大而增大，隨增大而減小。缺點(diǎn)也很明顯，在迭代過程中，可能出現(xiàn)分母為0的情況。結(jié)果部分下面給出各序列的從到的解。（1）第一個序列0,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,1,1,0,0,0,1,0,0,0,1,1,1（2）第二個序列1,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,1,1（3）第三個序列1,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,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,1,1,0,1（4）第四個序列1,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,1,1,0,1,1,1,0,1,1,1,0,1,0,0,0（5）第五個序列1,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,0,1,1,1（6）第六個序列1,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,0,1,1,1,1,0,0,0,0,1,0,0,1,1,0,1,1,0,0,0,1,1（7）第七個序列1,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,1,1,1,1,1,0,0,0,1,1,0,0,1,1,0,1（8）第八個序列0,1,1,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,0,1,1,1,1,1,0,1,1,1,0,1,1,0,1,1,1,0,1,1,1,0,1,0,0,0（9）第九個序列0,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,1,1,1,0,0,1,0,0,0,1,1,1（10）第十個序列z1,1,0,0,0,1,1,1,0,0,0,1,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,1,1（11）第十一個序列1,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,1,1,0,1（12）第十二個序列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,1,0,1,1,0,1,1,1,0,0,1,1,1,1,1,0,1,1,1,0,1,1,0,1,1,1,0,1,1,1,0,1,0,0,07.相關(guān)代碼7.1生成校驗方程importscipy

importsys,time

fromscipy.specialimportcomb

importre

importmath

N=4000000#序列數(shù)

n=60#級數(shù)

p=0.75#相關(guān)概率

fx=[3,9,16,35,37,47,56,60]#反饋多項式的系數(shù)

#fx=[1,2,3,5]

t=len(fx)#計算抽頭數(shù)

importscipy

importsys,time

importre

importmath

#讀取序列z

defReadFile(filename):

datafile=open(filename)

try:

text=datafile.read()

returneval('['+text[4:-1]+']')

finally:

datafile.close()

defwriteFile(filename,data_write):

try:

file_object=open(filename,'w')

#file_object.write('0.75\n'+str(data).replace('','')[1:-1]+',')

file_object.write('0.75\n'+str(data_write).replace('','')[1:-1]+',')

finally:

file_object.close()

N=4000000#序列數(shù)

n=60#級數(shù)

fx=[3,9,16,35,37,47,56,60]#反饋多項式的系數(shù)

#fx=[1,2,3,5]

t=len(fx)#計算抽頭數(shù)

M=round(math.log(N/(2*n),2)*(t+1))#計算每位平均需要校驗方程數(shù)

imax=math.floor(math.log(N/n,2))

an=[[0foriinrange(t+1)]foriinrange(3*M)]#用于存儲最終校驗多項式

#print(imax)

defCreatePoly(w):#w為檢測第幾位

imax=math.floor(math.log(N/n,2))#乘方的最大值

count=0#記錄校驗方程的個數(shù)

a1=[[0foriinrange(t)]foriinrange(imax+1)]#用以保存校驗方程的序號

a1[0]=fx

#生成倍式（第一行為原反饋多項式）

foriinrange(1,imax+1):

forjinrange(t):

a1[i][j]=a1[0][j]*pow(2,i)

#print(a1)

#生成校驗方程

a2=[[0foriinrange(t+1)]foriinrange(imax+1)]

#print(a2)

forcolumninrange(imax+1):#將校驗等式左邊寫進(jìn)a2的最后一列

a2[column][t]=a1[column][t-1]

#print(a2)

foriinrange(imax+1):

forjinrange(t):

a2[i][t-j-1]=a2[i][t]-a1[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:

continue

else:

forkinrange(t+1):

an[count][k]=offset+a2[i][k]

count=count+1

returncount#返回校驗方程總數(shù)

deffindBite1():

rightnum=[]

data=ReadFile("data-1.txt")

forwinrange(4000000):

count=0

a=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("test1.txt",'a')

#f.write(str(an[i])+',')

count=count+1

#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.close()

b=len(data)

an=[[0foriinrange(60)]]

foriinrange(60):

count=0

forkinrange(10000):

forjinrange(9):

ifdata[k][j]==12800+i:

an[i]=12800+i

count=count+1

print("找到",count,"個了")

break

print(an)7.2算法Ⅰ實現(xiàn)代碼importscipy

importsys,time

fromscipy.specialimportcomb

importre

importmath

N=4000000#序列數(shù)

n=60#級數(shù)

p=0.75#相關(guān)概率

fx=[3,9,16,35,37,47,56,60]#反饋多項式的系數(shù)

#fx=[1,2,3,5]

t=len(fx)#計算抽頭數(shù)

#step1:

M=round(math.log(N/(2*n),2)*(t+1))#計算每位平均需要校驗方程數(shù)

#step2:

defS(p,t):

ift==1:

returnp

returnp*S(p,t-1)+(1-p)*(1-S(p,t-1))

#step3:

defQ(p,M,h):

q=0

foriinrange(h,M+1):

q=comb(M,i)*(p*pow(S(p,t),i)*pow((1-S(p,t)),M-i)+(1-p)*pow(1-S(p,t),i)*pow(S(p,t),M-i))+q

returnq

#print(Q(p,M,1))

#step4:

defV(p,M,h):

v=0

foriinrange(h,M+1):

v=comb(M,i)*(p*pow(S(p,i),i)*pow((1-S(p,i)),M-i))+v

returnv

defT(p,M,h):

t=V(p,M,h)/Q(p,M,h)

#step5:

deffindHmax():

count=0

forhinrange(1,M+1):

ifQ(p,M,h)*N>=n:

count=count+1

returncount

defcalR():

r=(1-T(p,M,h=findHmax()))*n

#step6

#從python下標(biāo)為n的位的連續(xù)60個數(shù)組

defProspective(n,zn_temp2):

point=n

#print(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)

zn_temp.pop()

point=point-1

print(zn_temp)

returnzn_temp

#step7

defLastCheck(zn_temp):

count_right=0

point=60

whilepoint<=4000000-1:

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+1

point=point+1

returncount_right/(4000000-60)

#step8

defChangeHaming(zn_temp):

flag=1

count=0

zn_temp_copy=zn_temp.copy()

whileflagandcount<=59:

Pros_zn=Prospective(12800,zn_temp_copy)

result=LastCheck(Pros_zn)

print(result,count)

print('開頭序列',Pros_zn)

print('選取序列',zn_temp_copy)

ifresult>0.8orresult<0.70:

zn_temp_copy=zn_temp.copy()

zn_temp_copy[count]=zn_temp_copy[count]^1

count=count+1

else:

flag=0

zn=ReadFile('data-1.txt')

ChangeHaming(zn[12800:12860])7.3算法Ⅱ?qū)崿F(xiàn)代碼importscipy

fromscipy.specialimportcomb

importsys,time

importrandom

an=[[0foriinrange(9)]foriinrange(180)]

data=[0foriinrange(4000000)]

list_p=[0foriinrange(160)]

list_S=[0foriinrange(160)]

pn=[0.75foriinrange(4000000)]#zn的概率pn

#存儲校驗正確與錯誤的校驗方程系數(shù)

correctpos=[0foriinrange(160)]

errorpos=[0foriinrange(160)]

defReadFile(filename):

datafile=open(filename)

try:

text=datafile.read()

returneval('['+text[4:-1]+']')

finally:

datafile.close()

defWriteFile(filename):

try:

file_object=open(filename,'w')

file_object.write('0.75\n'+str(data).replace('','')[1:-1]+',')

finally:

file_object.close()

defCreatePoly(n):

imax=0

count=0

a0=[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)*a0[j]

imax=imax+1

foriinrange(imax):

forjinrange(9):

offset=n-ai[i][j]

ifoffset>=0:

ifai[i][8]+offset>=4000000:

continue

forzinrange(9):

an[count][z]=ai[i][z]+offset

count=count+1

#print("成功生成",count,"個校驗方程")

#foriinrange(count):

#print(an[i])

returncount

#s

defCalusp_t(p,t):

ift==0:

returnpow(1-p,t)

return(pow(2*p-1,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==1:

returnpn[an[i-1][0]]

else:

return(1-pn[an[i-1][t-1]])*(1-CalcuS(i-1,t-1))+pn[an[i-1][t-1]]*CalcuS(i-1,t-1)

defMakeListOfValue_S():

foriinrange(160):

list_S[i]=CalcuS(i,8)

#計算第i個位置的條件概率P^*

defCalcuP(h,i,M):

Y=1

foriinrange(1,h+1):

Y=CalcuS(correctpos[i],8)*Y

foriinrange(h+1,M+1):

Y=Y*(1-CalcuS(errorpos[i],8))

Y=Y*pn[i]

T=1

foriinrange(1,h+1):

T=(1-CalcuS(correctpos[i],8))*T

foriinrange(h+1,M+1):

T=T*CalcuS(errorpos[i],8)

T=(1-pn[i])*T

returnY/(Y+T)

#Q

defCalcuU(p,M,h):

Q=0

s=CalcuS(0,8)

foriinrange(h,M+1):

Q=comb(M,i)*(p*pow(s,i)*pow((1-s),M-i)+(1-p)*pow(1-s,i)*pow(s,M-i))+Q

returnQ

#R

defCalcuV(p,M,h):

T=0

s=CalcuS(0,8)

foriinrange(1,h):

T=comb(M,i)*(p*pow(s,i)*pow((1-s),M-i))+T

returnT

defCalcuT(p,M,h):

returnCalcuV(p,M,h)/CalcuU(p,M,h)

defCalcuW(p,M,h):

T=0

s=CalcuS(0,8)

foriinrange(1,h+1):

T=comb(M,i)*((1-p)*pow(1-s,i)*pow(s,M-i))+T

returnT

deffindHmax(p,M):

Hmax=0

Imax=0

foriinrange(M):

#print(CalcuW(p,M,i),CalcuV(p,M,i))

ifCalcuW(p,M,i)-CalcuV(p,M,i)>Imax:

Hmax=i

#print(Hmax)

return0.5*(CalcuP(Hmax,p,M)+CalcuP(Hmax+1,p,M)),Hmax

defGetEvenVerify(n):

M=CreatePoly(n)

Pthr,Hmax=findHmax(0.75,M)

Nthr=CalcuU(0.75,M,Hmax)*4000000

#S=CalusS(0.75,8)

#Hmax=findHmax(0.75,M,S)

currentnum=0

errornum=0

forjinrange(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:

correctpos[currentnum]=j

currentnum=currentnum+1

else:

errorpos[errornum