1
$\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.

$\endgroup$
3
  • $\begingroup$ What are the ciphertext sizes in bits? What is the source of this question? $\endgroup$
    – kelalaka
    Apr 29 '20 at 12:50
  • $\begingroup$ Cipher text have a size of 128 bytes. The messages are "First test" and "Second test" $\endgroup$
    – root2d3877
    Apr 29 '20 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 '20 at 12:37
1
$\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).

$\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 '20 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 '20 at 15:27
  • $\begingroup$ I know, 65537 is the 4th fermat number and I tried with it. Thank you anyway. $\endgroup$
    – root2d3877
    Apr 29 '20 at 15:38
  • $\begingroup$ @root2d3877 Are you sure that the plaintext values are not padded somehow? $\endgroup$
    – Maarten Bodewes
    Apr 29 '20 at 22:32
  • $\begingroup$ @MaartenBodewes Yes, I am. The problems says that there is no padding $\endgroup$
    – root2d3877
    Apr 30 '20 at 8:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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