//============================================ // Signature Generation of (projected) SFLASH // the program reads in the private key from private_key.txt // and generates a signature for a randomly chosen message // message and signature are stored in message.txt //============================================== function squareandmultiply(m,e,p) // for efficient exponentiation e:=Intseq(e,2); s:=# e; erg:=1; for i:=1 to s do if e[i] eq 1 then erg:=erg *m mod p; end if; m:=m^2 mod p; end for; return erg; end function; printf "****************************************************** \n"; printf "*** SFLASH Signature Scheme - Signature Generation *** \n"; printf "****************************************************** \n \n"; load "private_key.txt"; Vn:=VectorSpace(F,n); Poly:=PolynomialRing(F); hashspace:=VectorSpace(F,n-a); hash:=Random(hashspace); printf"Generate Signature for the message %o \n \n", hash; MS:=Matrix(F,n-a,n,MS); // read in private key MT:=Matrix(F,n,n,MT); cS:=Matrix(F,n-a,1,cS); cT:=Matrix(F,n,1,cT); repeat // ------------------------------------------------------------------------------------------------------------ //find pre image of hash under S _,x,kernel:=IsConsistent(Transpose(MS), hash - hashspace!Eltseq(cS)); x:=Eltseq(x+Random(kernel)); //central map MIB:=0; // lift to the extension field for i:=1 to n do MIB:=MIB+x[i]*X^(n-i); end for; MIA:=squareandmultiply(MIB,thetainv,irrpol); // invert central MI map y:=[]; // move the result to the vector space for i:=1 to n do y[i]:=MonomialCoefficient(MIA,X^(n-i)); end for; // map T _,signature,kernel:=IsConsistent(Transpose(MT), Vn!(y) - Vn!Eltseq(cT)); signature:=Eltseq(signature); tr:=true; // test if the last s components of signature are 0 for i:=n-s+1 to n do if signature[i] ne 0 then tr:=false; end if; end for; printf"S^-1 (message):= %o \n \n", x; printf"MIB:= %o \n \n", MIB; printf"MIA:= %o \n \n", MIA; printf"T (signature):= %o \n \n", y; printf"signature := %o \n \n", signature; if tr eq false then printf" Projection fails. Choose other preimage. \n \n -------------------------- \n \n"; end if; until tr ; //------------------------------------------------------------------------------------ for i:=1 to s do // remove the last s elements from signature Prune(~signature); end for; if s gt 0 then printf "\n ------------------ \n \n signature:= %o \n", signature; end if; printf "Write signature.txt \n \n"; SetOutputFile("signature.txt":Overwrite:=true); printf "hashspace:=VectorSpace(F,n-a); \n \n"; printf "signspace:=VectorSpace(F,n-s); \n \n"; printf "hash:= hashspace!(%o) ; \n \n", Eltseq(hash); printf "signature:= signspace!(%o); \n \n", Eltseq(signature); UnsetOutputFile();