RSA Vulnerability 1
RSA is a very secure encryption algorithm for transmitting messages over the internet when used correctly. This problem assumes a good understanding of how RSA works so if you don't, head over to the link above.
RSA is used in emails. However, it is seldom the case where RSA is used to directly encrypt the message for transmission since it is a pretty slow process and has its vulnerabilities. Instead, RSA is often used to encrypt a key that is then used to encrypt the message. An example of this is in Pretty Good Privacy (PGP) .
A key is generated by the sender, and used to encrypt the main message. The key is then encrypted using RSA, and sent over to the receiver, along with the encrypted main message. The receiver then decrypts the key and uses the key to decrypt the main message. It is noted that should the same message be sent more than once, the key generated would be different every time.
Your school staff communicates with each other via an internal messaging system that uses RSA to encrypt the message. However, it does not use a key. Instead, it encrypts the whole message using RSA by splitting the message into blocks and encrypting each block. The blocks are then sent to the receiver who decrypts the blocks accordingly. Here is the source code: RSA Algorithm used . Note that corresponds to the modulus, exponent, private key and ciphertext.
You are going to fail physics. You don't want to fail physics. Hence you want to obtain the answer sheet to the physics exam. You know that Mr. Boh is going to send somebody the physics answer sheet via the above mentioned internal messaging system. In order to intercept the message, you installed a program on Mr. Boh's computer that makes it send the same message over and over: 520 times to be exact. Then, you perform a Man-in-the-middle Attack on Mr. Boh's computer to intercept the values of and from the intended receiver to Mr. Boh and the value of from Mr. Boh. The intercepted values are summarised in this file: Intercepted Messages
What is the answer to Question 99 of the Physics Exam?
Bonus: How would you modify the above-mentioned strategy such that the receiver does not receive a large number of messages from Mr. Boh, which would probably raise suspicions?
The answer is 9662206.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
The thing to note is that the same message is being encrypted many times. Knowing d , e , c for all 520 encryptions, you can construct a system of modular equations for m , the message you are trying to retrieve.
c 1 c 2 . . . c 5 2 0 ≡ m e ( m o d n 1 ) ≡ m e ( m o d n 2 ) . . . ≡ m e ( m o d n 5 2 0 )
You can find a solution for m e ≡ x ( m o d n 1 n 2 n 3 . . . n j ) by implementing the Chinese Remainder Theorem on the first j equations. In order to retrieve m , we can make n 1 n 2 n 3 . . . n j > m e by considering a susficiently large j so that m e does not even wrap around the modulus, making x = m e . So by taking x e 1 , we obtain m
Via the source code, we know that n > 1 0 3 0 8 and for each block, m < 1 0 9 1 . Hence, an upper bound for the minimum of j satisfies 3 0 8 j > 9 1 e , min ( j ) < 7 6 (which is far less than 520).
The code I used to execute this can be found here . My online implementation can be found here . This gives the output:
Going to the URL would bring you to the answer sheet.
I don't know why the last block did not decrypt properly. If you know why, please tell me.