Prime numbers and cryptography

synkk

Hello, this is rather vague but I had a lecture around a year ago about prime numbers and how a mathematician (Hardy or Euler?) found a proof to do with prime numbers and then this lead on to cryptography and internet security...

That's all I can particularly remember but I'm wondering on what was the theorem or who was the mathematician that proved this specific "thing" which lead to the creation of cryptography.

Also I remember it had Modular arithmetic!

jackmell

That's actually a very beautiful subject if you like math but would take some time to understand. It's no particular theorem but just rather the real-life inability to factor large numbers easily. So if I write down a 1000-digit number and it's the product of two primes, and if those two primes are carefully chosen, it's virtually impossible to determine them by any means even by trial and error using the current state of compute technology. Therefore, if I encrypt a message, convert it to numbers and this conversion involves the product of two very large primes, it's practically impossible to decipher my code without knowing beforehand what the prime numbers used in the encryption were.

Here's one reference: "A Concrete Introduction to Higher Algebra", by Lindsay Childs. It has several chapters dealing with the algorithm, knows as the RSA algorithm.

chiro

Hey synkk.

To follow up on your post, the reason why cryptography is based on primes for most of the protocols is that it is believed that factoring is NP-hard in the way that the computational complexity is exponential in terms of O(e^n) (or something similar).

The main premise of cryptography is that we want a process that has an inverse which is easy to do, but hard to undo. As of now, it turns out that number theory provides the hard part to 'undo', because a lot of these schemes rely on the fact that it's hard to factor numbers: The schemes don't actually factor primes specifically, but the factoring of prime numbers for a lot of these schemes is equivalent to decoding a particular message.

If there were other techniques that provided this 'easy to do, hard to undo' mechanism that didn't involve primes, then they would most likely be considered and in fact, in the security realm of mathematics, these are considered in many related ways like with one-way functions (One-way functions are not bijective like with encoding and decoding messages, but they are important for security purposes).

So thats the basic reason why number theory is used: many people believe that factoring is a hard process and based on this, we continue to use the schemes based on number theory, diophantine analysis, and primes.

haruspex

Except, perhaps, the algebra which shows the encode and decode algorithms are indeed inverses.

Bacle2

A basic source for you, on RSA criptography-Public Key:

http://en.wikipedia.org/wiki/RSA_(algorithm)