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.

 

[dangerstat]

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.

I'll be honest it isn't an easy area to begin with. Perhaps review that maths knowledge and then give it a go? If you do then even Wikipedia should give you enough to get started. I know that's not what you want to hear but encryption is not an area to "mess around with" if you haven't got a grasp of intermediate maths. If you want to play about with trivial encryption why not just attempt some simple substitution routines.

 

[tntcoder]

hmm you really do need a solid foundation in maths if you want to understand things like RSA & AES at algorithm level. RSA is the easier of the two to understand. And both AES and RSA have many sub topics that you would need to understand, for example group theory, modular exponentiation, Diffie-Hellman problems, block cipher-theory etc. So basically you will struggle to find a newbie style guide for these kind of things simply due to the complexity and topics involved.

Saying that the Wikipedia articles are good if you want a highlevel explanation, and they link to psuedocode, but to understand how and why the algorithms are secure and how they work you need to look at learning cryptography as a whole.

If you want a really good book that will cover both the maths and the algorithms, Fundamentals of Computer Security (Monographs in Theoretical Computer Science) by Josef Pieprzyk, Thomas Hardjono, and Jennifer Seberry is great.

http://en.wikibooks.org/wiki/Cryptography that might also help, and the king Bruce Schneier's Applied Cryptography book is although now dated still a worthy read.

If you have any specific questions on AES/RSA or something else post away

 

[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.

 

[tntcoder]

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.

Sure, post them up. m is the plaintext, typically just a single character, for example the ASCII code for a character. Then it's repeated for each character in the string. Textbook RSA like that is very insecure, and it's typically used as a building block in something like RSA-OAEP which makes it practically secure using padding.

 

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

 

[tntcoder]

Ok yer, I really recommend hitting the maths books

GCD = greatest common divisor, 2 numbers are coprime if their GCD=1. e.g the GCD of 4,8 is 4.

(n,e) and (n,d) just refer to how your two keys are constructed. For example a public key is made up of n and e and the secret private key is n and d. There is no maths here, (n,e) just means consists of n and e.

Here's a worked example with your two primes:

p = 73
q = 47
n = 3431 (not 4891, just n=pq = 73*47 = 3431)
φ(pq) = (73-1) * (47-1) = 3312
e = 61 (Randomly selected, and coprime to the totient 3312, i.e gcd(61, 3312) = 1)
d = 2389 (calculated as a modular congruence)

Now our public key is (n,e) = (3431, 61)
And our private key is (n, d) = (3431, 2389)

Lets encrypt given the public key the test message m = 1337

ciphertext = m^e mod n
ciphertext = 1337^61 mod 3431 = 549

Now lets decrypt it given the private key, to see if we get the correct plaintext.
plaintext = c^d mod n
plaintext = 549^2389 mod 3431 = 1337 Correctness.

Hope that helps.

 

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

 

[tntcoder]

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?

Modular Arithmetic


Basically it limits a number to within a certain range. If we look at mod 12 we are working in the range 0-11.

Any number 0-11 mod 12 is fine and is left unchanged, anything higher gets 'moved' to within that range.

Consider 13 mod 12 = 1, it's essentially the remainder after division to get to 12. e.g 13/12 = 1.xxx -> therefore result = 13-(12*1) = 1.

say 24 mod 12 = 0, because its exactly divisible, there is no remainder. 209 mod 12 = 5 because 209/12 = 17.4..., and 209-(17*12) = 5.

Modular arithmetic is very useful and widely used in cryptography.

(I'm not a mathematician by any means, so that may not be the best explanation )

Computing d in the RSA example is done by solving a modular congruence relation, in the form aX = b (mod n), you can solve these using a number of methods. I just used: http://numeratus.net/applets/mod/mod.html but the Euclidean algorithm explains how to do it by hand.

 

[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.

 

[Xelene]

Read Cryptonomicom by Neal Stephenson.

http://en.wikipedia.org/wiki/Cryptonomicon

 

[Inquisitor]

Here's a gentle intro to AES:

http://www.moserware.com/2009/09/stick-figure-guide-to-advanced.html

Be warned, though: cryptography is a very specialized and involved field and it'd take years to become properly familiar and confident with the majority of techniques used, let alone be able to apply them to your own systems.