Булева алгебра. Законы логики

Буль изобрёл своеобразную алгебру- систему обозначения и правил,применимую по всевозможным объектам, от чисел и букв до предложений. Его именем она теперь и называется:алгебра Буля или булева алгебра. Булева состоит из компонентов: 1 лог.объекты(выражения);2.операции над логюобъектами;3.аксиомы и теоремы, регламентирующие эти операции. Лог. выражения делятся на:1.лог.утверждения;2.предикаты. Логические утверждения-это конкретные частные утверждения, заведомо истинные или ложные,лог.константы. Лог.редикаты-это лог.высказывания,значения которых могут меняться в зависимости от входящих в них переменных величин, это лог.переменны. Пр:А+В>С.

Осн.законы логики:

1. Отсутствие степеней и коэффициентов (идемпотентность)

А v А = А

А ^ А = А

2. Двойное отрицание (инволюция)

(А) = А

3. Закон исключенного третьего

А v А = 1 (всегда истина)

4. Закон противоречия

А ^ А = 0 (всегда ложь)

5. Независимость от перестановки мест (коммутативность)

A v B = B v A

A ^ B = B ^ A

6. Независимость от порядка выполнения однотипных действий (ассоциативность)

(A v B) v С = A v (B v С);(A ^ B) ^ С= A ^ (B ^ С)

7. Распределительный закон относительно логического умножения и сложения (дистрибутивность):

Распределение относительно логического умножения: (А v В) ^ C = (A ^ C) v (В ^ C) и наоборот (А v В) v (В ^C)= В ^ (А v C)

Сложение - А v В^С=(А v В) ^(А v С)

8. Законы де Моргана

(А ^ В) = А v В; (А v В) = А ^ В

Общая схема симметричного шифрования

Классическая(одноключевая) крип-я опирается на использ симметрич-х алг-ов шифр-ния,в которых шиф-ние и расшиф-ние отлич только порядком выполнения и направлением некоторых шагов. Эти алг-ы используют один и тот же секретный эл-нт (ключ),и второе действие (расшиф-ие) явл простым обращением 1-го (шифр-я).Поэтому каждый из участников обмена может как зашиф-ть, так и расшиф-ть сообщ СХЕМА

На передающей стороне имеются источник сообщ-й и источник ключей. Источник ключей выбирает конкретный ключ К возможных ключей Этот ключ К передается некоторым способом принимающей стороне,причем предполаг-я,что его нельзя перехватить, напр, ключ передается специальным курьером (поэтому симметричное шиф-е назв также шифр-ем с закрытым ключом). Источник сообщ-й формирует некоторое сообщ М, которое шифруется с использ выбранного ключа. В результате процедуры шифр-я получ зашиф-ное сообщ Е (криптограммой). Далее криптограмма Е передается по каналу связи. Так как канал связи явл открытым,то передаваемое сообщ может быть перехвачено противником. На принимающей стороне криптограмму Е с помощью ключа расшифр-ют и получают исходное сообщ М

Если М – сообщение, К – ключ, а Е – зашифрованное сообщение, то можно записать E=f(M,K)

то есть зашифр-е сообщ Е явл некоторой функцией от исходного сообщ-я М и ключа К

По причине большой избыточности естественных языков в зашифр-ное сообщ трудно внести осмысленное изменение,поэтому классич крип-ия обеспеч защиту от навязывания ложных данных. Если же избыточности оказывается недостаточно для надежной защиты сообщ от модификации,избыточность может быть искусственно увеличена путем добавл к сообщ-ю спец контрольной комбинации, наз-ой имитовставкой

Известны разные методы шифрования с закрытым ключом СХЕМА

- В методах перестановки символы исходного текста меняются местами друг с другом по определенному правилу

- В методах замены (или подстановки) символы открытого текста заменяются некоторыми эквивалентами шифрованного текста.

- С целью повышения надежности шифр-я текст,зашифр-ый с помощью одного метода,может быть еще раз зашифрован с помощью другого метода.В этом случае получ комбинированный или композиционный шифр. Применяемые на практике в наст вр блочные или поточные симметричные шифры также относятся к комбинирован-м, т к в них использ несколько операций для зашифр-я сообщ

Шифры перестановки

Зашифруем, например, указанным способом фразу:

ПРИМЕРМАРШРУТНОЙПЕРЕСТАНОВКИ

Используем прямоугольник размера 4*7

ПРИМЕРМ

НТУРШРА

ОЙПЕРЕС

ИКВОНАТ

Зашифрованная фраза выглядит так:

МАСТАЕРРЕШРНОЕРМИУПВКЙТРПНОИ

Теоретически маршруты могут быть значительно более изощренными, однако запутанность маршрутов усложняет использование таких шифров.

РЕШЕТКА

Для использования шифра, называемого поворотной решеткой, изготавливается трафарет из прямоугольного листа клетчатой бумаги размера 2m*2k клеток. В трафарете вырезано m*k клеток так, что при наложении его на лист чистой бумаги того же размера четырьмя возможными способами его вырезы полностью покрывают всю площадь листа.

Буквы сообщения последовательно вписываются в вырезы трафарета (по строкам, в каждой строке слева направо) при каждом из четырех его возможных положений в заранее установленном порядке.