////  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 ;