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