I say this program on TV, which referred to encryption and I found it really interesting, so I thought I should make a small encryption program to implement all those things I saw and read later.
I want my program to encrypt and decrypt the message using the RSA algorithm. It doesn't have to be anything advanced, I am only doing it for fun. For the past 3 days I have been trying to make the original RSA algorith to work, but I simply can't.
Here is a link to a picture that has the algorithm and here is the only part on the site that eplains it a bit.
<< The RSA algorithm works as follows: take two large primes, p and q, and compute their product n = pq; n is called the modulus. Choose a number, e, less than n and relatively prime to (p-1)(q-1), which means e and (p-1)(q-1) have no common factors except 1. Find another number d such that (ed - 1) is divisible by (p-1)(q-1). The values e and d are called the public and private exponents, respectively. The public key is the pair (n, e); the private key is (n, d). The factors p and q may be destroyed or kept with the private key. >>
I think that the best way to make you see my mistake (which I can't) is to tell how I think it works and what equations I use in my program. So here I go.
First I pick two prime numbers, P and Q. Then I run a loop where I try to find a number E that doesn't have any common factors with (P-1)*(Q-1), ie when E mod A = 0 E mod (P-1)*(Q-1) =/ 0 (2<A<E). If for example I have the prime numbers P=11 and Q=17 I come up with E being 3. Of course there is more than one E, but loop stops when it finds the first number than fullfills all the criteria.
So according to the algorithm, E is part of the public key, of what you tell everyone in order to encrpt their messages and send them to you, and they do so with this equation
C = M^E mod N (C = encrypted message, M= the message you want to encrypt, N = P*Q)
So if say I want to send the message '88' what I do is say, C = 88^3 mod 187 which is 44. Now in order to decrypt the message C I have to use this equation, M = C^D mod N. We need D though. For D though he have two equations, the first one from the picture above and it is
E*D = 1 mod (P-1)*(Q-1) (it's not really '=' but three dashes which means equevalent, I don't know if that makes a big difference, if so please tell me! )
Now, correct if I am wrong but (P-1)*(Q-1) can't be zero because your prime numbers have to be greater than 1 there for 1 mod (P-1)*(Q-1) is always 1! Which leads to the conclution than E*D = 1, ie D = 1/D. I am 100% sure than this is completely wrong because if your secret key was 1 over the public key, then it's not secret! That's why I didn't use this equation in my program, I used this one
(E*D-1) mod (p-1)*(q-1) = 0 (I get this equation from this frase, "Find another number d such that (ed - 1) is divisible by (p-1)(q-1)") In my example E is 3, P = 11 and Q = 17 so D could be 53. Again D can be a lot of numbers as long as they fullfill the previous criteria, and 53 does, because 3*53+1 = 160 and 160 mod 160 = 0!
So if everything that I have done so far is correct I would be able to encrypt a message and then decrypt it using these two equations
C = M^E mod N
C = 88^3 mod 187 => C = 44
M = C^D mod N
M = 44^53 mod N => M = 176 which is wrong because my message was '88'.
So what exactly am I doing wrong here? Can you spot something? I bet my mistake is so big and obvious that I am going to have to hide.
BTW, on that TV show, I remember seeing this equation M = C^1/e *(Q-1)*(P-1).
I just had a flash. In my program (VB) I use "Long" which is basically big integers, could it be that I should be using Decimals? OMFG of course I do. Still, can you see something else that is wrong with my thinking?
Thanx in advance
[edit]Now that I think about it again, I don't have to use floats do I?[/edit]
I want my program to encrypt and decrypt the message using the RSA algorithm. It doesn't have to be anything advanced, I am only doing it for fun. For the past 3 days I have been trying to make the original RSA algorith to work, but I simply can't.
Here is a link to a picture that has the algorithm and here is the only part on the site that eplains it a bit.
<< The RSA algorithm works as follows: take two large primes, p and q, and compute their product n = pq; n is called the modulus. Choose a number, e, less than n and relatively prime to (p-1)(q-1), which means e and (p-1)(q-1) have no common factors except 1. Find another number d such that (ed - 1) is divisible by (p-1)(q-1). The values e and d are called the public and private exponents, respectively. The public key is the pair (n, e); the private key is (n, d). The factors p and q may be destroyed or kept with the private key. >>
I think that the best way to make you see my mistake (which I can't) is to tell how I think it works and what equations I use in my program. So here I go.
First I pick two prime numbers, P and Q. Then I run a loop where I try to find a number E that doesn't have any common factors with (P-1)*(Q-1), ie when E mod A = 0 E mod (P-1)*(Q-1) =/ 0 (2<A<E). If for example I have the prime numbers P=11 and Q=17 I come up with E being 3. Of course there is more than one E, but loop stops when it finds the first number than fullfills all the criteria.
So according to the algorithm, E is part of the public key, of what you tell everyone in order to encrpt their messages and send them to you, and they do so with this equation
C = M^E mod N (C = encrypted message, M= the message you want to encrypt, N = P*Q)
So if say I want to send the message '88' what I do is say, C = 88^3 mod 187 which is 44. Now in order to decrypt the message C I have to use this equation, M = C^D mod N. We need D though. For D though he have two equations, the first one from the picture above and it is
E*D = 1 mod (P-1)*(Q-1) (it's not really '=' but three dashes which means equevalent, I don't know if that makes a big difference, if so please tell me! )
Now, correct if I am wrong but (P-1)*(Q-1) can't be zero because your prime numbers have to be greater than 1 there for 1 mod (P-1)*(Q-1) is always 1! Which leads to the conclution than E*D = 1, ie D = 1/D. I am 100% sure than this is completely wrong because if your secret key was 1 over the public key, then it's not secret! That's why I didn't use this equation in my program, I used this one
(E*D-1) mod (p-1)*(q-1) = 0 (I get this equation from this frase, "Find another number d such that (ed - 1) is divisible by (p-1)(q-1)") In my example E is 3, P = 11 and Q = 17 so D could be 53. Again D can be a lot of numbers as long as they fullfill the previous criteria, and 53 does, because 3*53+1 = 160 and 160 mod 160 = 0!
So if everything that I have done so far is correct I would be able to encrypt a message and then decrypt it using these two equations
C = M^E mod N
C = 88^3 mod 187 => C = 44
M = C^D mod N
M = 44^53 mod N => M = 176 which is wrong because my message was '88'.
So what exactly am I doing wrong here? Can you spot something? I bet my mistake is so big and obvious that I am going to have to hide.
BTW, on that TV show, I remember seeing this equation M = C^1/e *(Q-1)*(P-1).
I just had a flash. In my program (VB) I use "Long" which is basically big integers, could it be that I should be using Decimals? OMFG of course I do. Still, can you see something else that is wrong with my thinking?
Thanx in advance
[edit]Now that I think about it again, I don't have to use floats do I?[/edit]