Hace unos años, ¡ostras, 12 años ya!, me lie la manta a la cabeza resolviendo este crackme mediante fuerza bruta. Reconozco que tengo cierta debilidad por él, tanto es así, que me he decidido a darle una vuelta de tuerca para darle el contexto matemático que esta maravilla de crackme se merece.
Recordemos las restricciones:
\begin{cases}
&x_1 \cdot x_2 \neq 0\\
&x_1 \neq x_2\\
&1 < x_1 < 10^{10}\\
&1 < x_2 < 10^{10}\\
&\left\lfloor 10^{16} \cdot \sin(x_1)\cdot \sin(x_2) \right\rfloor = 0
\end{cases}La alternativa a la fuerza bruta consiste en no buscar en todo el rango, sino ir directamente a los enteros que tienen más probabilidades de funcionar. Para este crackme interesa que el seno sea muy pequeño, es decir, que el valor esté muy cerca de un múltiplo de 𝜋. Aquí entra en juego la teoría de fracciones continuas, que permite encontrar aproximaciones racionales muy buenas de 𝜋.
Una fracción continua es una forma alternativa de representar un número real como una sucesión de enteros encadenados mediante divisiones, lo que permite descomponerlo en una estructura mucho más informativa que su simple expresión decimal. A diferencia de los decimales, que solo aproximan el valor con mayor o menor precisión, las fracciones continuas generan de manera natural una serie de fracciones racionales llamadas convergentes, que son las mejores aproximaciones posibles del número con denominadores relativamente pequeños. Esto significa que cada convergente no es una aproximación cualquiera, sino una óptima dentro de su rango. Esta propiedad resulta especialmente útil cuando se trabaja con números irracionales como π, ya que permite encontrar relaciones muy precisas entre enteros. En el contexto del crackme, esto se traduce en que los numeradores de esas fracciones proporcionan valores que están muy cerca de múltiplos de π, lo que implica que su seno es muy pequeño. Por tanto, aprovecharemos esto para reducir drásticamente el espacio de búsqueda y localizar de forma eficiente los candidatos que cumplen la condición del problema.
Acabamos de nombrar el concepto clave, convergente. Un convergente es cada una de las fracciones que se obtiene al ir construyendo progresivamente una fracción continua y detenerla en distintos puntos. Cada vez que nos quedamos con un término más de la secuencia, obtenemos una nueva aproximación racional del número original. Lo interesante es que en estas aproximaciones cada convergente suele ser extraordinariamente bueno en relación con el tamaño de sus números. Un ejemplo muy conocido es la aproximación de Arquímedes 22/7 que aproxima a π con bastante precisión pese a usar números muy pequeños. Esa fracción no aparece por casualidad, sino que es uno de los primeros convergentes de la fracción continua de π. Conforme se añaden más términos, van apareciendo convergentes todavía mejores, como 355/113 cuya precisión ya es bastante buena.
| Convergente | Valor decimal | Decimales | | ---------------------- | ------------------------ | --------- | | 3/1 | 3.00000000000000000000 | 0 | | 22/7 | 3.14285714285714285714 | 2 | | 333/106 | 3.14150943396226415094 | 4 | | 355/113 | 3.14159292035398230088 | 6 | | 103993/33102 | 3.14159265301190260407 | 9 | | 104348/33215 | 3.14159265392142152672 | 9 | | 208341/66317 | 3.14159265346743675291 | 9 | | 312689/99532 | 3.14159265361893656630 | 9 | | 833719/265381 | 3.14159265358107777120 | 11 | | 1146408/364913 | 3.14159265359140397848 | 10 | | 4272943/1360120 | 3.14159265358938917154 | 12 | | 5419351/1725033 | 3.14159265358981538323 | 12 | | 80143857/25510582 | 3.14159265358979267191 | 14 | | 165707065/52746197 | 3.14159265358979312841 | 15 | | 245850922/78256779 | 3.14159265358979324748 | 16 | | 411557987/131002976 | 3.14159265358979323751 | 17 | | 1068966896/340262731 | 3.14159265358979323851 | 18 | | 2549491779/811528438 | 3.14159265358979323842 | 19 | | 6167950454/1963319607 | 3.141592653589793238467 | 20 | | 14885392687/4738167652 | 3.1415926535897932384621 | 21 | | ... | ... | ... | | π | 3.1415926535897932384626 | ∞ |
Ya que hemos nombrado a los convergentes, también podemos aprovechar los semiconvergentes, que no son más que aproximaciones intermedias entre dos convergentes consecutivos.
| Convergente (Actual) | Siguiente Término | Semiconvergentes | | :----------------------- | :---------------: | :--------------: | | 3 / 1 | 7 | 6 | | 22 / 7 | 15 | 14 | | 333 / 106 | 1 | 0 | | 355 / 113 | 292 | 291 | | 103993 / 33102 | 1 | 0 | | 104348 / 33215 | 1 | 0 | | 208341 / 66317 | 1 | 0 | | 312689 / 99532 | 2 | 1 | | 833719 / 265381 | 1 | 0 | | 1146408 / 364913 | 3 | 2 | | 4272943 / 1360120 | 1 | 0 | | 5419351 / 1725033 | 14 | 13 | | 80143857 / 25510582 | 2 | 1 | | 165707065 / 52746197 | 1 | 0 | | 245850922 / 78256779 | 1 | 0 | | 411557987 / 131002976 | 2 | 1 | | 1068966896 / 340262731 | 2 | 1 | | 2549491779 / 811528438 | 2 | 1 | | 6167950454 / 1963319607 | 2 | 1 | | 14885392687 / 4738167652 | 1 | 0 |
Antes de nada una cosa importante en cuanto a las restricciones del crackme. En el código vemos que los candidatos deben estar entre 1 y 1010, pero en realidad el crackme no acepta números de 10 cifras, es decir, el número más alto que acepta es 109-1 = 999999999. Esto nos limita hasta el convergente 16 (411557987 / 131002976) ya que el convergente 17 tiene diez cifras. Aún así, entre el convergente 16 y 17 disponemos de un hueco para buscar algún semiconvergente y rascar un poco más. Si atendemos a esta reflexión podemos buscar rápidamente entre 16 candidatos convergentes y 329 semiconvergentes o lo que es lo mismo, debemos comprobar 345 candidatos.
// ============================================================
// CONFIGURACIÓN
// ============================================================
const EXTENDED_MODE = true; // true: Múltiplos + Combinaciones (sumas/restas)
const MAX_N = 999_999_999n;
// Precisión interna (30 decimales)
const PI_STR = "3141592653589793238462643383279";
const PI_VAL = BigInt(PI_STR);
const PI_FACTOR = 10n ** 30n;
const OUTPUT_SCALE = 10n ** 16n;
// ============================================================
// LÓGICA MATEMÁTICA
// ============================================================
function getSinEst(p, q) {
let error = (p * PI_FACTOR) - (q * PI_VAL);
// sin(p) ≈ (-1)^q * (p - q*pi)
return (q % 2n === 0n) ? error : -error;
}
function getContinuedFraction(termsCount) {
let terms = [];
let p = PI_VAL, q = PI_FACTOR;
for (let i = 0; i < termsCount; i++) {
let a = p / q;
terms.push(a);
let next_q = p % q;
p = q; q = next_q;
if (q === 0n) break;
}
return terms;
}
function buildCandidates(limitN) {
let cf = getContinuedFraction(50);
let rawData = new Map();
// 1. CONVERGENTES
let p_m2 = 0n, p_m1 = 1n, q_m2 = 1n, q_m1 = 0n;
let convs = [];
for (let a of cf) {
let p = a * p_m1 + p_m2, q = a * q_m1 + q_m2;
convs.push({ p, q, a });
if (p <= limitN) rawData.set(p, { q, source: "convergente" });
if (p > limitN) break;
p_m2 = p_m1; p_m1 = p; q_m2 = q_m1; q_m1 = q;
}
// 2. SEMICONVERGENTES MATEMÁTICOS
for (let i = 1; i < convs.length; i++) {
let pk = convs[i - 1].p, qk = convs[i - 1].q, aNext = convs[i].a;
let pPrev = (i === 1) ? 1n : convs[i - 2].p;
let qPrev = (i === 1) ? 0n : convs[i - 2].q;
for (let t = 1n; t < aNext; t++) {
let p = t * pk + pPrev, q = t * qk + qPrev;
if (p > limitN) break;
if (!rawData.has(p)) rawData.set(p, { q, source: "semiconvergente" });
}
}
// 3. MODO EXTENDIDO (Múltiplos + Combinaciones)
if (EXTENDED_MODE) {
let baseItems = Array.from(rawData.entries()); // [p, {q, source}]
// A. Múltiplos (del 2 al 10)
baseItems.forEach(([p, data]) => {
for (let k = 2n; k <= 10n; k++) {
let np = p * k, nq = data.q * k;
if (np <= limitN && !rawData.has(np)) {
rawData.set(np, { q: nq, source: "múltiplo" });
}
}
});
// B. Combinaciones (Sumas y Restas) de los mejores
// Seleccionamos los 10 candidatos con el error más bajo para combinar
let sortedByError = Array.from(rawData.entries())
.map(([p, d]) => ({ p, q: d.q, err: getSinEst(p, d.q) }))
.sort((a, b) => {
let absA = a.err < 0n ? -a.err : a.err;
let absB = b.err < 0n ? -b.err : b.err;
return absA < absB ? -1 : 1;
})
.slice(0, 10);
for (let i = 0; i < sortedByError.length; i++) {
for (let j = i + 1; j < sortedByError.length; j++) {
let c1 = sortedByError[i];
let c2 = sortedByError[j];
// Probar Suma
let sp = c1.p + c2.p;
let sq = c1.q + c2.q;
if (sp <= limitN && !rawData.has(sp)) {
rawData.set(sp, { q: sq, source: "combinación" });
}
// Probar Resta (valor absoluto)
let rp = c1.p > c2.p ? c1.p - c2.p : c2.p - c1.p;
let rq = c1.q > c2.q ? c1.q - c2.q : c2.q - c1.q;
if (rp > 1n && !rawData.has(rp)) {
rawData.set(rp, { q: rq, source: "combinación" });
}
}
}
}
return Array.from(rawData.entries()).map(([p, d]) => ({
n: p, q: d.q, sinEst: getSinEst(p, d.q), source: d.source
})).sort((a, b) => a.n < b.n ? -1 : 1);
}
// ============================================================
// EJECUCIÓN
// ============================================================
function run() {
const MODE_TEXT = EXTENDED_MODE ? "EXTENDIDO (Total)" : "PURO";
console.log(`\n--- MODO ${MODE_TEXT} ---`);
let candidates = buildCandidates(MAX_N);
let validPairs = [];
let pos = candidates.filter(c => c.sinEst > 0n);
let neg = candidates.filter(c => c.sinEst < 0n);
[pos, neg].forEach(group => {
for (let i = 0; i < group.length; i++) {
for (let j = i + 1; j < group.length; j++) {
let c1 = group[i], c2 = group[j];
let prod = (c1.sinEst * c2.sinEst * OUTPUT_SCALE) / (PI_FACTOR * PI_FACTOR);
if (prod === 0n) {
let valNum = Number(c1.sinEst * c2.sinEst) * 1e16 / 1e60;
validPairs.push({
x1: c1.n.toString(),
x2: c2.n.toString(),
"1e16*sin*sin": valNum.toExponential(10),
floor: 0,
tipo: `${c1.source}, ${c2.source}`
});
}
}
}
});
console.log(`Candidatos analizados: ${candidates.length}`);
console.log(`Pares válidos encontrados: ${validPairs.length}`);
if (validPairs.length > 0) {
console.table(validPairs.sort((a,b) => Number(a.x1) - Number(b.x1)));
}
}
run();
Usando los candidatos convergentes y semiconvergentes puros obtenemos sólamente 3 pares válidos. Uno de ellos es la solución que proporcionó Cronos (245850922 – 411557987) que son dos convergentes puros.
--- MODO PURO --- Candidatos analizados: 345 Pares válidos encontrados: 3 ┌─────────┬─────────────┬─────────────┬───────────────────┬───────┬────────────────────────────────┐ │ (index) │ x1 │ x2 │ 1e16*sin*sin │ floor │ tipo │ ├─────────┼─────────────┼─────────────┼───────────────────┼───────┼────────────────────────────────┤ │ 0 │ '245850922' │ '411557987' │ '1.5519794664e-1' │ 0 │ 'convergente, convergente' │ │ 1 │ '245850922' │ '657408909' │ '2.1910929367e-1' │ 0 │ 'convergente, semiconvergente' │ │ 2 │ '411557987' │ '657408909' │ '9.0848663357e-2' │ 0 │ 'convergente, semiconvergente' │ └─────────┴─────────────┴─────────────┴───────────────────┴───────┴────────────────────────────────┘
Una vez más, no me voy a conformar con tres resultados. Tiene que haber una forma sencilla de encontrar más candidatos, ¿pero cómo? Muy fácil, como ya tenemos los mejores candidatos, los puros, vamos a jugar con ellos para generar otros que, aunque no sean tan óptimos matemáticamente, nos sigan valiendo. La solución más rápida es usar múltiplos y combinaciones. En el caso de los múltiplos, si un candidato puro tiene un seno muy cercano a cero, su doble también lo tendrá, al igual que su triple y así sucesivamente (en el código lo he limitado a 10). Con las sumas y restas ocurre lo mismo, combinando los candidatos puros entre sí obtenemos nuevos valores válidos. Al implementar en JavaScript, he limitado la combinación a los 10 mejores para no ralentizar el navegador. Con este número podéis jugar para ver como influye en el número de soluciones encontradas, por ejemplo, si limitamos a los 5 mejores encontramos 15 soluciones, con los 8 mejores ya subimos a 21 y a partir de 10 encontramos las ansiadas 22 soluciones.
Gracias a esta sencilla estrategia, ampliamos de 345 a 3421 candidatos, encontrando al instante los 22 pares que tardé horas en obtener por fuerza bruta.
--- MODO EXTENDIDO --- Candidatos analizados: 3421 Pares válidos encontrados: 22 ┌─────────┬─────────────┬─────────────┬───────────────────┬───────┬────────────────────────────────┐ │ (index) │ x1 │ x2 │ 1e16*sin*sin │ floor │ tipo │ ├─────────┼─────────────┼─────────────┼───────────────────┼───────┼────────────────────────────────┤ │ 0 │ '165707065' │ '577265052' │ '9.6859964679e-1' │ 0 │ 'convergente, combinación' │ │ 1 │ '165707065' │ '903259831' │ '8.3946314397e-1' │ 0 │ 'convergente, combinación' │ │ 2 │ '245850922' │ '411557987' │ '1.5519794664e-1' │ 0 │ 'convergente, convergente' │ │ 3 │ '245850922' │ '657408909' │ '2.1910929367e-1' │ 0 │ 'convergente, semiconvergente' │ │ 4 │ '245850922' │ '823115974' │ '3.1039589328e-1' │ 0 │ 'convergente, múltiplo' │ │ 5 │ '251270273' │ '411557987' │ '8.1383963641e-1' │ 0 │ 'combinación, convergente' │ │ 6 │ '325994779' │ '411557987' │ '5.2994312320e-1' │ 0 │ 'combinación, convergente' │ │ 7 │ '325994779' │ '657408909' │ '7.4817654436e-1' │ 0 │ 'combinación, semiconvergente' │ │ 8 │ '331414130' │ '411557987' │ '4.3909445985e-1' │ 0 │ 'múltiplo, convergente' │ │ 9 │ '331414130' │ '657408909' │ '6.1991591405e-1' │ 0 │ 'múltiplo, semiconvergente' │ │ 10 │ '331414130' │ '823115974' │ '8.7818891969e-1' │ 0 │ 'múltiplo, múltiplo' │ │ 11 │ '406138636' │ '411557987' │ '9.0468829977e-1' │ 0 │ 'combinación, convergente' │ │ 12 │ '411557987' │ '657408909' │ '9.0848663357e-2' │ 0 │ 'convergente, semiconvergente' │ │ 13 │ '411557987' │ '662828260' │ '8.7818891969e-1' │ 0 │ 'convergente, múltiplo' │ │ 14 │ '411557987' │ '737552766' │ '4.6559383992e-1' │ 0 │ 'convergente, múltiplo' │ │ 15 │ '411557987' │ '742972117' │ '5.0344374313e-1' │ 0 │ 'convergente, combinación' │ │ 16 │ '411557987' │ '817696623' │ '8.4033901648e-1' │ 0 │ 'convergente, combinación' │ │ 17 │ '411557987' │ '823115974' │ '1.2869856657e-1' │ 0 │ 'convergente, múltiplo' │ │ 18 │ '657408909' │ '737552766' │ '6.5732788100e-1' │ 0 │ 'semiconvergente, múltiplo' │ │ 19 │ '657408909' │ '742972117' │ '7.1076457741e-1' │ 0 │ 'semiconvergente, combinación' │ │ 20 │ '657408909' │ '823115974' │ '1.8169732671e-1' │ 0 │ 'semiconvergente, múltiplo' │ │ 21 │ '737552766' │ '823115974' │ '9.3118767984e-1' │ 0 │ 'múltiplo, múltiplo' │ └─────────┴─────────────┴─────────────┴───────────────────┴───────┴────────────────────────────────┘
Este reto es un recordatorio de que en la ingeniería inversa y la programación, la fuerza bruta es a menudo el camino más largo entre dos puntos. Lo que hace doce años me costó horas de computación resolver, hoy lo he resuelto en milisegundos utilizando la elegancia de la teoría de números. Al final, no se trata solo de romper la cerradura, sino de entender la mecánica que permite que la llave gire.