Prime Numbers..

[TcM]

What is the deal with prime numbers in encryption? I see this a lot of time.. but what is the deal with them? Using prime numbers is more secure?

[WingedPanther]

Prime powers of numbers have special properties that do not exist with composite powers. If you study Number Theory you can learn more about it, but it can get pretty deep pretty fast. Think of it as the equivalent of calculus on integers.

[monkey_instinct]

Checking if a number is hard is extremely hard for relatively big numbers. There's no formula for getting the nth prime number so, the reason of using prime number for encryption must be something related to that property.

[TcM]

Originally Posted by WingedPanther

If you study Number Theory you can learn more about it

Seems like Math to me.. Doesn't seem to be listed in my favorite subjects list.

[WingedPanther]

Here's a like that explains some of how it works: RSA - Wikipedia, the free encyclopedia

[TcM]

Thanks, I'm sure I will not understand everything, but thanks for helping. I will read it as soon as I post this message.

EDIT:-

For example in here:


what are those three lines supposed to mean?

[Maurice_Z]

Table of mathematical symbols - Wikipedia, the free encyclopedia
This should be helpful.

[TcM]

Ow yeah! congruent, I knew that I already saw that symbol... but I couldn't remember what it was, I used this in Math...

[WingedPanther]

1. Choose two distinct large random prime numbers p and q

For this I'll use small primes: 23 and 29

2. Compute n = p q ( n is used as the modulus for both the public and private keys)

n = 23*29 = 667

3. Compute the totient: phi(n) = (p-1)(q-1)

phi(n) = 22 * 28 = 616

4. Choose an integer e, such that 1 < e < phi(n) and e and phi(n) share no factors other than 1 (i.e. e and phi(n) are coprime) (e is released as the public key exponent)

Prime factors of phi(n) are 2,2,2,7,11, so e could be 13*17 = 221

5. Compute d to satisfy the congruence relation d e equivalent to 1 mod phi(n); i.e. de = 1 + k phi(n) for some integer k. ( d is kept as the private key exponent)

After a little work, we get: d = (some value higher than 30) where (d*e) % 616 = 1