Hardware

Ask something
Discussion Locked

Integer factorization and RSA problem

0 helpful
42 replies

by brother martin de porres 1 view

Closed to new repliesThis discussion is closed. It stays readable, but it takes no new replies.

The solution to factorization of 'dual-prime' composite numbers, is so trivial, that the mind boggles at this method of encryption. It is about as secure as a wet paper bag of rotten eggs! I will personally be posting the factors of all $625,000 worth of RSA challenge numbers on Wikipedia, just to prove the point!
In 1974, a similar system passed through my in-tray, while working for RSRE (Royal Signals Research Establishment) It foxed us for a few days I admit, but the trivial algebraic solution just jumped off the page. We were all sworn to secrecy so it was impossible to alert the general public, as to how dangerous this weak method of encryption actally was. Now that our UK 30 year rule is well over, I would be happy to share the solution with any interested parties. You may kick yourself for not seeing it first. Grade School algebra. you don't even need asymptotes! A direct factorization is possible with any arbitrary precision calculator like BigCalc. CAVEAT!

42 replies

by santeewelding

He feels that a revealment like this deserves its own post, the way that "dual prime" with respect to "composite" deserved the quotes.

by brother martin de porres

Thanks for the support 'santeewelding'. That is exactly my point and purpose. This 25 digit dual-prime composite, that I constructed with the help of my telephone directory and a pin. should illustrate the point. You will need Windows Calculator to follow the protocol. First enter:-
2,612,064,319,773,176,994,885,077

I will skip the explanation as to how we deduce that the ratio of the two primes, is about 137/207. The method involves an algorithm and a test of 'squareness'. We know if the two primes 'P' and 'Q' form a rectangle of given proportions, a similar much smaller rectangle with the same proportions, when multiplied together, the product is pseudo-square.

We also know that:-
(P + Q)^2 = 4(P x Q) + (P - Q)^2,

I said 'Trivial Algebra' and I meant it!

2612064319773176994885077 x (137 x 207)

= 74075532044447526397945898643

The square root of that is:-
272168205425335.32015070563454555

So let's try 272168205425336...Nope!
Try again 272168205425337...Nope!
Try Again 272168205425338...BINGO! EUREKA!

272168205425338 x 272168205425338
= 74075532044448985137492414244

And 74075532044448985137492414244 minus
74075532044447526397945898643 is equal to

1458739546515601

And the square root of that is exactly:-
38193449

EUREKA!...The rest is trivial algebra.
I will post the factors later, for those who want to work it out for themselves.
Cheers!

by brother martin de porres

Thanks for asking Palmerto, I guess my concern, was the startling coincidence of 9/11 and 7/7 London, both engaged in 'Exercises' that bore an almost exact similarity to the 'actual terrorist attacks!'

It is hard to dismiss the distinct possiblity that security was compromised on both occasions. What better way to sew confusion, than to duplicate the 'exersize' with 'reality'? Secure communications can be a matter of life and death!

by charliespencer

because I still have no idea what your talking about or what it has to do with terrorist attacks. But as long as you two are happy, don't mind me.

by brother martin de porres

Oops! Thank you for pulling me up! I quite aggree 'Factor' is correct.

So as promised here are the 'Factors'

272168205425338 - 38193449 = 272168167231889

272168167231889 / 137 = 1986628957897

2612064319773176994885077 / 1986628957897 = 1314822432941

1314822432941 & 1986628957897 "Factors!"

by santeewelding

How did you come by the composite, 2,612,064,319,..? Does your procedure work only for that composite, with those primes, or does it represent the general solution for the series, predictive arbitrarily far out? (in which case you will become famous for all human time)

The "prime rectangle" is neat. Hadn't seen that before.

by brother martin de porres

Thanks 'santeewelding', for keeping this little orphan of a discussion going. I fear I am more likely to become 'imfamous!', "The man who opened the back door into every bank account in the world!" To answer your question, I derived the composite with the help of my telephone directory, using a pin. I select three numbers one each side and the middle integer. It's about as random as it gets. Then I used Bcalc to find the nearest prime. It has a neat factor facility. The solution is 'general' as you asked.

