Challenge "RSA with Special d"

Challenge "RSA with Special d"  

  By: admin on May 7, 2010, 2:29 p.m.

It is well known that RSA with a small private key is insecure. The company, Smart, Inc. has decided to try using special private keys that are large but have a small Hamming weight in order to speed up decryptions and signature generation. The question is whether these keys are safe. Try to reconstruct the private key d from the public parameters.The codeword for this challenge is the private key d in decimal notation.

 Last edited by: admin on Oct. 31, 2021, 2:54 a.m., edited 1 time in total.

Re: Challenge "RSA with special d"  

  By: nobody on Oct. 22, 2010, 7:05 p.m.

`Fri Oct 22 18:54:09 2010: success: d =1**************************

It would be much more fun if we get a nice message with some interesting information about crypto history or something like that as a reward for our hard work.

Nice one! Please more =)

Re: Challenge "RSA with special d"  

  By: susannah on March 19, 2011, 1:25 a.m.

I am reading the paper Wiener_RSA_Attack –
Cryptanalysis of Short RSA Secret Exponents
which requires continued fraction algorithm. Found it sort of hard.

am I on the right track?

Re: Challenge "RSA with special d"  

  By: mazze on March 21, 2011, 7:01 a.m.

An appropriate extension of Wiener's original attack should work.

However, personally I prefer to use lattices instead of the continued fraction expansion. Maybe try to realize Wiener's attack using lattices and then think about how to attack the special form of the secret key in this case.


Re: Challenge "RSA with special d"  

  By: susannah on March 21, 2011, 9:16 a.m.

I know the wiener's attack only works when log(d)< 1/4log(N). In this challenge d = 400 bits and N = 302 * 8 (bits). This challenge doesn't satisfy. After running my wiener's implementation, I get the putative encryption exponent is 191.

What is the appropriate way to extend the wiener's attack? Can I have any hint.


Re: Challenge "RSA with special d"  

  By: nobody on March 21, 2011, 11:38 a.m.


To solve the challenge you need a little creativity. Otherwise it would not be a level 3 challenge.

Have a look at the structure of d and try to combine it with Mazzes hint.


Re: Challenge "RSA with special d"  

  By: susannah on March 21, 2011, 6:32 p.m.

thanks for your reply. Any of your hint to resolving it is very valuable to me.

Implement Wiener's paper and do the calculation step by step. The impl works on
(160523347,60728973) —-> d = 37
(8973,2621)—-> d = 5
looks correctly. But, for the input of this challenge, its output is 191.
Obviously, it is wrong.

The main reason is here d has special structure as it is indicated in the problem statement:
it totally has 400 bits: the first bit is on, 3 bits are set out of the next 309 bits, the final 90 bits are really random.

I am guessing 90 bits are small enough satisfy Wiener's attack requirement. But 191 is only 10111111 (assuming my impl is 100% correct), not enough. And the expansion part must deal with the 3 out 309 bits. It is one permutation Choose 3 out of 309. It is related to which part of Wiener's attack?

I am given the hint that using lattice instead of continued fraction in wiener's attack. I understand the key of Wiener's attack is to find the numerator and denominator close to e/N. When talking "lattice", are we talking about "lattice reduction algorithm"? If yes, I need to figure out what is the input and output of L here. And the relationship between L's output and "d".

Re: Challenge "RSA with Special d"  

  By: fretty on Aug. 30, 2011, 10:50 p.m.

Just to clarify, when you say "set" do you mean "has bit value 1"?

In other words does the challenge mean to say that out of those 309 middle bits, only 3 of them are 1…or does it mean that the company decides the values of those 3 bits for everyone and the other 306 of the 309 can be anything?

Re: Challenge "RSA with Special d"  

  By: Bart13 on July 23, 2012, 11:06 a.m.

Yes, lattices did the trick for me.
Very good challenge; I learned a great deal from it !

Re: Challenge  

  By: fmoraes on Nov. 20, 2013, 10:31 p.m.

I'd like to work on this challenge and I understand some of the basics but lattices still hurt my head. Can you some help me understand how to get started better? I can see the basics of what needs to be done, but I have trouble translating that into a program.

Currently 10 guests and 0 members are online.
Powered by the CrypTool project
© 2009-2021 MysteryTwister team