NaN, what sch.jnn is implying is: it is simplier than that:

look at it significant bit by significant bit.....

B, gotta go ARRRRRRgh
Posted on 2002-05-07 10:41:07 by Brad
If I could I would light two lamps!


To me this is a Deeeeeeeeply rucursive solution. And through rucursive concultions, you can expand outward to the final two "large" primes. Since if i was able to get '51', i would know that P1 == 17. And then i can subtract this from the 221 key value and know the result is x * 10 * P1. All of which is solveable. Just need to 'recurse' to it.

My problem with this idea, is i cant figure out your big-number library. I try to run it in VB and it just 'flashes' quickly a few numbers and the window is gone before i realize it. (( Im too lazy to learn VB... :( ))


All your suspects are very close. Especially about the recursive solution. And something else. Let us see if other guys help you see.

My BNLib has nothing to do except for verifying (yet) the deeper laying events. Please press Ctrl+G before the program start, to see the check results in VB. Anyway I believe your samples could be solved without it :)

Giovanni
Posted on 2002-05-07 10:52:04 by sch.jnn
Giovanni, discovery is very fun stuff! :alright:
Posted on 2002-05-07 11:02:29 by bitRAKE

Giovanni, discovery is very fun stuff! :alright:


I do agree.

People have a nice evening, I'm off.

Giovanni
Posted on 2002-05-07 11:11:16 by sch.jnn
i think i dont understand.


is this what you mean ?


bye

eko
Posted on 2002-05-07 13:26:47 by eko
Hi, all,

I think you need another little hint: if you write down 17 * 11 or 13 * 11 or 23 * 11, or n * 11, is there anything happening which is too obvious to see :) ? Before you go and sum?

Giovanni
Posted on 2002-05-07 15:19:59 by sch.jnn
hi

hey, stop looking for something that doesn' t exist. there is nothing 'graphical', or 'obvious' you would find that the army of mathematicians working on RSAP or IFP more generally wouldn' t have found. particularly, we don' t care 'bout the 'strange things happening when multiplying by 11', 'coz if i ever find a RSA modulo that has 11 in factor, i would laugh alot (well, i was told that a shareware protected by asprotect had an even modulo...) =). anyway, it' s obvious this guy is pulling your leg, saying 'yeah, you' re very close' to whatever dumb things you might say, or 'congratulations' to an obvious remark. that' s just not serious =). just factor a reasonnably long rsa modulo, and we' ll be convinced. or keep on saying 'i doubt if i publish the solution or not', and we won' t trust a word of what you say =)
enough time lost in aporethical talks =)

by the way, if you' re looking for totally random remarks :
have you noticed that 17 is 11h in hexadecimal, maybe this can help ! 17*11 is in fact 11h * 11 !

oh by the way, there is no trapdoor in RSA, what is called a trapdoor (or backdoor) in cryptosystems, is here in fact the fact that knowing p and q allow to easily decipher, there is no magic algorithm that would permit the NSA to decrypt all RSA messages =)

hehehhehehehehhehehhe
anyway, this thread made me laugh alot, and i' m not the only one =) there should be more threads just like this one, why not one on DLP, ECDLP, and maybe you can invent and break ECRSA ? maybe we can wonder why toast always fall on the butter ? maybe the answer is easy ? maybe we can factor tomato soup ? maybe we can crack a cornflake ? maybe we can start to talk seriously, and learn cryptography =)))))

sorry =)
Posted on 2002-05-07 15:40:49 by roy
ouch
Posted on 2002-05-07 15:57:16 by Will

hi

hey, stop looking for something that doesn' t exist. there is nothing 'graphical', or 'obvious' you would find that the army of mathematicians working on RSAP or IFP more generally wouldn' t have found. particularly, we don' t care 'bout the 'strange things happening when multiplying by 11', 'coz if i ever find a RSA modulo that has 11 in factor, i would laugh alot (well, i was told that a shareware protected by asprotect had an even modulo...) =). anyway, it' s obvious this guy is pulling your leg, saying 'yeah, you' re very close' to whatever dumb things you might say, or 'congratulations' to an obvious remark. that' s just not serious =). just factor a reasonnably long rsa modulo, and we' ll be convinced. or keep on saying 'i doubt if i publish the solution or not', and we won' t trust a word of what you say =)
enough time lost in aporethical talks =)


