Bob, Alice, and Eve

logistic_guy

logistic_guy

Senior Member
Joined
Apr 17, 2024
Messages
2,215
Bob and Alice use a cryptosystem in which their private key is a (large) prime \(\displaystyle k\) and their plaintexts and ciphertexts are integers. Bob encrypts a message \(\displaystyle m\) by computing the product \(\displaystyle c = km\). Eve intercepts the following two ciphertexts:

\(\displaystyle c_1 = 12849217045006222\)
\(\displaystyle c_2 = 6485880443666222\)

Find Bob and Alice’s private key.

Hint: Use the GCD method.
 
We will try to solve this problem by the Euclidean algorithm. We will start with:

\(\displaystyle 12849217045006222 = (1)6485880443666222 + 6363336601340000\)
 
Next

\(\displaystyle 12849217045006222 = (1)6485880443666222 + 6363336601340000\)
\(\displaystyle 6485880443666222 = (1)6363336601340000 + 122543842326222\)
 
Next

\(\displaystyle 12849217045006222 = (1)6485880443666222 + 6363336601340000\)
\(\displaystyle 6485880443666222 = (1)6363336601340000 + 122543842326222\)
\(\displaystyle 6363336601340000 = (51)122543842326222 + 113600642702678\)
 
Next

\(\displaystyle 12849217045006222 = (1)6485880443666222 + 6363336601340000\)
\(\displaystyle 6485880443666222 = (1)6363336601340000 + 122543842326222\)
\(\displaystyle 6363336601340000 = (51)122543842326222 + 113600642702678\)
\(\displaystyle 122543842326222 = (1)113600642702678 + 8943199623544\)
 
Next

\(\displaystyle 12849217045006222 = (1)6485880443666222 + 6363336601340000\)
\(\displaystyle 6485880443666222 = (1)6363336601340000 + 122543842326222\)
\(\displaystyle 6363336601340000 = (51)122543842326222 + 113600642702678\)
\(\displaystyle 122543842326222 = (1)113600642702678 + 8943199623544\)
\(\displaystyle 113600642702678 = (12)8943199623544 + 6282247220150\)
 
Next

\(\displaystyle 12849217045006222 = (1)6485880443666222 + 6363336601340000\)
\(\displaystyle 6485880443666222 = (1)6363336601340000 + 122543842326222\)
\(\displaystyle 6363336601340000 = (51)122543842326222 + 113600642702678\)
\(\displaystyle 122543842326222 = (1)113600642702678 + 8943199623544\)
\(\displaystyle 113600642702678 = (12)8943199623544 + 6282247220150\)
\(\displaystyle 8943199623544 = (1)6282247220150 + 2660952403394\)
 
Next

\(\displaystyle 12849217045006222 = (1)6485880443666222 + 6363336601340000\)
\(\displaystyle 6485880443666222 = (1)6363336601340000 + 122543842326222\)
\(\displaystyle 6363336601340000 = (51)122543842326222 + 113600642702678\)
\(\displaystyle 122543842326222 = (1)113600642702678 + 8943199623544\)
\(\displaystyle 113600642702678 = (12)8943199623544 + 6282247220150\)
\(\displaystyle 8943199623544 = (1)6282247220150 + 2660952403394\)
\(\displaystyle 6282247220150 = (2)2660952403394 + 960342413362\)
 
Next

\(\displaystyle 12849217045006222 = (1)6485880443666222 + 6363336601340000\)
\(\displaystyle 6485880443666222 = (1)6363336601340000 + 122543842326222\)
\(\displaystyle 6363336601340000 = (51)122543842326222 + 113600642702678\)
\(\displaystyle 122543842326222 = (1)113600642702678 + 8943199623544\)
\(\displaystyle 113600642702678 = (12)8943199623544 + 6282247220150\)
\(\displaystyle 8943199623544 = (1)6282247220150 + 2660952403394\)
\(\displaystyle 6282247220150 = (2)2660952403394 + 960342413362\)
\(\displaystyle 2660952403394 = (2)960342413362 + 740267576670\)
 
