# The Math behind RSA

HS Thomas
Ranch Hand
Posts: 3404
This has to be the simplest and most straightforward description of the Math behind RSA - a form of public key cryptography that I have come across.
Adam wants to send Eve a message.
1: Adam picks two giant prime numbers,p and q. The primes should be enormous. The larger the prime the greater the security .Adam must keep the numbers secret.
2: Adam multiplies them to get another number, N.
( e and (p-1) x (q-1) should be relatively prime,but this is a technicality.)
3. Adam can now publish e and N in something like a telephone directory.
Since these two numbers are necessary for encryption, they must be available to anybody who might want to encrypt a message to Adam.
Together these two numbers are called the public key. (As well as being part of Alice's public key , e could also be part of everybody else's public-key. However, everybody must have a different value of N, which depends on their choice of prime numbers ,p and q.)
4. To encrypt a message , the message must first be converted into a number, M.
For example, a word is changed into ASCII binary digits, and the binary digits can be considered as a decimal number. M is encrypted to give the ciphertext, C, according to the formula

5. Imagine that Adam wants to send Eve a simple kiss; the letter X. In ASCII this is represented by 1011000, equivalent to 88 in decimal.
So,M=88.
And the power behind the Math:
For sufficiently large values of N all the computers in the world will need longer than the age of the Universe to break the code.
Adam no longer has to worry about securely transporting the key to Eve or that the Snake might intercept the key. The more people who see the key the merrier because it helps only with encryption, not decryption.
The only thing that needs to remain secret at all times is the private-key used for decryption, and Adam can keep this with him at all times.
It took 600 volunteers 17 years ( 1977 - 1994) to decipher the value of N ( 10 to the power 129) into p and q, using their spare time on their workstations , mainframes and supercomputers each tackling a fraction of the problem.
Banking transactions, N tends to be in the region 10 to the power 308.
Sometime in the future someone may find a quick way to factor N and therefore RSA would become useless. However for the last 2000 years mathematicians have failed to find a short-cut and factoring remains a time-consuming calculation.
Rivest, Shamir and Adleman (RSA) are credited with finding the most beautiful implementation of public key cryptography at the MIT CS Lab,
though the British Government are challenging for the title of inventor of public key cryptography.

regards
[ August 19, 2003: Message edited by: HS Thomas ]

Mark Herschberg
Sheriff
Posts: 6037
Originally posted by HS Thomas:

Rivest, Shamir and Adleman (RSA) are credited with finding the most beautiful implementation of public key cryptography at the MIT CS Lab,
though the British Government are challenging for the title of inventor of public key cryptography.

The statment above seems to imply that Britian's challenge is related to RSA, which it is not. RSA did not invent public key cryptography--they simply had the most commerically successful implementation.
Diffie-Hellman predated RSA as the earlist public key crypto system. However some historians argue that Clifford Cocks and Malcolm Williamson did the first public key crypto work, but that because it was classified, the public only know about Diffie and Hellman's work.
--Mark

HS Thomas
Ranch Hand
Posts: 3404
Thanks Mark. There is some talk about history books being re-written. Does this actually ever happen ? Do you know of any case where it has ?
I mean a new author might release a new book in time. But do they re-call books that are historically deemed wrong ? This seems a rather trivial case (other than to the people who really invented PKC and their families) but still !
regards

Mark Herschberg
Sheriff
Posts: 6037
Who is "they?"
That's what it comes down to. After the Soviet Bloc fell, there were lots of out of date high school history books.* The schools couldn't afford new books, which are usually used for 10-20 years Heck, I'll bet many schools today have history books which say this.
The reality is books don't get recalled. When a never version comes out, they hopefully get updated. Until then, hopefully the publisher/reader makes a good decision on whether or not its accurate enough for its role.

*There was a cute ISP ad where some girl is giving a history report and says, "and to this day they still remain behind the iron curtain." Then the voice over comes on talking about how your child's book are out of date, but an up to date encyclopedia is one of the many benefits of their service.
--Mark

HS Thomas
Ranch Hand
Posts: 3404
Who is "they?"

By *they* I meant the authors. I would have thought that they'd have a reputation to uphold.
Second and Third editions of history books could outnumber Java book editions, authors and publishers just haven't cottoned on yet.
Having said that, with everything expected to happen under the eye of the camera/the world for instant analysis , there wouldn't be much room for conjecture and debate in the history of the future. But they could well be re-writing books of the past until year 2005 several times over to explain why things happen in the future. Blame it on the past,hey!
Video footage cannot lie up to a point.
Historians, as we know them ,may be another endangered species.
The news reporter may step in to fill the breach and the world will debate for ever more how those bits of video were cobbled together.

regards
[ August 20, 2003: Message edited by: HS Thomas ]

Mark Herschberg
Sheriff
Posts: 6037
Originally posted by HS Thomas:

By *they* I meant the authors. I would have thought that they'd have a reputation to uphold.
Second and Third editions of history books could outnumber Java book editions, authors and publishers just haven't cottoned on yet.

I think it's understood that history books do get dated. Undoubtedly they do reprints and try to update it before it's done. However, they can't simply update an entire book every time the geo-political wind shifts. In the last few years we've seen changes in the government of Afganistan, Iraq, and Liberia. We've seen US foreign policy undergo a major shift in the last few years.
Your typical high school text book costs about \$40. Think the schools can afford to buy new ones? Publishers won't print unless someone will buy.
Originally posted by HS Thomas:

Video footage cannot lie up to a point.
Historians, as we know them ,may be another endangered species.
The news reporter may step in to fill the breach and the world will debate for ever more how those bits of video were cobbled together.

The still photogrpah can't lie either; nor can the tape recorder. Historians have endured despite these technological advances. just as a good programmer does more than bang out code, a good historian doesn't simply state facts, but instead analyzes data and draws trends. Historians are analysts. Videos can't analyze and journalists don't have time to consider the broad implications as they rush to meet a 5pm deadline.

--Mark

HS Thomas
Ranch Hand
Posts: 3404
Historians are analysts.

I agree in part that historians may continue as they always have.But good TV news reporters are increasingly asked about giving analyses at the scene. In time you'd find news reporters everywhere.
Have you come across a history book about the First Gulf War - or something close enough worthy of the title.
If you were to teach history about the First Gulf War what would you use as resources ? ( And I am not talking about Oliver North's biography).
That happened so rapidly ,information was available as it happened real-time that to my mind , history was being written as it happened.

People still buy newspapers but it is hardly for breaking-news . They might like a reporter's writing style , or for other garbage you find in papers.
With search engines and other information packaging tools, similar interest group's views ,can't one build one's own view of history - a very sophisticated view.The facts have to be undisputed. Trying to capture a historical analysis for posterity in a book may have a hard time selling it in the future.
What I am saying is that in the future you are hardly likely to settle for a single analysis but rather a composite whole. You now have access to instant debate.

regards
[ August 20, 2003: Message edited by: HS Thomas ]

HS Thomas
Ranch Hand
Posts: 3404
Hare Brain or Tortoise Mind - What shall it be ?
Hare,Tortoise
Which I think says you need a brain like a hare (jumps around quickly) but a mind (consciousness) that works like a tortoise - time for conjencture and appreciation. So Mark , I think you are right that historians will survive.
But I note you haven't nominated any History Books for the First Gulf War, yet. I just wondered if there were any being used to teach.
regards
[ August 21, 2003: Message edited by: HS Thomas ]