100 Degrees - UmassCTF2024
Reto Miscelánea basado en la construcción del Polinomio Interpolador de Lagrange.
Autor del reto: unknown
Dificultad: Fácil
Enunciado
“Mr. Krabs has been tinkering with the restaurant thermometer to see what makes his staff the most productive. He’s been tracking the data in his journal, but some “Lagrange” guy just called saying Mr. Krabs already has all the info he needs. Can you help Mr. Krabs predict how his staff will fare?”
Archivos
En este reto solo tenemos el siguiente archivo.
journal.txt: Contiene los puntos x e y.
Archivos utilizados aquí.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
```
p = 137
DAY(0) = 81
DAY(1) = 67
DAY(2) = 110
DAY(3) = 116
DAY(4) = 49
DAY(5) = 111
DAY(6) = 74
DAY(7) = 53
DAY(8) = 93
DAY(9) = 83
DAY(10) = 55
DAY(11) = 122
DAY(12) = 67
DAY(13) = 47
DAY(14) = 85
(...)
```
Analizando el código
En este ejercicio nos dan dos pares de valores, uno correspondiente al número del día y el otro par al resultado que hizo ese dia junto con valores desconocidos desde el día 101 al día 132 los cuales se corresponde con la flag en ASCII.
Solución
Nuestra misión será calcular dichos puntos desconocidos haciendo uso de la Interpolación Polinómica de Lagrange aplicado a campo finito p ya que estamos trabajando con módulos y necesitamos calcular los valores discretos desconocidos.
De forma sencilla, el Polinomio de Lagrange es un análisis numérico que se usa para interpolar datos. La interpolación se basa en estimar valores entre los datos ya conocidos, proporcionando una forma de encontrar un polinomio que pase exactamente a través de ellos y además poder predecir los puntos adyacentes.
Para comenzar, hablando en términos del Polinomio de Lagrange, mientras más puntos del polinomio a extrapolar conozcamos, más exactas serán nuestras aproximaciones para los valores próximos a calcular. A medida que nos alejamos del último punto conocido, la interpolación será menos precisa. Sin embargo, en este caso, como estamos aplicando Lagrange en un campo finito y contamos con valores próximos, no encontraremos problemas en el proceso.
Para abordar el problema, simplemente lo que haremos será una función que se encargue de recorrer todos los datos que conocemos, calcule el término correspondiente a dicho dato y por último sume todos los términos para obtener el valor interpolado en el punto x.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def lagrange_polynomial_finite_field(x, days, values, p):
result = 0
for j in range(len(values)):
term = values[j]
for k in range(len(values)):
if k != j:
term *= (x - days[k]) * pow((days[j] - days[k]) % p, -1, p)
term %= p
result += term
result %= p
return result
days = list(range(101))
values = [
81, 67, 110, 116, 49, 111, 74, 53, 93, 83, 55, 122, 67, 47, 85, 91, 88, 84, 63, 96,
59, 87, 46, 99, 93, 126, 62, 65, 76, 55, 48, 116, 79, 106, 45, 54, 102, 100, 65, 93,
122, 84, 118, 64, 103, 76, 65, 109, 90, 99, 69, 50, 64, 61, 115, 111, 64, 80, 60, 68,
105, 113, 84, 119, 55, 77, 124, 55, 115, 21, 112, 41, 88, 136, 66, 43, 48, 55, 60, 41,
43, 103, 118, 19, 99, 34, 118, 73, 97, 74, 7, 78, 60, 48, 123, 125, 119, 0, 36, 123, 22
]
p = 137
valores_predichos = []
for dia_predicho in range(101, 133):
valor_predicho = lagrange_polynomial_finite_field(dia_predicho, days, values, p)
valores_predichos.append(valor_predicho)
interpole = ""
for dia, valor in zip(range(101, 133), valores_predichos):
print("Valor aproximado para DAY({}) en el campo finito es: {}".format(dia, valor))
interpole += chr(valor)
print(interpole)
Básicamente definimos la función lagrange_polynomial_finite_field que toma un valor $x$ para interpolar, una lista de días (days), una lista de valores correspondientes (values) y un primo (p) que define el campo finito.
Dicha función utiliza la fórmula del polinomio de Lagrange para calcular el valor interpolado para el valor $x$ a calcular, dichos valores estarán entre el 101 y 132.
Por último, recopilamos dichos valores obtenidos en la función y los transformamos en caracteres ASCII para ver la flag.
NOTA
He encontrado otra solución más sencilla que utiliza sagemath.
1
2
3
4
5
6
7
F = GF(137)
points = [(0, 81), (1, 67), (2, 110), (3, 116), (4, 49), (5, 111), (6, 74), (7, 53), (8, 93), (9, 83), (10, 55), (11, 122), (12, 67), (13, 47), (14, 85), (15, 91), (16, 88), (17, 84), (18, 63), (19, 96), (20, 59), (21, 87), (22, 46), (23, 99), (24, 93), (25, 126), (26, 62), (27, 65), (28, 76), (29, 55), (30, 48), (31, 116), (32, 79), (33, 106), (34, 45), (35, 54), (36, 102), (37, 100), (38, 65), (39, 93), (40, 122), (41, 84), (42, 118), (43, 64), (44, 103), (45, 76), (46, 65), (47, 109), (48, 90), (49, 99), (50, 69), (51, 50), (52, 64), (53, 61), (54, 115), (55, 111), (56, 64), (57, 80), (58, 60), (59, 68), (60, 105), (61, 113), (62, 84), (63, 119), (64, 55), (65, 77), (66, 124), (67, 55), (68, 115), (69, 21), (70, 112), (71, 41), (72, 88), (73, 136), (74, 66), (75, 43), (76, 48), (77, 55), (78, 60), (79, 41), (80, 43), (81, 103), (82, 118), (83, 19), (84, 99), (85, 34), (86, 118), (87, 73), (88, 97), (89, 74), (90, 7), (91, 78), (92, 60), (93, 48), (94, 123), (95, 125), (96, 119), (97, 0), (98, 36), (99, 123), (100, 22)]
R = F['x']
print(R.lagrange_polynomial(points))
h = R.lagrange_polynomial(points)
for i in range(101,133):
print(h(i))
Flag
UMASS{1nt3rpr3t_n0r_1nt3rp0l@t3}