Next

\(\displaystyle 12849217045006222 = (1)6485880443666222 + 6363336601340000\)
\(\displaystyle 6485880443666222 = (1)6363336601340000 + 122543842326222\)
\(\displaystyle 6363336601340000 = (51)122543842326222 + 113600642702678\)
\(\displaystyle 122543842326222 = (1)113600642702678 + 8943199623544\)
\(\displaystyle 113600642702678 = (12)8943199623544 + 6282247220150\)
\(\displaystyle 8943199623544 = (1)6282247220150 + 2660952403394\)
\(\displaystyle 6282247220150 = (2)2660952403394 + 960342413362\)
\(\displaystyle 2660952403394 = (2)960342413362 + 740267576670\)
\(\displaystyle 960342413362 = (1)740267576670 + 220074836692\)
 
Next

\(\displaystyle 12849217045006222 = (1)6485880443666222 + 6363336601340000\)
\(\displaystyle 6485880443666222 = (1)6363336601340000 + 122543842326222\)
\(\displaystyle 6363336601340000 = (51)122543842326222 + 113600642702678\)
\(\displaystyle 122543842326222 = (1)113600642702678 + 8943199623544\)
\(\displaystyle 113600642702678 = (12)8943199623544 + 6282247220150\)
\(\displaystyle 8943199623544 = (1)6282247220150 + 2660952403394\)
\(\displaystyle 6282247220150 = (2)2660952403394 + 960342413362\)
\(\displaystyle 2660952403394 = (2)960342413362 + 740267576670\)
\(\displaystyle 960342413362 = (1)740267576670 + 220074836692\)
\(\displaystyle 740267576670 = (3)220074836692 + 80043066594\)
 
Next

\(\displaystyle 12849217045006222 = (1)6485880443666222 + 6363336601340000\)
\(\displaystyle 6485880443666222 = (1)6363336601340000 + 122543842326222\)
\(\displaystyle 6363336601340000 = (51)122543842326222 + 113600642702678\)
\(\displaystyle 122543842326222 = (1)113600642702678 + 8943199623544\)
\(\displaystyle 113600642702678 = (12)8943199623544 + 6282247220150\)
\(\displaystyle 8943199623544 = (1)6282247220150 + 2660952403394\)
\(\displaystyle 6282247220150 = (2)2660952403394 + 960342413362\)
\(\displaystyle 2660952403394 = (2)960342413362 + 740267576670\)
\(\displaystyle 960342413362 = (1)740267576670 + 220074836692\)
\(\displaystyle 740267576670 = (3)220074836692 + 80043066594\)
\(\displaystyle 220074836692 = (2)80043066594 + 59988703504\)
 
Next

\(\displaystyle 12849217045006222 = (1)6485880443666222 + 6363336601340000\)
\(\displaystyle 6485880443666222 = (1)6363336601340000 + 122543842326222\)
\(\displaystyle 6363336601340000 = (51)122543842326222 + 113600642702678\)
\(\displaystyle 122543842326222 = (1)113600642702678 + 8943199623544\)
\(\displaystyle 113600642702678 = (12)8943199623544 + 6282247220150\)
\(\displaystyle 8943199623544 = (1)6282247220150 + 2660952403394\)
\(\displaystyle 6282247220150 = (2)2660952403394 + 960342413362\)
\(\displaystyle 2660952403394 = (2)960342413362 + 740267576670\)
\(\displaystyle 960342413362 = (1)740267576670 + 220074836692\)
\(\displaystyle 740267576670 = (3)220074836692 + 80043066594\)
\(\displaystyle 220074836692 = (2)80043066594 + 59988703504\)
\(\displaystyle 80043066594 = (1)59988703504 + 20054363090\)
 
Next

