Forum

Challenge "RSA: Two different keys — same ciphertext"  

  By: admin on Aug. 15, 2011, 5:04 p.m.

You found out that a message encrypted with two different public keys but same modulus yield to the same ciphertexts. Are you able to name the smallest private key to decrypt ciphertexts that were generated with this parameters?
Read more...

 Last edited by: admin on July 22, 2022, 6:11 p.m., edited 11 times in total.

Re: Challenge "RSA: Two different keys - same ciphertext"  

  By: Dano on Aug. 16, 2011, 3:08 a.m.

also ich habe es mit BruteForce gelöst… da ja sonst nie jemand was in die foren schreibt^^

alle D durchprobiert bis die gegenprobe wieder auf das jeweilige C1…C4 kam

mfg Dano

Re: Challenge "RSA: Two different keys - same ciphertext"  

  By: fretty on Aug. 16, 2011, 11:13 a.m.

There is a weakness…quite a major one but you might have to know a little bit of number theory to exploit it.

Re: Challenge "RSA: Two different keys - same ciphertext"  

  By: Gummiboot on Aug. 16, 2011, 9:51 p.m.

Ich verstehe es nicht. Ich habe das gesuchte 'd' und alle anderen Werte
die man braucht um RSA zu zerlegen.
Aber was soll bei:

12306 # 40C3F
15434 # 370AE

der Code sein? Der Rechte Teil ergibt jeweils etwas lesbares der linke Teil nicht.
Hat '#' eine mathematische Bedeutung die ich nicht kenne?
Muß man die vordere Zahl und '#' mit angeben bei der Lösung?
Ich hab jetzt schon 7 Versuche verheizt, mir ist aber schleierhaft was ich mit 'zahl #' anfangen soll…

Re: Challenge "RSA: Two different keys - same ciphertext"  

  By: fretty on Aug. 16, 2011, 9:58 p.m.

It is simply a separator for the ciphertext blocks formed from the encryption.

So you have to do 4 decryptions here.

Re: Challenge "RSA: Two different keys - same ciphertext"  

  By: Gummiboot on Aug. 16, 2011, 10:10 p.m.

thank you!

Re: Challenge "RSA: Two different keys - same ciphertext"  

  By: h3po on Aug. 22, 2011, 10:16 p.m.

can someone please give an example how to enter the solution?
as i understand it, i am supposed to enter the reduced d and then the 4 latter plaintexts.
i tried the hex value in upper and lowercase, with and without "0x"

edit:
strange thing: i mistyped my factor p. yet when reducing d and decrypting with that it lead to the correct plaintext. i don't understand the math behind that xD

Re: Challenge "RSA: Two different keys - same ciphertext"  

  By: TomG on Sept. 16, 2011, 2:13 p.m.

I've the decrypted letters. I also have d1 (as inverse of e1) and a d2 (as inverse of e2). Both decrypt the message correctly.

Further I found (by trying all possibilities) some other d values which decode the encrypted letters (and all other stuff I tried). But the smallest value for d which decodes all encrypted texts correctly for the given e1 and e2 won't be accepted as correct answer.

My solution is the "smallest" d value (consisting of three hex digits without leading 0) and the apparently eight correctly decrypted letters.

Is there something special to be considered by entering the solution?

Re: Challenge "RSA: Two different keys - same ciphertext"  

  By: sam.jerry on March 15, 2012, 7:25 p.m.

We are able to crack d. We also managed to find the
plaintext. But the site does not accept our plaintext. Is there any
specific format that you use to submit the plaintext to the site? Could you
please help us with this?

Thanks,
Sam

Re: Challenge "RSA: Two different keys - same ciphertext"  

  By: be on March 16, 2012, 12:41 a.m.

We are able to crack d. We also managed to find the plaintext. But the site does not accept our plaintext. Is there any specific format that you use to submit the plaintext to the site? Could you please help us with this?

Hello Sam,
the description says:

Send us the hexadecimal value of d and the two different plaintexts as a readable text (all in a row, without blanks).
So if d=A12F3 and the two words are "Lemon" and "Tree", then send in: A12F3LEMONTREE.
I hope this helps. If not, please contact me via mail.
Regards, Be

How to find smallest value of d...  

  By: Illusionist21 on Oct. 27, 2013, 8:51 a.m.

I have got d1 and d2 values and was able to decrypt the Ciphertext…. but how can I find the smallest value of d … any hint??

RSA 2 keys  

  By: ExAstris on May 19, 2018, 11:33 p.m.

Hi all,

I have a problem with the smallest value of d.

In the whole assignment, there is only one modulus N (6A163), and, except for
the examples on the last page, only two e's, e1 (1E437) and e2 (35A47).

From this information and the factorization of N, I get both (two) d's, d1 and d2.

I am able to verify that both CT's are indeed 57A27, and both PT's are OK.
Since there are only 2 d's, I can easily find the smallest.
I used that value throughout the rest of the assignment and found the PT.

First attempt:

Part 1 explicitely asks to find the smallest value of d, using only N, e1 and e2.
Unless I am mistaken, there is only one value of d corresponding to a given e,
so I only have the 2 values of d.

If I use the process described in the example with the above N, e1/e2, I get:

C = M^e1 mod N, where i = 0:e1-1 (CT's of all possible PT's encrypted with e1)
C = M^e2 mod N, where i = 0:e2-1 (CT's of all possible PT's encrypted with e2)

But the pair N, e1 would only yield to d1 (single value), and N, e2 to d2,
so again only two d's.

Second attempt:

Assuming other e values and using the procedure above, I find the corresponding
d values (from the modular inverse), then encode all messages.

In this case,

C[j] = M^e[j] mod N, where i = 0:e[j]-1 and e[j] = 3:lcm(p−1, q−1)-1:2 (all odd values up to the lcm)

Don't know if this makes any sense; I am basing the range for e[j] on the following:

λ(n) = lcm(p−1, q−1), where λ is Carmichael's totient function (the PDF uses lcd?).

e exponents must be chosen such that 1 < e < λ(n) and gcd(e, λ(n)) = 1; i.e., e and λ(n) are coprime.

I take the above into account in my program and find the smallest d in the range 1 < e < λ(n).

I am entering the hex value and the PT (4 parts), all in capital letters and no blanks.
I also tried a few upper values of e, but none of the answers for the smallest d are correct.

Where do I go wrong?
It's probably trivial, but I just don't get it from the wording in the PDF.

Any nudge is appreciated!

Thanks,

Eric**

Re: RSA 2 keys  

  By: be on May 31, 2018, 12:46 a.m.

I have a problem with the smallest value of d.

You are very close. I send you an email.

Re: Challenge  

  By: ExAstris on May 31, 2018, 4:15 p.m.

I forgot to say that I finally solved it!
I just had the wrong exponent d.

Re: How to find smallest value of d...  

  By: RandyWaterhouse on Aug. 19, 2019, 7:32 a.m.

I have got d1 and d2 values and was able to decrypt the Ciphertext…. but how can I find the smallest value of d … any hint??

At this point I tried all values of d between this initial d and down to 2 and checked whether they resulted in the same plaintext. The last d-value found is the smallest one and therefore the answer (together with the plaintext). That was accepted.


Currently 30 guests and 0 members are online.
Powered by the CrypTool project
Contact | Privacy | Imprint
© 2009-2024 MysteryTwister team