> For the complete documentation index, see [llms.txt](https://szczygielka.gitbook.io/writeups/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://szczygielka.gitbook.io/writeups/ctfs-writeups/ritsec-ctf-2024/failed-file-transfer-crypto.md).
# Failed File Transfer - Crypto
## Task
Hello, Investigator,
We have intercepted a transmission that was sent to the thief of Anthony’s invention. We believe it may contain information pertinent to your investigation! Additionally, the sender accidentally failed to encrypt the file with the thief's most recent provisioned key, requiring them to resend the message. I am not sure why, but the keys don’t seem all that different… There may be a vulnerability with the provisioning process. Nevertheless, we have provided you with all attempts captured in transmission and the keys used for posterity. Good luck!
## Solution
There are 6 files attached to this task:
```
szczygielka@hacks$ ls
file1.txt file2.txt file3.txt pk1.pem pk2.pem pk3.pem
```
The files `file1.txt`, `file2.txt` and `file3.txt` contain encrypted messages, and the files `pk1.pem`, `pk2.pem` and `pk3.pem` corresponding OpenSSL public keys. We also know that 2 of these ciphertexts should contain the same message.
At first glance, `pk1.pem` and `pk2.pem` seems to be very similar. Let's check where the differences are:
Let's check the N and e values of these two keys. We can do that using Python:
```
from Crypto.PublicKey import RSA
pk1= RSA.importKey(open('pk1.pem', 'r').read())
pk2= RSA.importKey(open('pk2.pem', 'r').read())
print("Public key pk1.pem:")
print("N:", pk1.n)
print("e:", pk1.e,"\n")
print("Public key pk2.pem:")
print("N:", pk2.n)
print("e:", pk2.e)
```
After running the script, we get the following values:
{% code overflow="wrap" %}
```
szczygielka@hacks$ python3 check_public_keys.py
Public key pk1.pem:
N: 28328155133789285412996485843849200476439065854667450765531808634398279813714628611356505714448351029445206816297052695426468253209725620716288482361102009067488713792451157452440320904129625879607490043398774470615404369860538006179371183327649709712501068068177273167061064338155527388645013573819301396993041088782234723965610645795972735632259386678942658723374218497702728373253510668221460843692893157119362969141683846788307008594470839378698903964555806830095684319234830057112110046745094252937455819876945923393366316612953799035331034631039025141050433840806360637677929177247521035208032331912039593186471
e: 17
Public key pk2.pem:
N: 28328155133789285412996485843849200476439065854667450765531808634398279813714628611356505714448351029445206816297052695426468253209725620716288482361102009067488713792451157452440320904129625879607490043398774470615404369860538006179371183327649709712501068068177273167061064338155527388645013573819301396993041088782234723965610645795972735632259386678942658723374218497702728373253510668221460843692893157119362969141683846788307008594470839378698903964555806830095684319234830057112110046745094252937455819876945923393366316612953799035331034631039025141050433840806360637677929177247521035208032331912039593186471
e: 65537
```
{% endcode %}
We can see that the N values for both keys are the same:
$$
N\_1=N\_2
$$
### Common modulus attack
A common modulus attack can be used to recover the message if we have 2 ciphertexts of the same message, encrypted with 2 RSA keys that use the same modulus and relatively prime encryption exponents. That means that the greatest common divisor of $$e\_{1}$$ and $$e\_{2}$$ should be equal 1:
$$
gcd(e\_1,e\_2)=1
$$
The Euclidean Algorithm states that for given integers $$e\_1$$and $$e\_2$$, there is always an integral solution to the equation:
$$
ae\_{1}+be\_{2}=gcd(e\_1,e\_2)
$$
From Bézout's Theorem, we know that for positive integers $$e\_1$$ and $$e\_2$$, if $$gcd(e\_1,e\_2)=1$$, exist integers $$a$$ and $$b$$ such that:
$$
ae\_1+be\_2=1
$$
Based on this knowledge we can calculate the message as:
$$
C\_{1}^a\cdot C\_{2}^b=(M\_{1}^{e\_{1}})^a\cdot(M\_{2}^{e\_{2}})^b=M\_{1}^{ae\_{1}}\cdot M\_{2}^{be\_{2}} =M^{ae\_{1}+be\_{2}}=M^{1}=M
$$
All the attack assumptions have been met, so we can use this attack to get the message. Using all of this information we can implement a Python script to calculate the message:
```
from Crypto.PublicKey import RSA
from Crypto.Util.number import long_to_bytes,bytes_to_long
public_key_1 = RSA.importKey(open('pk1.pem', 'r').read())
public_key_2 = RSA.importKey(open('pk2.pem', 'r').read())
c1=bytes_to_long(open('file1.txt', 'rb').read())
c2=bytes_to_long(open('file2.txt', 'rb').read())
def egcd(a, b):
if (a == 0):
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
cdg, a, b = egcd(public_key_1.e,public_key_2.e)
msg = pow(c1,a,public_key_1.n) * pow(c2,b,public_key_1.n) % public_key_1.n
print(long_to_bytes(msg))
```
After executing the script we get the flag.
Flag:
```
RS{Y0U_C4NT_R3AD_M3_R1GHT??}
```
---
# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.
## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://szczygielka.gitbook.io/writeups/ctfs-writeups/ritsec-ctf-2024/failed-file-transfer-crypto.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.