I believe you have a better research going. Could you please explain us how to find a formula starting from, let' say, an 8192 Bit product from pq? I am sure you own a huge mainframe factory and have some testing done ;)

I am watching with attention what's going on here, and like to encourage people to look to an conventionally unsolvable problem from another point of view. But I am not going to give my knowledge away for nothing, at least I want to see the concept catched by a few interested. If you're looking for a more easy solution, please switch to another thread.

Maybe there is no need to publish any solution, and it looks like as if we had some round robins who could check it out in a tenth of the time it took for my rosted brain. I am playing, that's true, but not with people. My game are numbers, as it has been to Phytagoras or some other well known guys. If you aren't fixed on brute force factoring and eyes wide open, you must admit, that reverse engineering of numbers is a world wide practice, and many surprising facts were discovered. Lately there was even a film about John Nash, who solved some chaotic equations (he'll will laugh about this expression, I'm sure).

Anyway, you're not obligged to follow this thread with interest, as you actually did, and believe the stars pinned on the sky.

Giovanni

PS: I am sure somebody has found something. There is no doubt at all.
Posted on 2002-05-07 16:09:21 by sch.jnn
i am even leeter than this guy..me can cr4ck rsa with special hardware used by nasa called zx spectrum...just a small modification in the zx hardware and u can make
of it a damn fast bruteforcer! (err, imagine a 1000ghz athlon)
now, this is very easy and someone might know/have done that already (most likely)
it's really easy! u don't have to be a hardware expert like me to do this!
the bruteforce algo ist in 48k basic, but really fast moth3r f*cker..i tell u..oh, really fast, dude!
now i want u ppl to figure out what i changed in the zx hardware in order to make it that strong, before i actually tell u how this is done! (it's obvious...really easy..u won't believe how easy this is done)
Posted on 2002-05-07 17:07:14 by DZA
now I'm feeling down because it's too hard for me :(


;(
Posted on 2002-05-07 17:32:22 by Hiroshimator

maybe we can wonder why toast always fall on the butter ?


actually, my physics class was given an article from a newspaper about this... it just has to do with angular momentum and the height of a table (and how if ppl were a couple of feet taller than we already are, we would topple with disasterous results... which means, our toast will always fall butter side down)

the article also gave some suggestions for stopping it from falling... i'll try to find it sometime and post it.
Posted on 2002-05-07 18:47:27 by jademtech
the article also gave some suggestions for stopping it from falling... i'll try to find it sometime and post it.


I think i read this somewhere... if i recall, is suggested to spread the butter on the toast using a table instead of with the palm of your hand.

:grin: NaN :grin:
Posted on 2002-05-07 23:00:30 by NaN
What!!! no-one has solved it yet???? :)

Roy???....It's a good exercise.....(especially when no-one can prove the contrary).....

I'll bet God could solve it....:grin:


Added:

Let's say sch.jnn is playing a game with us...or he does have an answer.....or he has a partial answer, and is trying to get us to help....or he thinks he has the right answer, yet not proven......either way, he has got us thinking the problem...which likely would have been dis-missed without his colorful presentation... :)...hat's off; sch.jnn

B
Posted on 2002-05-07 23:13:18 by Brad
Okay, here's another interesting thing, this time about multiplication.

When you multiply two numbers:
11*11:
you get:
121

or:
97*97
you get
9409

or:
101*97:
9797



So it means that, the number of significant digits a product has is either:
(let m=significant digits of first factor, n= significant digits of second factor, p=significant digits of product)
p=m+n, or
p=m+n-1

It is impossible for the number of significant digits to vary very much. It's either the sum of the significant digits of the factors, or the sum of the significant digits of the factors, minus one.

So basically, if we know that the product has, say, 56 significant bits, we can be sure that the sum of the significant digits of the factors is equal to 56 or 57.

Which brings us to a discussion of pass codes and keys. How many of you have ever had a password such as AAAAAAA? or even AAAAAAAB?

This leads us to an analysis of the human brain. *Nobody* uses such lame passwords because *any cr@cker* will go through that password first. So *real cr@ckers* don't check those passwords anymore. Since we want to reduce our load, *we* don't check the obvious, since the obvious is avoided by *everyone.*

In much the same way, *nobody* would use a private key that is only 8-bits significant. Thus, the probability that a public key with 56-bits significant, having a 48/49-bit significant prime1 and an 8-bit significant prime2 is not very high.

It is more likely that the prime1 and prime2 will have p/2 significant figures (p is still the number of significant bits of the public key). So a 56-bit significant public key will, most likely, have two 28-bit prime factors, maybe a 28-bit and a 29-bit significant prime factors. Thus, when cracking a p-bit significant public key, we must start with p/2-bit primes, then work outward, to p/2 and p/2+1, p/2-1 and p/2+1, etc.

Ne?
Posted on 2002-05-07 23:50:54 by AmkG
It is more likely that the prime1 and prime2 will have p/2 significant figures


Well, though I'm going to the discussion.
But I don't reveal any secret when mention of very very old Fermat algorithm (I submited some time ago 32 bit tutoring version of it), that very fast find the two multipliers from their product if the two multiplyers has closed to each other number of
digits. To say more precisely - close to each other values.

I also can write some math proof (though I have no idea Fermat if proved it).
That's why in any Good RSA algo using primes with closed values is avoided.

Well the thread has nothing to do with asm algos.
Maybe at least it will do something with math?
I didn't see any formulas, only talks. 1700 views a lot of replies and NOT A BIT OF INFO.

I'm not agains math ideas even though they may be false or sholastic (I'm not sure of spelling).
But at least it should be expressed.
Posted on 2002-05-08 01:27:12 by The Svin