I will describe the 'goldilocks' method of selecting a suitable small rectangle, in more detail later, again it involves trivial algebra, It can be a little tedious, when the composite is very large, say a 256 bit composite or over. As often happens, by a fluke, I struck lucky with quite a small ratio. I looked at the 2,612,064...and immediately figured it was bang in the middle of the ubiquitous 'bell-curve' a ratio of about 2:3, and 26 just screamed out 13:20. That looked square enough so 39 +6 & 60 + 8 revealed that 45:68 was even better. 45 x 3 = 135, & 68 x 3 = 204, now add the 2:3 ratio to get 137:207...it just happened to be a winner!

If you have say a 40 digit composite, there are deterministic methods of finding the front and back ten digits, the middle 20 will remain a mystery! however those front ten digits are a great help starting the algorithm going. Another feature of this method, is that one is spoilt for choice as to which small ratio to use. As the composite increases in size, the number of suitable 'small ratios', goes into the zillions. some of those RSA challenge numbers can be unscrambled with more small ratios, than there are atoms in our universe...and then some! A graphic explanation of this, would be to 'square' the dual-prime composite, so that we had a gigantic matrix of rectangles. P rectangles times Q rectangles. Now follow the diagonal line from top corner to bottom corner, every time that diagonal approximately coincides with one of the corners of a rectangle, Bingo! we have yet another suitable ratio to unscramble our dual prime composite. Indeed millions of integers to either side of where the diagonal intersected a rectangle could also be suitable with a suffiently large dual-prime composite. Size actually makes the problem MORE! easy to solve! (With computer software)

R.S.R.E. way back in 1974 thought this was far too insecure to merit consideration as an encryption protocol, but needless to say, were very happy for the public to adopt it. THANKS for all the useful information over the years! The Military like to know what is brewing in the world.
Cheers!
~Alastair Carnegie (Military Chaplain)

by santeewelding

That is, my perception of you laboring by a lone candle over parchment removed from the profane, the "Brother" and the "Senior Manager" meaning elevated rank in the Order.

Seems now there is the glow of a monitor illuminating your work, the candle my quaint imagination.

by l. bontes

74037563479561712828046796097429573142593188889231289084936232638972765034028266276891996419625117843995894330502127585370118968098286733173273108930900552505116877063299072396380786710086096962537934650563796359

It's RSA-704. I don't really believe what you mentioned above gives an easy general solution for RSA size numbers, since you've picked the example number yourself. But it would be extremely interesting if it is faster than GNFS.

by l. bontes

"and immediately figured it was bang in the middle of the ubiquitous 'bell-curve' a ratio of about 2:3"

What is this ubiquitous 'bell-curve'?

by brother martin de porres

Credit where credit is due, 'santeewelding'.

I am just the pupil, Paul Erdős was the 'Master'. Airdish Pal said he would pray for my dead soul. He regarded all 'applied mathematicians' as dead! (to the beauty of 'Pure Mathematics')

by brother martin de porres

I had to laugh at your description of me, and it's reasonably close to the mark. I write letters with a cut quill from a Himalayan Goose! My dear boss, Merlin Hay, 24th Earl of Erroll, as well as being Head of Her Majesty's Household Scotland, Lord High Constable, Knight Marshal etc. is also our UK parliamentary spokesperson on computer related issues. We were both computer geeks when only in short trousers. We both have a keen interest in military affairs. Thankfully my job description is about 'preventing' war. I have not had much success of late! The elevated rank, owes much to buoyancy, dead fish tend to float to the top of the tank, where they can make one hell of a stink! On that point, I keep my powder dry, and seldom invoke authority. Our job is not to interfere, but rather to oil the wheels, if and when asked to do so.

I mentioned that military intel, was quite comprehensive, the only intel the military act upon, is when it impacts military affairs. Like the three monkeys, we see no evil, hear no evil and speak no evil. I personally hope that as technology advances, computers can do the job for us. just flag up points of interest. I have no objections to an inanimate object invading my privacy. Sadly in today's world, that is increasingly necessary. The military must never forget their primary purpose, which is to protect the citizenry. If they don't, I can make that aweful stink!

