Hi everybody!

I've found an easy end extremely fast way to ***** any public exponent, if it is the result of two primes. That means in other words, RSA is actually *****ed.

Before I started the research, I've been looking for the money offered by RSA Labs for their 2048 Bit challenge, but when I found a valid solution for *****ing, I started to worry about.

I tried to get some suggestions from NSA and RSA Labs, but they actually didn't even reply, so I believe they aren't really interested and maybe have found the same solution, because it's terribly easy.

Now I'd like to hear some opinions from you what to do. Mathematics are a philosophical question to me and I'd like to publish the solution. On the other hand, publishing it means to destroy tens of years of studies and maybe there will be no valid RSA substitute.

In other words, many people will loose their jobs, encryption AS-IS with the private/public key will not be valid any more and I really don't know what to do.

:confused:

Any suggestions?

Giovanni

Giovanni,

I have edited the thread to remove reference to a topic that is illegal in this forum, please see my posting at the end of the thread. hutch--
Posted on 2002-05-05 15:49:11 by sch.jnn
if you have cracked the RSA algorithm then by all means you should publish it to the world since else people will have a false sense of security.

Better having to do all over again while staying secure then being not secure at all. (or even worse: thinking you're secure while in reality you're not)

That's my personal opinion on such a matter.
Posted on 2002-05-05 15:58:08 by Hiroshimator
Does this break involve Win32ASM?

Besides i allways expected government algorithms to have backdoors its only logic they will not want to loose time decrypting others messages.

AFAIK serious protections use propretary algorithms never revealed to the public ...
Posted on 2002-05-05 16:16:49 by BogdanOntanu
why not let it be you. sooner or later somone intelligent enough would figure it out. maybe someone already has figured it out and used the same method as you. maybe that person is using it for unlawful activities. the possibility is there and if you dont let everyone in on it those who are using that encryption sceam are volnurable. if you actually figured out, its more of an obligation to let everyone know than anything else.
Posted on 2002-05-05 16:19:17 by smurf
How about a little demonstration first? ;)

Public exponent:
65537

Public modulus:
19865587416304612150728302784331791297706084718427776781686001670583455772759169015371775080194368343296756326717567210622842259025993922807289983749394009489041321995601422359062765078032665869134047079262202558684574084020054322235150617792242426877795079435106074062378070215811507932959372230827655425812006962154822675491927457065206398832298250851350888711326542997440472752840678932576246583034110055285387756106958347332703658442626710552683525816265771310099259553594115469075946519415025317319245367926383242165568425037255816154363407162636170422238800205585863317774893070681467334885453310812512126105233

Sorry, but I have to see it to believe ;)

AFAIK serious protections use propretary algorithms never revealed to the public ...

That's called security by obscurity ;)
Posted on 2002-05-05 16:20:22 by Tola
woohoo i just cracked your encryption Tola! here it is:

19865587416304612150728302784331791297706084718427
77678168600167058345577275916901537177508019436834
3291111111SMURF11111112822590259939228172899837493
94009489111111IS1111111112765078032665869134047
07926220255868457408111111111VERY11111111224242687
77950794351060740623780702158115079329593722308276
55425111111111VERY11111111111157065206398832298250
85135088871132654299744047275284067893257624658303
41100552853877561069583473327036584426267105526835
258162657711111111111COOL1111111111946519415025317
31924536792638324216556842503725581615436340716263
61704222388002055858633177748930706814673348854533
10812512126105233
Posted on 2002-05-05 16:29:07 by smurf
ROFL
Posted on 2002-05-05 16:37:20 by Tola
Just post it here :)
Posted on 2002-05-05 17:06:03 by Kudos

Just post it here :)


Nice. Any opinion or suggestion?

Giovanni
Posted on 2002-05-05 17:16:48 by sch.jnn
Hi Giovanni !

Don't be afraid to publish it. It's better everyone knows about this leck than is being kept in mind, he is secure ...

Also I don't believe that isn't the mysterium as it seems to be. Many numerical interested mathematicians should have found this, too.

And I don't believe that many will lose their job, because they are needed to find other solutions for protecting. (It would cost much more money to teach new workers than let the "older" ones learning some weeks)

Greetings, Caleb
Posted on 2002-05-05 17:17:59 by Caleb
security through obscurity has never really worked... the best you
can do is slow down attackers. Yeah, even using proprietary *hardware*
will be broken, if your attackers are serious enough.
Posted on 2002-05-05 17:40:26 by f0dder
I love your jokes!

Sorry I won't prove any number in this place, since you might let me do the solution for the RSA challenge(s) and take some money. I am not talking here about how I could solve an "unsolvable" question, but I appreciate opinions.

