Forum

Correct equations  

  By: Theofanidis on Oct. 7, 2012, 7:43 p.m.

Dear Viktor,
Thanks a lot

I will focus to rewrite these two equations again from the start, using the extra file you attached

I actually was using the original file given at the forum, after i have replaced the _ symbol and . with * as you suggested

Best regards
George

Re: Challenge  

  By: Veselovský on Oct. 7, 2012, 8:15 p.m.

You can obtain equations form the file I sent easily. All can be done by computer.
Read the whole file as a text string and then split it at comas ",".
You will get 13 separate strings. Each string then represents one equation (polynomial).
Then simply convert the string into expression in software you use.

I hope you have not spent a lot of time solving the wrong system of equations ;-)

On more try with new format equations  

  By: Theofanidis on Oct. 8, 2012, 8:27 a.m.

Hello again

I will use only the equations from the file you provided

From a first look the contents of your file differs from the contents of the file provided at the challenge, or just the terms are positioned in a different way ?

Since yesterday i rewritten the equations from the file of the challenge regarding Vec 4 and 6 but the results were the same

If i have something else i will contact you again

Thanks again a lot
Best regards
George

Re: On more try with new format equations  

  By: Veselovský on Oct. 8, 2012, 10:11 a.m.

From a first look the contents of your file differs from the contents of the file provided at the challenge, or just the terms are positioned in a different way ?

Yes, terms of polynomials are ordered differently in my file. It is like writing x^2+2x+1 as 1+2x+x^2, which has no effect on the value of polynomial of course.

Problem with equations remains - result OK ?  

  By: Theofanidis on Oct. 8, 2012, 11:36 a.m.

Hello again
I just finished replacing my "old" equations with the ones provided in your file
When i have x as
[1,12,11,3,4,16,15,6,7,9,5,10,14,2,7,11,9,3,6,0,4,1,16,5,15,12,2,7,3,7,6,13,3,14,4,11,16,8,10]
i still have as result
[387848,408608,397792,795326,369892,745224,398088,390785,388085,409469,376453,394883,396031]
and in mod 17 as
[10,13,9,15,6,12,16,6,9,7,5,7,16]
instead of
[10,13,9,6,6,6,16,6,9,7,5,7,16] - which you provided
Are you absolutely sure that your result is correct ?
Also when i have x as
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,0,1,2]
i have as result
[392724,414971,394476,783765,395934,777882,419535,376062,412306,394672,397176,386288,391596]
and in mod 17 as
[7,1,8,14,4,13,9,5,5,0,5,14,1]

I believe that the equations were and are correct. The program just sums up the terms of each equation and provides this sum as mod 17 for every equation

Thanks again for your effort and persistence
Best regards
George

Re: Challenge  

  By: jomandi on Oct. 8, 2012, 12:54 p.m.

@theofanidis

in your results (without reduction modulo 17) the 4th and the 6th value are in both examples approximately 2 times the value, that it should be. maybe you copy and paste or calculate something twice there.

the correct values:

[1,12,11,3,4,16,15,6,7,9,5,10,14,2,7,11,9,3,6,0,4,1,16,5,15,12,2,7,3,7,6,13,3,14,4,11,16,8,10]
->[10,13,9,6,6,6,16,6,9,7,5,7,16]
(=[387848,408608,397792,397534,369892,375332,398088,390785,388085,409469,376453,394883,396031] mod 17)

[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,0,1,2]
->[7,1,8,6,4,9,9,5,5,0,5,14,1]
(=[392724,414971,394476,389289,395934,381948,419535,376062,412306,394672,397176,386288,391596] mod 17)

here are some further examples to test your equations:

[6,3,15,9,9,7,2,7,6,0,11,14,9,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,0,1,2,3,4,5,6,7,8,9]
->[1,1,1,1,1,1,1,1,1,1,1,1,1]
(=[332334,319125,330702,325568,323715,299354,317578,303961,321845,330668,321301,328917,327727] mod 17)

[15,10,13,11,10,16,6,10,11,14,6,13,15,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,0,1,2,3,4,5,6,7,8,9]
->[16,16,16,16,16,16,16,16,16,16,16,16,16]
(=[462688,451655,462773,449292,455480,428314,444294,440605,452777,457061,454868,449122,464218] mod 17)

