Link for Download
A Reaction Attack against Cryptosystems based on LRPC Codes
First we need to load auxiliary functions used in the attack and parameters
load("utils.sage")
q=2
m=5
n=30
k=20
r=3
d=3
t=ceil(d*n/(n-k)-1)
create field and polinomial ring
field_K =GF(q)
field_K_extension, iso_K_to_Kext = field_K.extension(m, 'z', map=True)
R = PolynomialRing(field_K_extension,'x', d+r+d*n+(n-k)^2, order='lex');
x = R.gens()
In our case, R is the bases of H and e, and the unknown coefficients of H, and the unknown coefficients of $S’$ (Sprime)
First, we create private basis and elements of H and the coefficients.
private H, S, Hknown created using the chosen bases
basisHknown=matrix(R,1,d,[field_K_extension.random_element() for a in range(d)])
coef1,coef2,coef3 = createvectorsH(n,k,d)
Hknown= creatematrixH(n,k,d,basisHknown,coef1,coef2,coef3)
S=creatematrixS(n,k)
We then generate the public key, the basis, and create a H matrix with the secret coefficients and unkown basis
Gprime=creatematrixGprime(n,k)
F=creatematrixF(n,k,Gprime,Hknown,S)
basisH=matrix(R,1,d,[x[a] for a in range(d)])
basisE=matrix(R,1,r,[x[a] for a in range(d,r+d)])
H=creatematrixH(n,k,d,basisH,coef1,coef2,coef3)
print "Matrix H is:"
print H
Matrix H is:
[ x0 + x2 x2 0 x0 + x2 x1 + x2 x2 x2 x0 x2 x0 + x1 x0 x2 0 x1 + x2 x2 x0 x0 + x1 + x2 x1 x0 x0 + x2 x1 x0 + x2 x0 + x1 + x2 x0 + x2 x0 + x1 + x2 0 x1 x0 + x1 + x2 0 x1]
[ x0 + x1 x0 + x2 x2 0 x0 + x2 x1 + x2 x2 x2 x0 x2 x0 + x2 x0 x2 0 x1 + x2 x2 x0 x0 + x1 + x2 x1 x0 x1 x1 x0 + x2 x0 + x1 + x2 x0 + x2 x0 + x1 + x2 0 x1 x0 + x1 + x2 0]
[ x2 x0 + x1 x0 + x2 x2 0 x0 + x2 x1 + x2 x2 x2 x0 x0 x0 + x2 x0 x2 0 x1 + x2 x2 x0 x0 + x1 + x2 x1 0 x1 x1 x0 + x2 x0 + x1 + x2 x0 + x2 x0 + x1 + x2 0 x1 x0 + x1 + x2]
[ x0 x2 x0 + x1 x0 + x2 x2 0 x0 + x2 x1 + x2 x2 x2 x1 x0 x0 + x2 x0 x2 0 x1 + x2 x2 x0 x0 + x1 + x2 x0 + x1 + x2 0 x1 x1 x0 + x2 x0 + x1 + x2 x0 + x2 x0 + x1 + x2 0 x1]
[ x2 x0 x2 x0 + x1 x0 + x2 x2 0 x0 + x2 x1 + x2 x2 x0 + x1 + x2 x1 x0 x0 + x2 x0 x2 0 x1 + x2 x2 x0 x1 x0 + x1 + x2 0 x1 x1 x0 + x2 x0 + x1 + x2 x0 + x2 x0 + x1 + x2 0]
[ x2 x2 x0 x2 x0 + x1 x0 + x2 x2 0 x0 + x2 x1 + x2 x0 x0 + x1 + x2 x1 x0 x0 + x2 x0 x2 0 x1 + x2 x2 0 x1 x0 + x1 + x2 0 x1 x1 x0 + x2 x0 + x1 + x2 x0 + x2 x0 + x1 + x2]
[ x1 + x2 x2 x2 x0 x2 x0 + x1 x0 + x2 x2 0 x0 + x2 x2 x0 x0 + x1 + x2 x1 x0 x0 + x2 x0 x2 0 x1 + x2 x0 + x1 + x2 0 x1 x0 + x1 + x2 0 x1 x1 x0 + x2 x0 + x1 + x2 x0 + x2]
[ x0 + x2 x1 + x2 x2 x2 x0 x2 x0 + x1 x0 + x2 x2 0 x1 + x2 x2 x0 x0 + x1 + x2 x1 x0 x0 + x2 x0 x2 0 x0 + x2 x0 + x1 + x2 0 x1 x0 + x1 + x2 0 x1 x1 x0 + x2 x0 + x1 + x2]
[ 0 x0 + x2 x1 + x2 x2 x2 x0 x2 x0 + x1 x0 + x2 x2 0 x1 + x2 x2 x0 x0 + x1 + x2 x1 x0 x0 + x2 x0 x2 x0 + x1 + x2 x0 + x2 x0 + x1 + x2 0 x1 x0 + x1 + x2 0 x1 x1 x0 + x2]
[ x2 0 x0 + x2 x1 + x2 x2 x2 x0 x2 x0 + x1 x0 + x2 x2 0 x1 + x2 x2 x0 x0 + x1 + x2 x1 x0 x0 + x2 x0 x0 + x2 x0 + x1 + x2 x0 + x2 x0 + x1 + x2 0 x1 x0 + x1 + x2 0 x1 x1]Creation of the errorList, valid messages and the ciphertexts.
errorsList=[]
for i in range(n):
basisEknown=matrix(R,1,r,[field_K_extension.random_element() for a in range(r)])
etemp,coef=createerrorE(n,r,basisE)
e=createerrorEknown(n,r,basisEknown,coef)
errorsList.append(e)
messageList=[]
for i in range(n):
mtemp=matrix(R,1,k,[field_K_extension.random_element() for a in range(k)])
messageList.append(mtemp)
ciphertextList=[]
for i in range(n):
c1=messageList[i]*Gprime+errorsList[i]
c2=messageList[i]*F
ciphertextList.append((c1,c2))
Now, we start the attack. We create H with unknown coefficients in basisH.
Hunknown=createUnknownMatrixH(n,k,d,basisH,[x[i] for i in range(r+d,r+d+n*d)])
trials=0
repeatflag=true
while repeatflag:
flagSuccess=false
while not flagSuccess:
trials+=1
# known errors that cause decryption failures together with the corresponding kernel elements
eknown,kerknown=FindErrorsAndKernels(H,t,n,k,r,d)
SunknownList=CreateSunknown(Hunknown,eknown,t,n,k,r,d)
# candidate kernel elements
kerunknown=CreateRandom(t,n,k,r,d)
# use this if you want to test the validity of the algorithm for known kernel elements
system=CreateSystem(SunknownList,kerknown, t,n,k,r,d)
flagSuccess,solution=SolveSystem(system,n,k,r,d)
print(flagSuccess, len(solution))
print("Found valid kernel elements in ", trials, "trials")
if flagSuccess:
sol=FindOneSolution(solution,n,k,r,d)
basisH=matrix(R,1,d,[x[a] for a in range(d)])
HunknownBasis=createUnknownMatrixH(n,k,d,basisH,sol)
# create the unknown matrix S
MatrixSunknown=creatematrixSunknown(n,k)
#This function uses the equivalent keys, i.e., Section 4
Hfound,Sfound,repeatflag=FindSolutionCoefHandS(basisH,HunknownBasis,MatrixSunknown,ciphertextList,errorsList,n,k,r,d)
if repeatflag==false:
# perform check on the ciphertexts
Ffound=creatematrixF(n,k,Gprime,Hfound,Sfound.inverse())
ciphertextFoundList=[]
for i in range(n):
c1=messageList[i]*Gprime+errorsList[i]
c2=messageList[i]*Ffound
ciphertextFoundList.append((c1,c2))
eq=(c1-errorsList[i])*Hfound.transpose()-c2*Sfound.inverse()
print(" ")
print("Check whether the final solution produces the same ciphertexts...")
countsame=0
for i in range(n):
if ciphertextList[i][1]==ciphertextFoundList[i][1]:
countsame+=1
if countsame==n:
print ("found matrix H equals to:")
print Hfound
print("Everything OK! Attack successful!")
repeatflag=false
break
repeatflag=false
else:
repeatflag=true
################################
print("Complexity is:")
print(float(((r*d - 1)*t)+3*log(n*d,2)))
(True, 20)
('Found valid kernel elements in ', 1, 'trials')
(True, 20)
('Found valid kernel elements in ', 2, 'trials')
(True, 21)
('Found valid kernel elements in ', 3, 'trials')
(True, 21)
('Found valid kernel elements in ', 4, 'trials')
(True, 20)
('Found valid kernel elements in ', 5, 'trials')
(True, 20)
('Found valid kernel elements in ', 6, 'trials')
Found S is nonsingular
Check whether the final solution produces the same ciphertexts...
found matrix H equals to:
[ (z + 1) (z) (z^3 + z + 1) (z^3 + z + 1) (z^3 + 1) (z^3 + 1) (z^3 + 1) (z^3 + z + 1) (z^3 + z + 1) (z + 1) (z^3 + 1) (z^3 + z + 1) 0 (z^3 + 1) (z^3 + z + 1) (z^3 + z + 1) (z) 1 (z^3 + z + 1) 0 (z + 1) (z + 1) (z^3 + z) (z + 1) (z^3 + z) (z^3 + z) (z + 1) 0 (z^3 + z) (z^3 + z)]
[ (z + 1) (z + 1) (z) (z^3 + z + 1) (z^3 + z + 1) (z^3 + 1) (z^3 + 1) (z^3 + 1) (z^3 + z + 1) (z^3 + z + 1) 0 (z^3 + 1) (z^3 + z + 1) 0 (z^3 + 1) (z^3 + z + 1) (z^3 + z + 1) (z) 1 (z^3 + z + 1) (z^3 + z) (z + 1) (z + 1) (z^3 + z) (z + 1) (z^3 + z) (z^3 + z) (z + 1) 0 (z^3 + z)]
[(z^3 + z + 1) (z + 1) (z + 1) (z) (z^3 + z + 1) (z^3 + z + 1) (z^3 + 1) (z^3 + 1) (z^3 + 1) (z^3 + z + 1) (z^3 + z + 1) 0 (z^3 + 1) (z^3 + z + 1) 0 (z^3 + 1) (z^3 + z + 1) (z^3 + z + 1) (z) 1 (z^3 + z) (z^3 + z) (z + 1) (z + 1) (z^3 + z) (z + 1) (z^3 + z) (z^3 + z) (z + 1) 0]
[(z^3 + z + 1) (z^3 + z + 1) (z + 1) (z + 1) (z) (z^3 + z + 1) (z^3 + z + 1) (z^3 + 1) (z^3 + 1) (z^3 + 1) 1 (z^3 + z + 1) 0 (z^3 + 1) (z^3 + z + 1) 0 (z^3 + 1) (z^3 + z + 1) (z^3 + z + 1) (z) 0 (z^3 + z) (z^3 + z) (z + 1) (z + 1) (z^3 + z) (z + 1) (z^3 + z) (z^3 + z) (z + 1)]
[ (z^3 + 1) (z^3 + z + 1) (z^3 + z + 1) (z + 1) (z + 1) (z) (z^3 + z + 1) (z^3 + z + 1) (z^3 + 1) (z^3 + 1) (z) 1 (z^3 + z + 1) 0 (z^3 + 1) (z^3 + z + 1) 0 (z^3 + 1) (z^3 + z + 1) (z^3 + z + 1) (z + 1) 0 (z^3 + z) (z^3 + z) (z + 1) (z + 1) (z^3 + z) (z + 1) (z^3 + z) (z^3 + z)]
[ (z^3 + 1) (z^3 + 1) (z^3 + z + 1) (z^3 + z + 1) (z + 1) (z + 1) (z) (z^3 + z + 1) (z^3 + z + 1) (z^3 + 1) (z^3 + z + 1) (z) 1 (z^3 + z + 1) 0 (z^3 + 1) (z^3 + z + 1) 0 (z^3 + 1) (z^3 + z + 1) (z^3 + z) (z + 1) 0 (z^3 + z) (z^3 + z) (z + 1) (z + 1) (z^3 + z) (z + 1) (z^3 + z)]
[ (z^3 + 1) (z^3 + 1) (z^3 + 1) (z^3 + z + 1) (z^3 + z + 1) (z + 1) (z + 1) (z) (z^3 + z + 1) (z^3 + z + 1) (z^3 + z + 1) (z^3 + z + 1) (z) 1 (z^3 + z + 1) 0 (z^3 + 1) (z^3 + z + 1) 0 (z^3 + 1) (z^3 + z) (z^3 + z) (z + 1) 0 (z^3 + z) (z^3 + z) (z + 1) (z + 1) (z^3 + z) (z + 1)]
[(z^3 + z + 1) (z^3 + 1) (z^3 + 1) (z^3 + 1) (z^3 + z + 1) (z^3 + z + 1) (z + 1) (z + 1) (z) (z^3 + z + 1) (z^3 + 1) (z^3 + z + 1) (z^3 + z + 1) (z) 1 (z^3 + z + 1) 0 (z^3 + 1) (z^3 + z + 1) 0 (z + 1) (z^3 + z) (z^3 + z) (z + 1) 0 (z^3 + z) (z^3 + z) (z + 1) (z + 1) (z^3 + z)]
[(z^3 + z + 1) (z^3 + z + 1) (z^3 + 1) (z^3 + 1) (z^3 + 1) (z^3 + z + 1) (z^3 + z + 1) (z + 1) (z + 1) (z) 0 (z^3 + 1) (z^3 + z + 1) (z^3 + z + 1) (z) 1 (z^3 + z + 1) 0 (z^3 + 1) (z^3 + z + 1) (z^3 + z) (z + 1) (z^3 + z) (z^3 + z) (z + 1) 0 (z^3 + z) (z^3 + z) (z + 1) (z + 1)]
[ (z) (z^3 + z + 1) (z^3 + z + 1) (z^3 + 1) (z^3 + 1) (z^3 + 1) (z^3 + z + 1) (z^3 + z + 1) (z + 1) (z + 1) (z^3 + z + 1) 0 (z^3 + 1) (z^3 + z + 1) (z^3 + z + 1) (z) 1 (z^3 + z + 1) 0 (z^3 + 1) (z + 1) (z^3 + z) (z + 1) (z^3 + z) (z^3 + z) (z + 1) 0 (z^3 + z) (z^3 + z) (z + 1)]
Everything OK! Attack successful!
Complexity is:
83.475559289