//// Oil and Vinegar balanced odd characteristic //// forge a signature using public key only //// write to file signature.txt just like program sign does //// then use verify.txt to see if signature is accepted clear ; print GetSeed() ; load "public_key.txt" ; if IsEven(q) then printf "q=%o is even need to load file forge_even\n",q; else // creating a forgery forgery := [Random(GF): i in [1..o]]; // forgery to be signed // generate matrices from public key QB:=[]; for k in [1..o] do QB[k] := ZeroMatrix(GF,n,n) ; for i in [1..n] do QB[k][i,i]:= MonomialCoefficient(Pk[k],x[i]^2); for j in [i+1..n] do QB[k][i][j]:=MonomialCoefficient(Pk[k],x[i]*x[j])/2 ; QB[k][j][i]:= QB[k][i][j] ; end for ; end for ; end for ; a := [] ; success := false ; tries := 0 ; // try to find a matrix, whose charateristic polynomial has an // irreducible polynomial of degree v repeat tries +:= 1 ; // generate matrices in QB repeat a[1] := Random(GF) ; W1 := a[1]* QB[1] ; for i in [2..o] do a[i] := Random(GF) ; W1 +:= a[i]* QB[i] ; end for ; until Determinant(W1) ne 0 ; print "Linear Combinations for W1= ",a ; repeat a[1] := Random(GF) ; W2 := a[1]* QB[1] ; for i in [2..o] do a[i] := Random(GF) ; W2 +:= a[i]* QB[i] ; end for ; until Determinant(W2) ne 0 ; print "Linear Combinations for W2= ",a ; success := true ; W12 := W1^(-1) * W2 ; f10 :=CharacteristicPolynomial(W12); f12 := Factorization( f10 ) ; print "Characteristic Polyomial of W12 in factored form" ; print f12 ; if (f12[1][2] eq 2) then c1 := f12[1][1] ; for j in [2..#f12] do if ( f12[j][2] eq 2 ) then c1 *:= f12[j][1] ; else success := false ; end if ; end for ; else success := false ; end if ; // look for irreducible factors only //if (Degree(f12[1][1]) ne v ) then // success := false ; //end if ; until (success ) or (tries gt 100) ; // find eigenspace of c1(w12) print "Found big enough eigenspace:",success ; W := W12 ; c := Coefficients(c1) ; e1 := c[1] * IdentityMatrix(GF,n) +c[2]* W12 ; for i in [3..v+1] do W := W*W12 ; e1 +:= c[i]*W ; end for ; n1 := NullSpace( Transpose( e1 ) ); if Rank(n1) ne v then print "Did not get full rank for n1"; end if ; n11 := ExtendBasis( n1, VectorSpace(GF,n) ) ; m11 := Matrix(GF,n,n,n11) ; // change basis with m11 Q1new :=[] ; for k in [1..o] do Q1new[k] := m11 *QB[k] *Transpose( m11) ; end for ; forgery := [Random(GF): i in [1..o]]; // forgery to be signed fnew := [] ; for k in [1..o] do temp := P!0 ; for i in [1..n] do for j in [1..n] do temp +:= Q1new[k][i][j] * x[i]*x[j] ; end for ; end for ; fnew[k] := temp ; end for ; repeat vinegar := [Random(GF): i in [1..v]] ; // Evaluate private functions fnew ov:=[x[i]:i in [1..o]] cat vinegar ; z1:=[] ; M := ZeroMatrix( GF, o, o ) ; z00 := [GF!0: i in [1..n]] ; z10 := []; for k in [1..o] do z1[k]:=Evaluate( fnew[k], ov ) ; for i in [1..o] do M[i,k] := Coefficient( z1[k], x[i], 1 ) ; end for ; z10[k] := forgery[k] - Evaluate( z1[k], z00 ); end for ; until Rank(M) eq o ; w := Vector(GF, z10) ; oil := Solution( M,w ) ; oilvin :=Vector(GF,n,[GF!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 ; signatureforg := oilvin * m11 ; /////////////// 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 ;