\(\displaystyle 12849217045006222 = (1)6485880443666222 + 6363336601340000\)
\(\displaystyle 6485880443666222 = (1)6363336601340000 + 122543842326222\)
\(\displaystyle 6363336601340000 = (51)122543842326222 + 113600642702678\)
\(\displaystyle 122543842326222 = (1)113600642702678 + 8943199623544\)
\(\displaystyle 113600642702678 = (12)8943199623544 + 6282247220150\)
\(\displaystyle 8943199623544 = (1)6282247220150 + 2660952403394\)
\(\displaystyle 6282247220150 = (2)2660952403394 + 960342413362\)
\(\displaystyle 2660952403394 = (2)960342413362 + 740267576670\)
\(\displaystyle 960342413362 = (1)740267576670 + 220074836692\)
\(\displaystyle 740267576670 = (3)220074836692 + 80043066594\)
\(\displaystyle 220074836692 = (2)80043066594 + 59988703504\)
\(\displaystyle 80043066594 = (1)59988703504 + 20054363090\)
\(\displaystyle 59988703504 = (2)20054363090 + 19879977324\)
 
Next

\(\displaystyle 12849217045006222 = (1)6485880443666222 + 6363336601340000\)
\(\displaystyle 6485880443666222 = (1)6363336601340000 + 122543842326222\)
\(\displaystyle 6363336601340000 = (51)122543842326222 + 113600642702678\)
\(\displaystyle 122543842326222 = (1)113600642702678 + 8943199623544\)
\(\displaystyle 113600642702678 = (12)8943199623544 + 6282247220150\)
\(\displaystyle 8943199623544 = (1)6282247220150 + 2660952403394\)
\(\displaystyle 6282247220150 = (2)2660952403394 + 960342413362\)
\(\displaystyle 2660952403394 = (2)960342413362 + 740267576670\)
\(\displaystyle 960342413362 = (1)740267576670 + 220074836692\)
\(\displaystyle 740267576670 = (3)220074836692 + 80043066594\)
\(\displaystyle 220074836692 = (2)80043066594 + 59988703504\)
\(\displaystyle 80043066594 = (1)59988703504 + 20054363090\)
\(\displaystyle 59988703504 = (2)20054363090 + 19879977324\)
\(\displaystyle 20054363090 = (1)19879977324 + 174385766\)
 
Next

\(\displaystyle 12849217045006222 = (1)6485880443666222 + 6363336601340000\)
\(\displaystyle 6485880443666222 = (1)6363336601340000 + 122543842326222\)
\(\displaystyle 6363336601340000 = (51)122543842326222 + 113600642702678\)
\(\displaystyle 122543842326222 = (1)113600642702678 + 8943199623544\)
\(\displaystyle 113600642702678 = (12)8943199623544 + 6282247220150\)
\(\displaystyle 8943199623544 = (1)6282247220150 + 2660952403394\)
\(\displaystyle 6282247220150 = (2)2660952403394 + 960342413362\)
\(\displaystyle 2660952403394 = (2)960342413362 + 740267576670\)
\(\displaystyle 960342413362 = (1)740267576670 + 220074836692\)
\(\displaystyle 740267576670 = (3)220074836692 + 80043066594\)
\(\displaystyle 220074836692 = (2)80043066594 + 59988703504\)
\(\displaystyle 80043066594 = (1)59988703504 + 20054363090\)
\(\displaystyle 59988703504 = (2)20054363090 + 19879977324\)
\(\displaystyle 20054363090 = (1)19879977324 + 174385766\)
\(\displaystyle 19879977324 = (114)174385766 + \textcolor{red}{0}\)

\(\displaystyle \textcolor{indigo}{\bold{FINALLY}}\)

🤩🥳😎😍

\(\displaystyle \text{gcd}(12849217045006222,6485880443666222) = \textcolor{blue}{174385766}\)

\(\displaystyle \frac{174385766}{2} = 87192883\)

Since \(\displaystyle 87192883\) is a prime number and both large numbers share it, then it is the Bob and Alice’s private key.

\(\displaystyle k = \textcolor{green}{87192883}\)
 
You must log in or register to reply here.
Top