by brother martin de porres

On the subject of 'quill pens', RSA type encryption does have a useful application with strong identification, like signing messages. "The Roadblock Problem", shows that there is a limit on time, and it can be proved to have a lower bound 2^N. for 'any' algorithm whatsoever. The example dual-prime composite I gave, would be one from the reject pile. By a fluke that 'diagonal' hit close to bulls-eye, at just 137:207. This is a common occurrence, and a lesson to would-be DIY security geeks! and that example is not the only weak link in this particular chain. It is usually quite easy to mount a defense against most attacks, I am sure RSA do it all the time. In essence, if the signature is not verrified in the allotted time, then the door closes. In my view, that is an appropriate use of this system.

by dhcdbd

I have long maintained that RSA is insecure. Adding a few digits, or as history has done, doubling the bit width every time someone cracks the latest certainly increases the rendition time 2^n. This is why most security agencies laugh at PGP. PGP privacy is pretty good privacy for most people if they have nothing to really hide. This is why banks only use it to send the initial key and then switch to another algorithm.

Let's see you take a crack at the Mersien Twister algorithm.

by santeewelding

He did say, "military". Any one having anything to do with that or any algorithm gives it up one way or the other with deadly force put to the back of the head. If none do, no matter how many, their shenanigans won't matter when they all go away.

by dhcdbd

the corporeal force method works so well in Afghanistan, Pakistan, and Iraq.

Without intent of being cryptic, the method described by 'Brother' is nearly identical to the method employed by the Brits to solve the Enigma code. A little different, but not much. With the 'Enigma' the code was put into a three dimensional box and the intersection of the lines was taken. In the instant case, only a single diagonal is taken. This is an application of the 'Turing Machine' principle, which many of the British are fond of.

The problem with encryption is that it is, in fact, a deterministic problem (N^n). There is much research in the area, but few real (effective) solutions. I deliberately picked the most difficult algorithm I know of. But the basic premise, could be applied to any derived encoding algorithm. Even those algorithms generally used to validate files such as MDA5 or SHA.

While I mentioned business and you hold to Military, the two are not mutually exclusive. The trick is to confuse the message just long enough to render the contents meaningless when they are finally decrypted.

by brother martin de porres

The almost frightening speed of the latest processors, is going to impact on security. Especially as these chips will probably be standard in many consumer devices. We should be on our guard.

by robo_dev

Field Programmable Gate Arrays allow an attacker to custom-craft a cracking-engine for less that $1,000. Cracking a DES key can be done at a reasonable cost in the comfort of one's own home/criminal hideout.

'security researchers' have figured out how to hack RFID-based smart-keys used in certain automobiles and other devices such as subway payment systems. They use FPGAs to crack these keys.

Further, massively parallel processing GPU devices, such as found in nVidia graphics cards, can allow ordinary PCs to crack keys at 20 times the rate of their CPU alone. The Russian firm Elcomsoft sells password 'recovery' software that uses this tecnology.

by santeewelding

Please, for my miserable sake, lay off the instruction. I ask that you put it as how you have learned, been instructed, or see thereby in your eye. This would be apparent in a fully excellent approach.

I recognize like expertise in myself, by myself, and owing in large part to myself. I am instantly dismissive of any other approach.

If you do wish to descend here with the absolute, come armed.

by brother martin de porres

It's a bad habit of mine, I have a bad 'insecurity complex', and fear that some folk will, as often happens, accuse me of making bogus claims. The raw mathematics is hard to refute!

by brother martin de porres

The now three decade old RSA cryptosystem, is at the heart of nearly every secure??? electronic communication transacted today. Terrorism in my own view, is just a convenient 'front' for criminal activity. Economics Professor Loretta Napoleoni highlights this problem in her best selling books. a recent review writes:-

