// ========================================= // Key Generation of (Projected) SFLASH // The program generates a random (P)FLASH key pair // and stores the public key in public_key.txt and the private key in private_key.txt // ================================================= function squareandmultiply(m,e,p) // for fast exponentiation e:=Intseq(e,2); s:=# e; // bitlength of 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; // parameters q:=4; n:=5; // # variables a:=2; // # Minus Equations s:=1; // # projected variables m:=n-a; // # equations theta:=2; g,thetainv,_:=XGCD(q^theta+1, q^n-1); // exponent for decryption thetainv:= thetainv mod (q^n-1) ; if g gt 1 then printf"FEHLER!!! Falsches theta"; end if; F:=GaloisField(q); Vectn:=VectorSpace(F,n); Vectm:=VectorSpace(F,m); Pol<[x]>:=PolynomialRing(F,n); Poly:=PolynomialRing(Pol); Poll<[y]>:=PolynomialRing(Pol,n); irrpol:=Poly!(IrreduciblePolynomial(F,n)); FIELDEQ:=[]; // field equations over ground field for i:=1 to n do FIELDEQ:=FIELDEQ cat [x[i]^q-x[i]]; end for; FIELDIdeal:=Ideal(FIELDEQ); // affine map T ---------------------------------------------------------------- repeat MT:=RandomMatrix(F,n,n); until IsInvertible(MT) eq true; cT:=Random(Vectn); T:=[]; for i:=1 to n do T[i]:=cT[i]+MT[i][1]*Pol.1; for j:= 2 to n do T[i]:=T[i]+MT[i][j]*Pol.j; end for; end for; // ---------------------------------------------------------------------------- //----------------affine map S ---------------------------------------------- repeat MSF:=RandomMatrix(F,m,n); until Rank(MSF) eq m; MS:=Matrix(Pol,m,n,ChangeUniverse(Eltseq(MSF),Pol)); cSF:=RandomMatrix(F,m,1); cS:=Matrix(Pol,m,1,ChangeUniverse(Eltseq(cSF),Pol)); // ----------------------------------------------------------------------- MIA:=0; // lift to the extension field for i:=1 to n do MIA:=MIA+T[i]*X^(n-i); end for; MIB:=squareandmultiply(MIA,q^theta+1,irrpol) mod irrpol; p:=[]; // move down to the vector space for i:=1 to n do p[i]:=MonomialCoefficient(MIB,X^(n-i)); end for; for i:=1 to n do // reduce modulo field equations p[i]:=NormalForm(p[i],FIELDIdeal); end for; MIB:=Pol!0; for i:=1 to n do MIB:=MIB+p[i]*X^(i-1); end for; P:=ZeroMatrix(Pol,n,1); for i:=1 to n do P[i][1]:=p[i]; end for; Pk:=Eltseq(MS*P+cS); // Compute public key // Projection ---------------------------- for i:=1 to m do for j:=n-s+1 to n do Pk[i]:= Evaluate(Pk[i],x[j],F!0); end for; end for; // --------------------------------------------- // Output =========================================== printf "************************************************ \n"; printf "*** SFLASH Signature Scheme - Key Generation *** \n"; printf "************************************************ \n \n"; printf "q:= %o \n \n", q; printf "n:= %o \n \n", n; printf "Minus:= %o \n \n", a; printf "Projection:= %o \n \n", s; printf "irrpol:= %o \n \n", irrpol; printf "theta:= %o \n \n", theta; printf "thetainv:= %o \n \n", thetainv; printf "S:= \n%o \n \n", MS; printf "cS:= %o \n \n", VectorSpace(F,m)!Eltseq(cS); printf "T:= \n%o \n \n", MT; printf "cT:= %o \n \n", cT; printf "MIA:= %o \n \n", MIA; printf "MIB:= \n%o \n \n", MIB; printf "pk:= \n%o \n \n", Pk; printf"Write public_key.txt \n \n"; SetOutputFile("public_key.txt":Overwrite:=true); printf "q:= %o ; \n \n", q; printf "n:= %o ; \n \n", n; printf "a:= %o ; \n \n", a; printf "s:= %o ; \n \n", s; printf "F:=GaloisField(q); \n \n"; printf "Pol<[x]>:=PolynomialRing(F,n); \n \n"; printf "Pk:= %o ; \n \n",Pk; ; UnsetOutputFile(); printf"Write private_key.txt \n \n"; SetOutputFile("private_key.txt":Overwrite:=true); printf "q:= %o ; \n \n", q; printf "n:= %o ; \n \n", n; printf "a:= %o ; \n \n", a; printf "s:= %o ; \n \n", s; printf "F:=GaloisField(q); \n \n"; printf "Pol<[x]>:=PolynomialRing(F,n); \n \n"; printf "P:=PolynomialRing(F); \n \n"; printf "thetainv:= %o ;\n \n", thetainv; printf "irrpol:= %o ; \n \n", irrpol; printf "MT:= %o ; \n \n", Eltseq(MT); printf "cT:= %o ; \n \n", Eltseq(cT); printf "MS:= \n%o ; \n \n", Eltseq(MS); printf "cS:= \n%o ; \n \n", Eltseq(cS); UnsetOutputFile();