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