| Mark Crispin 2008-02-24, 12:33 pm |
| On Sun, 24 Feb 2008, Richard B. Gilbert posted:
> Not so! If the encryption key is random and never reused, it's theoretically
> impossible to break the encryption. This follows from the fact that
> encryption by an additive key is represented by one equation with two
> unknowns (plain+key=cipher). If you have both the key and the cipher text,
> decryption is trivial. Likewise, if you have both the plain and the cipher
> text you can recover the key. If not, you are generally out of luck.
The classic example of this is a key that is XORed to the plaintext to
generate the ciphertext. If the length of the key equals the length of
the plaintext and is never reused, then it is impossible to decrypt the
ciphertext.
If, on the other hand, the key is reused, then decryption of an XOR
encryption is a laughably trivial exercise. Once you have any known
plaintext, you have the corresponding portion of the key, which in turn
can be used to obtain more plaintext where that key is reused.
Most products that use XOR keys claim that they avoid this via a random
number generation device that does not reuse the key. What the device
uses is a time-based polynomial (since the legitimate receipient has to be
able to decode the ciphertext). The attacker then seeks to discover both
the polynomial and its inputs. Very few of these devices are secure
against such attack.
> The
> generation and secure distribution of the key is a logistical nightmare.
> This level of encryption is generally used only by governments.
Indeed. This is why XOR encryption is the domain of the clueless, the
quacks, or governments that have the resources for secure distribution of
huge keys.
IIRC, the Anti-Spoofing encryption for the Precise Positioning Service of
GPS uses an XOR key. The plaintext, cyphertext, and full history of the
key to date are completely known. What isn't known are the future key
bits nor the algorithm by which they are generated. The military value to
this encryption is the ability to decrypt in real time.
Again IIRC, PPS receivers have an interface to a military-issued module
which does the decryption. This module is installed into authorized PPS
receivers at a secure US goverment facility, has anti-tamper features, and
must periodically be sent back for an updated module.
This is not something that would work well for mobile phones. Hence the
popularity of public key type systems, which use separate encryption and
decryption keys.
Many of these are based upon the idea that while it is easy to generate
very large prime numbers, it is very difficult to factor the product of
two very large primes. Hence an algorithm which encrypts using the
product, and decrypts using the two factors, is secure as long as the
product is large enough that brute force factoring is impractical...and
that no mathematical breakthrough for factoring huge numbers is
discovered (and people are working on trying to solve that problem!).
-- Mark --
http://staff.washington.edu/mrc
Science does not emerge from voting, party politics, or public debate.
Si vis pacem, para bellum.
|