clear ; print GetSeed() ; load "public_key.txt" ; if IsOdd(q) then printf "q=%o is even need to load file forge_odd\n",q; else xtndbss := procedure( ~A, n ) // A must be in echelon form m := Rank(A) ; d := [i: i in [1..n]] ; j := 0 ; for i in [1..m] do repeat j +:= 1 ; until (A[i][j] ne 0) ; d[j] := 0 ; end for ; j := 0 ; for i in [m+1..n] do repeat j+:= 1 ; until d[j] ne 0 ; A[i][j] := 1 ; end for ; end procedure ; ovsigndocument := function(G0, x, o,v, f, Linv, doc) // G0 finite field // x // o number of oil variables // v number of vinegar variables // f secrete function // Linv inverse of secrete transformation // doc: document to be signed // returns signature n := o + v ; repeat vinegar := [Random(G0): i in [1..v]] ; // Evaluate private functions f ov:=[x[i]:i in [1..o]] cat vinegar ; z1:=[] ; M := ZeroMatrix( G0, o, o ) ; z00 := [G0!0: i in [1..n]] ; z10 := []; for k in [1..o] do z1[k]:=Evaluate( f[k], ov ) ; for i in [1..o] do M[i,k] := Coefficient( z1[k], x[i], 1 ) ; end for ; z10[k] := doc[k] - Evaluate( z1[k], z00 ); end for ; until Rank(M) eq o ; w := Vector(G0, z10) ; oil := Solution( M,w ) ; oilvin :=Vector(G0,n,[G0!0:i in [1..n]]) ; for i in [1..o] do oilvin[i] := oil[i] ; end for ; for i in [1..v] do ; oilvin[i+o] := vinegar[i] ; end for ; signature :=oilvin * Linv ; return signature ; end function ; printf "************************************************************* \n"; printf "*** Kipnis-Shamir Attack against Balanced Oil and Vinegar *** \n"; printf "************************************************************* \n"; printf " even characteristic case \n \n"; printf " Afterwards use verify.txt to verify that forged signature is valid\n"; // creating a forgery forgery := [Random(GF): i in [1..o]]; // forgery to be signed // generate matrices from public polynomials QBnew :=[] ; for k := 1 to o do QBnew[k] := ZeroMatrix( GF,n,n ) ; for i in [1..n] do for j in [i..n] do QBnew[k][i,j] := MonomialCoefficient( Pk[k],x[i]*x[j] ) ; end for ; end for ; end for ; QBT := [] ; for i in [1..o] do QBT[i] := QBnew[i] + Transpose(QBnew[i]) ; end for ; success := false ; tries := 0 ; // try to find a matrix, whose charateristic polynomial has a // polynomial of degree 1 (repeated twice) a := [] ; repeat tries +:= 1 ; // generate matrices in QB repeat a[1] := Random(GF); W1 := a[1]* QBT[1] ; for i in [2..o] do a[i] := Random(GF); W1 +:= a[i]* QBT[i] ; end for ; print "determinant of W1=",Determinant(W1); until Determinant(W1) ne 0 ; print "Linear Combinations for W1= ",a ; repeat a[1] := Random(GF); W2 := a[1]* QBT[1] ; for i in [2..o] do a[i] := Random(GF); W2 +:= a[i]* QBT[i] ; end for ; print "deterimant of W2=",Determinant(W2); until Determinant(W2) ne 0 ; print "Linear Combinations for W2= ",a ; W12 := W1^(-1) * W2 ; f10 :=CharacteristicPolynomial(W12); f12 := Factorization( f10 ) ; print f12 ; for i in [1..#f12] do if (Degree(f12[i][1]) eq 1 ) and (f12[i][2] eq 2) then success := true ; c1 := f12[i][1] ; break ; end if ; end for ; until (success ) or (tries gt 100) ; print "tries=",tries; if tries gt 100 then print "Did not find a simple eigenvalue" ; end if ; c0 := Coefficients(c1)[1]; // simple eigenvalue b1 := Basis(Eigenspace( Transpose(W12),c0 )) ; Wij:= [] ; //generate n matrices for tries in [1..n] do // generate matrices in QBT repeat W1 := Random(GF)* QBT[1] ; for i in [2..o] do W1 +:= Random(GF)* QBT[i] ; end for ; until Determinant(W1) ne 0 ; repeat W2 := Random(GF)* QBT[1] ; for i in [2..o] do W2 +:= Random(GF)* QBT[i] ; end for ; until Determinant(W2) ne 0 ; Wij[tries] := W1^(-1) * W2 ; end for ; Q1new :=[] ; s1 := ZeroMatrix(GF,n,n) ; success := false ; // set up all possible eigenvectors S := { b1[1]+a2*b1[2] : a2 in GF}; S := S join {b1[2]}; for b in S do print "using b=",b; for k in [1..n] do s0 := b*Transpose( Wij[k] ); s1[k] := s0; end for ; if Rank(s1) eq o then s2 := EchelonForm( s1 ) ; xtndbss( ~s2,n ) ; print "change basis with =", s2 ; if Rank( s2 ) ne n then print "DID not extend s2 properly!! " ,s2 ; end if ; for k in [1..o] do Q1new[k] := s2*QBT[k] *Transpose( s2 ); end for; ; success := true ; print "success with eigenvector =",b; break ; end if ; end for ; print "start forgery using equivalent oil vinegar equations"; s2inv := s2^-1 ; Qnew := [] ; for k in [1..o] do Qnew[k] := s2inv * QBnew[k] * Transpose( s2inv) ; end for ; fnew := [] ; for k in [1..o] do temp := P!0 ; for i in [1..n] do for j in [1..n] do temp +:= Qnew[k][i][j] * x[i]*x[j] ; end for ; end for ; fnew[k] := temp ; end for ; signatureforg := ovsigndocument(GF,x,o,v, fnew, s2, forgery ); /////////////// write out signature, then use verify ///////////////////////////////// printf "The forged document is %o \n ", forgery ; printf "forged signature := %o \n \n", signatureforg; printf"Write signature.txt \n \n"; SetOutputFile("signature.txt":Overwrite:=true); printf "Hashspace:=VectorSpace(GF,o); \n \n"; printf "Signspace:=VectorSpace(GF,n); \n \n"; printf "hashvalue:= Hashspace!(%o) ; \n \n", Eltseq(forgery); printf "signature:=Signspace!(%o) ; \n \n", Eltseq(signatureforg); UnsetOutputFile(); end if ;