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 ;