"After looking into how terrorism gets paid for (Terror Incorporated: Tracing the Money Behind Global Terrorism), Napoleoni tackles the whole of capitalism's dark side: the economics of illegal, criminal and terrorist activities worldwide. There's no shortage of material, including the sex trade of Eastern Europe, internet fraud, piracy (both nautical and intellectual), human slavery, drugs and even the subprime mortgage lending scandal. Unsettling, eye-opening statistics abound, one third of all fish eaten in the UK is illegally poached; today, 27 million slaves worldwide generate annual profits of $31 billion; up until 9/11, 80 percent of the $1.5 trillion underworld economy was laundered through the US (the Patriot Act moved much of this business to Europe)?and Napoleoni's bold analysis begs controversy..."

A security system that is patently NOT SECURE! is a gift to these Terrorist/Criminal organisations. I am afraid to say 'Palmetto', that I am definitely not having "a good time", I wish I was! This is a very serious topic,involving Trillions of Dollars in criminal proceeds, Economic Warfare no less, it's your money and mine, and it is a subject that deserves urgent attention.

by brother martin de porres

My first Tutor in cryptanalysis, and probably the best Cricket player at Wellington College, (Mr. M) would have awarded you full marks for that comment. That was just over forty years ago...HAPPY DAYS!

by brother martin de porres

Check out the Queen Mary University of London page "Computer Science For Fun CS4FN" and have a go at the 'Tantrix: P = NP? puzzle. There is a million dollar prize waiting out there, and someone might get lucky. I think it was Prof. Sir Roger Penrose, who solved a tricky puzzle. A gigantic hall one million feet and one inch square, needs to be tiled with one square foot tiles. how many complete tiles will fit the floor? you would think it was a Trillion, but you would be wrong, about another twenty or so thousand could fit in. I wish I could locate my book with the exact solution. each tile is set on a slight slant, it is also a cunning attack on the RSA problem. (think Pythagoras)

by brother martin de porres

Thanks 'robo-dev', fascinating information. Martin Margala's team at The University of Rochester NY. may soon have their 'Ballistic Transistor' up and running? The proof of principle model was demonstrated three years ago.
http://www.rochester.edu/news/show.php?id=2585

Similar efforts are underway all over the globe. This is bound to impact on security. I believe quantum security may provide an answer, recent proposals published in Nature, have advocated satelite links. Fibre optics are limited to distances in the order of 100 miles, paired photons can only travel that far. Perhaps secure relay stations and satelite links could be combined to provide security? We may have to wait a few years yet, but I am optimistic for the long term. Currently we should be on our guard. Thanks again!

by brother martin de porres

Hi 'I_bontes',

The $30,000 challenge, my old Fortran puter is gathering dust in my loft! I will have to tackle this one with Bcalc. a 5012 digit version of Windoze Calculator. I note that Wikipedia have posted it up with all the others.(I assume correctly!) Just now is a bad time, our UK Parliament are debating the proposed new Iraq Inquiry (in secret!) and my MP, Gordon Prentice wants it to be public! I am bogged down with Army Regulation 700/48. etc. written by Major Denise Nichols and Dr. Doug Rokke. It's a life and death issue for our veterans and combat soldiers.

It will however provide some welcome relief, so thanks for the challenge. Remember that an hour or so's work with a manual entry calculator, can be completed in miliseconds or less with a suitable program. It will be interesting to extract the front-end digits of the two primes that compose this monster.

by l. bontes

I finally do understand the method, and agree it works generally on all numbers after all. The only thing missing is how to calculate the ratio. Would just a brute force search be sufficient? I've looked at the progression of ratios of large prime composites, but was never able to find a pattern in them. So a trivial method for finding the ratio would be most intriguing.

by l. bontes

What you have posted so far has been very intresting. I have been looking into this problem for many years, and would really like to see a solution (or at least a significant speed up over GNFS).

I was following the matter of the public enquiry on the news. It's indeed an important issue!

by brother martin de porres

Very kind comment I_bontes, blush-worthy!

I will put on my thinking cap (fools-cap paper rolled into a cone, with a delta logo) pyramid-power to the grey cells!;-)

