Теория Информации
Mathematical Backgrounds. Information Theory In 1949, Shannon provides a theoretical foundations for cryptography based on his fundamental work on information theory. He measured the theoretical secrecy of a cipher by the uncertainty about the plaintext given the received ciphertext. If, no matter how much ciphertext is intercepted, nothing can be learned about the plaintext, the cipher achieves perfect secrecy. Entropy and Equivocation Information theory measures the amount of information in a message by the average number of bits needed to encoded all possible messages in an optimal encoding. The Sex field in a database, for example, contains only one bit of information because it can be encoded with one bit (Male can be represented by “0”, Female by “1”). If the field is represented by an ASCII character encoding of the character strings “MALE” and “FEMALE”, it will take up more space, but will not contain any more information. Mathematical Backgrounds. Information Theory The amount of information in a message is formally measured by the entropy of the message. The entropy is a function of the probability distribution over the set of all possible messages. Let X1,..., Xn be n possible messages occurring with probabilities p(X1),...,p(Xn), the sum of this probabilities p(Xi), i=1,...,n equals to one. The entropy of a given message is defined by the weighted average: H(X)=−Σinp(Xi)log2 p(Xi). As the sum taken over all messages X: H(X)=–ΣXp(X)log2 p(X)=ΣXp(X)log2 [1/p(X)].