# Reversing key exchange algorithm

I'm analyzing some software and finding key exchanging procedure. Its looks like very similar with Diffie–Hellman, but not the same. I can’t understand the purpose of this.

The step of algorithm is:

1. Generate random KEY (128 byte)
2. Get constant G1 and P1
3. Calculate Y1 = G1 ^ KEY mod P1 // looks like Diffie–Hellman
4. Get another const G2 and P2 // ???
5. Calculate Y2 = Y1 ^ G2 mod P2, so Y2 = (G1 ^ KEY mod P1) ^ G2 mod P2
6. Transmit Y2 and receive key from other side FY2
7. Calculate Y3 = FY2 ^ KEY mod P1 // private key
8. On next step Y3 using as seed for stream cipher

I trying to simulate this procedure to get key exchange and its fail. Y3 keys on both side are not same. Looks like procedure on other side is different from this.

Any suggestion how can this algorithm works?

I assume that you've verified that $P_1 \ne P_2$ (and that they are distinct primes).

Well, I suppose that it could work; if the logic on the other side is a bit different.

If $P_2 > P_1$ (and $G_2$ is relatively prime to $P_2$), then the other side could rederive $Y_1$ from $Y_2$; hence the logic on the other side would be:

1. Generate random Key'
2. Get constant G1 and P1 (same values as the other side)
3. Calcuate Z1 = G1 ^ Key' mod P1
4. Transmit Z1 and receive key from other side Y2
5. Get another constant G3 and P2 (where G2 * G3 mod P2 - 1 = 1)
6. Calculate Y1 = FY2^G3 mod P2
7. Calculate Y3 = Y1^Key' mod P1

This is just Diffie-Hellman, written with an additional encoding step; it'd work, but I don't why this is necessarily better...

• After get more reserch i think step 5 in my initial message is RSA encryption with public key {G2,P2} end message Y1. So to decode this i need private key {G3,P2}. Is this the correct interpretation? Can you tell how you get the equation on G3 (G2 * G3 mod P2 - 1 = 1)? Is it possible to get private key {G3,P2}? PS I cheched constant, P1 - is prime, but P2 - not. P2 > P2 is true. – HenryLeaf Nov 8 '17 at 12:14
• @HenryLeaf: if P2 is not prime, you are likely correct that they are using RSA (and, if G2 is a small value, such as 3 or 65537, that would confirm it). In that case, the above logic would hold, however, we would have G2 * G3 mod lambda(P2) = 1, where lambda(P2) is a value that you probably can't compute (hence, you wouldn't be able to implement the other side logic), hence recovering the private key G3 isn't feasible, unless they made a mistake somewhere... – poncho Nov 8 '17 at 13:30