|
A crypto challenge from nneonneo
|
|
Well, having had so much fun doing Gendou's crypto challenges, I thought I might try my hand at making one ^^ Alice and Bob are two very important people in cryptography. Alice is always trying to send Bob some secret message, and trying all these neat crypto techniques. But Bob rarely gets to send anything -- this needs to change! So, Bob has decided to try his hand at some cryptography. He's selected the RSA cryptosystem, and obtained Alice's key. Alice's public modulus is (linewrapped to avoid breaking layout) 186510729383594485418966876583305670827225088191612574891087751678084367585531520638706391511228289313248269554322720505 126495204308005051097443191758746506218412016524112851994225528583552754202810274300847075466296534656718125234427749661 233440048626045519651233820892862606037652209482189962386893501202650481195714107523326609122454990989042732274537349194 625695822944651665070740305755189723096947843170150916737194898261309664370978163508588963012466712619453496019559662599 183169043664087112303223992970630351734766464439811640674128302087190768904359664039630039909325765670185173266388748377 59727691864189851 and her public encryption exponent is 3. Bob encrypts a message as follows: he picks a message m, and expresses its ASCII values as a number (e.g. "hello" is 0x68656c6c6f). He then takes the number to the power of the public exponent (3), and takes the result mod the public modulus. Alice can decrypt the message by using her private key, which consists of the two large prime factors of the modulus combined with a decryption exponent. For reference, the encryption of "hello" under this scheme is 90143305010218464651239068244550223. Bob's selected an 86-byte long message and encrypted it with this scheme. He sends Alice the encrypted message: 708991467069033373432585442354043047233174676369336748476568667955286929237250210149180295921072056010377697483590372018 892804068704565523181967286840832741401209516610478167743534425251454095074353701092767126925062619088257512291571703080 662638273623174259793014384162271952361442185475745606297884118137820889830024246887344278127336237379143032708078623976 308250962261399904548426426829856003457362445339984698493638658913600877224555409786761237275622666077202953921207264836 127880283534948772314187097644830324928892340488916314200447320051718744396924979638232737623688640265570355860307477407 8012426812313158 You've intercepted this message, and you really want to know what Bob has to say. Figure it out, and PM me with your answer (and code, if you wrote it). Good luck! (Any and all hints are given in the challenge statement above. Clarification requests are welcome.) |
|
Re: A crypto challenge from nneonneo
Link |
by
on 2010-12-20 16:23:17 (edited 2010-12-20 18:16:08)
|
Oh hell yes! I'll give it a shot.m = cd % nThe unknown on the right hand side is d, Alice's private key.I can attack her key by trying to replay the "hello" message. Then, I can use it along with the known values of c and n to compute m. Running brute force for d against the encrypted "hello" message. Will you give me an upper bound on the private key so I stop if I made a mistake? 
|
|
Re: A crypto challenge from nneonneo
|
| d is not prime (in fact, its last digit is a 5). I can tell you that p and q are 309 decimal digits each, and d is 617 decimal digits, though (hint) you do not need to know p, q or d in order to solve this challenge. |
|
Re: A crypto challenge from nneonneo
Link |
by
on 2010-12-20 18:17:21 (edited 2010-12-20 19:42:18)
|
|
Oh, so small e and small m are easy to decrypt given the large value of n. Sweet! OK, so I'm not getting the right answer. The tricky part is taking the cube root of the cipher text. My cube root algorithm might be giving me bad results. When I run echo 'e(l(...)/3)' | bc -l I get a nice looking number, but it doesn't appear to be the right answer...
|
|
Re: A crypto challenge from nneonneo
|
| While the "hello" encryption above is a perfect cube, the longer encrypted message might not be... |
|
Re: A crypto challenge from nneonneo
Link |
by
on 2010-12-20 21:47:54 (edited 2010-12-21 12:49:50)
|
|
Right, so I keep adding n then taking the cube root until I find a plain text message, but again, I've not found it after many iterations (10,000). Question: does the message c contain any ASCII characters aside from 32 to 127?
|
|
Re: A crypto challenge from nneonneo
|
|
The message is pure ASCII, 32 to 127 only. (Also, your second line may be construed as too much of a hint.) |
|
Re: A crypto challenge from nneonneo
Link |
by
on 2010-12-21 02:23:00 (edited 2010-12-21 02:36:34)
|
|
I give up. It doesn't work in PHP using BCMath, or in Python using Decimal. Update: I guess Python 2.5 doesn't support non-integer exponents to the Decimal function power(), and is also missing the Decimal function ln(), so it's basically impossible to do large cube roots. I'll have to try Python 2.7 at work tomorrow. This is a mean challenge.
|
|
Re: A crypto challenge from nneonneo
|
|
From the documentation of the decimal library: Changed in version 2.6: y may now be nonintegral in x**y. Stricter requirements for the three-argument version. Well, it looks like you'll get your wish. |
|
Re: A crypto challenge from nneonneo
Link |
by
on 2010-12-21 12:50:40 (edited 2010-12-21 13:01:42)
|
OK I Finally got it here at work, where we have Python 2.6!WHOO!Would you mind if I used something similar to this as cryptography challenge #64?
|
|
Re: A crypto challenge from nneonneo
|
| Yes, feel free to use this to make a crypto challenge. I would simply appreciate it if you could credit me on the challenge page :) |