Just for fun, I want to encrypt a message that will take about 10 or so years to decrypt. My idea is to encrypt a message with AES-512 with a password one million decimal digits long.
Knowing not much about cryptography, is this any more difficult to decrypt than a shorter password? (I'm trying to prevent brute-forcing, until computing power becomes so high that it is irrelevant).
There is no AES-512; AES takes keys of 128, 192 or 256 bits.
When encrypting with a password, there are two steps: first the password is converted into a key for the symmetric encryption, then the encryption is applied. Brute force can be applied either on the password (enumerating all possible passwords until a match is found) or on the key itself (enumerating all possible keys until a match is found).
A 128-bit key is large enough to defeat brute force for long period of times. You can use a larger key for display purposes (larger figures impress managers, and some people apparently believe that key length correlates with manhood -- in the same way as big cars).
The same applies to a password with 128 bits of entropy -- which is a way of saying that there are 2128 possible passwords, and you chose one at random among them. You can lower the entropy requirements on the password by using a slow hashing process; roughly speaking, if the function which converts the password into a key has the cost of 220 elementary encryption operations (that's about one million, and will be done in a fraction of a second with a basic PC) then you can be content with 108 bits of password entropy.
If your passwords are random sequences of alphanumeric characters (uppercase letters, lowercase letters, digits), then 19 characters are enough (because you use 62 distinct signs, and 6219 is greater than 2108). More characters are useless. Note that "random" is an important word: I am certainly not talking about choosing the password with your head ! Human brains are definitely bad at randomness. Use a coin, dice, or a computer with /dev/urandom.
All of the above is about making sure that the message will not be decrypted within the next 10 years. A much harder problem is to also ensure that the message will be more or less easily decrypted in year 2022, but not before. I suggest entrusting the key to a notary, with instructions to reveal it at a specific future date.
Independent from deployed algorithm: The parameter space of a text string grows exponentially with the length and polynomially with the character set, i.e. roughly, length contributes more to security than special characters.
The class of algorithm you mention is not scalable and so cannot immediately be fed with arbitrary passwords. Usually you use a hash function, which maps a password to a hash-value of suitable length, which might serve as initialization vector for the encryption algorithm.
The entropy of your password can be measured by a hufman encoding based on the actual character set and the distribution of the characters.
When the entropy of your password is larger than that of the hash-value-space, you might split it accordingly to build a set of alternating initialization vectors.
In order to answer your question: With these measures security increases monotonously with the password entropy.
This may not focus directly on AES and is somewhat tangential, but currently there are debates as to the efficacy of large complex passwords, especially multiple ones. People write them down. This is compounded by automatic password expiry and password recycling rules.
Most IT guys have huge lists of passwords written down in books, spreadsheets and post-its. What use AES 999 block BBC mode cipher when the passwords are stored in a spreadsheet called PASSWORDS?
If you have a million character password, and you don't store it in some format what's the point? You might as well just randomly scramble your message and have people reorder it. And apart from tectonic or stellar movements, how do you intend to predict the future that far out or to access our processing capability in 10 years time?
According to Gibson Research's Password Haystacks website 23 digits would take 35 years at 100 trillion guesses per second.
