The advantage of modular arithmetic, e.g. cyclic groups?

[nomadreid]

In starting to look into the mathematical side of encryption , I note the heavy dependence upon modular arithmetic. What is the advantage is this? For example, why are finite cyclic groups and rings preferable? Note: I know zilch about programming; I am approaching it from the mathematical side.

 

[jim mcnamara]

I do not know exactly what you are asking for. But, if we start from base requirements, for public key crypto let's try this:

Crypto algorithms get vetted by the community. That means everybody understands fully how the algorithm works. So to provide safety decryption has to be unfeasible in terms of 'computing power' required for a successful brute force attack. Obviously, no cracking algorithm should be found to exist that greatly reduces the computing effort to successfully attack. Over time algorithms have gone out of use generally because someone found a crack or because brute force analysis became feasible.

One time pad (Shannon) is the only (a theorem) proven to be impossible to crack. But essentially useless on a practical basis.

Is this the direction you want to go - practicality? Which is an answer to your question: Why this type of algorithm is chosen?

 

[nomadreid]

Thanks for the reply, jim mcnamara. If practicality is the reason why modular arithmetic has been chosen, then yes, that would be the way I would want to go, and details would be appreciated. So, if I understand it, appropriate formulations in terms of modular arithmetic are possible for today's computers to encrypt easily but difficult to decrypt , as opposed to formulations in terms of simply the integers that would be either easier than the ones in modular arithmetic to decrypt, or outside the range of today's computers to encrypt. I am not yet quite sure why this should be the case, though.

 

[jim mcnamara]

crypto has a political aspect to it. Step one is get agreement that, yes, the algorithm works as required. Next step is a check on the implementation (practicality, I guess). We still use RSA which came out in the early 1990's. Not because it is great but because lots of older systems have and it can be expensive to upgrade to something else. So, what happens is, Ron Rivest, the principal author of RSA, has tried some additional tweaking to get a few more good years out of it. RSA keys are standard for ssh-keys (passwordless access, key exchange). The ssh protocol supports it. (Note RSA is used in two contexts, and with two separate alogithms: asymmetic encryption and digital signatures (http://en.wikipedia.org/wiki/Digital_signature)

So if my vendors use RSA keys and create public RSA keys for the asymmetric encryption applications here, we use RSA. Is it the best choice? No.

Some things in crypto do get blown away to an extent. The MD5 hash algorithm is pretty much out of the picture, and SHA-2 is now being used in it's stead. Someone found a crack for MD5, and there was a mass exodus.

So. I am oversimplifying this stuff. And cryptoanalysts will get heartburn reading it.
Start with this:
http://en.wikipedia.org/wiki/Public-key_cryptography
http://en.wikipedia.org/wiki/Elliptic_curve_cryptography
http://en.wikipedia.org/wiki/Key_exchange

These are all general, kinda limited links, but if you have questions I might be able to help a little. But remember this is Commerce and Government, not necessarily Mathematics

 

[rcgldr]

In the case of RSA, using modular arithmetic limits the size of the "numbers" used during encryption and decryption. In the case of AES encryption, when it is implemented in hardware, perhaps 10 more more encrypters operating in parallel, reducing the gate count is important. Part of AES encryption involves the Rijndael_S-box (wiki link), finding the 8 bit value (1/x) modulo a 9 bit polynomial (1 bit coefficients, hex 11b) which is implemented as a 256 byte lookup table for software, but for hardware implementation, gate count has been reduced well below that of the equivalent of a 256 byte lookup table by using an advanced method called sub-field mapping where the 8 bit field is mapped into two 4 bit fields which in turn are mapped into four 2 bit fields.

 

[nomadreid]

Thanks again, jim mcnamara, and thanks rcgldr. You have both given me much to munch on, and I shall be working my way through your explanations and links.

 

[rcgldr]

If you want to go bonkers on the sub-field mapping and related finite field stuff ...

For a finite field module a prime number p, there are primitives, calling one of them e, where every non-zero number in the field can be represented as e^i % p, where i goes from 0 to p-2. e^(p-1)%p = 1. For example, consider the finite field modulo 5, then all non-zero numbers can be powers of 2:

{2^0 % 5 = 1, 2^1 % 5 = 2, 2^2 % 5 = 4, 2^3 % 5 = 3} (this wraps around at 2^4 % 5 = 1).

or powers of 3:

{3^0 % 5 = 1, 3^1 % 5 = 3, 3^2 % 5 = 4, 3^3 % 5 = 2} (this wraps around at 3^4 % 5 = 1).

For an 8 bit field modulo a 9 bit "prime" polynomial (1 bit coefficients, add and subtract are effectively replaced by xor), there are also primitives. Normally a polynomial where 2 (binary 10) is a primitive is chosen, but AES uses a polynomial where 2 is not a primitive (more on this below).

A simple example of sub-field mapping:

http://rcgldr.net/misc/m8to44.doc

As mentioned, AES uses a 9 bit polynomial where 2 is not a primitive, but typically the 4 bit sub-field mapping will use polynomials x^2 + ax + b where 1x + 0 is a primitive. A brute force search for a combination of primitive 'e' for the 9 bit polynomial, 'a' and 'b' for a potential "compatable" 4 bit sub-field polynomial x^2 + ax + b to map first to two 4 bit sub-fields and then again to a 2 bit sub-field polynomial x^2 + x + 1 to map to four 2 bit sub-fields is done, looking for the combination that results in the fewest number of gates. Link to a pdf file about optimizing an "s-box". The point isn't to understand all the complex math in the document, but to note the effort put into this to reduce the gate count by about 20% (since there can be 10 or more s-boxes on a AES device, the gate count is important).

http://www.iacr.org/archive/ches2005/032.pdf

 

[nomadreid]

Hey, rcgldr, great stuff in those two documents, and in your text. I really like that: documents written in information science that clearly discuss the mathematics involved, not just giving a bunch of programs. Just the approach I need. Thanks very much!