matters more convincing, Alice and Bob should concoct some mildly incriminating dummy messages to take the place of the really incriminating real messages. A pair of Israeli spies once did this.

Alice could take P and encrypt it with her favorite algorithm and key K to get C. Then she takes C and XORs it with some piece of mundane plaintext - Pride and Prejudice for example, to get K. She stores both C and the XOR on her hard disk. Now, when the secret police interrogate her, she can explain that she is an amateur cryptographer and that K is a merely one-time pad for C. The secret police might suspect something, but unless they know K they cannot prove that Alices explanation isnt valid.

Another method is to encrypt P with a symmetric algorithm and K, and D with K. Intertwine bits (or bytes) of the ciphertext to make the final ciphertexts. If the secret police demand the key, Alice gives them K and says that the alternating bits (or bytes) are random noise designed to frustrate cryptanalysts. The trouble is the explanation is so implausible that the secret police will probably not believe her (especially considering it is suggested in this book). A better way is for Alice to create a dummy me s-sage, D, such that the concatenation of P and D, compressed, is about the same size as D. Call this concatenation P. Alice then encrypts P with whatever algorithm she and Bob share to get C. Then she sends C to Bob. Bob decrypts C to get P, and then P and D. Then they both compute C 0 D = K. This K becomes the dummy one-time pad they use in case the secret police break their doors down. Alice has to transmit D so that hers and Bobs alibis match.

Another method is for Alice to take an innocuous message and run it through some error-correcting code. Then she can i n-troduce errors that correspond to the secret encrypted message. On the receiving end, Bob can extract the errors to reconstruct the secret message and decrypt it. He can also use the error-correcting code to recover the innocuous message. Alice and Bob might be hard pressed to explain to the secret police why they consistently get a 30 percent bit-error rate on an otherwise noise-free computer network, but in some circumstances this scheme can work.

Finally, Alice and Bob can use the subliminal channels in their digital signature algorithms (see Sections 4.2 and 23.3). This is undetectable, works great, but has the drawback of only allowing 20 or so characters of subliminal text to be sent per signed innocuous message. It really isnt good for much more than sending keys.

10.9 DESTROYING INFORMATION

When you delete a file on most computers, the file isnt really deleted. The only thing deleted is an entry in the disks index file, telling the machine that the file is there. Many software vendors have made a fortune selling file-recovery software that recovers files after they have been deleted.

And theres yet another worry: Virtual memory means your computer can read and write memory to disk any time. Even if you dont save it, you never know when a sensitive document you are working on is shipped off to disk. This means that even if you never save your plaintext data, your computer might do it for you. And driver-level compression programs like Stacker and DoubleSpace can make it even harder to predict how and where information is stored on a disk.

To erase a file so that file-recovery software cannot read it, you have to physically write over all of the files bits on the disk. According to the National Computer Security Center [1148]:

Overwriting is a process by which unclassified data are written to storage locations that previously held sensitive data.... To

purge the ... storage media, the DoD requires overwriting with a pattern, then its complement, and finally with another pattern; e.g., overwrite first with 0011 0101, followed by 1100 1010, then 1001 0111. The number of times an overwrite must be acco m-plished depends on the storage media, sometimes on its sensitivity, and sometimes on different DoD component requirements. In any case, a purge is not complete until a final over- write is made using unclassified data.

You may have to erase files or you may have to erase entire drives. You should also erase all unused space on your hard

Most commercial programs that claim to implement the DoD standard over- write three times: first with all ones, then with all zeros, and finally with a repeating one-zero pattern. Given my general level of paranoia, I recommend overwriting a deleted file seven times: the first time with all ones, the second time with all zeros, and five times with a cryptographically secure pseudorandom sequence. Recent developments at the National Institute of Standards and Technology with electron-tunneling microscopes suggest even that might not be enough. Honestly, if your data is sufficiently valuable, assume that it is impossible to erase data completely off magnetic media. Burn or shred the media; its cheaper to buy media new than to lose your secrets.

Часть III

Криптографические алгоритмы

Глава 11

Математические основы

11.1 Теория информации

Современная теория информации впервые была опубликована в 1948 году Клодом Э. Шенноном (Claude Elmwood Shannon) [1431, 1432]. (Его работы были переизданы в IEEE Press [1433].) С математической точки зрения эта тема хорошо рассмотрена в [593]. В этой главе я только схем атично излагаю основные идеи.

Энтропия и неопределенность

Теория информации определяет количество информации в сообщении как минимальное количество бит, необходимое для кодирования всех возможных значений сообщения, считая все сообщения равновероятными. Например, для поля дня недели в базе данных достаточно использовать три бита информации, так как вся и н-формация может быть закодирована 3 битами:

000- Воскресенье

001- Понедельник

010- Вторник

011- Среда

100- Четверг

101- Пятница

110- Суббота

111- Не используется

Если эта информация была бы представлена соответствующими строками ASCII символов, она заняла бы больше места в памяти, но не содержала бы больше информации. Аналогично, поле базы данных "пол" соде р-жит только один бит информации, хотя эта информация может храниться как одно из двух 7-байтовых ASCII строк: "МУЖЧИНА" или "ЖЕНЩИНА".

Формально, количество информации в сообщении M измеряется энтропией сообщения, обозначаемое как H(M). Энтропия сообщения, определяющего пол, составляет1 бит, а энтропия сообщения, определяющего день недели, немного меньше, чем 3 бита. В общем случае энтропия сообщения, измеряемая в битах, равна log 2 n, где n - это количество возможных значений. При этом предполагается, что все значения равновероятны.

Энтропия сообщения также является мерой его неопределенности. Это количество битов открытого текста, которое нужно раскрыть в шифротексте сообщения, чтобы узнать весь открытый текст. Например, если блок шифротекста "QHP*5M означает либо "МУЖЧИНА", либо "ЖЕНЩИНА", то неопределенность сообщения равна 1. Криптоаналитику нужно узнать только один правильно выбранный бит, чтобы раскрыть с ообщение.

Норма языка

Для данного языка норма языка равна

r = H(M)/N

где N - это длина сообщения. При больших N норма обычного английского языка принимает различные зн а-чения от 1.0 бит/буква до 1.5 бит/буква. Шеннон в [1434] говорит, что энтропия зависит от длины текста. Ко н-кретно он показал, что норма для 8-буквенных блоков равна 2.3 бит/буква, но ее значение падает и находится между 1.3 и 1.5 для 16-буквенных блоков. Томас Кавер (Thomas Cover) использовал игровую методику оценки и обнаружил, что энтропия равна 1.3 бит/символ [386]. (В этой книге я буду использовать значение 1.3.) Абсолютная норма языка равна максимальному количеству битов, которое может быть передано каждым символом при условии, что все последовательности символов равновероятны. Если в языке L символов, то абсолютная норма равна:

R = log2 L

Это максимум энтропии отдельных символов.

Для английского языка с 26 буквами абсолютная норма равна log 2 26, или около 4.7 бит/буква. Вас не должно удивлять, что действительная норма английского языка намного меньше, чем абсолютная - естественные языки обладают высокой избыточностью. Избыточность языка, обозначаемая D, определяется как:

D=R - r

Считая, что норма английского языка равна 1.3, избыточность составит 3.4 бит/буква. Это означает, что к а-ждая английская буква содержит 3.4 бита избыточной информации.

У сообщения ASCII, состоящего только из английских букв, количество информации на каждый байт с о-