2 minute read

Shamir’s Conundrum

Challenge description: shAmir haS been Clumsy and lost hIs keys! can you help fInd them?

An overview

This was a medium difficulty crypto challenge called “Shamir’s Conundrum” that I created for my annual university society capture the flag event. Below is the solution to the challenge.

Finding the coordinates

The challange .zip file comes with three image files. Using exiftool on each image reveals a strange string hidden in the description of each image. An example can be seen below:

Utilising the coordinates

As hinted to by the name of the challenge, these coordinates should be used with Shamir’s Secret Sharing algorithm to produce a secret. I decided to keep this nice and easy and require only three shares. This happens to also be the same number of shares used in the example on the wiki page for the algorithm which can easily followed to get the secret.

The Lagrange interpolating polynomial

We now need to construct a Lagrange interpolating polynomial utilising the 3 coordinates we have obtained. This will give us the original polynomial equation used to contruct the 3 coordinates and then in-turn the y-intercept value (which is the secret we need to find).

We can construct this equation in two ways. The hard way, and the easy way.

The easy way involves utilising the following dcode page and entering the three coordinates on there.

The harder way is calculating the equation manually. I have done this using some code which can be seen below. The equation used is the same one explained on the wiki page

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

    from sympy import *

    x = Symbol("x")

    x1 = 1
    x2 = 2
    x3 = 3
    y1 = 187487937770258527551376584174027344358336404665303440177725298190123934275010313915513125371501489849562109571712718047613539978670520799378269649188525301
    y2 = 467858610866537168606071610585075020104991321611140736516388291862404375663659724892519233968463792992572939096647046086618639519188795825950395113421984939
    y3 = 914112129288951924134086149234153032240016750960512249017028987416852224214948346931968330690898409524032606575312985257016508631054924080196381192776379039

    l1 = ((x-x2) / (x1-x2)) * ((x-x3) / (x1-x3))
    l2 = ((x-x1) / (x2-x1)) * ((x-x3) / (x2-x3))
    l3 = ((x-x1) / (x3-x1)) * ((x-x2) / (x3-x2))

    equation = (l1*y1) + (l2*y2) + (l3*y3)

    print(expand(equation))

The print statement at the end outputs the following, where the last element is the secret:

82941422663068057236659756119015168194185256201767108080988850941083703581319605531221494062736156694224418976865805565696384785673926613836930307560467231*x**2 + 31546405107074469344715758054002171164099148340535972095696440849029330644690594383341626408753833060337572594336911341915945183496495185061334541552057945*x + 73000110000116000970001070001010005000052000123000360001040006400010900049000114000950004900011500095000118000510001140001210009500099000480004800076000125

Getting the flag

Now that we have the secret, all we have to do is find the flag. You may notice a repeating pattern of 0’s in the secret. Utilising the hint in the challenge description (the capital letters), we know to look out for some ASCII code. We know the flag will start with Intake24{, so I in ASCII is 73, n is 110, t is 116, etc. If we look at the start of the secret we can see 73, 110 and 116 which are all seperated by three 0’s exactly. Replacing every three occurances of 0 with a space would then give us an easy to read sequence of ASCII code:

73 11 0116 97 107 101 5 052 123 36 104 64 109 49 114 95 49 115 95 118 51 114 121 95 99 48 48 76 125

This still needs a bit of manual cleanup:

73 110 116 97 107 101 50 52 123 36 104 64 109 49 114 95 49 115 95 118 51 114 121 95 99 48 48 76 125

Decoding this from decimal (I used cyberchef) gives us the flag:

Intake24{$h@m1r_1s_v3ry_c00L}