2
$\begingroup$

I have two plain texts files cipher with RSA (with the same public and private key) and I have their cipher texts too. Would it be possible know the public key from that information?

My messages have 10 characters and I cannot calculate a huge exponential operation. No padding is used on the messages before encryption.

Improve this question
$\endgroup$
3
  • $\begingroup$ What are the ciphertext sizes in bits? What is the source of this question? $\endgroup$
    – kelalaka
    Apr 29, 2020 at 12:50
  • $\begingroup$ Cipher text have a size of 128 bytes. The messages are "First test" and "Second test" $\endgroup$
    – root2d3877
    Apr 29, 2020 at 13:05
  • $\begingroup$ Suggestion: maybe you converted your plaintexts into integers incorrectly. Did you try little endian or big endian? $\endgroup$
    – user69015
    Apr 30, 2020 at 12:37

1 Answer 1

Reset to default
2
$\begingroup$

From a couple of plaintext/ciphertext $(m_1, c_1)$ and $(m_2, c_2)$, then the modulus $n$ is a factor of $$ \gcd(m_1^e-c_1, m_2^e-c_2). $$ The explanation is that $$ c_i = m_i^e - \lambda_i n $$ for some unknown $\lambda_i$, so $n$ both divides $m_1^e-c_1$ and $m_2^e-c_2$.

Of course, this solution works if you know $e$, but it can be tried with some classically used values ($e=3$ for instance).

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thank you so much for your answer. That it is what I tried and I have not any result yet. I tried with the first 8000 numbers and the first 4 fermat numbers. I hope that I come up with the e value or with another way to solve this problem $\endgroup$
    – root2d3877
    Apr 29, 2020 at 14:08
  • 1
    $\begingroup$ The most used value for $e$ is $65537$, so if you can manage exponentiation with it, you may find something. $\endgroup$
    – user69015
    Apr 29, 2020 at 15:27
  • $\begingroup$ I know, 65537 is the 4th fermat number and I tried with it. Thank you anyway. $\endgroup$
    – root2d3877
    Apr 29, 2020 at 15:38
  • $\begingroup$ @root2d3877 Are you sure that the plaintext values are not padded somehow? $\endgroup$
    – Maarten Bodewes ♦
    Apr 29, 2020 at 22:32
  • $\begingroup$ @MaartenBodewes Yes, I am. The problems says that there is no padding $\endgroup$
    – root2d3877
    Apr 30, 2020 at 8:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.