BTW...Boy! Oh! Boy! is the Iraq Inquiry a can of worms! As a military chaplain, my concern is the welfare of our troops, and of course those non-combatants cought up in the turmoil. Vital (life-saving) Army Regulations have been ignored left-right-and-center! Except in rare circumstances, that is tantamount to sedition!..blah! Fortunately the military have plenty of good folk, and factual information will trickle out. Dr. Doug Rokke Ph.D., who was the Colonel at the Pentagon who was Director of Nuclear, Bio & Chem hazards writes:- "...Casualties include those who were killed in action (KIA), wounded in action (WIA), and disease and non-battle injuries (DNBI). Sadly the majority of casualties or those classified as disease and non-battle injuries are not reported in the public media..." We are looking at over half a million servicemen in the DNBI category. The death toll is slowly mounting and may soon surpass 100,000!

I really am most grateful to you I_bontes, that RSA 704, is just the kind of distraction/therapy I need just now, each day I learn of new horrors!

by brother martin de porres

http://en.wikipedia.org/wiki/Standard_deviation

But Wolfram MathWorld's entry is more specific. A random binary sequence of fixed length, is tested for primality, and then another. The product of these two primes compose the 'PQ' Public Key, semi-prime.

As both primes are selected by a random process, they obey the rules of 'Standard deviation. At the edges of the 'bell' we have a very square dual-prime and a very double-square rectangle. Say two primes that start 1000000000010110011...etc. & 1111111111110100110010101110...etc. or a pair of either to make a very square semi-prime composite.

The relevance, is that we will be better off searching first in the middle of the bell-curve. There are pseudo-deterministic methods of finding the front 25% of the digits in each of the primes. You can multiply the composite by 4, 9, 25, 49 etc....that is equivalent to multiplying each prime by 2, 3, 5, & 7. ...It's a good check on the results When I get round to RSA 704, I can post up a worked example. Knowing the front-end digits, is a great help establishing the ratio, but only the very first few digits are easy. It's best to use a program for the remainder of that front 25%. If you care to get hold of a large sheet of graph paper, and construct a multiplication table of all the cardinal numbers that will fit on the page (the '++' feature on a pocket calculator will help) you will note how the products distribute themselves along the 'diagonal' which of course is the series of square numbers. 1, 4, 9, 16, 25, 36, 49, etc. This is yet another clue, as to how to figure out those front-end digits...blah! Thanks for expressing so much interest in the subject. It's a great way to exercise the old grey matter, and very beneficial, it gets the blood circulating as well!;-D

by l. bontes

Thanks for the reply, the answer exceeded my expectations.
The average ratio values of the so far factored numbers on wikipedia is roughly 0.72, certainly close to 2:3.

Indeed if one tries digit values for a and b so that a*b=n, then 2a*2b=4n must also hold if the values tried are correct. Brilliant. It's a small job to figure out the first few digits in this way for the computers in front of us... Coding it would also be a good excersize for me, rather than sticking pieces of software together which I normally do!

by brother martin de porres

We seem to be on the veritable 'war-path', as far as RSA 704 goes. It would make a great conversation piece at the next RSA Conference Europe 2009, 20th-22nd October at the Hilton London Metropole. They will be expecting my conference 'postcard', last year the artistic theme was 'Fisherman's Paradise', based on Norman Rockwell's design.

http://www.goantiques.com/scripts/images,id,519267.html

Chosen for the 'square' theme. This year it will be an M.C.Escher theme with cryptic tile tessellations.
http://www.mcescher.com/

by santeewelding

Quit tripping around the edges. Confirm the series for all time.

Otherwise, I shall quit my fantasy of Brother Marin de Porres laboring under candlelight on his rope-chair on a stone floor.

The glare of a flucking computer in the corner.

by brother martin de porres

I shall have to send TechRepublic photos from the RSA Conference Europe 2009, 20th-22nd October, this year at the Hilton London Metropole. You have given me some great ideas for a costume! as well as artistic inspiration. A few monks would suit this years M.C. Escher Conference Postcard theme.
THANKS!

http://en.wikipedia.org/wiki/Slains_Pursuivant