Tola, a little hint: I don't need the modula. The RSA challenges show a big number (product of 2 strong primes = public exponent) and all they want is those 2 primes.

---

http://www.rsasecurity.com/rsalabs/challenges/factoring/numbers.html

Hint to all: say you don't know anything about primes, and somebody gives you the RSA-576 bit number:

18819881292060796383869723946165043980716356337941
73827007633564229888597152346654853190606065047430
45317388011303396716199692321205734031879550656996
221305168759307650257059

How could you find the 2 primes?

Take paper and pencil, try 17 * 11, and see what happens. Try another couple of known numbers, and compare. There is happening something very obvious, but you *must* do it by hand, otherwise you'll miss it. If you see *what* happens, you'll solve the number above in, let's say, 1 week just with paper and pencil, as I did. But it took me more than *6 months* to see what happens. Anyway it works with any product of 2 primes.

Programming the algo isn't so easy, though. Maybe I am not that intelligent :)

Giovanni
Posted on 2002-05-05 17:42:21 by sch.jnn
I don't believe you've found a solution to factoring large numbers composed of the product of two large primes. If you have, prove yourself. Besides what does this have to do with asm?
Posted on 2002-05-05 17:47:08 by Asm_Freak
If he *has* done it (which sounds pretty unlikely to me), it doens't
matter at all if this is related to asm or not - it will be very interesting.

Btw, what's the deal with two threads? Double posting sucks.

sch.jnn, put your money where your mouth is and give us the
solution for tola's number...
Posted on 2002-05-05 17:54:40 by f0dder
sch.jnn, I have generously moved this to the Algo section - generous because there is a hint of an algo. Also, I have merged in the double post. Do you know how many people have worked on this problem? I once believe that I found a way to tri-sect and angle with straight edge and compass - it took me a week to prove myself wrong. :) Please, post more and we will help you work through your solution.
Posted on 2002-05-05 17:57:48 by bitRAKE
Sorry I won't prove any number in this place, since you might let me do the solution for the RSA challenge(s) and take some money.

Don't challenges like this require you to show how you worked it out to claim the money?
Posted on 2002-05-05 18:05:05 by Kudos
Quotes:

why not let it be you. sooner or later somone intelligent enough would figure it out. maybe someone already has figured it out and used the same method as you. maybe that person is using it for unlawful activities. the possibility is there and if you dont let everyone in on it those who are using that encryption sceam are volnurable. if you actually figured out, its more of an obligation to let everyone know than anything else.

---

Besides i allways expected government algorithms to have backdoors its only logic they will not want to loose time decrypting others messages.

---

if you have cracked the RSA algorithm then by all means you should publish it to the world since else people will have a false sense of security.
Better having to do all over again while staying secure then being not secure at all. (or even worse: thinking you're secure while in reality you're not)
That's my personal opinion on such a matter.

===


Actually I believe someone has found the same solution, because it doesn't need any special knowledge. Just manual multiplying is fine. This guy now may be closed into NSA Labs.

I am split between publishing and not. Many people believe RSA is the best algo found for public key encryption, and I do so, too. In the end it's RSA's fault to pay solutions. If these numbers weren't there, I never tried to solve them.

---

Some of you pointed out, publishing would be appreciated by people who actually trust RSA, or people who have some doubt but don't know how to prove a weakness. If I put myself into those people, I admit I'd like to know what else we could do except factoring. I've to think about it.

Thanks for all opinions yet!

Giovanni
Posted on 2002-05-05 18:08:48 by sch.jnn

Tola, a little hint: I don't need the modula. The RSA challenges show a big number (product of 2 strong primes = public exponent) and all they want is those 2 primes.


the modulus i presented to you above actually is the product of 2 primes (strong ones, that is, if that matters to you).
the public exponent is a pretty small fixed number (usually 3 or 65537, speeds up the calculations).
Posted on 2002-05-05 18:08:56 by Tola


Don't challenges like this require you to show how you worked it out to claim the money?


No, they don't. You may do this, if you like, and usually you do, because you become famous. If you have a look at the least solved challenge, you'll find out nothing special. Just a general Sieve and hundreds of coworkers, and a mainframe for the final task.

So if you get from somewhere these 2 primes you may claim them as your own. So far RSA is proof :)

Giovanni
Posted on 2002-05-05 18:15:01 by sch.jnn

I don't believe you've found a solution to factoring large numbers composed of the product of two large primes. If you have, prove yourself. Besides what does this have to do with asm?


I don't factor.

I wrote myself a big number library to prove if I were right. All other explainings would be equivalent to publishing. Would you like the code? All pure ASM. Wait a bit, today I answer opinions and reflect, and some more day's too. Later we'll see where to attach the code, ok?

Giovanni
Posted on 2002-05-05 18:24:03 by sch.jnn