Points: 134

Tags: crypto

Poll rating:

Writeups

ActionRatingAuthor team
5.0
the cr0wn
You need to authenticate and join a team to post writeups leanu – Dec. 31, 2018, 8:16 p.m.

Can please anyone explain how you solved it?
I found only 39 equations with 40 unknowns and with modulo and gave up :(

MyriaBreak – Jan. 1, 2019, 3:08 a.m.

me too... :(
Can please anyone explain how you solved it?

amirag – Jan. 1, 2019, 6:16 a.m.

I had an idea last night although i don't know if it's the answer (didn't try yet because i had a hard time with installing numpy).
i'm sorry if something is unclear, i don't tent to write in english a lot, especially not mathematical stuff.
(and didn't we have 40 equations ?)
we can enter the known challanges into a matrix, together with the response (mod p). this will allow us to use mod arithmetics with the cost of iterating later over 40 values of (response = n*p + r, while can't be more than 40*p - 40).
we can later use gaussian elimination and try to get a line in the matrix which looks like that:
t*A + 0 + 0 + ... + 0 | B
when A is our challnage, t is a coefficient for our challange that came from the elimination and B is a result that also came from the elimination.
we then calculate X such as (t*A)*X = B (mod p). p and (t*A) should still be coprime (p is 134 bits, i don't think the matrix gaussian elimination will add enough bits to contradict this)
X should be our part of the key (or, X + p*n but X can't be larger than p as X is only 124 bits)

take it with a grain of salt, it's the result of a sleepless night and lack of enough verifications

zhsh – Jan. 3, 2019, 4:13 a.m.

>>> (and didn't we have 40 equations ?)
No. One of the server's responses was 'ACCESS DENIED', so we could not add that equation to the system.

I tried to approach the problem from different angles, and then I simply put the 39 equations into Sage, and it found a solution for the system. Even though there are infinite number of other solutions modulo P, the solution found by Sage was exactly the one that I needed.