How does one scale encryption strength upwards from 256-bit?

I have seen many examples of encryption up to about 256-bit. But how does one programmatically scale the logic upwards in a language such as PHP or Java to say 1024-bit or even 4096-bit and higher?

Are there any websites that explain the workings of a very large encryption on a modern 64-bit computer? For example what kind of numbers (Long Int, Double, etc.) would one use and how can one even extend that range and still keep it computable to the computer?

Would this scaling's security be compromised by the limitations of the processing power available, i.e. 64-bit processor?

I understand that time is a factor in very large encryptions, but in this case time doesn't matter that much.

-

As @David Schwartz said, using something like 3AES should work to scale up the security (but see my comment on the meet-in-the-middle attack). But seriously, why would you even need 512-bits of security in a symmetric algorithm? According to the analysis on wikipedia it would take 50,955,671,114,250,100,000,000,000,000,000,000,000,000,000,000,000,000 years to bruteforce 256 bit AES (given a few assumptions on speed). I doubt you have any data that needs to be secured for that long.

As far as whether the CPU limits the security strength, it doesn't. There are libraries out there which provide "infinite" precision numbers (i.e., gmplib for c/c++, BigInteger and BigDecimal for Java, etc). For more on computing with large numbers, see chapter 14 of the Handbook of Applied Cryptography (HAC). Internally, these libraries use things like long long int or even plain int stored in an array. HAC has the algorithms.

-

For asymmetric encryption such as embodied by RSA, the "key length" is conventionally taken to be the length of one of the public key elements. Such a key is highly structured (only a very few sequences of bits of that length are valid keys) and security relies on robustness of this structure with regards to some specific analysis algorithms. E.g., in RSA, the "key size" is the length of a big integer (called the "modulus") and RSA is secure as long as one cannot factor that big integer into its prime factors. Integer factorization becomes hard, then unfeasible with existing technology, when we consider large enough integers. 1024-bit integers for RSA are commonplace, and it is recommended to use larger ones (e.g. 2048 bits -- cryptographers just love powers of 2), to account for possible advances in technology in the next decades. Implementation of RSA requires "big integers", i.e. integers with length not limited to that of the CPU registers. See @mikeazo's answer for pointers.

For symmetric encryption, it makes no real sense to use a key larger than 256 bits (arguably, 256 bits are already extreme overkill). Symmetric encryption algorithms accept as keys all sequences of a given size. The key size must be such that it is not feasible to try all possible keys, an attack known as "exhaustive search". 256 bits are already way beyond the reasonable and also the unreasonable; see this answer on security.SE for a more detailed analysis.

A non-weak symmetric encryption algorithm is such that if you do not use exactly the right key, you get utter garbage, so that you cannot approximate the key: you really have to hit it. Another way to say it is that for a non-weak algorithm, exhaustive search is the best attack. Yet another way to say it is that if enlarging the key beyond 256 bits makes any difference to security, then you are using weak symmetric encryption algorithms. It is a rather risky bet to assume that weaknesses in an algorithm can be overcome with larger keys; a much safer attitude would be to just stop using weak algorithms.

As for implementations, some cryptographic algorithms are defined with arithmetic operations on relatively large operands. E.g. RC6 uses multiplications of 32-bit integers. This is done because big processors (such as the core CPU of a PC) are good at such kinds of operations. However, smaller processors are not: smartcard developers, and people who design custom circuits on ASIC or FPGA are not fond of RC6. So other algorithms are built only on elements which are easy to deal with on any platform. E.g. the AES uses only 8-bit operations. There is no relation between the block size (128 bits for AES), the key size (128, 192 or 256 bits for AES), and the type of elementary operation the block cipher is built on.

Anyway, if an algorithm runs at all anywhere, then it is implementable with only transistors (what else is there in a CPU ?) and a transistor handles only 1-bit values.

-
+1 Excellent discussion. One point, however, about the overkill of long keys. This assumes that a believed strong algorithm is in fact strong. If a break is found against the algorithm, then extra key bits can certainly provide a valuable safety margin. You hint at this in your answer at security.SE when you discuss QC (which could be considered a kind of "break"), but I wanted to bring it forward here as well. – Rob Napier Oct 4 '11 at 13:13

It's very unlikely to yield any more security. The security of an encryption algorithm is directly tied to how well it has been studied. There really are no well-studied symmetric algorithms with keyspaces over 256-bits. So the short answer is -- nobody knows yet.

The question is kind of like "what kind of cars will people drive in the year 2100?"

You should be perfectly safe cascading a known-safe algorithm, like the way 3DES expanded the keys of DES. You could, for example, create 3AES to get 512-bit keys.

-
2AES would only have a max of 256-bit security due to the meet in the middle attack. 3AES would have a max of 512 bits of security. Also, weren't there some recently published attacks on 256 bit AES? – mikeazo Sep 30 '11 at 11:19
You are right about 2AES, I edited my answer. There are some attacks on 256-bit AES, personally I think 128-bit AES is at least as strong as 256-bit AES. (Which kind of proves my larger point.) – David Schwartz Sep 30 '11 at 11:22
you are definitely right about the AES-256 attacks proving your point. Schneier has a writeup (and links to the papers) on his blog (schneier.com/blog/archives/2009/07/another_new_aes.html). – mikeazo Sep 30 '11 at 11:57
Yep. More is not better. Better is better. If we knew how to do it better, we'd be doing it better. – David Schwartz Sep 30 '11 at 12:00
As a side note for anyone who is interested, the comments on Schneier's post about the AES-256 attack are pretty interesting. I especially liked the explanation of how "single-key 2AES-256" would actually fix the AES-256 attack (main point is it doubles the number of rounds and keeps the key size at 256-bits, thus increasing diffusion). – mikeazo Sep 30 '11 at 12:10