That's why in any Good RSA algo using primes with closed values is avoided.


(I assume you meen 'closed' as having close values, with nearly equal significant digits.)

REALLY?

GOOD! We can reduce it even more! AVOID prime factors with close values, we can skip the two 28-bit primes and maybe start with the 28-bit and 29-bit prime factors, maybe even 27-bit and 29-bit primes.

Maybe we should put this in The Heap or something... Heck, this thing probably deserves its own forum... although it might be wise to inform everyone before moving it...
Posted on 2002-05-08 01:54:20 by AmkG
maybe even 27-bit and 29-bit primes


Why not 15 bit or 13?

Our board need primary shcool.
RSA is not for us.
Posted on 2002-05-08 03:30:55 by The Svin
I see our discussion becomes a bit messy. It looks like to re-invent the General Prime Sieve, which actually tries to simplify a brute force Tomato Soup Attack. From this point Roy is right. Nobody would be able to separate the tomatoes from the soup :)

The discovery *is* unconventional, and has nothing to do with determining the approx. size of the prime factors. If pq were m * 1, my algo would find or m, or 1. I believe no-one would use such a modula, but you never know (in this case, m would be a prime).

In any case, the estimated size of the primes could be a help for timing reasons, since pq 10 digit primes will produce 10 (unknown) numbers to sum, with one constant.

Whatever you're going to do, you'll need another *vague* constant, or else you're not able to derive a rule. I know I am boring, but you should have a photographical look at 17 * 11. Pay attention to the butter toast in the mean time! It is not the 11 which is important though, as Roy subspected (this is why he read this thread with interest), but the 17. In fact, 11 could be substituted by any number, but 11 is the easiest. Well, if you like, try to use 111 or 1111 to evidence the fact ;)

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

Well the thread has nothing to do with asm algos.
Maybe at least it will do something with math?
I didn't see any formulas, only talks. 1700 views a lot of replies and NOT A BIT OF INFO.

I'm not agains math ideas even though they may be false or sholastic (I'm not sure of spelling).
But at least it should be expressed.


c^n = a^2 + b^2, where c is our constant, where n is the probability you'll guess what the formula is talking about, where a is a-bit-of-patience, and b is the propagation base :alright:

I could actually talk about my ping-pong algo, but could you follow it if you miss the essentials of something we do a thousand times a day without caring *what* we're doing? I admit it's a stupid question I am asking for, and have nothing to expect than stupid answers. But maybe one of these replies will be the right one.

If you are into coding, you might have wondered how it could happen not to see something evident, such as a missing or wrong variable, inverted order of sequence. This happens to everybody who enjoys seriously his work. This implies you're looking at it not only as if it was only a source of money, but a source of new knowledge too.

If I would simply write down the almost endless listing of the RSA-576 reverse engineering, it will take you years to check it out, except if you're able to see some redundance. Still. if you'll see it, you may not understand why. All I want is to make sure we follow the right way, before loosing us in the jungle of multiple nested recursive carry rollbacks and running hot our needle printer ;)

All what I told here is actually enough to solve the problem, but it's somehow cryptic.

Giovanni
Posted on 2002-05-08 05:11:56 by sch.jnn