Hi Martin, I managed to circumvent the bug in the variety function for ideals for the GF(2) equation system generated by AES by using a sat solver. When generating an AES equation system over GF(2^e), I run into the same error using the variety function and was wondering if you knew any way around it?
Thanks again for the help, Sam On Thursday, July 15, 2021 at 6:19:12 PM UTC+1 Sam Ratcliffe wrote: > Hi Martin, > > Thank you for the assistance! I am in the process of performing repeated > experiments in which I extract the key bits from the ideal/Groebner basis, > so reading off the solutions by hand is not ideal for repeated usage or the > scenarios in which there are fewer equations than variables and I can't > directly extract the key bits without solving for other variables too. I > tried to extract the generators from the ideal and construct a polynomial > sequence to solve and extract the key bits. I have tried doing this using > the solve() function for linear equations, but I can't seem to find a way > to specify that the solutions I am looking for are within GF(2). > > Additionally, I have run into problems with the groebner_basis() function. > For SR(i,1,1,4) the function seems to work correctly for all values of i. > However, when I change the array size to even SR(2,2,2,4) the > groebner_basis() function won't compute the Groebner basis of the > polynomial system, it runs for a while, and aborts with an error message. I > run the following: > > sage: sr = mq.SR(2,2,2,4,gf2=True,polybori=True,allow_zero_inversions=True) > sage: R = sr.ring().base_ring() > sage: P = sr.vector([R.random_element() for _ in range(sr.r*sr.c*sr.e)]) > sage: K = sr.vector([R.random_element() for _ in range(sr.r*sr.c*sr.e)]) > sage: C = sr(P, K) > sage: F, s = sr.polynomial_system(P=P, C=C) > sage: G = F.groebner_basis() > > And receive the following error: > > terminate called after throwing an instance of 'polybori::PBoRiError' > what(): Built-in matrix-size exceeded! > --------------------------------------------------------------------------- > RuntimeError Traceback (most recent call last) > <ipython-input-10-9eabeb133a4e> in <module> > ----> 1 G = F.groebner_basis() > > /opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/rings/polynomial/multi_polynomial_sequence.py > > in groebner_basis(self, *args, **kwargs) > 534 [a, b, d] > 535 """ > --> 536 return self.ideal().groebner_basis(*args, **kwargs) > 537 > 538 def monomials(self): > > /opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/rings/polynomial/pbori/pbori.pyx > > in sage.rings.polynomial.pbori.pbori.BooleanPolynomialIdeal.groebner_basis > (build/cythonized/sage/rings/polynomial/pbori/pbori.cpp:42313)() > 5095 if "redsb" not in kwds: > 5096 kwds["redsb"]=True > -> 5097 sig_on() > 5098 gb = self._groebner_basis(**kwds) > 5099 sig_off() > > RuntimeError: Aborted > > Any help with getting past this would be appreciated. > > Thanks again, > > Sam > > On Friday, July 2, 2021 at 8:48:14 AM UTC+1 [email protected] wrote: > >> Thanks, Martin! >> >> > A workaround is to look at the linear equations directly and to extract >> a solution from it “by hand >> >> Oh, you mean he can directly look at the ideal and extract the solutions >> from there without having to compute the variety? >> >> For the particular SR(2,1,1,4) example the ideal would be >> >> sage: I >> Ideal (k200, k201, k202 + 1, k203, x200, x201 + 1, x202 + 1, x203, w200, >> w201 + 1, w202 + 1, w203 + 1, s100, s101, s102 + 1, s103 + 1, k100 + 1, >> k101 + 1, k102 + 1, k103, x100 + 1, x101 + 1, x102 + 1, x103 + 1, w100 + 1, >> w101, w102, w103, s000 + 1, s001 + 1, s002, s003, k000 + 1, k001, k002 + 1, >> k003) of Boolean PolynomialRing in k200, k201, k202, k203, x200, x201, >> x202, x203, w200, w201, w202, w203, s100, s101, s102, s103, k100, k101, >> k102, k103, x100, x101, x102, x103, w100, w101, w102, w103, s000, s001, >> s002, s003, k000, k001, k002, k003 >> >> The above are the linear equations you are referring to, right? >> >> Best, >> Vesselin >> >> On Friday, July 2, 2021 at 12:13:04 AM UTC+1 Martin Albrecht wrote: >> >>> Hi Vesselin, >>> >>> Sorry! Name-clash: Sage uses SR for the “Symbolic Ring” and we use >>> “mq.SR” for the small scale AES generator. This is what caused Dima’s >>> confusion, that’s all. >>> >>> A workaround is to look at the linear equations directly and to extract >>> a solution from it “by hand”, i.e. there’s a bug. >>> >>> Indeed, the bug is unrelated to PolyBoRi: >>> >>> sage: R = PolynomialRing(GF(2), 36, "x", order="lex") >>> sage: I = Ideal([R.random_element(degree=1, terms=20) for _ in >>> range(36)]) >>> sage: I.groebner_basis() # bombs out >>> RuntimeError: error in Singular function call 'groebner': >>> int overflow in hilb 1 >>> error occurred in or before standard.lib::stdhilb line 300: ` intvec hi >>> = hilb( Id[1],1,W );` >>> expected intvec-expression. type 'help intvec;' >>> leaving standard.lib::stdhilb (0) >>> >>> FWIW: >>> >>> sage: I.groebner_basis(algorithm="singular:std") # works as expected >>> >>> >>> Cheers, >>> Martin >>> >>> Vesselin Velichkov <[email protected]> writes: >>> > Hi Martin, >>> > >>> > Thank you for your reply! >>> > >>> > By "name clash" do you mean that both mq and BooleanPolynomialRing use >>> the >>> > same name i.e. "variety" for two different functions? >>> > >>> > Also, I didn't quite understand your solution -- the call to >>> > G.ideal().variety() from your first example still fails on my side >>> with the >>> > same overflow error. The call to I.variety() in the second example >>> succeeds >>> > though. >>> > >>> > Also, what do you mean by reading off the solution directly? How can >>> one do >>> > that? >>> > >>> > Thanks again! >>> > >>> > Best, >>> > Vesselin >>> > >>> > On Thursday, July 1, 2021 at 11:19:07 PM UTC+1 Martin Albrecht wrote: >>> > >>> >> Hi all, >>> >> >>> >> I think there’s a name clash here. mq.SR is a thing I wrote ages ago >>> for >>> >> producing systems of equations for small-scale variants of AES (not >>> the >>> >> symbolic ring). >>> >> >>> >> The problem comes from the variety() call and I think Sam did find a >>> bug: >>> >> >>> >> sage: sr = mq.SR(2,1,1,4, gf2=True, polybori=True, >>> >> allow_zero_inversions=True) >>> >> sage: P = sr.vector([0, 0, 1, 0]) >>> >> sage: C = sr.vector([1, 0, 0, 0]) >>> >> sage: F,s = sr.polynomial_system(P=P, C=C) >>> >> sage: G = F.groebner_basis() # this succeeds >>> >> sage: G.ideal().variety() >>> >> >>> >> More directly: >>> >> >>> >> sage: B = BooleanPolynomialRing(36, "x") >>> >> sage: I = Ideal([B.random_element(degree=1) for _ in range(36)]) >>> >> sage: I.variety() >>> >> >>> >> RuntimeError: error in Singular function call 'groebner': >>> >> int overflow in hilb 1 >>> >> error occurred in or before standard.lib::stdhilb line 300: ` intvec >>> hi = >>> >> hilb( Id[1],1,W );` >>> >> expected intvec-expression. type 'help intvec;' >>> >> leaving standard.lib::stdhilb (0) >>> >> leaving standard.lib::groebner (1104) >>> >> >>> >> @Sam: as a workaround, you can “read off” the solution directly. >>> >> >>> >> Cheers, >>> >> Martin >>> >> >>> >> Dima Pasechnik <[email protected]> writes: >>> >> > Don't do Groebner bases over SR, use a proper polynomial ring. >>> >> > >>> >> > On Thu, Jul 1, 2021 at 4:56 PM Sam Ratcliffe >>> >> > <[email protected]> wrote: >>> >> >> >>> >> >> I am using the SageMath implementation of SR and wish to recover >>> all >>> >> solutions to a polynomial system using the variety function for >>> ideals as >>> >> specified here: >>> >> >>> https://doc.sagemath.org/html/en/reference/cryptography/sage/crypto/mq/sr.html >>> >>> >> >> >>> >> >> When I run the following (as available on the above link): >>> >> >> >>> >> >> sage: sr = mq.SR(1,1,1,4, gf2=True, polybori=True) >>> >> >> sage: K = sr.base_ring() >>> >> >> sage: a = K.gen() >>> >> >> sage: K = [a] >>> >> >> sage: P = [1] >>> >> >> sage: F,s = sr.polynomial_system(P=P, K=K) >>> >> >> sage: I = F.ideal() >>> >> >> sage: for V in I.variety(): >>> >> >> ....: for k,v in sorted(V.items()): ....: print("{} {}".format(k, >>> v)) >>> >> ....: print("\n") >>> >> >> >>> >> >> -- >>> >> >> You received this message because you are subscribed to the Google >>> >> Groups "sage-support" group. >>> >> >> To unsubscribe from this group and stop receiving emails from it, >>> send >>> >> an email to [email protected]. >>> >> >> To view this discussion on the web visit >>> >> >>> https://groups.google.com/d/msgid/sage-support/535596c4-8138-4894-b7c0-13293904ee30n%40googlegroups.com >>> >>> >> . >>> >> >>> >> >>> >> -- >>> >> >>> >> _pgp: https://keybase.io/martinralbrecht >>> >> _www: https://malb.io >>> >> _prn: he/him or they/them >>> >> >>> >> >>> >>> >>> -- >>> >>> _pgp: https://keybase.io/martinralbrecht >>> _www: https://malb.io >>> _prn: he/him or they/them >>> >>> -- You received this message because you are subscribed to the Google Groups "sage-support" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/sage-support/f9f1d60f-6a25-4282-9e57-0cc0372bc4f5n%40googlegroups.com.
