Cryptohack

Again, I do not know how to solve this problem. Leave it to the future me to digest how to solve lattice problems and understand a bit more about group theory. The original attack is from Shamir et al., but a low-density attack that leverages the LLL algorithm. A version is mentioned in this awesome paper. Sage Implementation: 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 35 a = [ #public key ] s = #ciphertext n = len(a) N = ceil(sqrt(n) / 2) b = [] for i in range(n): vec = [0 for _ in range(n + 1)] vec[i] = 1 vec[-1] = N * a[i] b....

I did not manage to solve this challenge. The private key is composed by some $f, g$, both smaller than $\sqrt{\frac{q}{2}}$, with the relation that $fh - g = 0 \mod q$ This means that there exists a $k$ such that $fh = qk + g$, since $h$ is about the same size of $q$, we have that $k$ is the same size of $f$. We have the observation that $f \cdot (h, 1) + (-k) \cdot (q, 1) = (g, f - k)$, where both components of the result are small (g is around the square root of $\frac{q}{2}$, and $f$ is approximately $k$)....

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....

Useful Sage documentation link about the syntax for matrices. We are given a somewhat similar to a Diffie-Hellman key-exchange, a secret $s$ is picked out, then $H = G * s$ is calculated. They also generate a random vector $v$ in the matrix space. The product of $H \times v = w$ is calculated. Given the two vectors $v, w$, we have to derive the value of the secret $s$ to obtain the decryption key....

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:...

Short and sweet challenge. The script has one fatal flaw when doing Diffie-Hellman: 1 2 3 4 5 def generate_public_int(g, a, p): return g ^ a % p def generate_shared_secret(A, b, p): return A ^ b % p g ^ b % p is equivalent to g ^ (b % p), and ^ is binary xor in Python, not pow. Hence, we can easily retrieve Bob’s secret my doing B ^ g, as B = g ^ (b % p), and b < p, which leads to b % p = b....

This is weirdly RSA, but in a “matrix” context. To decrypt message in RSA, we need to calculate $m = c ^ d \mod p$, where $d = e ^ {-1} \mod \phi(n)$. $\phi(n)$ is the multiplicative order of the group. In this challenge, we are under some group of matrix with size 50x50, or in math notations, $GF(50, GF(2))$ and not under $\mod n$. Thus, $d = e ^ {-1} \mod |G|$, where $|G|$ is the order of the group $GF(50, GF(2))$....