ASIS Quals 2017 – DLP – 158 points

Posted on by bomotodo

Description:

You should solve a DLP challenge, but how? Of course , you don’t expect us to give you a regular and boring DLP problem!

nc 146.185.143.84 28416

Untitled

Here is the [C]ryptography function

As we can see, that fuction random n and s then compute:

enc\equiv (n+1)^{msg}\; mod\;n^{s+1}

We have:

(a+1)^{2}=a^{2}+2a+1

(a+1)^{3}=a^{3}+3a^{2}+3a+1=(a+3)*a^{2}+3a+1

(a+1)^{4}=a^{4}+4a^{3}+6a^{2}+4{a}+1=(a^{2}+4a+6)*a^{2}+4a+1

Take a look at the Pascal’s triangle:

Untitled

We can easily realize that :

(a+1)^{n}=X*a^{2}+n*a+1

We don’t care whatever the value of X is. We compute:

(a+1)^{n}\equiv a*n + 1\;mod\; n^{2}

 Then, if we have (a+1)^{n} we can compute n efficiently, luckily we already had (a+1)^{n}\;mod\;n^{s+1} with s+1 > 2

Now we compute n:

enc\equiv (n+1)^{msg}\; mod\;n^{s+1}

enc\equiv (n+1)*msg+1\; mod \;n^{2}

where (n+1)*msg+1 is smaller than n^{2} then:

msg=\frac{enc\%n^{2}-1}{n}

I got the numbers like that

Untitled.png

then compute:

Untitled

I wonder if it was an easy challange or i solved it with a different method. I joked with my friend that was a “paper with one line of code challenge” 😀 😀

Bình luận về bài viết này