Encryption and stuff (pgp)

[Noodle]

I saw 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.

http://www.rsasecurity.com/developer...algorithm2.gif


<< 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?

[kedaman]

I'm not sure but it might be that it's hard to do RSA Encryption with Vb, or at least it will be too slow to be effective. You need to use really huge number, even out of the Decimal's range, at least that's what i read a while ago. Might be that that is the problem since small numbers would just create interferences since it's integers. I'll go try some myself...