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. Therefore, we can divide everything by $p$, which makes the inversion possible on modulo $n / p = q$
$$
xka = x \times k_A = (vka) / p
$$
$$
xkakb = x \times k_A \times k_B = (vkakb) / p
$$
$$
xkb = x \times k_B = (vkb) / p
$$
Hence, as we can now invert $xkb$ under modulo $q$, we can then have:
$$
k_A = xkakb \times xkb^{-1}
$$
$$
x = k_A^{-1} \times xka
$$
From $x$, calculating the original $v$ is trivial. There are other solution that uses CRT as well, but all are doing operation under modulo $q$.
Python 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
|
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from hashlib import sha256
from Crypto.Util.number import getPrime, GCD, bytes_to_long, long_to_bytes, inverse
p, q = (10699940648196411028170713430726559470427113689721202803392638457920771439452897032229838317321639599506283870585924807089941510579727013041135771337631951, 11956676387836512151480744979869173960415735990945471431153245263360714040288733895951317727355037104240049869019766679351362643879028085294045007143623763)
vka = 124641741967121300068241280971408306625050636261192655845274494695382484894973990899018981438824398885984003880665335336872849819983045790478166909381968949910717906136475842568208640203811766079825364974168541198988879036997489130022151352858776555178444457677074095521488219905950926757695656018450299948207
vkakb = 114778245184091677576134046724609868204771151111446457870524843414356897479473739627212552495413311985409829523700919603502616667323311977056345059189257932050632105761365449853358722065048852091755612586569454771946427631498462394616623706064561443106503673008210435922340001958432623802886222040403262923652
vkb = 6568897840127713147382345832798645667110237168011335640630440006583923102503659273104899584827637961921428677335180620421654712000512310008036693022785945317428066257236409339677041133038317088022368203160674699948914222030034711433252914821805540365972835274052062305301998463475108156010447054013166491083
c = 'fef29e5ff72f28160027959474fc462e2a9e0b2d84b1508f7bd0e270bc98fac942e1402aa12db6e6a36fb380e7b53323'
c = bytes.fromhex(c)
n = p * q
xka = vka // p
xkakb = vkakb // p
xkb = vkb // p
ka = xkakb * pow(xkb, -1, q)
x = pow(ka, -1, q) * xka
v = (p * x) % n
key = sha256(long_to_bytes(v)).digest()
cipher = AES.new(key, AES.MODE_ECB)
m = unpad(cipher.decrypt(c), 16)
print(m)
|