Sign In
Create Account
Follow Us on Twitter
Subscribe on Youtube
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?
8 replies to this topic
#1
Posted 08 January 2008 - 11:01 AM
TcM
-
- Members
-
- 11,147 posts
Writes binary right handed and hex left handed
Back to top|
|
|
#2
Posted 10 January 2008 - 08:56 AM
WingedPanther
-
- Moderators
-
- 16,831 posts
A spammer's worst nightmare
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.
#3
Posted 10 January 2008 - 11:02 AM
monkey_instinct
-
- Members
-
- 88 posts
Learning Programmer
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.
#4
Posted 11 January 2008 - 11:04 AM
TcM
-
- Members
-
- 11,147 posts
Writes binary right handed and hex left handed
WingedPanther said:
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.
#5
Posted 14 January 2008 - 09:16 AM
WingedPanther
-
- Moderators
-
- 16,831 posts
A spammer's worst nightmare
Here's a like that explains some of how it works: RSA - Wikipedia, the free encyclopedia
#6
Posted 14 January 2008 - 10:04 AM
TcM
-
- Members
-
- 11,147 posts
Writes binary right handed and hex left handed
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?
EDIT:-
For example in here:
what are those three lines supposed to mean?
#8
Posted 15 January 2008 - 08:49 AM
TcM
-
- Members
-
- 11,147 posts
Writes binary right handed and hex left handed
Ow yeah! congruent, I knew that I already saw that symbol... but I couldn't remember what it was, I used this in Math...
#9
Posted 15 January 2008 - 09:17 AM
WingedPanther
-
- Moderators
-
- 16,831 posts
A spammer's worst nightmare
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
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
