This challenge marks a really important point in my CryptoHack journey. I have conquered a lattice related challenge knowing what is going on. Lattices have been something I have zero idea about (and I would looove to stay away from), but thanks to the incredible help and explanation from Kel Zin, I can say I understand 0.01% of how lattices work now. If we write the problem in mathematical terms, we have the following:...
We can factor $N$ using the given phi, or just simply look up the number on FactorDB. If the number returned has the form of $c = g ^ {k}$ with some even number $k$, we have the observation that for every factor of $N$, $c$ is a quadratic residue under that base, whereas the randomly generated number almost never generate a number that is a quadratic residue of all factors....
Googling the name of the challenge should point us to a paper, detailing how Miller-Rabin tests are misused in practice - some strong pseudoprimes can still pass the Miller-Rabin test. Searching for the implementation of this challenge will lead us to this Github repo. Running the script should lead to a pseudoprime n = p1 * p2 * p3. Sending the base as one of the primes and the prime as n will return the flag....
No shot I would get this. This challenge is based on the Paillier cryptosystem, an additive homomorphic cryptosystem. Paillier cryptosystem exploits the fact that certain discrete logarithms can be computed easily. Indeed, by binomial theorem: $$ (1 + n) ^ x = 1 + nx + {x \choose 2} n ^ 2 + \text{higher powers of n} $$ which, under modulo $n ^ 2$, leads to: $$ (1 + n) ^ x = 1 + nx \mod n^2 $$ This is the crux of the challenge....
I did not know the way to solve the challenge after some naive idea of using Pohlig-Hellman on the smooth prime given. Nonetheless, it was a good try as after peeking at the solution, there is no shot that I can solve this without knowing some group theory of have acute observation of the number patterns. The first way to solve this, and one can look up in this paper, about Genus 0 Curves....
We are presented a key-exchange protocol where there is some $v$ generated by $p * x$, where $p$ is one of the two primes given, $x$ is a random number generated. We are also given the following: $$ vka = v \times k_A \mod n $$ $$ vkakb = vka \times k_B \mod n $$ $$ vkb = v \times k_B \mod n $$ Obviously we can calculate $k_A$ by doing $(vkb)^{-1} \times vkakb$, but unfortunately $v$ is a multiple of $p$ that is not possible....
Try my luck with factorizing N using FactorDB. It works for special challenge like this where the N is something kinda special, or we just get lucky that FactorDB has done the factorising work for us ;) 1 2 3 4 5 6 7 8 9 10 11 12 13 from Crypto.Util.number import bytes_to_long, long_to_bytes N = 89820998365358013473897522178239129504456795742012047145284663770709932773990122507570315308220128739656230032209252739482850153821841585443253284474483254217510876146854423759901130591536438014306597399390867386257374956301247066160070998068007088716177575177441106230294270738703222381930945708365089958721 c = 0x5233da71cc1dc1c5f21039f51eb51c80657e1af217d563aa25a8104a4e84a42379040ecdfdd5afa191156ccb40b6f188f4ad96c58922428c4c0bc17fd5384456853e139afde40c3f95988879629297f48d0efa6b335716a4c24bfee36f714d34a4e810a9689e93a0af8502528844ae578100b0188a2790518c695c095c9d677b # From FactorDB p = 8239835397208516111720362847949425401045672365829937602117480449316694558226622200110057535873802132963548914201468383545676262090246827792522994758916609 q = 10900824353334471830007307529937357926160386461967884446160315218630687793341471079170750548554707926611542019859296605188535413447791710067186432371970369 b = 0x7fe8cafec59886e9318830f33747cafd200588406e7c42741859e15994ab62410438991ab5d9fc94f386219e3c27d6ffc73754f791e7b2c565611f8fe5054dd132b8c4f3eadcf1180cd8f2a3cc756b06996f2d5b67c390adcba9d444697b13d12b2badfc3c7d5459df16a047ca25f4d18570cd6fa727aed46394576cfdb56b41 e = 0x10001 phi = (p - 1) * (q - 1) d = pow(e, -1, phi) print(long_to_bytes(pow(c, d, N))) The intended solution relies on the observation about RSA Fixed Point, or messages $m$, for some given $e, n$ yields:...