[13,8,9,0,8,5,5,2,16,10,7,9,15,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
->[1,2,3,4,5,6,7,8,9,10,11,12,13]
(=[81193,71980,71794,75705,74074,79770,80723,74332,77036,72124,81067,74880,76326] mod 17)

best regards,
jomandi

Re: Challenge  

  By: Bart13 on Jan. 27, 2013, 8:28 p.m.

What is the correct format for the solution?
I'm pretty sure I've got a valid signature but it keeps getting rejected.

Re: Challenge  

  By: jomandi on Jan. 27, 2013, 9:19 p.m.

the format should be like in the following example:

[13,8,9,0,8,5,5,2,16,10,7,9,15,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]

if you want, then you can send me a pm with your solution and i will check it.

best regards,
jomandi

Re: Challenge  

  By: Bart13 on Jan. 27, 2013, 9:59 p.m.

@ jomandi:

thanks for the offer.
I've send you a pm.

Re: Challenge  

  By: jomandi on Jan. 27, 2013, 10:50 p.m.

the challenge is to calculate the following signature:
f1(x1,..,x39) = 4 mod 17
f2(x1,..,x39) =12 mod 17
.
.
f13(x1,..,x39)=10 mod 17

when you take the first equation and bring the right side to the left one, then you get:
0=f1(x1,..,x39)-4=f1(x1,..,x39)+13 mod 17.

when you define a new function
g1(x1,..,x39):=f1(x1,..,x39)+13 mod 17, then the following equation must be filfilled:

g1(x1,..,x39)=0 mod 17

analogously for the remaining 12 functions.
g2(x1,..,x39) :=f2(x1,..,x39) +5 mod 17
.
.
g13(x1,..,x39):=f13(x1,..,x39)+7 mod 17

you have now the following system of equations:

g1(x1,..,x39) =0 mod 17
g2(x1,..,x39) =0 mod 17
.
.
g13(x1,..,x39)=0 mod 17

and this g1,..,g13 are exactly the vectors in the additional challenge file. when you solve this system of equations, you will get the correct solution.

what i have explained here is, what the following note in the challenge means:

Note: The equations are given in polynomial format, i.e. they are implicitly equal to zero.

@Bart13: you solved the following system of equations:

g1(x1,..,x39) = 4 mod 17
g2(x1,..,x39) =12 mod 17
.
.
g13(x1,..,x39)=10 mod 17

i hope this helps.

best regards,
jomandi

Re: Challenge  

  By: Bart13 on Jan. 27, 2013, 11:12 p.m.

i hope this helps.

best regards,
jomandi

Yes it did, thank you!

Stupid of me to do all the hard (and difficult) work to write a fast program and than to overlook the fact that the given equations already had the values for the message in them.

Took me only 9 seconds to get a correct signature.

Re: Challenge  

  By: Integral on Feb. 19, 2014, 1:33 p.m.

Hi All,

Do I have to calculate the Groebner basis of the Ideal generated by (for example) the 13 multivariate quadratic polynomials in the first 13 variables X_1 to x_13 over Z/Z17? (assuming variables x_14 to x_39 are all =0) ?

If yes, this looks pretty hard… I've downloaded Mathematica and Sage.
The first one ran for 3 days without issuing any result.
The second one is still running.
I'm using WIndows7, which makes things even more (boringly) complex…

If no, can any of the solvers of this challenge give me a hint about what I'm missing ?

Many thanks in advance,
Integral

Re: Challenge  

  By: mir0soft on May 16, 2017, 4:20 p.m.

Hi All,

Do I have to calculate the Groebner basis of the Ideal generated by (for example) the 13 multivariate quadratic polynomials in the first 13 variables X_1 to x_13 over Z/Z17? (assuming variables x_14 to x_39 are all =0) ?

If yes, this looks pretty hard… I've downloaded Mathematica and Sage.
The first one ran for 3 days without issuing any result.
The second one is still running.
I'm using WIndows7, which makes things even more (boringly) complex…

If no, can any of the solvers of this challenge give me a hint about what I'm missing ?

Many thanks in advance,
Integral

I saw you have tried to find the Groebner basis (and that you have already solved the challenge).

Just as update -> I have calculated the Groebner basis for the ideal generated by the 13 multivariate quadratic polynomials in the first 13 variables x1 to x13 over GF(17). It took me few hours and the result is 2708 equations. Saving the result took me another several minutes and the size is frightening -> 331 MB.

Inspecting the results further didn't give me some easy strategy to continue.
For example, the last equation (using lexicographical order) is:

x3x5 - 2x4x5 + x5^2 - 6x1x6 + x2x6 + 2x3x6 + 5x4x6 - 4x5x6 + 4x6^2 + 4x1x7 - 5x2x7 + 4x3x7 - 4x4x7 - x5x7 + 6x6x7 + x7^2 - 8x1x8 - 4x2x8 + 5x3x8 - 8x4x8 + 3x5x8 - 6x6x8 + 8x7x8 + 3x8^2 + 5x1x9 - 7x2x9 - 6x3x9 + 7x4x9 - 2x5x9 + x6x9 - 4x7x9 + 5x8x9 - x9^2 - x1x10 - 2x2x10 + 4x3x10 - 4x4x10 - 8x5x10 + x6x10 + 6x7x10 + 3x8x10 + 5x9x10 - 6x10^2 + 4x1x11 - 3x2x11 - 2x3x11 + 2x4x11 - 6x5x11 + 4x6x11 + x7x11 - 4x8x11 + x9x11 + 8x10x11 + x11^2 - 8x1x12 - 5x2x12 - 6x3x12 + 3x4x12 - 7x5x12 + 4x6x12 + 4x7x12 - 2x8x12 + 4x9x12 + 5x11x12 + 7x12^2 - x1x13 + 6x2x13 - 4x3x13 - 7x4x13 - 3x5x13 + 6x6x13 - 6x7x13 + 7x8x13 + 5x9x13 + 8x10x13 + 2x11x13 - x12x13 - 6x13^2 + 3x1 - 2x2 + 4x3 - 5x4 + x5 + 4x7 + 5x8 - 5x9 + 5x10 + 6x11 - x12 - 2*x13 + 5

Re: Challenge  

  By: admin on June 5, 2017, 4:08 p.m.

Hello crypto contestants.

The verification program of this challenge had a problem.
We fixed this now.

If you have sent in a correct solution before which was rejected and if we didn't award the point now, please send in your solution again.

Thanks for your feedback and cooperation.

Kind regards


Currently 29 guests and 0 members are online.
Powered by the CrypTool project
Contact | Privacy | Imprint
© 2009-2024 MysteryTwister team