Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Nov 17, 2014 #1
    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.
     
  2. jcsd
  3. Nov 17, 2014 #2

    jim mcnamara

    User Avatar

    Staff: Mentor

    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?
     
    Last edited: Nov 17, 2014
  4. Nov 17, 2014 #3
    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.
     
  5. Nov 17, 2014 #4

    jim mcnamara

    User Avatar

    Staff: Mentor

    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
     
  6. Nov 17, 2014 #5

    rcgldr

    User Avatar
    Homework Helper

    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.
     
    Last edited: Nov 18, 2014
  7. Nov 18, 2014 #6
    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.
     
  8. Nov 18, 2014 #7

    rcgldr

    User Avatar
    Homework Helper

    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
     
    Last edited: Nov 18, 2014
  9. Nov 18, 2014 #8
    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!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: The advantage of modular arithmetic, e.g. cyclic groups?
  1. Modular Multiplication (Replies: 14)

Loading...