In depth encryption algorithm explaination

[Auraomega]

I've been looking into encryption methods to learn more about how strong encryption is made, I've done the simple XOR stuff however when trying to find something more advanced I seem to only be faced with overly confusing algorithms like AES, RSA, etc. Couple my lack of theory with my memory failure for maths and looking at the explanation is not only mind numbing, but is inducing an aneurysm!

I'm basically look for some sort of newbie explanation that will explain both the theory as well as the maths; example code (psudo preferably) would be an advantage. Failing that some easy encryption algorithms to learn from might prove useful too.

 

[Auraomega]

I suspected that'd be the case. I have been slogging through the Wiki article on RSA, as well as this. It's been pretty difficult understanding the math, specifically I've forgotten what modular expressions are (I always thought I'd never find a use for any of that maths I learned at college).

I believe I've managed to get the figures for a test RSA algorithm, however I'm stuck working out the public and private keys. In the encryption section, it refers to m which I'm not sure how I'm supposed to work out, is it to do with the padding?

If I post my figures, would you mind checking that I've done everything right up to this point? They aren't huge, just something small to get an algorithm up, once I've made sure it's all working and I understand enough of the maths, I may end up using more complex numbers.

 

[Auraomega]

Ok, following my scrawling from 3am, this is what I have:
p = 73
q = 47
n = 4891
φ(pq) = 4752
e = 13
d = 4021

I have no clue whether d is right, I don't even know how I got that number now.

A couple of things which after re-reading don't make much sense:

Choose an integer e, 1 < e < phi, such that gcd(e, phi) = 1

What is gcd?

The public key is (n, e) and the private key is (n, d)

What does (n, e) and (n, d) refer to?

 

[Auraomega]

Yes, you're probably right. I'll see if I can dig out my old college notes, bound to be something helpful there.

I gave the wrong value for q, which is why everything else was so far out. It was supposed to be 67

Thanks for the explanation on public/private keys thing, it's plainly obvious now I can see it!

I've just double checked all my figures, with the exception of d.

Can you explain to me how mod works?

 

[Auraomega]

Thanks for that, your explanation has actually made a lot of sense everything else I found online was too simplified and had no relevance, or too complicated and confused me!

This should allow me to take the next couple of steps (hopefully), I'm going to give it a break though for now, may come back to it later today or tomorrow.