We have some great costumes, perhaps my boss's Slains Pursuivant might attend? Merlin Hay 24th Earl of Erroll, is our chief parliamentary spokesman on all things 'computer' especially 'security'. Those minutes are recorded in Latin (I am not joking!)

by dhcdbd

This sound very close to some work I had to do several years ago in school.

My bipolar kicked up and I had to take a semester off. I dropped most classes but was granted an extension in a programming class. During the extended work the prof worked closely with me and pushed me very hard; harder than he would push a normal student, especially in the area of prime number analysis. Between him, my uncle who has a Ph.D. in math, and my asinine stubbornness, we came up with a method that sounds close to this to predict primes. Uncle has an interest in Mersenne Primes. I'll have to dig through my old HD's and see if I can't find the work and the emails.

No, I'm not nuts; just please don't turn the squirrels loose.

by brother martin de porres

Hi DHCDBD,
The great F.N.Cole in 1903 astonished the mathematics world at a lecture, in which he did not speak a word. he wrote up a large multiplication on the blackboard:-

193707721.761838257287;

At the end, his audience recognised Mersene 67, which everyone till then had believed was prime. There was a standing ovation! Prime numbers are a great mathematical playground. When a difficult problem is solved, one's feet hardly touch the ground for days even weeks after, such is the contented feeling of elation. It's very therapeutic!

I am working on some artwork, which will also be a subtle clue for and RSA solution. I have some lovely big canvases. I can give a hint; If you square the dual semi-prime, there will be a square block of rectangles, let's take a trivial example 77, squared it's 5929, there will be seven by eleven 7 x 11 rectangles that form the square. Now the subtle bit, we take four of these large squares, and use a 'herring-bone' pattern to lay rectangular 'tiles', and then we draw another oblique square at 45 degrees, top & side centers as the corners. The result is very interesting! You can construct it with Windoze Paint pixel by pixel. Root two and Pythagoras at work.(I may post the picture up on Wikipedia!;-)

by l. bontes

"There are pseudo-deterministic methods of finding the front 25% of the digits in each of the primes."

Can you elaborate a bit more please? The only method I can think of so far is trying to multiply all possible values for a and b, but this gives a lot of possibilities. i.e. Looking at the first few digits of RSA640 310741 and trying 4 digit values for a and b, I can find 3154 x 9829, 1335 x 2323, 3626 x 8550 and 1630 x 1902 all seem to be reasonable matched. How does one elimate some of these possibilities?

by l. bontes

Finding out the ratio seems not important. One can easily try out all ratios. The main method needs little calculation to verify the result. The number of small rectangles indeed goes into zillions for huge numbers. Just 19153(107*179) has 40 (!) consecutive matches with ratios 0.608938 .. 0.587982.
To be continued.

by brother martin de porres

Hi I-Bontes,

You are a star! for expressing so much interest...FULL MARKS...GRADE 'A' REPORT!

Let us consider this case:-
123456789 x 987654321,

We know that (a + b + c) x (d + e + f)
= ad + ae + af + bd + be + bf + cd + ce + cf,

we can break the product into parts,
ie.
(123,000,000 + 456,000 + 789)
X (987,000,000 + 654,000 + 321)

There are multiple ways we can break down this product, but the important thing to remember, is that the 'front' and 'back' digits are highly predictable, forget about terrifying (BANG!), the two BIG componets 123 million times 987 million, are going to have priority, and the back digits are even less 'ambiguous'. in the lucky 'PQ' example I cited above, that ended 885,077, well the square root of that is 940.7853103..., and we now know the back three digits of each of the primes was '941' & '897'. I admit that such an easy result is mere coincidence, but they are ubiquitous in this game, we could have got there by trial and error, only '9 X 3' & '1 x 7', will produce a 'seven' at the end...blah. The important thing to remember, is that 941 + 897 = 1838, when we are looking for the solution to 'P' + 'Q' those back-end digits are going to reduce the search time considerably, we can skip the non-starters! A solution in 'Polynomial Time' is our objective. OK computers now process at giga-flop, and soon tera-flop speed, but why waste precious time?

This discussion is closed to new replies.