Almost every article in the popular press dealing with cryptography (coding messages so the bad guys can’t read them) mentions a “key” and that prime numbers are an integral part of a “key.” I understand “key” as in the “one time pad” method of encoding messages, but I don’t undersatnd why a prime number is so important in association with a difficult to break key.
As an aside, I called several of the individuals who have written these articles and asked them the question as to why a prime number key was so important. One said it was obvious and hung up! The other dude sheepishly admitted to writing what he was told by the cryptography experts…but he really didn’t understand why!
Prime numbers are often used for one-way functions. There are no “real” on way functions, but there are functions that are very easy to do one way and very difficult to do backwards. An example is the product of two large prime numbers. It takes less than a second to multiply two large prime numbers, but it takes a very long time to find the prime factors of a number. When we’re dealing with products on the order of 10[sup]300[/sup], it would take millions of years to find the factors.
One way functions are useful for a variety of applications, especially making public key-pairs.
I used to wonder the same thing … until I read The Code Book, by Simon Singh. It’s excellent written, and covers the history of codes and ciphers from the times of the Babylonians until the modern day. (Quantum cryptography, anybody?) If you’re really interested in this, I would check it out. There’s an excellent bibliography at the end, too.
[Note: I am in no way associated with the author or his publisher. I just really liked the book.]
This is from another thread:
http://boards.straightdope.com/sdmb/showthread.php?threadid=48456
I know it is spam to cross post but this seems relevent.
Searching for crypo stuff on the web is a real hassle because there is so much out there. But most of the stuff is
just a rehash of listing popular encryption schemes or adds for companies which will sell you encrpytion software.
The basic algorithm for RSA encryption:
Choose to really big prime numbers called P and Q. Then choose another number E.
E must have no common denominators with (P-1)*(Q-1).
Use P and Q to find N N=Q*P
N is a semi prime number becuase it has two factors p and q which are prime numbers.
Find D where (ED) mod((P-1)(Q-1))
x mod y is the remainder of x/y.
D and N are you private key which only you know.
Publish N and E to every one this is your public key.
If someone else wants to send you a message they use the N and E you have published.
To encrypt your message convert you message to a string of numbers which are not bigger than N.
take this string of numbers and make a new string of numbers with the formula:
C=M^E(mod N)
M one of the string of numbers
C is the corisponding new number
They then send you the string of new numbers
To decrypt the message
M=(C^D) mod (N)
This works because is is very har to find P and Q given N if P and Q are really big.
Here is a sort of goofy RSA simulator. There may be some dumb pop up window associated with going to the
site.
http://my.netian.com/~dubs37/english/
gazpacho, you’re not in any trouble. Posting links to other threads is fine, and in fact encouraged. The problem comes with posting links to irrelevant threads. Since the thread you linked to is perfectly relevant to this discussion, it’s good.